Skip to content

Commit

Permalink
[clangd] Populate include graph during static indexing action.
Browse files Browse the repository at this point in the history
Summary:
This is the second part for introducing include hierarchy into index
files produced by clangd. You can see the base patch that introduces structures
and discusses the future of the patches in D54817

Reviewers: ilya-biryukov

Subscribers: mgorny, ioeric, MaskRay, jkorous, arphaman, cfe-commits

Differential Revision: https://reviews.llvm.org/D54999

llvm-svn: 348005
  • Loading branch information
kadircet committed Nov 30, 2018
1 parent f487334 commit 5399552
Showing 7 changed files with 359 additions and 14 deletions.
4 changes: 3 additions & 1 deletion clang-tools-extra/clangd/Headers.h
Original file line number Diff line number Diff line change
@@ -46,7 +46,7 @@ struct Inclusion {
unsigned HashOffset = 0; // Byte offset from start of file to #.
SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User;
};
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion&);
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &);

// Contains information about one file in the build grpah and its direct
// dependencies. Doesn't own the strings it references (IncludeGraph is
@@ -60,6 +60,8 @@ struct IncludeGraphNode {
};
// FileURI and FileInclusions are references to keys of the map containing
// them.
// Important: The graph generated by those callbacks might contain cycles, self
// edges and multi edges.
using IncludeGraph = llvm::StringMap<IncludeGraphNode>;

// Information captured about the inclusion graph in a translation unit.
3 changes: 2 additions & 1 deletion clang-tools-extra/clangd/index/Background.cpp
Original file line number Diff line number Diff line change
@@ -342,7 +342,8 @@ Error BackgroundIndex::index(tooling::CompileCommand Cmd,
RefSlab Refs;
auto Action = createStaticIndexingAction(
IndexOpts, [&](SymbolSlab S) { Symbols = std::move(S); },
[&](RefSlab R) { Refs = std::move(R); });
[&](RefSlab R) { Refs = std::move(R); },
/*IncludeGraphCallback=*/nullptr);

