Explicitly detect recursive response files

[chrisglover]

Summary

Previous detection relied upon an arbitrary hard coded limit of 21 response files, which some code bases were running up against.

The new detection maintains a stack of processing response files and explicitly checks if a newly encountered file is in the current stack. Some bookkeeping data is necessary in order to detect when to pop the stack.

[smeenai]

llvm/lib/Support/CommandLine.cpp

1110 ↗

(On Diff #202635)

Argv.size() can increase, so we could end up potentially popping this off, right? Perhaps something like std::numeric_limits<size_t>::max (or just -1 if you don't feel like being wordy) would be better?

1136 ↗

(On Diff #202635)

Needs to be clang-formatted. You can use git clang-format to format your entire commit. See https://llvm.org/docs/GettingStarted.html#sending-patches

1157 ↗

(On Diff #202635)

@rsp file?

I'd say something like "Increase the end of all active records by the number of newly expanded arguments, minus the response file itself"

llvm/unittests/Support/CommandLineTest.cpp

857 ↗

(On Diff #202635)

Could you expand this test? In particular, we should ensure that we don't have any recursive expansion at all, and we should also test mutual recursion.

[chrisglover]

llvm/lib/Support/CommandLine.cpp

1110 ↗

(On Diff #202635)

If I got this correct, this particular node will never be popped off. There's an assert at the end of the function that checks that the value of this node did indeed expand out to the size of the argument list
assert(Argv.size() == FileStack.back().End);
But, when I think about it, this assert isn't checking any particular post-condition, it's just validating that the algorithm is correct. For this kind of code, which is a bit complex, I feel like this is reasonable choice to defend against future changes, but really it comes down to a philosophical choice that I'm not strongly attached to one way of the other.

1136 ↗

(On Diff #202635)

Ack.

1157 ↗

(On Diff #202635)

Fair. I'll use this wording.

llvm/unittests/Support/CommandLineTest.cpp

857 ↗

(On Diff #202635)

Good point, especially the mutual recursion. I'll add that.

[chrisglover]

• Reworded comment based on review feedback
• Updated unit test to explicitly ensure we never expand recursive response files
• Ran git clang-format

[chrisglover]

• Added one more test to make sure non-recursive, but repeated response files continue to work.

[jyknight]

I like it. Some minor suggestions for a few extra comments, but other than that LGTM.

llvm/lib/Support/CommandLine.cpp

1106 ↗

(On Diff #203064)

Could use a comment as to what this represents -- the position of the last argument that came (including recursively) from the named file.

1114 ↗

(On Diff #203064)

Also can use a comment -- drop any files from the stack if we've finished their arguments.

1167 ↗

(On Diff #203064)

Worth putting a comment here as to why this is the case.

[smeenai]

llvm/lib/Support/CommandLine.cpp

1167 ↗

(On Diff #203064)

Yeah, this would address the confusion I had :)

1110 ↗

(On Diff #202635)

Yeah, I understand now. I forgot to account for the dummy entry also having its End incremented in the loop below.

[chrisglover]

llvm/lib/Support/CommandLine.cpp

1106 ↗

(On Diff #203064)

How about

// To detect recursive response files, we maintain a stack of files and the
// position of the last argument in the file. This position is
// updated dynamically as we recursively expand files.

1114 ↗

(On Diff #203064)

How about

  
// Passing the end of a file's argument list, so we can remove it from the
// stack.

1167 ↗

(On Diff #203064)

Does this make sense? Too wordy?

// If successful, the top of the file stack will mark the end of the Argv
// stream. A failure here indicates a bug in the stack popping logic above.
// Note that FileStack may have more than one element at this point because we
// don't have a chance to pop the stack when encountering recursive files at
// the end of the stream, so seeing that doesn't indicate a bug.

[jyknight]

Comment updates SGTM.

llvm/lib/Support/CommandLine.cpp

1167 ↗

(On Diff #203064)

SGTM. Probably worth changing the assert to also check size > 0:
assert(FileStack.size() > 0 && Argv.size() == FileStack.back().End);

[chrisglover]

• Added FileStack.size() > 0 check in assert at end of function.

[chrisglover]

If this looks good, someone else will need to commit as I don't have commit access.

[chrisglover]

Ping

[smeenai]

Sorry, I thought James was gonna commit this, but I'll go ahead and do so.

llvm/trunk/lib/Support/CommandLine.cpp

static bool ExpandResponseFile(StringRef FName, StringSaver &Saver,
   return true;
 }
 
 /// Expand response files on a command line recursively using the given
 /// StringSaver and tokenization strategy.
 bool cl::ExpandResponseFiles(StringSaver &Saver, TokenizerCallback Tokenizer,
                              SmallVectorImpl<const char *> &Argv,
                              bool MarkEOLs, bool RelativeNames) {
-  unsigned ExpandedRspFiles = 0;
   bool AllExpanded = true;
+  struct ResponseFileRecord {
+    const char *File;
+    size_t End;
+  };
+
+  // To detect recursive response files, we maintain a stack of files and the
+  // position of the last argument in the file. This position is updated
+  // dynamically as we recursively expand files.
+  SmallVector<ResponseFileRecord, 3> FileStack;
+
+  // Push a dummy entry that represents the initial command line, removing
+  // the need to check for an empty list.
+  FileStack.push_back({"", Argv.size()});
 
   // Don't cache Argv.size() because it can change.
   for (unsigned I = 0; I != Argv.size();) {
+    while (I == FileStack.back().End) {
+      // Passing the end of a file's argument list, so we can remove it from the
+      // stack.
+      FileStack.pop_back();
+    }
+
     const char *Arg = Argv[I];
     // Check if it is an EOL marker
     if (Arg == nullptr) {
       ++I;
       continue;
     }
+
     if (Arg[0] != '@') {
       ++I;
       continue;
     }
 
-    // If we have too many response files, leave some unexpanded.  This avoids
-    // crashing on self-referential response files.
-    if (ExpandedRspFiles > 20)
-      return false;
+    const char *FName = Arg + 1;
+    auto IsEquivalent = [FName](const ResponseFileRecord &RFile) {
+      return sys::fs::equivalent(RFile.File, FName);
+    };
+
+    // Check for recursive response files.
+    if (std::any_of(FileStack.begin() + 1, FileStack.end(), IsEquivalent)) {
+      // This file is recursive, so we leave it in the argument stream and
+      // move on.
+      AllExpanded = false;
+      ++I;
+      continue;
+    }
 
     // Replace this response file argument with the tokenization of its
     // contents.  Nested response files are expanded in subsequent iterations.
     SmallVector<const char *, 0> ExpandedArgv;
-    if (ExpandResponseFile(Arg + 1, Saver, Tokenizer, ExpandedArgv, MarkEOLs,
+    if (!ExpandResponseFile(FName, Saver, Tokenizer, ExpandedArgv, MarkEOLs,
                             RelativeNames)) {
-      ++ExpandedRspFiles;
-    } else {
       // We couldn't read this file, so we leave it in the argument stream and
       // move on.
       AllExpanded = false;
       ++I;
       continue;
     }
+
+    for (ResponseFileRecord &Record : FileStack) {
+      // Increase the end of all active records by the number of newly expanded
+      // arguments, minus the response file itself.
+      Record.End += ExpandedArgv.size() - 1;
+    }
+
+    FileStack.push_back({FName, I + ExpandedArgv.size()});
     Argv.erase(Argv.begin() + I);
     Argv.insert(Argv.begin() + I, ExpandedArgv.begin(), ExpandedArgv.end());
   }
+
+  // If successful, the top of the file stack will mark the end of the Argv
+  // stream. A failure here indicates a bug in the stack popping logic above.
+  // Note that FileStack may have more than one element at this point because we
+  // don't have a chance to pop the stack when encountering recursive files at
+  // the end of the stream, so seeing that doesn't indicate a bug.
+  assert(FileStack.size() > 0 && Argv.size() == FileStack.back().End);
   return AllExpanded;
 }
 
 bool cl::readConfigFile(StringRef CfgFile, StringSaver &Saver,
                         SmallVectorImpl<const char *> &Argv) {
   if (!ExpandResponseFile(CfgFile, Saver, cl::tokenizeConfigFile, Argv,
                           /*MarkEOLs*/ false, /*RelativeNames*/ true))
     return false;

llvm/trunk/unittests/Support/CommandLineTest.cpp

TEST(CommandLineTest, ResponseFiles) {
 
   // Create included response file of first level.
   llvm::SmallString<128> IncludedFileName;
   llvm::sys::path::append(IncludedFileName, TestDir, "resp1");
   std::ofstream IncludedFile(IncludedFileName.c_str());
   EXPECT_TRUE(IncludedFile.is_open());
   IncludedFile << "-option_1 -option_2\n"
                   "@incdir/resp2\n"
-                  "-option_3=abcd\n";
+                  "-option_3=abcd\n"
+                  "@incdir/resp3\n"
+                  "-option_4=efjk\n";
   IncludedFile.close();
 
   // Directory for included file.
   llvm::SmallString<128> IncDir;
   llvm::sys::path::append(IncDir, TestDir, "incdir");
   EC = llvm::sys::fs::create_directory(IncDir);
   EXPECT_TRUE(!EC);
 
   // Create included response file of second level.
   llvm::SmallString<128> IncludedFileName2;
   llvm::sys::path::append(IncludedFileName2, IncDir, "resp2");
   std::ofstream IncludedFile2(IncludedFileName2.c_str());
   EXPECT_TRUE(IncludedFile2.is_open());
   IncludedFile2 << "-option_21 -option_22\n";
   IncludedFile2 << "-option_23=abcd\n";
   IncludedFile2.close();
 
+  // Create second included response file of second level.
+  llvm::SmallString<128> IncludedFileName3;
+  llvm::sys::path::append(IncludedFileName3, IncDir, "resp3");
+  std::ofstream IncludedFile3(IncludedFileName3.c_str());
+  EXPECT_TRUE(IncludedFile3.is_open());
+  IncludedFile3 << "-option_31 -option_32\n";
+  IncludedFile3 << "-option_33=abcd\n";
+  IncludedFile3.close();
+
   // Prepare 'file' with reference to response file.
   SmallString<128> IncRef;
   IncRef.append(1, '@');
   IncRef.append(IncludedFileName.c_str());
   llvm::SmallVector<const char *, 4> Argv =
                           { "test/test", "-flag_1", IncRef.c_str(), "-flag_2" };
 
   // Expand response files.
   llvm::BumpPtrAllocator A;
   llvm::StringSaver Saver(A);
   bool Res = llvm::cl::ExpandResponseFiles(
                     Saver, llvm::cl::TokenizeGNUCommandLine, Argv, false, true);
   EXPECT_TRUE(Res);
-  EXPECT_EQ(Argv.size(), 9U);
+  EXPECT_EQ(Argv.size(), 13U);
   EXPECT_STREQ(Argv[0], "test/test");
   EXPECT_STREQ(Argv[1], "-flag_1");
   EXPECT_STREQ(Argv[2], "-option_1");
   EXPECT_STREQ(Argv[3], "-option_2");
   EXPECT_STREQ(Argv[4], "-option_21");
   EXPECT_STREQ(Argv[5], "-option_22");
   EXPECT_STREQ(Argv[6], "-option_23=abcd");
   EXPECT_STREQ(Argv[7], "-option_3=abcd");
-  EXPECT_STREQ(Argv[8], "-flag_2");
+  EXPECT_STREQ(Argv[8], "-option_31");
+  EXPECT_STREQ(Argv[9], "-option_32");
+  EXPECT_STREQ(Argv[10], "-option_33=abcd");
+  EXPECT_STREQ(Argv[11], "-option_4=efjk");
+  EXPECT_STREQ(Argv[12], "-flag_2");
 
+  llvm::sys::fs::remove(IncludedFileName3);
   llvm::sys::fs::remove(IncludedFileName2);
   llvm::sys::fs::remove(IncDir);
   llvm::sys::fs::remove(IncludedFileName);
   llvm::sys::fs::remove(TestDir);
 }
 
 TEST(CommandLineTest, RecursiveResponseFiles) {
   SmallString<128> TestDir;
   std::error_code EC = sys::fs::createUniqueDirectory("unittest", TestDir);
   EXPECT_TRUE(!EC);
 
-  SmallString<128> ResponseFilePath;
-  sys::path::append(ResponseFilePath, TestDir, "recursive.rsp");
-  std::string ResponseFileRef = std::string("@") + ResponseFilePath.c_str();
-
-  std::ofstream ResponseFile(ResponseFilePath.str());
-  EXPECT_TRUE(ResponseFile.is_open());
-  ResponseFile << ResponseFileRef << "\n";
-  ResponseFile << ResponseFileRef << "\n";
-  ResponseFile.close();
-
-  // Ensure the recursive expansion terminates.
-  SmallVector<const char *, 4> Argv = {"test/test", ResponseFileRef.c_str()};
+  SmallString<128> SelfFilePath;
+  sys::path::append(SelfFilePath, TestDir, "self.rsp");
+  std::string SelfFileRef = std::string("@") + SelfFilePath.c_str();
+
+  SmallString<128> NestedFilePath;
+  sys::path::append(NestedFilePath, TestDir, "nested.rsp");
+  std::string NestedFileRef = std::string("@") + NestedFilePath.c_str();
+
+  SmallString<128> FlagFilePath;
+  sys::path::append(FlagFilePath, TestDir, "flag.rsp");
+  std::string FlagFileRef = std::string("@") + FlagFilePath.c_str();
+
+  std::ofstream SelfFile(SelfFilePath.str());
+  EXPECT_TRUE(SelfFile.is_open());
+  SelfFile << "-option_1\n";
+  SelfFile << FlagFileRef << "\n";
+  SelfFile << NestedFileRef << "\n";
+  SelfFile << SelfFileRef << "\n";
+  SelfFile.close();
+
+  std::ofstream NestedFile(NestedFilePath.str());
+  EXPECT_TRUE(NestedFile.is_open());
+  NestedFile << "-option_2\n";
+  NestedFile << FlagFileRef << "\n";
+  NestedFile << SelfFileRef << "\n";
+  NestedFile << NestedFileRef << "\n";
+  NestedFile.close();
+
+  std::ofstream FlagFile(FlagFilePath.str());
+  EXPECT_TRUE(FlagFile.is_open());
+  FlagFile << "-option_x\n";
+  FlagFile.close();
+
+  // Ensure:
+  // Recursive expansion terminates
+  // Recursive files never expand
+  // Non-recursive repeats are allowed
+  SmallVector<const char *, 4> Argv = {"test/test", SelfFileRef.c_str(),
+                                       "-option_3"};
   BumpPtrAllocator A;
   StringSaver Saver(A);
 #ifdef _WIN32
   cl::TokenizerCallback Tokenizer = cl::TokenizeWindowsCommandLine;
 #else
   cl::TokenizerCallback Tokenizer = cl::TokenizeGNUCommandLine;
 #endif
   bool Res = cl::ExpandResponseFiles(Saver, Tokenizer, Argv, false, false);
   EXPECT_FALSE(Res);
 
-  // Ensure some expansion took place.
-  EXPECT_GT(Argv.size(), 2U);
+  EXPECT_EQ(Argv.size(), 9U);
   EXPECT_STREQ(Argv[0], "test/test");
-  for (size_t i = 1; i < Argv.size(); ++i)
-    EXPECT_STREQ(Argv[i], ResponseFileRef.c_str());
+  EXPECT_STREQ(Argv[1], "-option_1");
+  EXPECT_STREQ(Argv[2], "-option_x");
+  EXPECT_STREQ(Argv[3], "-option_2");
+  EXPECT_STREQ(Argv[4], "-option_x");
+  EXPECT_STREQ(Argv[5], SelfFileRef.c_str());
+  EXPECT_STREQ(Argv[6], NestedFileRef.c_str());
+  EXPECT_STREQ(Argv[7], SelfFileRef.c_str());
+  EXPECT_STREQ(Argv[8], "-option_3");
 }
 
 TEST(CommandLineTest, ResponseFilesAtArguments) {
   SmallString<128> TestDir;
   std::error_code EC = sys::fs::createUniqueDirectory("unittest", TestDir);
   EXPECT_TRUE(!EC);
 
   SmallString<128> ResponseFilePath;