[clang][lex] Ensure minimizer output is never larger than input

[jansvoboda11]

Summary

This patch ensures the output of source minimizer is never larger than the input. This property will be handy in a follow up patch that makes it possible to pad the minimized output to the size of the original input.

[jansvoboda11]

Fix assert wording

[dexonsmith]

This patch ensures the output of source minimizer is never larger than the input. This property will be handy in a follow up patch that makes it possible to pad the minimized output to the size of the original input.

I suppose when I wrote first wrote this I was thinking of a secondary purpose of canonicalizing the sources; in which case, adding a trailing newline (for example) seems like feature rather than a bug. I'm not too attached to that, but I am curious for more context about why it's important to be able to pad the file to the same size, and whether that indicates a bug that should be fixed somewhere else instead. (I'll read the follow-up patches in the stack...)

clang/unittests/Lex/DependencyDirectivesSourceMinimizerTest.cpp

149

I'm not comfortable with this change... the idea of the (/*invalid*/ was to guarantee that an invalid macro argument list didn't get minimized to something valid.

Perhaps the result could be "#define MACRO(\n", and just strip the comment?

[dexonsmith]

Another thing to consider: a client that wants the minimized source to be "no bigger than" the original source can use the original source if it ends up growing. For example, https://reviews.llvm.org/D104462 could check the resulting size, and just return the original source in the (extremely unlikely?) corner case where the minimized sources are bigger.

In that case, we wouldn't need this patch's assertion.

I bet some of these changes are good to do anyway (like dropping the /*invalid*/ comment, which was useful as a canary-in-the-coal-mine when testing the prototype on large bodies of sources (and maybe has outlived its usefulness)), but you could skip the fiddly changes here that complicate the logic and make the output less canonical and harder to read, like "maintain 0 whitespace after macro names" and "maintain missing newline at EOF".

clang/lib/Lex/DependencyDirectivesSourceMinimizer.cpp

private:
 
   void printToNewline(const char *&First, const char *const End);
   void printAdjacentModuleNameParts(const char *&First, const char *const End);
   LLVM_NODISCARD bool printAtImportBody(const char *&First,
                                         const char *const End);
   void printDirectiveBody(const char *&First, const char *const End);
   void printAdjacentMacroArgs(const char *&First, const char *const End);
   LLVM_NODISCARD bool printMacroArgs(const char *&First, const char *const End);
+  void maybePrintNewLine(const char *&Last, const char *const End);
 
   /// Reports a diagnostic if the diagnostic engine is provided. Always returns
   /// true at the end.
   bool reportError(const char *CurPtr, unsigned Err);
 
   StringMap<char> SplitIds;
   StringRef Input;
   DiagnosticsEngine *Diags;
append(First, findFirstTrailingSpace(
                       First, LastBeforeTrailingSpace - 1));
 
     First = Last;
     skipNewline(First, End);
     skipOverSpaces(First, End);
   }
 }
 