// We're going to run clang here, and it could potentially crash.
// We could use CrashRecoveryContext to try to make indexing crashes nonfatal,
122 changes: 115 additions & 7 deletions clang-tools-extra/clangd/index/IndexAction.cpp
Original file line number Diff line number Diff line change
@@ -9,22 +9,119 @@ namespace clang {
namespace clangd {
namespace {

llvm::Optional<std::string> toURI(const FileEntry *File) {
if (!File)
return llvm::None;
auto AbsolutePath = File->tryGetRealPathName();
if (AbsolutePath.empty())
return llvm::None;
return URI::create(AbsolutePath).toString();
}

// Collects the nodes and edges of include graph during indexing action.
// Important: The graph generated by those callbacks might contain cycles and
// self edges.
struct IncludeGraphCollector : public PPCallbacks {
public:
IncludeGraphCollector(const SourceManager &SM, IncludeGraph &IG)
: SM(SM), IG(IG) {}

// Populates everything except direct includes for a node, which represents
// edges in the include graph and populated in inclusion directive.
// We cannot populate the fields in InclusionDirective because it does not
// have access to the contents of the included file.
void FileChanged(SourceLocation Loc, FileChangeReason Reason,
SrcMgr::CharacteristicKind FileType,
FileID PrevFID) override {
// We only need to process each file once. So we don't care about anything
// but entries.
if (Reason != FileChangeReason::EnterFile)
return;

const auto FileID = SM.getFileID(Loc);
const auto File = SM.getFileEntryForID(FileID);
auto URI = toURI(File);
if (!URI)
return;
auto I = IG.try_emplace(*URI).first;

auto &Node = I->getValue();
// Node has already been populated.
if (Node.URI.data() == I->getKeyData()) {
#ifndef NDEBUG
auto Digest = digestFile(SM, FileID);
assert(Digest && Node.Digest == *Digest &&
"Same file, different digest?");
#endif
return;
}
if (auto Digest = digestFile(SM, FileID))
Node.Digest = std::move(*Digest);
Node.IsTU = FileID == SM.getMainFileID();
Node.URI = I->getKey();
}

// Add edges from including files to includes.
void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
StringRef FileName, bool IsAngled,
CharSourceRange FilenameRange, const FileEntry *File,
StringRef SearchPath, StringRef RelativePath,
const Module *Imported,
SrcMgr::CharacteristicKind FileType) override {
auto IncludeURI = toURI(File);
if (!IncludeURI)
return;

auto IncludingURI = toURI(SM.getFileEntryForID(SM.getFileID(HashLoc)));
if (!IncludingURI)
return;

auto NodeForInclude = IG.try_emplace(*IncludeURI).first->getKey();
auto NodeForIncluding = IG.try_emplace(*IncludingURI);

NodeForIncluding.first->getValue().DirectIncludes.push_back(NodeForInclude);
}

// Sanity check to ensure we have already populated a skipped file.
void FileSkipped(const FileEntry &SkippedFile, const Token &FilenameTok,
SrcMgr::CharacteristicKind FileType) override {
#ifndef NDEBUG
auto URI = toURI(&SkippedFile);
if (!URI)
return;
auto I = IG.try_emplace(*URI);
assert(!I.second && "File inserted for the first time on skip.");
assert(I.first->getKeyData() == I.first->getValue().URI.data() &&
"Node have not been populated yet");
#endif
}

private:
const SourceManager &SM;
IncludeGraph &IG;
};

// Wraps the index action and reports index data after each translation unit.
class IndexAction : public WrapperFrontendAction {
public:
IndexAction(std::shared_ptr<SymbolCollector> C,
std::unique_ptr<CanonicalIncludes> Includes,
const index::IndexingOptions &Opts,
std::function<void(SymbolSlab)> SymbolsCallback,
std::function<void(RefSlab)> RefsCallback)
std::function<void(RefSlab)> RefsCallback,
std::function<void(IncludeGraph)> IncludeGraphCallback)
: WrapperFrontendAction(index::createIndexingAction(C, Opts, nullptr)),
SymbolsCallback(SymbolsCallback), RefsCallback(RefsCallback),
Collector(C), Includes(std::move(Includes)),
IncludeGraphCallback(IncludeGraphCallback), Collector(C),
Includes(std::move(Includes)),
PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {}

std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &CI,
StringRef InFile) override {
CI.getPreprocessor().addCommentHandler(PragmaHandler.get());
if (IncludeGraphCallback != nullptr)
CI.getPreprocessor().addPPCallbacks(
llvm::make_unique<IncludeGraphCollector>(CI.getSourceManager(), IG));
return WrapperFrontendAction::CreateASTConsumer(CI, InFile);
}

@@ -46,22 +143,33 @@ class IndexAction : public WrapperFrontendAction {
SymbolsCallback(Collector->takeSymbols());
if (RefsCallback != nullptr)
RefsCallback(Collector->takeRefs());
if (IncludeGraphCallback != nullptr) {
#ifndef NDEBUG
// This checks if all nodes are initialized.
for (const auto &Node : IG)
assert(Node.getKeyData() == Node.getValue().URI.data());
#endif
IncludeGraphCallback(std::move(IG));
}
}

private:
std::function<void(SymbolSlab)> SymbolsCallback;
std::function<void(RefSlab)> RefsCallback;
std::function<void(IncludeGraph)> IncludeGraphCallback;
std::shared_ptr<SymbolCollector> Collector;
std::unique_ptr<CanonicalIncludes> Includes;
std::unique_ptr<CommentHandler> PragmaHandler;
IncludeGraph IG;
};

} // namespace

std::unique_ptr<FrontendAction>
createStaticIndexingAction(SymbolCollector::Options Opts,
std::function<void(SymbolSlab)> SymbolsCallback,
std::function<void(RefSlab)> RefsCallback) {
std::unique_ptr<FrontendAction> createStaticIndexingAction(
SymbolCollector::Options Opts,
std::function<void(SymbolSlab)> SymbolsCallback,
std::function<void(RefSlab)> RefsCallback,
std::function<void(IncludeGraph)> IncludeGraphCallback) {
index::IndexingOptions IndexOpts;
IndexOpts.SystemSymbolFilter =
index::IndexingOptions::SystemSymbolFilterKind::All;
@@ -77,7 +185,7 @@ createStaticIndexingAction(SymbolCollector::Options Opts,
Opts.Includes = Includes.get();
return llvm::make_unique<IndexAction>(
std::make_shared<SymbolCollector>(std::move(Opts)), std::move(Includes),
IndexOpts, SymbolsCallback, RefsCallback);
IndexOpts, SymbolsCallback, RefsCallback, IncludeGraphCallback);
}

} // namespace clangd
10 changes: 6 additions & 4 deletions clang-tools-extra/clangd/index/IndexAction.h
Original file line number Diff line number Diff line change
@@ -9,6 +9,7 @@

#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_ACTION_H
#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_ACTION_H
#include "Headers.h"
#include "SymbolCollector.h"
#include "clang/Frontend/FrontendActions.h"

