sammccall updated this revision to Diff 140349.
sammccall added a comment.
Add tests, fix minor bugs, add lots of comments and structure.
Repository:
rC Clang
https://reviews.llvm.org/D45006
Files:
include/clang/Tooling/CompilationDatabase.h
lib/Tooling/CMakeLists.txt
lib/Tooling/InterpolatingCompilationDatabase.cpp
unittests/Tooling/CompilationDatabaseTest.cpp
Index: unittests/Tooling/CompilationDatabaseTest.cpp
===================================================================
--- unittests/Tooling/CompilationDatabaseTest.cpp
+++ unittests/Tooling/CompilationDatabaseTest.cpp
@@ -626,5 +626,99 @@
EXPECT_EQ(2, Argc);
}
+struct MemCDB : public CompilationDatabase {
+ using EntryMap = llvm::StringMap<SmallVector<CompileCommand, 1>>;
+ EntryMap Entries;
+ MemCDB(const EntryMap &E) : Entries(E) {}
+
+ std::vector<CompileCommand> getCompileCommands(StringRef F) const override {
+ auto Ret = Entries.lookup(F);
+ return {Ret.begin(), Ret.end()};
+ }
+
+ std::vector<std::string> getAllFiles() const override {
+ std::vector<std::string> Result;
+ for (const auto &Entry : Entries)
+ Result.push_back(Entry.first());
+ return Result;
+ }
+};
+
+class InterpolateTest : public ::testing::Test {
+protected:
+ // Adds an entry to the underlying compilation database.
+ // A flag is injected: -D <File>, so the command used can be identified.
+ void add(llvm::StringRef File, llvm::StringRef Flags = "") {
+ llvm::SmallVector<StringRef, 8> Argv = {"clang", File, "-D", File};
+ llvm::SplitString(Flags, Argv);
+ llvm::SmallString<32> Dir;
+ llvm::sys::path::system_temp_directory(false, Dir);
+ Entries[path(File)].push_back(
+ {Dir, File, {Argv.begin(), Argv.end()}, "foo.o"});
+ }
+
+ // Turn a unix path fragment (foo/bar.h) into a native path (C:\tmp\foo\bar.h)
+ std::string path(llvm::SmallString<32> File) {
+ llvm::SmallString<32> Dir;
+ llvm::sys::path::system_temp_directory(false, Dir);
+ llvm::sys::path::native(File);
+ llvm::SmallString<64> Result;
+ llvm::sys::path::append(Result, Dir, File);
+ return Result.str();
+ }
+
+ // Look up the command from a relative path, and return it in string form.
+ // The input file is not included in the returned command.
+ std::string getCommand(llvm::StringRef F) {
+ auto Results =
+ inferMissingCompileCommands(llvm::make_unique<MemCDB>(Entries))
+ ->getCompileCommands(path(F));
+ if (Results.empty())
+ return "none";
+ // drop the input file argument, so tests don't have to deal with path().
+ EXPECT_EQ(Results[0].CommandLine.back(), path(F))
+ << "Last arg should be the file";
+ Results[0].CommandLine.pop_back();
+ return llvm::join(Results[0].CommandLine, " ");
+ }
+
+ MemCDB::EntryMap Entries;
+};
+
+TEST_F(InterpolateTest, Nearby) {
+ add("dir/foo.cpp");
+ add("dir/bar.cpp");
+ add("an/other/foo.cpp");
+
+ // great: dir and name both match (prefix or suffix)
+ EXPECT_EQ(getCommand("dir/f.cpp"), "clang -D dir/foo.cpp");
+ EXPECT_EQ(getCommand("dir/o.cpp"), "clang -D dir/foo.cpp");
+ // no name match. prefer matching dir, break ties by alpha
+ EXPECT_EQ(getCommand("dir/a.cpp"), "clang -D dir/bar.cpp");
+ // an exact name match beats one segment of directory match
+ EXPECT_EQ(getCommand("some/other/bar.h"), "clang -x c++ -D dir/bar.cpp");
+ // two segments of directory match beat a prefix name match
+ EXPECT_EQ(getCommand("an/other/b.cpp"), "clang -D an/other/foo.cpp");
+ // if nothing matches at all, we still get the closest alpha match
+ EXPECT_EQ(getCommand("below/some/obscure/path.cpp"),
+ "clang -D an/other/foo.cpp");
+}
+
+TEST_F(InterpolateTest, Language) {
+ add("dir/foo.cpp");
+ add("dir/baz.cee", "-x c");
+
+ // extension changed, so we add explicit language flags
+ EXPECT_EQ(getCommand("foo.h"), "clang -x c++ -D dir/foo.cpp");
+ // but we don't add -x if it's already there
+ EXPECT_EQ(getCommand("baz.h"), "clang -D dir/baz.cee -x c");
+}
+
+TEST_F(InterpolateTest, Strip) {
+ add("dir/foo.cpp", "-o foo.o -Wall");
+ // the -o option and the input file are removed, but -Wall is preserved.
+ EXPECT_EQ(getCommand("dir/bar.cpp"), "clang -D dir/foo.cpp -Wall");
+}
+
} // end namespace tooling
} // end namespace clang
Index: lib/Tooling/InterpolatingCompilationDatabase.cpp
===================================================================
--- /dev/null
+++ lib/Tooling/InterpolatingCompilationDatabase.cpp
@@ -0,0 +1,340 @@
+//===- InterpolatingCompilationDatabase.cpp ---------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// InterpolatingCompilationDatabase wraps another CompilationDatabase and
+// attempts to heuristically determine appropriate compile commands for files
+// that are not included, such as headers or newly created files.
+//
+// We "borrow" the compile command for the closest available file:
+// - points are awarded if the filename matches (ignoring extension)
+// - points are awarded if the directory structure matches
+// - ties are broken by length of path prefix match
+//
+// The compile command is adjusted:
+// - the input filename is replaced
+// - if the extension differs, an "-x" flag is added to preserve the language
+// - output file arguments are removed
+//
+// This class is only useful when wrapping databases that can enumerate all
+// their compile commands. If getAllFilenames() is empty, no inference occurs.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Driver/Options.h"
+#include "clang/Driver/Types.h"
+#include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Option/ArgList.h"
+#include "llvm/Option/OptTable.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/StringSaver.h"
+#include "llvm/Support/raw_ostream.h"
+#include <memory>
+
+namespace clang {
+namespace tooling {
+namespace {
+using namespace llvm;
+
+// First, a bunch of helpers for comparing strings.
+// These are used for lookups into the index, and for comparing results.
+// As well as normal string lookups, we need prefix lookup (for basenames,
+// and for directory proximity), and reverse lookup (for basename suffixes).
+
+// The length of the prefix these two strings have in common.
+size_t matchingPrefix(StringRef L, StringRef R) {
+ size_t Limit = std::min(L.size(), R.size());
+ for (size_t I = 0; I < Limit; ++I)
+ if (L[I] != R[I])
+ return I;
+ return Limit;
+}
+
+// Like memcmp(), but traverses in reverse order. L and R are one-past-end.
+int rMemCompare(const char *L, const char *R, size_t N) {
+ for (const char *LStop = L - N; L > LStop;)
+ if (*--L != *--R)
+ return *L < *R ? -1 : 1;
+ return 0;
+}
+
+// This is like L.compare(R), but maybe with the order of characters reversed.
+template <bool Reverse>
+int compare(StringRef L, StringRef R) {
+ if (!Reverse)
+ return L.compare(R);
+ // Traverse the common region backwards, first differing byte is decisive.
+ if (int Cmp = rMemCompare(L.end(), R.end(), std::min(L.size(), R.size())))
+ return Cmp;
+ // No byte differed, so the shorter string is smaller.
+ return L.size() == R.size() ? 0 : L.size() < R.size() ? -1 : 1;
+}
+
+// Returns 0 if S starts with prefix, else -1 for S < Prefix, 1 for S > Prefix.
+template <bool Reverse> int prefixCompare(StringRef S, StringRef Prefix) {
+ if (S.size() >= Prefix.size())
+ return Reverse ? rMemCompare(S.end(), Prefix.end(), Prefix.size())
+ : memcmp(S.begin(), Prefix.begin(), Prefix.size());
+ return compare<Reverse>(S, Prefix);
+}
+
+// A comparator for searching SubstringWithIndexes with std::equal_range etc.
+// Optional prefix semantics (prefix compares equal), or reversed strings.
+template <bool Prefix, bool Reverse> struct Less {
+ bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const {
+ return Prefix ? prefixCompare<Reverse>(Value.first, Key) > 0
+ : compare<Reverse>(Key, Value.first) < 0;
+ }
+ bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const {
+ return Prefix ? prefixCompare<Reverse>(Value.first, Key) < 0
+ : compare<Reverse>(Value.first, Key) < 0;
+ }
+};
+
+// The basic strategy:
+// - On startup, capture all the filenames from the inner CDB
+// - Build indexes of each of the substrings we want to look up by.
+// These indexes are just sorted lists of the substrings.
+// - Forward requests to the inner CDB. If it fails, we must pick a proxy.
+// - Each criterion corresponds to a range lookup into the index, so we only
+// need O(log N) string comparisons to determine scores.
+// - We then break ties among the candidates with the highest score.
+class InterpolatingCompilationDatabase : public CompilationDatabase {
+public:
+ InterpolatingCompilationDatabase(std::unique_ptr<CompilationDatabase> Inner)
+ : Inner(std::move(Inner)), Strings(Arena) {
+ for (auto F : getAllFiles())
+ Paths.emplace_back(Strings.save(F), 0);
+ finalizeIndex();
+ }
+
+ std::vector<CompileCommand>
+ getCompileCommands(StringRef FilePath) const override {
+ auto Known = Inner->getCompileCommands(FilePath);
+ if (Paths.empty() || !Known.empty())
+ return Known;
+ return {inferCommand(FilePath)};
+ }
+
+ std::vector<std::string> getAllFiles() const override {
+ return Inner->getAllFiles();
+ }
+
+ std::vector<CompileCommand> getAllCompileCommands() const override {
+ return Inner->getAllCompileCommands();
+ }
+
+private:
+ using SubstringAndIndex = std::pair<StringRef, size_t>;
+
+ // Sort the paths list, and populate other index fields from it.
+ // We identify files by the index into (sorted) Paths.
+ void finalizeIndex() {
+ llvm::sort(Paths.begin(), Paths.end());
+ for (size_t I = 0; I < Paths.size(); ++I) {
+ Paths[I].second = I;
+ StringRef &Path = Paths[I].first;
+ Stems.emplace_back(sys::path::stem(Path), I);
+ auto Dir = ++sys::path::rbegin(Path), DirEnd = sys::path::rend(Path);
+ // Index up to 4 path components.
+ for (int J = 0; J < 4 && Dir != DirEnd; ++J, ++Dir)
+ if (Dir->size() > 2) // not trivial ones
+ Components.emplace_back(*Dir, I);
+ }
+ RStems = Stems;
+ llvm::sort(Stems.begin(), Stems.end());
+ llvm::sort(RStems.begin(), RStems.end(),
+ [](SubstringAndIndex L, SubstringAndIndex R) {
+ if (int Cmp = compare</*Reverse=*/true>(L.first, R.first))
+ return Cmp < 0;
+ return L.second < R.second;
+ });
+ llvm::sort(Components.begin(), Components.end());
+ }
+
+ // Called if the inner CDB failed and we have at least one candidate.
+ CompileCommand inferCommand(StringRef Filename) const {
+ assert(!Paths.empty() && "need at least one candidate!");
+
+ auto Candidates = ScoreCandidates(Filename);
+ std::pair<StringRef, int> Best = BreakTies(Candidates, Filename);
+
+ DEBUG_WITH_TYPE("interpolate", llvm::dbgs()
+ << "interpolate: chose " << Best.first
+ << " as proxy for " << Filename
+ << " score=" << Best.second << "\n");
+ auto Result = Inner->getCompileCommands(Best.first);
+ assert(!Result.empty() &&
+ "candidates returned by getFiles() should have compile commands!");
+ return adjust(std::move(Result[0]), Filename);
+ }
+
+ // Award points to candidate entries that should be considered for the file.
+ // Returned keys are indexes into paths, and the values are (nonzero) scores.
+ DenseMap<size_t, int> ScoreCandidates(StringRef Filename) const {
+ // Decompose Filename into the parts we care about.
+ // /some/path/complicated/project/Interesting.h
+ // [-prefix--][---dir---] [-dir-] [--stem---]
+ StringRef Stem = sys::path::stem(Filename);
+ llvm::SmallVector<StringRef, 2> Dirs; // Only look up the last 2.
+ llvm::StringRef Prefix;
+ auto Dir = ++sys::path::rbegin(Filename),
+ DirEnd = sys::path::rend(Filename);
+ for (int I = 0; I < 2 && Dir != DirEnd; ++I, ++Dir) {
+ if (Dir->size() > 2)
+ Dirs.push_back(*Dir);
+ Prefix = Filename.substr(0, Dir - DirEnd);
+ }
+
+ // Now award points based on lookups into our various indexes.
+ DenseMap<size_t, int> Candidates; // Index -> score.
+ auto Award = [&](int Points, ArrayRef<SubstringAndIndex> Range) {
+ for (const auto& Entry : Range)
+ Candidates[Entry.second] += Points;
+ };
+ // Award one point if the file's basename is a prefix of the candidate,
+ // and another if it's a suffix (so exact matches get two points).
+ Award(1, indexLookup</*Prefix=*/true, /*reverse=*/false>(Stem, Stems));
+ Award(1, indexLookup</*Prefix=*/true, /*reverse=*/true>(Stem, RStems));
+ // For each of the last two directories in the Filename, award a point
+ // if it's present in the candidate (in the last 4).
+ for (StringRef Dir : Dirs)
+ Award(1,
+ indexLookup</*Prefix=*/false, /*reverse=*/false>(Dir, Components));
+ // Award one more point if the whole rest of the path matches.
+ if (sys::path::root_directory(Prefix) != Prefix)
+ Award(1, indexLookup</*Prefix=*/true, /*reverse=*/false>(Prefix, Paths));
+ return Candidates;
+ }
+
+ // Pick a single winner from the set of scored candidates.
+ std::pair<StringRef, int> BreakTies(const DenseMap<size_t, int> &Candidates,
+ StringRef Filename) const {
+ // Choose the best candidate by (points, prefix length, alpha).
+ StringRef Best;
+ int BestPoints = 0;
+ size_t BestPrefixLength = 0;
+ for (const auto& Candidate : Candidates) {
+ if (Candidate.second < BestPoints)
+ continue;
+ StringRef CandidatePath = Paths[Candidate.first].first;
+ size_t PrefixLength = matchingPrefix(Filename, CandidatePath);
+ if (Candidate.second == BestPoints) {
+ if (PrefixLength < BestPrefixLength)
+ continue;
+ // hidden heuristics should at least be deterministic!
+ if (PrefixLength == BestPrefixLength)
+ if (CandidatePath > Best)
+ continue;
+ }
+ Best = CandidatePath;
+ BestPoints = Candidate.second;
+ BestPrefixLength = PrefixLength;
+ }
+ if (Best.empty()) // Edge case: no candidate got any points.
+ Best = longestMatch(Filename, Paths).first;
+ return {Best, BestPoints};
+ }
+
+ // Returns the range within a sorted index that compares equal to Key.
+ // If Prefix is true, it's instead the range starting with Key.
+ // If Reverse and Prefix are both true, it's a suffix search.
+ template <bool Prefix, bool Reverse>
+ ArrayRef<SubstringAndIndex>
+ indexLookup(StringRef Key, const std::vector<SubstringAndIndex> &Idx) const {
+ // Use pointers as iteratiors to ease conversion of result to ArrayRef.
+ auto Range = std::equal_range(&Idx[0], &Idx[Idx.size()], Key,
+ Less<Prefix, Reverse>());
+ return {Range.first, Range.second};
+ }
+
+ // Performs a point lookup into a nonempty index, returning a longest match.
+ SubstringAndIndex
+ longestMatch(StringRef Key, const std::vector<SubstringAndIndex> &Idx) const {
+ // Longest substring match will be adjacent to a direct lookup.
+ auto It = std::lower_bound(Idx.begin(), Idx.end(), Key,
+ Less<false, false>());
+ if (It == Paths.begin())
+ return *It;
+ if (It == Paths.end())
+ return *--It;
+ // Have to choose between It and It-1
+ size_t Prefix = matchingPrefix(Key, It->first);
+ size_t PrevPrefix = matchingPrefix(Key, (It - 1)->first);
+ return Prefix > PrevPrefix ? *It : *--It;
+ }
+
+ // Tweaks the CompileCommand for use with a different file.
+ // We use the real options parser to avoid fragile string replacements.
+ CompileCommand adjust(CompileCommand Base, StringRef Filename) const {
+ auto OptTable = clang::driver::createDriverOptTable();
+ std::vector<const char *> Argv;
+ for (unsigned I = 1; I < Base.CommandLine.size(); ++I)
+ Argv.push_back(Base.CommandLine[I].c_str());
+ unsigned MissingI, MissingC;
+ auto ArgList = OptTable->ParseArgs(Argv, MissingI, MissingC);
+
+ // Parse the old args in order to strip out input and -o.
+ std::vector<std::string> NewArgs;
+ bool HasLanguageFlag = false;
+ for (const auto *Arg : ArgList) {
+ const auto &option = Arg->getOption();
+ if (option.matches(clang::driver::options::OPT_INPUT) ||
+ option.matches(clang::driver::options::OPT_o)) {
+ continue;
+ }
+ if (option.matches(clang::driver::options::OPT_x))
+ HasLanguageFlag = true;
+ llvm::opt::ArgStringList ArgStrs;
+ Arg->render(ArgList, ArgStrs);
+ NewArgs.insert(NewArgs.end(), ArgStrs.begin(), ArgStrs.end());
+ }
+ NewArgs.emplace_back(Filename);
+
+ // Finally, build the final CompileCommand.
+ Base.CommandLine.resize(1); // keep argv[0]
+ if (!HasLanguageFlag && llvm::sys::path::extension(Filename) !=
+ llvm::sys::path::extension(Base.Filename)) {
+ // Language was inferred from the extension, which has changed. Add -x.
+ if (auto Lang = driver::types::lookupTypeForExtension(
+ llvm::sys::path::extension(Base.Filename).substr(1))) {
+ Base.CommandLine.push_back("-x");
+ Base.CommandLine.push_back(driver::types::getTypeName(Lang));
+ }
+ }
+ Base.CommandLine.insert(Base.CommandLine.end(), NewArgs.begin(),
+ NewArgs.end());
+ Base.Filename = Filename;
+ Base.Output.clear();
+ return Base;
+ }
+
+ std::unique_ptr<CompilationDatabase> Inner;
+ BumpPtrAllocator Arena;
+ StringSaver Strings;
+
+ // Index of candidates for borrowing compile commands.
+ // Invariants are established by finalizeIndex().
+ std::vector<SubstringAndIndex> Paths; // Full path, sorted.
+ std::vector<SubstringAndIndex> Stems; // Basename, without extension, sorted.
+ std::vector<SubstringAndIndex> RStems; // Stems sorted by reversed contents.
+ std::vector<SubstringAndIndex> Components; // Last path components, sorted.
+};
+
+}
+
+std::unique_ptr<CompilationDatabase>
+inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) {
+ return llvm::make_unique<InterpolatingCompilationDatabase>(std::move(Inner));
+}
+
+} // namespace tooling
+} // namespace clang
Index: lib/Tooling/CMakeLists.txt
===================================================================
--- lib/Tooling/CMakeLists.txt
+++ lib/Tooling/CMakeLists.txt
@@ -15,6 +15,7 @@
Execution.cpp
FileMatchTrie.cpp
FixIt.cpp
+ InterpolatingCompilationDatabase.cpp
JSONCompilationDatabase.cpp
Refactoring.cpp
RefactoringCallbacks.cpp
Index: include/clang/Tooling/CompilationDatabase.h
===================================================================
--- include/clang/Tooling/CompilationDatabase.h
+++ include/clang/Tooling/CompilationDatabase.h
@@ -213,6 +213,13 @@
std::vector<CompileCommand> CompileCommands;
};
+/// Returns a wrapped CompilationDatabase that defers to the provided one,
+/// but getCompileCommands() will infer commands for unknown files.
+/// The return value of getAllFiles() or getAllCompileCommands() is unchanged.
+/// See InterpolatingCompilationDatabase.cpp for details on heuristics.
+std::unique_ptr<CompilationDatabase>
+ inferMissingCompileCommands(std::unique_ptr<CompilationDatabase>);
+
} // namespace tooling
} // namespace clang
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
