Index: include/clang/Tooling/CompilationDatabase.h =================================================================== --- include/clang/Tooling/CompilationDatabase.h +++ include/clang/Tooling/CompilationDatabase.h @@ -213,6 +213,13 @@ std::vector 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 + inferMissingCompileCommands(std::unique_ptr); + } // 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: 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 + +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 +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 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(S, Prefix); +} + +// A comparator for searching SubstringWithIndexes with std::equal_range etc. +// Optional prefix semantics (prefix compares equal), or reversed strings. +template struct Less { + bool operator()(StringRef Key, std::pair Value) const { + return Prefix ? prefixCompare(Value.first, Key) > 0 + : compare(Key, Value.first) < 0; + } + bool operator()(std::pair Value, StringRef Key) const { + return Prefix ? prefixCompare(Value.first, Key) < 0 + : compare(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 Inner) + : Inner(std::move(Inner)), Strings(Arena) { + for (auto F : getAllFiles()) + Paths.emplace_back(Strings.save(F), 0); + finalizeIndex(); + } + + std::vector + getCompileCommands(StringRef FilePath) const override { + auto Known = Inner->getCompileCommands(FilePath); + if (Paths.empty() || !Known.empty()) + return Known; + return {inferCommand(FilePath)}; + } + + std::vector getAllFiles() const override { + return Inner->getAllFiles(); + } + + std::vector getAllCompileCommands() const override { + return Inner->getAllCompileCommands(); + } + +private: + using SubstringAndIndex = std::pair; + + // 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(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 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 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 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 Candidates; // Index -> score. + auto Award = [&](int Points, ArrayRef 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(Stem, Stems)); + Award(1, indexLookup(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(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, Paths)); + return Candidates; + } + + // Pick a single winner from the set of scored candidates. + std::pair BreakTies(const DenseMap &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 + ArrayRef + indexLookup(StringRef Key, const std::vector &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()); + return {Range.first, Range.second}; + } + + // Performs a point lookup into a nonempty index, returning a longest match. + SubstringAndIndex + longestMatch(StringRef Key, const std::vector &Idx) const { + // Longest substring match will be adjacent to a direct lookup. + auto It = std::lower_bound(Idx.begin(), Idx.end(), Key, + Less()); + 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 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 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 Inner; + BumpPtrAllocator Arena; + StringSaver Strings; + + // Index of candidates for borrowing compile commands. + // Invariants are established by finalizeIndex(). + std::vector Paths; // Full path, sorted. + std::vector Stems; // Basename, without extension, sorted. + std::vector RStems; // Stems sorted by reversed contents. + std::vector Components; // Last path components, sorted. +}; + +} + +std::unique_ptr +inferMissingCompileCommands(std::unique_ptr Inner) { + return llvm::make_unique(std::move(Inner)); +} + +} // namespace tooling +} // namespace clang 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>; + EntryMap Entries; + MemCDB(const EntryMap &E) : Entries(E) {} + + std::vector getCompileCommands(StringRef F) const override { + auto Ret = Entries.lookup(F); + return {Ret.begin(), Ret.end()}; + } + + std::vector getAllFiles() const override { + std::vector 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 , so the command used can be identified. + void add(llvm::StringRef File, llvm::StringRef Flags = "") { + llvm::SmallVector 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(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