-static void skipWhitespace(const char *&First, const char *const End) {
+static size_t skipWhitespace(const char *&First, const char *const End) {
+  const char *FirstBefore = First;
+
   for (;;) {
     assert(First <= End);
     skipOverSpaces(First, End);
 
     if (End - First < 2)
-      return;
+      break;
 
     if (First[0] == '\\' && isVerticalWhitespace(First[1])) {
       skipNewline(++First, End);
       continue;
     }
 
     // Check for a non-comment character.
     if (First[0] != '/')
-      return;
+      break;
 
     // "// ...".
     if (First[1] == '/') {
       skipLineComment(First, End);
-      return;
+      break;
     }
 
     // Cannot be a comment.
     if (First[1] != '*')
-      return;
+      break;
 
     // "/*...*/".
     skipBlockComment(First, End);
   }
+
+  return First - FirstBefore;
 }
 
 void Minimizer::printAdjacentModuleNameParts(const char *&First,
                                              const char *const End) {
   // Skip over parts of the body.
   const char *Last = First;
   do
     ++Last;
bool Minimizer::printAtImportBody(const char *&First, const char *const End) {
   }
 }
 
 void Minimizer::printDirectiveBody(const char *&First, const char *const End) {
   skipWhitespace(First, End); // Skip initial whitespace.
   printToNewline(First, End);
   while (Out.back() == ' ')
     Out.pop_back();
-  put('\n');
+  maybePrintNewLine(First, End);
 }
 
 LLVM_NODISCARD static const char *lexRawIdentifier(const char *First,
                                                    const char *const End) {
   assert(isIdentifierBody(*First) && "invalid identifer");
   const char *Last = First + 1;
   while (Last != End && isIdentifierBody(*Last))
     ++Last;
for (;;) {
     // This is intentionally fairly liberal.
     if (!(isIdentifierBody(*First) || *First == '.' || *First == ','))
       return true;
 
     printAdjacentMacroArgs(First, End);
   }
 }
 
+void Minimizer::maybePrintNewLine(const char *&Last, const char *const End) {
+  // Only print newline if doing so won't make the output larger than the input.
+  if (Last != End)
+    put('\n');
+}
+
 /// Looks for an identifier starting from Last.
 ///
 /// Updates "First" to just past the next identifier, if any.  Returns true iff
 /// the identifier matches "Id".
 bool Minimizer::isNextIdentifier(StringRef Id, const char *&First,
                                  const char *const End) {
   skipWhitespace(First, End);
   if (First == End || !isIdentifierHead(*First))
bool Minimizer::lexDefine(const char *&First, const char *const End) {
   if (Last == End)
     return false;
   if (*Last == '(') {
     size_t Size = Out.size();
     if (printMacroArgs(Last, End)) {
       // Be robust to bad macro arguments, since they can show up in disabled
       // code.
       Out.resize(Size);
-      append("(/* invalid */\n");
+      maybePrintNewLine(Last, End);
       skipLine(Last, End);
       return false;
     }
   }
-  skipWhitespace(Last, End);
+  size_t WhitespaceLength = skipWhitespace(Last, End);
   if (Last == End)
     return false;
-  if (!isVerticalWhitespace(*Last))
+  // Only print space if we actually skipped some whitespace. This prevents
+  // making the output larger than the input.
+  if (WhitespaceLength > 0 && !isVerticalWhitespace(*Last))
     put(' ');
   printDirectiveBody(Last, End);
   First = Last;
   return false;
 }
 
 bool Minimizer::lexPragma(const char *&First, const char *const End) {
   // #pragma.
while (First != End)
     if (lexPPLine(First, End))
       return true;
   return false;
 }
 
 bool Minimizer::minimize() {
   bool Error = minimizeImpl(Input.begin(), Input.end());
 
+  assert(Out.size() <= Input.size() && "Output is not larger than input");
+
   if (!Error) {
-    // Add a trailing newline and an EOF on success.
-    if (!Out.empty() && Out.back() != '\n')
+    // Add a trailing newline if it won't make the output larger than the input.
+    if (!Out.empty() && Out.back() != '\n' && Out.size() < Input.size())
       Out.push_back('\n');
     makeToken(pp_eof);
   }
 
   // Null-terminate the output. This way the memory buffer that's passed to
   // Clang will not have to worry about the terminating '\0'.
   Out.push_back(0);
   Out.pop_back();

clang/unittests/Lex/DependencyDirectivesSourceMinimizerTest.cpp

 }
 
 TEST(MinimizeSourceToDependencyDirectivesTest, Define) {
   SmallVector<char, 128> Out;
   SmallVector<Token, 4> Tokens;
 
   ASSERT_FALSE(
       minimizeSourceToDependencyDirectives("#define MACRO", Out, Tokens));
-  EXPECT_STREQ("#define MACRO\n", Out.data());
+  EXPECT_STREQ("#define MACRO", Out.data());
   ASSERT_EQ(2u, Tokens.size());
   ASSERT_EQ(pp_define, Tokens.front().K);
 }
 
 TEST(MinimizeSourceToDependencyDirectivesTest, DefineSpacing) {
   SmallVector<char, 128> Out;
 
   ASSERT_FALSE(
ASSERT_FALSE(
       minimizeSourceToDependencyDirectives("#define   MACRO\n\n\n", Out));
   EXPECT_STREQ("#define MACRO\n", Out.data());
 }
 
 TEST(MinimizeSourceToDependencyDirectivesTest, DefineMacroArguments) {
   SmallVector<char, 128> Out;
 
   ASSERT_FALSE(minimizeSourceToDependencyDirectives("#define MACRO()", Out));
-  EXPECT_STREQ("#define MACRO()\n", Out.data());
+  EXPECT_STREQ("#define MACRO()", Out.data());
 
   ASSERT_FALSE(
       minimizeSourceToDependencyDirectives("#define MACRO(a, b...)", Out));
   EXPECT_STREQ("#define MACRO(a,b...)\n", Out.data());
 
   ASSERT_FALSE(
       minimizeSourceToDependencyDirectives("#define MACRO content", Out));
-  EXPECT_STREQ("#define MACRO content\n", Out.data());
+  EXPECT_STREQ("#define MACRO content", Out.data());
 
   ASSERT_FALSE(minimizeSourceToDependencyDirectives(
       "#define MACRO   con  tent   ", Out));
   EXPECT_STREQ("#define MACRO con  tent\n", Out.data());
 
   ASSERT_FALSE(minimizeSourceToDependencyDirectives(
       "#define MACRO()   con  tent   ", Out));
   EXPECT_STREQ("#define MACRO() con  tent\n", Out.data());
 }
 
 TEST(MinimizeSourceToDependencyDirectivesTest, DefineInvalidMacroArguments) {
   SmallVector<char, 128> Out;
 
   ASSERT_FALSE(minimizeSourceToDependencyDirectives("#define MACRO((a))", Out));
-  EXPECT_STREQ("#define MACRO(/* invalid */\n", Out.data());
+  EXPECT_STREQ("#define MACRO\n", Out.data());
 
   ASSERT_FALSE(minimizeSourceToDependencyDirectives("#define MACRO(", Out));
-  EXPECT_STREQ("#define MACRO(/* invalid */\n", Out.data());
+  EXPECT_STREQ("#define MACRO\n", Out.data());
 
   ASSERT_FALSE(
       minimizeSourceToDependencyDirectives("#define MACRO(a * b)", Out));
-  EXPECT_STREQ("#define MACRO(/* invalid */\n", Out.data());
+  EXPECT_STREQ("#define MACRO\n", Out.data());
 }
 
 TEST(MinimizeSourceToDependencyDirectivesTest, DefineHorizontalWhitespace) {
   SmallVector<char, 128> Out;
 
   ASSERT_FALSE(minimizeSourceToDependencyDirectives(
       "#define MACRO(\t)\tcon \t tent\t", Out));
   EXPECT_STREQ("#define MACRO() con \t tent\n", Out.data());
TEST(MinimizeSourceToDependencyDirectivesTest, DefineNoName) {
 
   ASSERT_TRUE(minimizeSourceToDependencyDirectives("#define &\n", Out));
 }
 
 TEST(MinimizeSourceToDependencyDirectivesTest, DefineNoWhitespace) {
   SmallVector<char, 128> Out;
 
   ASSERT_FALSE(minimizeSourceToDependencyDirectives("#define AND&\n", Out));
-  EXPECT_STREQ("#define AND &\n", Out.data());
+  EXPECT_STREQ("#define AND&\n", Out.data());
 
   ASSERT_FALSE(minimizeSourceToDependencyDirectives("#define AND\\\n"
                                                     "&\n",
                                                     Out));
   EXPECT_STREQ("#define AND &\n", Out.data());
 }
 
 TEST(MinimizeSourceToDependencyDirectivesTest, MultilineComment) {