kbobyrev updated this revision to Diff 375151.
kbobyrev added a comment.
Rebase on top of main.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D110386/new/
https://reviews.llvm.org/D110386
Files:
clang-tools-extra/clangd/CodeComplete.cpp
clang-tools-extra/clangd/Headers.cpp
clang-tools-extra/clangd/Headers.h
clang-tools-extra/clangd/unittests/HeadersTests.cpp
clang-tools-extra/clangd/unittests/ParsedASTTests.cpp
Index: clang-tools-extra/clangd/unittests/ParsedASTTests.cpp
===================================================================
--- clang-tools-extra/clangd/unittests/ParsedASTTests.cpp
+++ clang-tools-extra/clangd/unittests/ParsedASTTests.cpp
@@ -47,6 +47,7 @@
using ::testing::ElementsAre;
using ::testing::ElementsAreArray;
using ::testing::IsEmpty;
+using ::testing::UnorderedElementsAreArray;
MATCHER_P(DeclNamed, Name, "") {
if (NamedDecl *ND = dyn_cast<NamedDecl>(arg))
@@ -507,18 +508,31 @@
EXPECT_THAT(PatchedAST->getIncludeStructure().MainFileIncludes,
testing::Pointwise(
EqInc(), ExpectedAST.getIncludeStructure().MainFileIncludes));
- auto StringMapToVector = [](const llvm::StringMap<unsigned> SM) {
+ auto Flatten = [](const llvm::DenseMap<IncludeStructure::HeaderID, unsigned>
+ &IncludeDepth,
+ const IncludeStructure &Structure) {
std::vector<std::pair<std::string, unsigned>> Res;
- for (const auto &E : SM)
- Res.push_back({E.first().str(), E.second});
+ for (const auto &E : IncludeDepth)
+ Res.emplace_back(Structure.getRealPath(E.first).str(), E.second);
llvm::sort(Res);
return Res;
};
// Ensure file proximity signals are correct.
- EXPECT_EQ(StringMapToVector(PatchedAST->getIncludeStructure().includeDepth(
- testPath("foo.cpp"))),
- StringMapToVector(ExpectedAST.getIncludeStructure().includeDepth(
- testPath("foo.cpp"))));
+ auto PatchedEntry = PatchedAST->getSourceManager().getFileManager().getFile(
+ testPath("foo.cpp"));
+ ASSERT_TRUE(PatchedEntry);
+ auto PatchedEntryID = PatchedAST->getIncludeStructure().getID(*PatchedEntry);
+ ASSERT_TRUE(bool(PatchedEntryID));
+ auto ExpectedEntry = PatchedAST->getSourceManager().getFileManager().getFile(
+ testPath("foo.cpp"));
+ ASSERT_TRUE(ExpectedEntry);
+ auto ExpectedEntryID = PatchedAST->getIncludeStructure().getID(*PatchedEntry);
+ ASSERT_TRUE(bool(ExpectedEntryID));
+ EXPECT_EQ(
+ Flatten(PatchedAST->getIncludeStructure().includeDepth(*PatchedEntryID),
+ PatchedAST->getIncludeStructure()),
+ Flatten(ExpectedAST.getIncludeStructure().includeDepth(*ExpectedEntryID),
+ ExpectedAST.getIncludeStructure()));
}
TEST(ParsedASTTest, PatchesDeletedIncludes) {
@@ -551,18 +565,31 @@
EXPECT_THAT(PatchedAST->getIncludeStructure().MainFileIncludes,
testing::Pointwise(
EqInc(), ExpectedAST.getIncludeStructure().MainFileIncludes));
- auto StringMapToVector = [](const llvm::StringMap<unsigned> SM) {
+ // Ensure file proximity signals are correct.
+ auto Flatten = [](const llvm::DenseMap<IncludeStructure::HeaderID, unsigned>
+ &IncludeDepth,
+ const IncludeStructure &Structure) {
std::vector<std::pair<std::string, unsigned>> Res;
- for (const auto &E : SM)
- Res.push_back({E.first().str(), E.second});
+ for (const auto &E : IncludeDepth)
+ Res.emplace_back(Structure.getRealPath(E.first).str(), E.second);
llvm::sort(Res);
return Res;
};
// Ensure file proximity signals are correct.
- EXPECT_EQ(StringMapToVector(PatchedAST->getIncludeStructure().includeDepth(
- testPath("foo.cpp"))),
- StringMapToVector(ExpectedAST.getIncludeStructure().includeDepth(
- testPath("foo.cpp"))));
+ auto PatchedEntry = PatchedAST->getSourceManager().getFileManager().getFile(
+ testPath("foo.cpp"));
+ ASSERT_TRUE(PatchedEntry);
+ auto PatchedEntryID = PatchedAST->getIncludeStructure().getID(*PatchedEntry);
+ ASSERT_TRUE(bool(PatchedEntryID));
+ EXPECT_EQ(
+ Flatten(PatchedAST->getIncludeStructure().includeDepth(*PatchedEntryID),
+ PatchedAST->getIncludeStructure())
+ .size(),
+ 1u);
+ EXPECT_TRUE(
+ Flatten(ExpectedAST.getIncludeStructure().includeDepth(*PatchedEntryID),
+ ExpectedAST.getIncludeStructure())
+ .empty());
}
// Returns Code guarded by #ifndef guards
Index: clang-tools-extra/clangd/unittests/HeadersTests.cpp
===================================================================
--- clang-tools-extra/clangd/unittests/HeadersTests.cpp
+++ clang-tools-extra/clangd/unittests/HeadersTests.cpp
@@ -17,6 +17,7 @@
#include "clang/Frontend/FrontendActions.h"
#include "clang/Lex/PreprocessorOptions.h"
#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/Path.h"
#include "gmock/gmock.h"
@@ -31,6 +32,7 @@
using ::testing::ElementsAre;
using ::testing::Not;
using ::testing::UnorderedElementsAre;
+using ::testing::UnorderedElementsAreArray;
class HeadersTest : public ::testing::Test {
public:
@@ -64,8 +66,15 @@
}
protected:
+ IncludeStructure::HeaderID getID(StringRef Filename) {
+ auto Includes = collectIncludes();
+ auto Entry = Clang->getSourceManager().getFileManager().getFile(Filename);
+ EXPECT_TRUE(Entry);
+ return Includes.getOrCreateID(*Entry);
+ }
+
IncludeStructure collectIncludes() {
- auto Clang = setupClang();
+ Clang = setupClang();
PreprocessOnlyAction Action;
EXPECT_TRUE(
Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]));
@@ -81,7 +90,7 @@
// inserted.
std::string calculate(PathRef Original, PathRef Preferred = "",
const std::vector<Inclusion> &Inclusions = {}) {
- auto Clang = setupClang();
+ Clang = setupClang();
PreprocessOnlyAction Action;
EXPECT_TRUE(
Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]));
@@ -107,7 +116,7 @@
}
llvm::Optional<TextEdit> insert(llvm::StringRef VerbatimHeader) {
- auto Clang = setupClang();
+ Clang = setupClang();
PreprocessOnlyAction Action;
EXPECT_TRUE(
Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]));
@@ -126,6 +135,7 @@
std::string Subdir = testPath("sub");
std::string SearchDirArg = (llvm::Twine("-I") + Subdir).str();
IgnoringDiagConsumer IgnoreDiags;
+ std::unique_ptr<CompilerInstance> Clang;
};
MATCHER_P(Written, Name, "") { return arg.Written == Name; }
@@ -134,11 +144,11 @@
MATCHER_P(Directive, D, "") { return arg.Directive == D; }
MATCHER_P2(Distance, File, D, "") {
- if (arg.getKey() != File)
- *result_listener << "file =" << arg.getKey().str();
- if (arg.getValue() != D)
- *result_listener << "distance =" << arg.getValue();
- return arg.getKey() == File && arg.getValue() == D;
+ if (arg.getFirst() != File)
+ *result_listener << "file =" << static_cast<unsigned>(arg.getFirst());
+ if (arg.getSecond() != D)
+ *result_listener << "distance =" << arg.getSecond();
+ return arg.getFirst() == File && arg.getSecond() == D;
}
TEST_F(HeadersTest, CollectRewrittenAndResolved) {
@@ -151,9 +161,9 @@
EXPECT_THAT(collectIncludes().MainFileIncludes,
UnorderedElementsAre(
AllOf(Written("\"sub/bar.h\""), Resolved(BarHeader))));
- EXPECT_THAT(collectIncludes().includeDepth(MainFile),
- UnorderedElementsAre(Distance(MainFile, 0u),
- Distance(testPath("sub/bar.h"), 1u)));
+ EXPECT_THAT(collectIncludes().includeDepth(getID(MainFile)),
+ UnorderedElementsAre(Distance(getID(MainFile), 0u),
+ Distance(getID(testPath("sub/bar.h")), 1u)));
}
TEST_F(HeadersTest, OnlyCollectInclusionsInMain) {
@@ -169,14 +179,14 @@
EXPECT_THAT(
collectIncludes().MainFileIncludes,
UnorderedElementsAre(AllOf(Written("\"bar.h\""), Resolved(BarHeader))));
- EXPECT_THAT(collectIncludes().includeDepth(MainFile),
- UnorderedElementsAre(Distance(MainFile, 0u),
- Distance(testPath("sub/bar.h"), 1u),
- Distance(testPath("sub/baz.h"), 2u)));
+ EXPECT_THAT(collectIncludes().includeDepth(getID(MainFile)),
+ UnorderedElementsAre(Distance(getID(MainFile), 0u),
+ Distance(getID(testPath("sub/bar.h")), 1u),
+ Distance(getID(testPath("sub/baz.h")), 2u)));
// includeDepth() also works for non-main files.
- EXPECT_THAT(collectIncludes().includeDepth(testPath("sub/bar.h")),
- UnorderedElementsAre(Distance(testPath("sub/bar.h"), 0u),
- Distance(testPath("sub/baz.h"), 1u)));
+ EXPECT_THAT(collectIncludes().includeDepth(getID(testPath("sub/bar.h"))),
+ UnorderedElementsAre(Distance(getID(testPath("sub/bar.h")), 0u),
+ Distance(getID(testPath("sub/baz.h")), 1u)));
}
TEST_F(HeadersTest, PreambleIncludesPresentOnce) {
@@ -202,8 +212,31 @@
EXPECT_THAT(collectIncludes().MainFileIncludes,
UnorderedElementsAre(AllOf(Written("\"foo.h\""), Resolved(""))));
- EXPECT_THAT(collectIncludes().includeDepth(MainFile),
- UnorderedElementsAre(Distance(MainFile, 0u)));
+ EXPECT_TRUE(collectIncludes().IncludeChildren.empty());
+}
+
+TEST_F(HeadersTest, IncludedFilesGraph) {
+ FS.Files[MainFile] = R"cpp(
+#include "bar.h"
+#include "foo.h"
+)cpp";
+ std::string BarHeader = testPath("bar.h");
+ FS.Files[BarHeader] = "";
+ std::string FooHeader = testPath("foo.h");
+ FS.Files[FooHeader] = R"cpp(
+#include "bar.h"
+#include "baz.h"
+)cpp";
+ std::string BazHeader = testPath("baz.h");
+ FS.Files[BazHeader] = "";
+
+ auto Includes = collectIncludes();
+ EXPECT_THAT(Includes.IncludeChildren[getID(MainFile)],
+ UnorderedElementsAreArray({getID(FooHeader), getID(BarHeader)}));
+ EXPECT_TRUE(Includes.IncludeChildren[getID(BarHeader)].empty());
+ EXPECT_THAT(Includes.IncludeChildren[getID(FooHeader)],
+ UnorderedElementsAreArray({getID(BarHeader), getID(BazHeader)}));
+ EXPECT_TRUE(Includes.IncludeChildren[getID(BazHeader)].empty());
}
TEST_F(HeadersTest, IncludeDirective) {
Index: clang-tools-extra/clangd/Headers.h
===================================================================
--- clang-tools-extra/clangd/Headers.h
+++ clang-tools-extra/clangd/Headers.h
@@ -12,6 +12,7 @@
#include "Protocol.h"
#include "SourceCode.h"
#include "index/Symbol.h"
+#include "support/Logger.h"
#include "support/Path.h"
#include "clang/Basic/TokenKinds.h"
#include "clang/Format/Format.h"
@@ -62,7 +63,7 @@
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &);
bool operator==(const Inclusion &LHS, const Inclusion &RHS);
-// Contains information about one file in the build grpah and its direct
+// Contains information about one file in the build graph and its direct
// dependencies. Doesn't own the strings it references (IncludeGraph is
// self-contained).
struct IncludeGraphNode {
@@ -112,7 +113,19 @@
// in any non-preamble inclusions.
class IncludeStructure {
public:
- std::vector<Inclusion> MainFileIncludes;
+ // Identifying files in a way that persists from preamble build to subsequent
+ // builds is surprisingly hard. FileID is unavailable in InclusionDirective(),
+ // and RealPathName and UniqueID are not preserved in the preamble.
+ // HeaderID is mapping the FileEntry::Name to the internal representation.
+ enum class HeaderID : unsigned {};
+
+ llvm::Optional<HeaderID> getID(const FileEntry *Entry) const;
+ HeaderID getOrCreateID(const FileEntry *Entry);
+
+ StringRef getRealPath(HeaderID ID) const {
+ assert(static_cast<unsigned>(ID) <= RealPathNames.size());
+ return RealPathNames[static_cast<unsigned>(ID)];
+ }
// Return all transitively reachable files.
llvm::ArrayRef<std::string> allHeaders() const { return RealPathNames; }
@@ -120,26 +133,21 @@
// 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 clang's name for a file, which may not be absolute.
- // Usually it should be SM.getFileEntryForID(SM.getMainFileID())->getName().
- llvm::StringMap<unsigned> includeDepth(llvm::StringRef Root) const;
+ // Root is the ID of the header being visited first.
+ // Usually it is getID(SM.getFileEntryForID(SM.getMainFileID())->getName()).
+ llvm::DenseMap<HeaderID, unsigned> includeDepth(HeaderID Root) const;
+
+ // Maps HeaderID to the ids of the files included from it.
+ llvm::DenseMap<HeaderID, SmallVector<HeaderID>> IncludeChildren;
- // This updates IncludeDepth(), but not MainFileIncludes.
- void recordInclude(llvm::StringRef IncludingName,
- llvm::StringRef IncludedName,
- llvm::StringRef IncludedRealName);
+ std::vector<Inclusion> MainFileIncludes;
private:
- // Identifying files in a way that persists from preamble build to subsequent
- // builds is surprisingly hard. FileID is unavailable in InclusionDirective(),
- // and RealPathName and UniqueID are not preserved in the preamble.
- // We use the FileEntry::Name, which is stable, interned into a "file index".
- // The paths we want to expose are the RealPathName, so store those too.
- std::vector<std::string> RealPathNames; // In file index order.
- unsigned fileIndex(llvm::StringRef Name);
- llvm::StringMap<unsigned> NameToIndex; // Values are file indexes.
- // Maps a file's index to that of the files it includes.
- llvm::DenseMap<unsigned, llvm::SmallVector<unsigned>> IncludeChildren;
+ std::vector<std::string> RealPathNames; // In HeaderID order.
+ // HeaderID identifies file in the include graph. It corresponds to a
+ // FileEntry rather than a FileID, but stays stable across preamble & main
+ // file builds.
+ llvm::StringMap<HeaderID> NameToIndex;
};
/// Returns a PPCallback that visits all inclusions in the main file.
@@ -205,4 +213,31 @@
} // namespace clangd
} // namespace clang
+namespace llvm {
+
+// Support Tokens as DenseMap keys.
+template <> struct DenseMapInfo<clang::clangd::IncludeStructure::HeaderID> {
+ static inline clang::clangd::IncludeStructure::HeaderID getEmptyKey() {
+ return static_cast<clang::clangd::IncludeStructure::HeaderID>(
+ DenseMapInfo<unsigned>::getEmptyKey());
+ }
+
+ static inline clang::clangd::IncludeStructure::HeaderID getTombstoneKey() {
+ return static_cast<clang::clangd::IncludeStructure::HeaderID>(
+ DenseMapInfo<unsigned>::getTombstoneKey());
+ }
+
+ static unsigned
+ getHashValue(const clang::clangd::IncludeStructure::HeaderID &Tag) {
+ return hash_value(static_cast<unsigned>(Tag));
+ }
+
+ static bool isEqual(const clang::clangd::IncludeStructure::HeaderID &LHS,
+ const clang::clangd::IncludeStructure::HeaderID &RHS) {
+ return LHS == RHS;
+ }
+};
+
+} // namespace llvm
+
#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H
Index: clang-tools-extra/clangd/Headers.cpp
===================================================================
--- clang-tools-extra/clangd/Headers.cpp
+++ clang-tools-extra/clangd/Headers.cpp
@@ -67,8 +67,9 @@
// Treat as if included from the main file.
IncludingFileEntry = SM.getFileEntryForID(MainFID);
}
- Out->recordInclude(IncludingFileEntry->getName(), File->getName(),
- File->tryGetRealPathName());
+ auto IncludingID = Out->getOrCreateID(IncludingFileEntry),
+ IncludedID = Out->getOrCreateID(File);
+ Out->IncludeChildren[IncludingID].push_back(IncludedID);
}
}
@@ -154,38 +155,46 @@
return std::make_unique<RecordHeaders>(SM, Out);
}
-void IncludeStructure::recordInclude(llvm::StringRef IncludingName,
- llvm::StringRef IncludedName,
- llvm::StringRef IncludedRealName) {
- auto Child = fileIndex(IncludedName);
- if (!IncludedRealName.empty() && RealPathNames[Child].empty())
- RealPathNames[Child] = std::string(IncludedRealName);
- auto Parent = fileIndex(IncludingName);
- IncludeChildren[Parent].push_back(Child);
+llvm::Optional<IncludeStructure::HeaderID>
+IncludeStructure::getID(const FileEntry *Entry) const {
+ auto It = NameToIndex.find(Entry->getName());
+ if (It == NameToIndex.end())
+ return llvm::None;
+ return It->second;
}
-unsigned IncludeStructure::fileIndex(llvm::StringRef Name) {
- auto R = NameToIndex.try_emplace(Name, RealPathNames.size());
+IncludeStructure::HeaderID
+IncludeStructure::getOrCreateID(const FileEntry *Entry) {
+ auto R = NameToIndex.try_emplace(
+ Entry->getName(),
+ static_cast<IncludeStructure::HeaderID>(RealPathNames.size()));
if (R.second)
RealPathNames.emplace_back();
- return R.first->getValue();
+ IncludeStructure::HeaderID Result = R.first->getValue();
+ auto RealPathName = Entry->tryGetRealPathName();
+ if (!RealPathName.empty() &&
+ RealPathNames[static_cast<unsigned>(Result)].empty())
+ RealPathNames[static_cast<unsigned>(Result)] = RealPathName.str();
+ return Result;
}
-llvm::StringMap<unsigned>
-IncludeStructure::includeDepth(llvm::StringRef Root) const {
+llvm::DenseMap<IncludeStructure::HeaderID, unsigned>
+IncludeStructure::includeDepth(HeaderID Root) const {
// Include depth 0 is the main file only.
- llvm::StringMap<unsigned> Result;
- Result[Root] = 0;
- std::vector<unsigned> CurrentLevel;
- llvm::DenseSet<unsigned> Seen;
- auto It = NameToIndex.find(Root);
- if (It != NameToIndex.end()) {
- CurrentLevel.push_back(It->second);
- Seen.insert(It->second);
+ llvm::DenseMap<HeaderID, unsigned> Result;
+ if (static_cast<unsigned>(Root) >= RealPathNames.size()) {
+ elog("Requested includeDepth for {0} which doesn't exist IncludeStructure",
+ static_cast<unsigned>(Root));
+ return Result;
}
+ Result[Root] = 0;
+ std::vector<IncludeStructure::HeaderID> CurrentLevel;
+ CurrentLevel.push_back(Root);
+ llvm::DenseSet<IncludeStructure::HeaderID> Seen;
+ Seen.insert(Root);
// Each round of BFS traversal finds the next depth level.
- std::vector<unsigned> PreviousLevel;
+ std::vector<IncludeStructure::HeaderID> PreviousLevel;
for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
PreviousLevel.clear();
PreviousLevel.swap(CurrentLevel);
@@ -193,10 +202,9 @@
for (const auto &Child : IncludeChildren.lookup(Parent)) {
if (Seen.insert(Child).second) {
CurrentLevel.push_back(Child);
- const auto &Name = RealPathNames[Child];
// Can't include files if we don't have their real path.
- if (!Name.empty())
- Result[Name] = Level;
+ if (!RealPathNames[static_cast<unsigned>(Child)].empty())
+ Result[Child] = Level;
}
}
}
Index: clang-tools-extra/clangd/CodeComplete.cpp
===================================================================
--- clang-tools-extra/clangd/CodeComplete.cpp
+++ clang-tools-extra/clangd/CodeComplete.cpp
@@ -1379,14 +1379,16 @@
FileDistanceOptions ProxOpts{}; // Use defaults.
const auto &SM = Recorder->CCSema->getSourceManager();
llvm::StringMap<SourceParams> ProxSources;
- for (auto &Entry : Includes.includeDepth(
- SM.getFileEntryForID(SM.getMainFileID())->getName())) {
- auto &Source = ProxSources[Entry.getKey()];
- Source.Cost = Entry.getValue() * ProxOpts.IncludeCost;
+ auto MainFileID =
+ Includes.getOrCreateID(SM.getFileEntryForID(SM.getMainFileID()));
+ for (auto &HeaderIDAndDepth : Includes.includeDepth(MainFileID)) {
+ auto &Source =
+ ProxSources[Includes.getRealPath(HeaderIDAndDepth.getFirst())];
+ Source.Cost = HeaderIDAndDepth.getSecond() * ProxOpts.IncludeCost;
// Symbols near our transitive includes are good, but only consider
// things in the same directory or below it. Otherwise there can be
// many false positives.
- if (Entry.getValue() > 0)
+ if (HeaderIDAndDepth.getSecond() > 0)
Source.MaxUpTraversals = 1;
}
FileProximity.emplace(ProxSources, ProxOpts);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
