[clangd] Refactor IncludeStructure: use File (unsigned) for most computations

[kbobyrev]

Summary

Preparation for D108194.

[sammccall]

clang-tools-extra/clangd/Headers.h

115

this concept needs documentation.

115

there's a naming issue here:

• "File" is an overloaded enough concept that you still end up referring to these as "file indexes" below, which isn't clear.
• obviously this integer isn't either the file itself nor our record of it, so the metaphor is a bit confusing

What do you think about just ID, which would be spelled from the outside as IncludeStructure::ID?
Maybe HeaderID is better. I don't think it's a big problem that we have one for the main file too...

117

"Name" certainly needs to be clarified here.
Do you have any use cases in mind where you wouldn't have a FileEntry on hand? That would make this typesafe (and in particular avoid passing absolute filenames, or strings like "utility" or "<utility>)

124

it's unclear from this patch whether you want to expose the whole graph or just allow querying per-file - I doubt we need both.

124

tests?

131

this public member is now sandwiched between methods

141

The public interface now uses the File abstraction, so this method sticks out. (It has an awkward interface in the first place due to the need to use strings)

Suggest replacing it with DenseMap<File, unsigned> includeDepth(File Root). We'd need to add StringRef RealPath(File) for the caller, but that seems to make sense anyway.

148

this isn't abstract :-)

also the public nature of it isn't used, in this patch at least.

151

File should be capitalized.

FWIW, for a private method I prefer the old name here

[kbobyrev]

Resolve review comments.

[kbobyrev]

s/ToVector/Flatten/g

[kbobyrev]

Update non-working test

[kbobyrev]

I resolved the comments we discussed offline, there's a weird SIGSEGV (out of boundary error) somewhere in the tests but it looks fine otherwise.

[kbobyrev]

Fix the last failing test. All tests are green now.

[kbobyrev]

Clean tests.

[tschuett]

Do you want to wrap the unsigned in a struct to make it slightly safer, but more complicated to use?

[sammccall]

Just nits left really.

In D110386#3020890, @tschuett wrote:

Do you want to wrap the unsigned in a struct to make it slightly safer, but more complicated to use?

