[clangd] Fix a reference invalidation

[kadircet]

Summary

Fix for the breakage in http://green.lab.llvm.org/green/job/clang-stage1-configure-RA/52811/consoleFull#-42777206a1ca8a51-895e-46c6-af87-ce24fa4cd561

[ilya-biryukov]

clangd/index/Background.cpp

521

We should avoid modifying the container we're iterating over instead.
I suggest we separate the queue and the return value into two separate vectors.

We would pop() from the queue and push() to the result vector, therefore making bugs like this impossible.

[kadircet]

• Change traversal logic to use two different containers

[ilya-biryukov]

clangd/index/Background.cpp

488

This reference makes it just as easy to access the vector we'll be modifying inside the loop.
Can we avoid modifying the values inside the vector completely? I.e. ideally we'll have only push_back into the vector and no modifications of the internal references?

[ilya-biryukov]

clangd/index/Background.cpp

488

Ah, but we don't modify the vector anymore.
Could you leave a comment that Dependencies is not modified further in the loop body, so it's fine to have a reference inside it?

[ilya-biryukov]

LGTM, but please add a comment the vector is not modified (it might be useful as a reminder in case we want to change the code later)

[kadircet]

• Add a comment

clangd/index/Background.cpp

BackgroundIndex::loadShard(const tooling::CompileCommand &Cmd,
   std::vector<ShardInfo> IntermediateSymbols;
   // Make sure we don't have duplicate elements in the queue. Keys are absolute
   // paths.
   llvm::StringSet<> InQueue;
   auto FS = FSProvider.getFileSystem();
   // Dependencies of this TU, paired with the information about whether they
   // need to be re-indexed or not.
   std::vector<Source> Dependencies;
+  std::queue<Source> ToVisit;
   std::string AbsolutePath = getAbsolutePath(Cmd).str();
   // Up until we load the shard related to a dependency it needs to be
   // re-indexed.
-  Dependencies.emplace_back(AbsolutePath, true);
+  ToVisit.emplace(AbsolutePath, true);
   InQueue.insert(AbsolutePath);
   // Goes over each dependency.
-  for (size_t CurrentDependency = 0; CurrentDependency < Dependencies.size();
-       CurrentDependency++) {
-    llvm::StringRef CurDependencyPath = Dependencies[CurrentDependency].Path;
+  while (!ToVisit.empty()) {
+    Dependencies.push_back(std::move(ToVisit.front()));
+    // Dependencies is not modified during the rest of the loop, so it is safe
+    // to keep the reference.
+    auto &CurDependency = Dependencies.back();
+    ToVisit.pop();
     // If we have already seen this shard before(either loaded or failed) don't
     // re-try again. Since the information in the shard won't change from one TU
     // to another.
-    if (!LoadedShards.try_emplace(CurDependencyPath).second) {
+    if (!LoadedShards.try_emplace(CurDependency.Path).second) {
       // If the dependency needs to be re-indexed, first occurence would already
       // have detected that, so we don't need to issue it again.
-      Dependencies[CurrentDependency].NeedsReIndexing = false;
+      CurDependency.NeedsReIndexing = false;
       continue;
     }
 
-    auto Shard = IndexStorage->loadShard(CurDependencyPath);
+    auto Shard = IndexStorage->loadShard(CurDependency.Path);
     if (!Shard || !Shard->Sources) {
       // File will be returned as requiring re-indexing to caller.
-      vlog("Failed to load shard: {0}", CurDependencyPath);
+      vlog("Failed to load shard: {0}", CurDependency.Path);
       continue;
     }
     // These are the edges in the include graph for current dependency.
     for (const auto &I : *Shard->Sources) {
       auto U = URI::parse(I.getKey());
       if (!U)
         continue;
-      auto AbsolutePath = URI::resolve(*U, CurDependencyPath);
+      auto AbsolutePath = URI::resolve(*U, CurDependency.Path);
       if (!AbsolutePath)
         continue;
       // Add file as dependency if haven't seen before.
       if (InQueue.try_emplace(*AbsolutePath).second)
-        Dependencies.emplace_back(*AbsolutePath, true);
+        ToVisit.emplace(*AbsolutePath, true);
       // The node contains symbol information only for current file, the rest is
       // just edges.
-      if (*AbsolutePath != CurDependencyPath)
+      if (*AbsolutePath != CurDependency.Path)
         continue;
 
       // We found source file info for current dependency.
       assert(I.getValue().Digest != FileDigest{{0}} && "Digest is empty?");
       ShardInfo SI;
-      SI.AbsolutePath = CurDependencyPath;
+      SI.AbsolutePath = CurDependency.Path;
       SI.Shard = std::move(Shard);
       SI.Digest = I.getValue().Digest;
       IntermediateSymbols.push_back(std::move(SI));
       // Check if the source needs re-indexing.
       // Get the digest, skip it if file doesn't exist.
-      auto Buf = FS->getBufferForFile(CurDependencyPath);
+      auto Buf = FS->getBufferForFile(CurDependency.Path);
       if (!Buf) {
-        elog("Couldn't get buffer for file: {0}: {1}", CurDependencyPath,
+        elog("Couldn't get buffer for file: {0}: {1}", CurDependency.Path,
              Buf.getError().message());
         continue;
       }
       // If digests match then dependency doesn't need re-indexing.
-      Dependencies[CurrentDependency].NeedsReIndexing =
+      CurDependency.NeedsReIndexing =
           digest(Buf->get()->getBuffer()) != I.getValue().Digest;
     }
   }
   // Load shard information into background-index.
   {
     std::lock_guard<std::mutex> Lock(DigestsMu);
     // This can override a newer version that is added in another thread,
     // if this thread sees the older version but finishes later. This