@@ -23,10 +24,11 @@ namespace clangd {
// - references are always counted
// - all references are collected (if RefsCallback is non-null)
// - the symbol origin is always Static
std::unique_ptr<FrontendAction>
createStaticIndexingAction(SymbolCollector::Options Opts,
std::function<void(SymbolSlab)> SymbolsCallback,
std::function<void(RefSlab)> RefsCallback);
std::unique_ptr<FrontendAction> createStaticIndexingAction(
SymbolCollector::Options Opts,
std::function<void(SymbolSlab)> SymbolsCallback,
std::function<void(RefSlab)> RefsCallback,
std::function<void(IncludeGraph)> IncludeGraphCallback);

} // namespace clangd
} // namespace clang
3 changes: 2 additions & 1 deletion clang-tools-extra/clangd/indexer/IndexerMain.cpp
Original file line number Diff line number Diff line change
@@ -62,7 +62,8 @@ class IndexActionFactory : public tooling::FrontendActionFactory {
for (const auto &Ref : Sym.second)
Refs.insert(Sym.first, Ref);
}
})
},
/*IncludeGraphCallback=*/nullptr)
.release();
}

1 change: 1 addition & 0 deletions clang-tools-extra/unittests/clangd/CMakeLists.txt
Original file line number Diff line number Diff line change
@@ -28,6 +28,7 @@ add_extra_unittest(ClangdTests
FuzzyMatchTests.cpp
GlobalCompilationDatabaseTests.cpp
HeadersTests.cpp
IndexActionTests.cpp
IndexTests.cpp
JSONTransportTests.cpp
QualityTests.cpp
230 changes: 230 additions & 0 deletions clang-tools-extra/unittests/clangd/IndexActionTests.cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,230 @@
//===------ IndexActionTests.cpp -------------------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include "TestFS.h"
#include "index/IndexAction.h"
#include "clang/Tooling/Tooling.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"

namespace clang {
namespace clangd {
namespace {

using ::testing::AllOf;
using ::testing::ElementsAre;
using ::testing::Not;
using ::testing::Pair;
using ::testing::UnorderedElementsAre;
using ::testing::UnorderedPointwise;

std::string toUri(llvm::StringRef Path) { return URI::create(Path).toString(); }

MATCHER(IsTU, "") { return arg.IsTU; }

MATCHER_P(HasDigest, Digest, "") { return arg.Digest == Digest; }

MATCHER(HasSameURI, "") {
llvm::StringRef URI = testing::get<0>(arg);
const std::string &Path = testing::get<1>(arg);
return toUri(Path) == URI;
}

testing::Matcher<const IncludeGraphNode &>
IncludesAre(const std::vector<std::string> &Includes) {
return ::testing::Field(&IncludeGraphNode::DirectIncludes,
UnorderedPointwise(HasSameURI(), Includes));
}

void checkNodesAreInitialized(const IndexFileIn &IndexFile,
const std::vector<std::string> &Paths) {
EXPECT_THAT(Paths.size(), IndexFile.Sources->size());
for (llvm::StringRef Path : Paths) {
auto URI = toUri(Path);
const auto &Node = IndexFile.Sources->lookup(URI);
// Uninitialized nodes will have an empty URI.
EXPECT_EQ(Node.URI.data(), IndexFile.Sources->find(URI)->getKeyData());
}
}

std::map<std::string, const IncludeGraphNode &> toMap(const IncludeGraph &IG) {
std::map<std::string, const IncludeGraphNode &> Nodes;
for (auto &I : IG)
Nodes.emplace(I.getKey(), I.getValue());
return Nodes;
}

class IndexActionTest : public ::testing::Test {
public:
IndexActionTest() : InMemoryFileSystem(new llvm::vfs::InMemoryFileSystem) {}

IndexFileIn
runIndexingAction(llvm::StringRef MainFilePath,
const std::vector<std::string> &ExtraArgs = {}) {
IndexFileIn IndexFile;
IntrusiveRefCntPtr<FileManager> Files(
new FileManager(FileSystemOptions(), InMemoryFileSystem));

auto Action = createStaticIndexingAction(
SymbolCollector::Options(),
[&](SymbolSlab S) { IndexFile.Symbols = std::move(S); },
[&](RefSlab R) { IndexFile.Refs = std::move(R); },
[&](IncludeGraph IG) { IndexFile.Sources = std::move(IG); });

std::vector<std::string> Args = {"index_action", "-fsyntax-only",
"-xc++", "-std=c++11",
"-iquote", testRoot()};
Args.insert(Args.end(), ExtraArgs.begin(), ExtraArgs.end());
Args.push_back(MainFilePath);

tooling::ToolInvocation Invocation(
Args, Action.release(), Files.get(),
std::make_shared<PCHContainerOperations>());

Invocation.run();

checkNodesAreInitialized(IndexFile, FilePaths);
return IndexFile;
}

void addFile(llvm::StringRef Path, llvm::StringRef Content) {
InMemoryFileSystem->addFile(Path, 0,
llvm::MemoryBuffer::getMemBuffer(Content));
FilePaths.push_back(Path);
}

protected:
std::vector<std::string> FilePaths;
IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem;
};

TEST_F(IndexActionTest, CollectIncludeGraph) {
std::string MainFilePath = testPath("main.cpp");
std::string MainCode = "#include \"level1.h\"";
std::string Level1HeaderPath = testPath("level1.h");
std::string Level1HeaderCode = "#include \"level2.h\"";
std::string Level2HeaderPath = testPath("level2.h");
std::string Level2HeaderCode = "";

addFile(MainFilePath, MainCode);
addFile(Level1HeaderPath, Level1HeaderCode);
addFile(Level2HeaderPath, Level2HeaderCode);

IndexFileIn IndexFile = runIndexingAction(MainFilePath);
auto Nodes = toMap(*IndexFile.Sources);

EXPECT_THAT(Nodes,
UnorderedElementsAre(
Pair(toUri(MainFilePath),
AllOf(IsTU(), IncludesAre({Level1HeaderPath}),
HasDigest(digest(MainCode)))),
Pair(toUri(Level1HeaderPath),
AllOf(Not(IsTU()), IncludesAre({Level2HeaderPath}),
HasDigest(digest(Level1HeaderCode)))),
Pair(toUri(Level2HeaderPath),
AllOf(Not(IsTU()), IncludesAre({}),
HasDigest(digest(Level2HeaderCode))))));
}

TEST_F(IndexActionTest, IncludeGraphSelfInclude) {
std::string MainFilePath = testPath("main.cpp");
std::string MainCode = "#include \"header.h\"";
std::string HeaderPath = testPath("header.h");
std::string HeaderCode = R"cpp(
#ifndef _GUARD_
#define _GUARD_
#include "header.h"
#endif)cpp";

addFile(MainFilePath, MainCode);
addFile(HeaderPath, HeaderCode);

IndexFileIn IndexFile = runIndexingAction(MainFilePath);
auto Nodes = toMap(*IndexFile.Sources);

EXPECT_THAT(
Nodes,
UnorderedElementsAre(
Pair(toUri(MainFilePath), AllOf(IsTU(), IncludesAre({HeaderPath}),
HasDigest(digest(MainCode)))),
Pair(toUri(HeaderPath), AllOf(Not(IsTU()), IncludesAre({HeaderPath}),
HasDigest(digest(HeaderCode))))));
}

TEST_F(IndexActionTest, IncludeGraphSkippedFile) {
std::string MainFilePath = testPath("main.cpp");
std::string MainCode = R"cpp(
#include "common.h"
#include "header.h"
)cpp";

std::string CommonHeaderPath = testPath("common.h");
std::string CommonHeaderCode = R"cpp(
#ifndef _GUARD_
#define _GUARD_
void f();
#endif)cpp";

std::string HeaderPath = testPath("header.h");
std::string HeaderCode = R"cpp(
#include "common.h"
void g();)cpp";

addFile(MainFilePath, MainCode);
addFile(HeaderPath, HeaderCode);
addFile(CommonHeaderPath, CommonHeaderCode);

IndexFileIn IndexFile = runIndexingAction(MainFilePath);
auto Nodes = toMap(*IndexFile.Sources);

EXPECT_THAT(
Nodes, UnorderedElementsAre(
Pair(toUri(MainFilePath),
AllOf(IsTU(), IncludesAre({HeaderPath, CommonHeaderPath}),
HasDigest(digest(MainCode)))),
Pair(toUri(HeaderPath),
AllOf(Not(IsTU()), IncludesAre({CommonHeaderPath}),
HasDigest(digest(HeaderCode)))),
Pair(toUri(CommonHeaderPath),
AllOf(Not(IsTU()), IncludesAre({}),
HasDigest(digest(CommonHeaderCode))))));
}

TEST_F(IndexActionTest, IncludeGraphDynamicInclude) {
std::string MainFilePath = testPath("main.cpp");
std::string MainCode = R"cpp(
#ifndef FOO
#define FOO "main.cpp"
#else
#define FOO "header.h"
#endif
#include FOO)cpp";
std::string HeaderPath = testPath("header.h");
std::string HeaderCode = "";

addFile(MainFilePath, MainCode);
addFile(HeaderPath, HeaderCode);

IndexFileIn IndexFile = runIndexingAction(MainFilePath);
auto Nodes = toMap(*IndexFile.Sources);

EXPECT_THAT(
Nodes,
UnorderedElementsAre(
Pair(toUri(MainFilePath),
AllOf(IsTU(), IncludesAre({MainFilePath, HeaderPath}),
HasDigest(digest(MainCode)))),
Pair(toUri(HeaderPath), AllOf(Not(IsTU()), IncludesAre({}),
HasDigest(digest(HeaderCode))))));
}

} // namespace
} // namespace clangd
} // namespace clang

0 comments on commit 5399552

Please sign in to comment.