I like this idea, though it's probably not a huge deal either way.
(I marginally prefer enum class HeaderID : unsigned {}; over a struct, but it's basically the same thing)

clang-tools-extra/clangd/CodeComplete.cpp

1382 ↗

(On Diff #374853)

this isn't the ID of the include structure, it's the ID of the main file

1383 ↗

(On Diff #374853)

IncludeStructure is mutable here, I think it'd be safe to getOrCreate here.

Alternatively, make this infallible having IncludeStructure record the HeaderID for the main file in its constructor, and just use Includes.Root here.

Either way, I'd rather not deal with Expected<> error handling at runtime if we can define this error away.

clang-tools-extra/clangd/Headers.h

131

As mentioned offline, this is an implementation comment, but it doesn't say *what the HeaderID is*.

Suggest something like:

HeaderID identifies file in the include graph.
It corresponds to a FileEntry rather than a FileID, but stays stable across preamble & main file builds.

I'd move this impl comment back down to the private StringMap, but it could also follow the description.

134

comment still refers to "file index" as if it were introducing a term we use elsewhere

139–140

comment is out of date

140

I think this can be Optional rather than Expected - much more lightweight.

142

getName() is not right here.
(Hopefully the example will fit on the "Usually" line when fixed?)

144

this should be an assertion (or just leave that up to the vector) - passing an out-of-range HeaderID is invalid

147

we don't need this method if IncludeChildren is exposed, right?

[kbobyrev]

Resolve all review comments.

[kbobyrev]

Rebase on top of main.

[sammccall]

clang-tools-extra/clangd/Headers.cpp

173

no auto here. I really hope this isn't std::string :-)

Actually I think you can avoid extracting this variable at all, because the !RealPathName.empty() check is redundant. The case where both sides are empty is rare enough that it's fine to assign as long as the *stored* name is empty.

175

extract std::string &RealPathName = RealPathNames[...]?

181

This is a "can't happen" condition - remove or replace with an assert?

199–200

This is no longer true, we don't need the check.

clang-tools-extra/clangd/Headers.h

131

This doesn't seem to be done.
You've added a line to the *bottom* of the implementation comment defining HeaderID in terms of the implementation.

A reader rather needs complete self-contained description of the concept at the *top*, optionally followed by an explanation about the implementation (separated by a blank line).

clang-tools-extra/clangd/unittests/HeadersTests.cpp

70 ↗

(On Diff #375151)

reparsing the code several times to obtain header IDs doesn't seem reasonable. It's surprising behavior from a test helper, and it requires that header IDs are stable across parses!

Can we just pass in the IncludeStructure instead?

234 ↗

(On Diff #375151)

Why are we asserting on every element of the map one at a time, instead of the whole map at once? Seems like it would be more regular and easier to read.

I'd probably just write:

DenseMap<HeaderID, SmallVector<HeaderID>> Expected = { ... };
EXPECT_EQ(Expected, Includes.IncludeChildren);

236 ↗

(On Diff #375151)

EXPECT_THAT(foo.empty()) -> EXPECT_THAT(foo, IsEmpty()).
(Much better error messages)

clang-tools-extra/clangd/unittests/ParsedASTTests.cpp

511 ↗

(On Diff #375151)

The ratio of setup to punchline of the rest of this test seems like it's gotten out of hand (it wasn't great before, but it's doubled).

What about just

auto &FM = PatchedAST->getSourceManager().getFileManager();
auto &Includes = PatchedAST->getIncludeStructure();
auto MainID = Includes.getID(FM.getFile(testPath("foo.cpp")));
auto AuxID = Includes.getID(FM.getFile(testPath("sub/aux.h")));
EXPECT_THAT(Includes.IncludeChildren.at(MainID), Contains(AuxID));

It tests a bit less I guess, but seems like enough

568 ↗

(On Diff #375151)

and here

[kbobyrev]

Resolve all but two comments, leave the clarification questions for these two.

clang-tools-extra/clangd/Headers.cpp

199–200

Wait, why not? We still have unresolved includes, e.g. preamble patches are like that, their RealPathNames stay empty.

clang-tools-extra/clangd/unittests/HeadersTests.cpp

234 ↗

(On Diff #375151)

This would expect the elements in the map to be in a particular order, isn't this something we don't want?

[sammccall]

clang-tools-extra/clangd/Headers.cpp

199–200

Right, but why do we need to filter them out here?
Can't we just drop them when we use them to seed the proximity sources?

clang-tools-extra/clangd/unittests/HeadersTests.cpp

234 ↗

(On Diff #375151)

== on DenseMap doesn't consider order.

If you mean the order within map values (i.e. lists of child edges): these are in the order the #includes appear in the file, which seems fine to depend on to me

[kbobyrev]

Switch to full DenseMap comparison in the tests.

clang-tools-extra/clangd/Headers.cpp

199–200

I feel like producing them in the first place is kind of redundant, what signal does it give to the user through such API?

Getting some "hidden"/"unresolved" includes certainly feels rather confusing to me, post-filtering outside probably requires understanding of the internals which does not look like a good idea. WDYT?

clang-tools-extra/clangd/unittests/HeadersTests.cpp

234 ↗

(On Diff #375151)

Yes, I initially meant the SmallVector order, but yeah, this seems reasonable, thank you!

[kbobyrev]

Resolve the last comment

[thakis]

Looks like this breaks tests on Windows: http://45.33.8.238/win/45971/step_9.txt

PTAL!

[thakis]

Reverted in 36dc5c048ac745ef62769dd824a9a13659afc2ef for now.

clang-tools-extra/clangd/Headers.h

struct Inclusion {
   Path Resolved; // Resolved path of included file. Empty if not resolved.
   unsigned HashOffset = 0; // Byte offset from start of file to #.
   int HashLine = 0;        // Line number containing the directive, 0-indexed.
   SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User;
 };
 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 {
   enum class SourceFlag : uint8_t {
     None = 0,
     // Whether current file is a main file rather than a header.
     IsTU = 1 << 0,
     // Whether current file had any uncompilable errors during indexing.

 //
 // It should be built incrementally with collectIncludeStructureCallback().
 // When we build the preamble, we capture and store its include structure along
 // with the preamble data. When we use the preamble, we can copy its
 // IncludeStructure and use another collectIncludeStructureCallback() to fill
 // in any non-preamble inclusions.
 class IncludeStructure {
 public:
+  using File = unsigned;
+
+  llvm::Optional<File> getFile(StringRef Name) const {
+    auto It = NameToIndex.find(Name);
+    if (It == NameToIndex.end() || Name.empty())
+      return llvm::None;
+    return It->second;
+  }
+
+  llvm::ArrayRef<File> getIncludedFiles(File Index) const {
+    auto It = IncludeChildren.find(Index);
+    if (It == IncludeChildren.end())
+      return {};
+    return It->second;
+  }
+
   std::vector<Inclusion> MainFileIncludes;
 
   // Return all transitively reachable files.
   llvm::ArrayRef<std::string> allHeaders() const { return RealPathNames; }
 
   // 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;
+  llvm::StringMap<unsigned> includeDepth(StringRef Name) const;
 
   // This updates IncludeDepth(), but not MainFileIncludes.
   void recordInclude(llvm::StringRef IncludingName,
                      llvm::StringRef IncludedName,
                      llvm::StringRef IncludedRealName);
 
+  using AbstractIncludeGraph = llvm::DenseMap<File, SmallVector<File>>;
+
 private:
+  File getOrCreatefileIndex(llvm::StringRef Name);
+
   // 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.
+  llvm::StringMap<File> NameToIndex;      // Values are file indexes.
   // Maps a file's index to that of the files it includes.
-  llvm::DenseMap<unsigned, llvm::SmallVector<unsigned>> IncludeChildren;
+  AbstractIncludeGraph IncludeChildren;
 };
 
 /// Returns a PPCallback that visits all inclusions in the main file.
 std::unique_ptr<PPCallbacks>
 collectIncludeStructureCallback(const SourceManager &SM, IncludeStructure *Out);
 
 // Calculates insertion edit for including a new header in a file.
 class IncludeInserter {

clang-tools-extra/clangd/Headers.cpp

 collectIncludeStructureCallback(const SourceManager &SM,
                                 IncludeStructure *Out) {
   return std::make_unique<RecordHeaders>(SM, Out);
 }
 
 void IncludeStructure::recordInclude(llvm::StringRef IncludingName,
                                      llvm::StringRef IncludedName,
                                      llvm::StringRef IncludedRealName) {
-  auto Child = fileIndex(IncludedName);
+  auto Child = getOrCreatefileIndex(IncludedName);
   if (!IncludedRealName.empty() && RealPathNames[Child].empty())
     RealPathNames[Child] = std::string(IncludedRealName);
-  auto Parent = fileIndex(IncludingName);
+  auto Parent = getOrCreatefileIndex(IncludingName);
   IncludeChildren[Parent].push_back(Child);
 }
 
-unsigned IncludeStructure::fileIndex(llvm::StringRef Name) {
+IncludeStructure::File
+IncludeStructure::getOrCreatefileIndex(llvm::StringRef Name) {
   auto R = NameToIndex.try_emplace(Name, RealPathNames.size());
   if (R.second)
     RealPathNames.emplace_back();
   return R.first->getValue();
 }
 
-llvm::StringMap<unsigned>
-IncludeStructure::includeDepth(llvm::StringRef Root) const {
+llvm::StringMap<unsigned> IncludeStructure::includeDepth(StringRef Name) const {
   // Include depth 0 is the main file only.
   llvm::StringMap<unsigned> Result;
-  Result[Root] = 0;
+  Result[Name] = 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::DenseSet<IncludeStructure::File> Seen;
+  auto Root = getFile(Name);
+  if (Root) {
+    CurrentLevel.push_back(*Root);
+    Seen.insert(*Root);
+  } else {
+    elog("Can not find the root ({0}) for includeDepth.", Name);
   }
 
   // Each round of BFS traversal finds the next depth level.
   std::vector<unsigned> PreviousLevel;
   for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
     PreviousLevel.clear();
     PreviousLevel.swap(CurrentLevel);
     for (const auto &Parent : PreviousLevel) {
       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;
         }
       }
     }
   }
   return Result;
 }