[LLVM] Fix handling of escaped closing brace `}` in `formatv` (under an option)

[jurahul]

Summary

• formatv was not handling closing braces as documented and treating them as unescaped. This also means that cases like "{{}}" would, post-formatting, be "{}}" which is not correct per the documented behavior.
• Fix the string parsing and analysis code to treat closing braces as requiring escape and assert of we find a closing brace not paired with an opening one.
• Unfortunately, many tests and code rely on the existing behavior, so introduce a FormatEscapeMode enum to switch between existing (legacy) and new (strict) mode. Also added a formatv_strict() function corresponding to the standalone formatv() function.
• Update some existing unit tests that to use strict mode.

[jurahul]

I ran into this issue when trying to attach default values to a parameter in the code generated by TableGen, which uses formatv(). Adding just {} does not work, so I thought {{}} should work based on the comments, but the code does not handle this. When testing, I found that there is a lot of existing code and tests that rely on this current (legacy) behavior, so decided to only enable the new mode optionally. Ideally, we should get rid of the legacy behavior, but it seems there are too many tests to fix (in clang, clangd etc), so I am not handling that with this change.

[sammccall]

I'm sympathetic to wanting to clean this up, but having two modes without a plan to remove one doesn't seem ideal.

What do you think about adjusting the documentation to describe the actual behaviour instead? It doesn't seem unreasonable - it requires { to be doubled but not }, and there's no ambiguity because } cannot appear inside a replacement sequence therefore must close one.

[jurahul]

That's a reasonable course of action as well. I could look into fixing all the in-tree uses of formatv() to conform to the strict mode, but I do have concern about out-of-tree uses breaking with this and leading to unnecessary API churn, so for that purpose we would potentially need to keep the legacy mode. So overall, I think updating the documentation seems reasonable. I'll update the review for that.

[jurahul]

Abandoning this one, will start a new one for the documentation changes and some simplification to the code as well.

[sammccall]

Thanks. I do think the strict behavior you describe here is a little bit better, but it's really hard to completely get there (not least because format strings often aren't tested...).
Formalizing the existing behavior is better than the halfway state.

llvm/include/llvm/Support/FormatVariadic.h

 #include <string>
 #include <tuple>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 enum class ReplacementType { Empty, Format, Literal };
+enum class FormatEscapeMode { Legacy, Strict };
 
 struct ReplacementItem {
   ReplacementItem() = default;
   explicit ReplacementItem(StringRef Literal)
       : Type(ReplacementType::Literal), Spec(Literal) {}
   ReplacementItem(StringRef Spec, size_t Index, size_t Align, AlignStyle Where,
                   char Pad, StringRef Options)
       : Type(ReplacementType::Format), Spec(Spec), Index(Index), Align(Align),
         Where(Where), Pad(Pad), Options(Options) {}
 
   ReplacementType Type = ReplacementType::Empty;
   StringRef Spec;
   size_t Index = 0;
   size_t Align = 0;
   AlignStyle Where = AlignStyle::Right;
   char Pad = 0;
   StringRef Options;
 };
 
 class formatv_object_base {
 protected:
   StringRef Fmt;
   ArrayRef<detail::format_adapter *> Adapters;
+  FormatEscapeMode EscapeMode;
 
   static bool consumeFieldLayout(StringRef &Spec, AlignStyle &Where,
                                  size_t &Align, char &Pad);
 
   static std::pair<ReplacementItem, StringRef>
-  splitLiteralAndReplacement(StringRef Fmt);
+  splitLiteralAndReplacement(StringRef Fmt, FormatEscapeMode EscapeMode);
 
   formatv_object_base(StringRef Fmt,
-                      ArrayRef<detail::format_adapter *> Adapters)
-      : Fmt(Fmt), Adapters(Adapters) {}
+                      ArrayRef<detail::format_adapter *> Adapters,
+                      FormatEscapeMode EscapeMode = FormatEscapeMode::Legacy)
+      : Fmt(Fmt), Adapters(Adapters), EscapeMode(EscapeMode) {}
 
   formatv_object_base(formatv_object_base const &rhs) = delete;
   formatv_object_base(formatv_object_base &&rhs) = default;
 
 public:
   void format(raw_ostream &S) const {
-    for (auto &R : parseFormatString(Fmt)) {
+    for (auto &R : parseFormatString(Fmt, EscapeMode)) {
       if (R.Type == ReplacementType::Empty)
         continue;
       if (R.Type == ReplacementType::Literal) {
         S << R.Spec;
         continue;
       }
       if (R.Index >= Adapters.size()) {
         S << R.Spec;
         continue;
       }
 
       auto W = Adapters[R.Index];
 
       FmtAlign Align(*W, R.Where, R.Align, R.Pad);
       Align.format(S, R.Options);
     }
   }
-  static SmallVector<ReplacementItem, 2> parseFormatString(StringRef Fmt);
+  static SmallVector<ReplacementItem, 2>
+  parseFormatString(StringRef Fmt,
+                    FormatEscapeMode EscapeMode = FormatEscapeMode::Legacy);
 
   static Optional<ReplacementItem> parseReplacementItem(StringRef Spec);
 
   std::string str() const {
     std::string Result;
     raw_string_ostream Stream(Result);
     Stream << *this;
     Stream.flush();
struct create_adapters {
     template <typename... Ts>
     std::array<detail::format_adapter *, std::tuple_size<Tuple>::value>
     operator()(Ts &... Items) {
       return {{&Items...}};
     }
   };
 
 public:
-  formatv_object(StringRef Fmt, Tuple &&Params)
-      : formatv_object_base(Fmt, ParameterPointers),
+  formatv_object(StringRef Fmt, Tuple &&Params,
+                 FormatEscapeMode EscapeMode = FormatEscapeMode::Legacy)
+      : formatv_object_base(Fmt, ParameterPointers, EscapeMode),
         Parameters(std::move(Params)) {
     ParameterPointers = apply_tuple(create_adapters(), Parameters);
   }
 
   formatv_object(formatv_object const &rhs) = delete;
 
   formatv_object(formatv_object &&rhs)
       : formatv_object_base(std::move(rhs)),

 //
 // ===Invalid Format String Handling===
 //
 // In the case of a format string which does not match the grammar described
 // above, the output is undefined.  With asserts enabled, LLVM will trigger an
 // assertion.  Otherwise, it will try to do something reasonable, but in general
 // the details of what that is are undefined.
 //
+namespace detail {
+
 template <typename... Ts>
-inline auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object<decltype(
-    std::make_tuple(detail::build_format_adapter(std::forward<Ts>(Vals))...))> {
+inline auto formatv_impl(const char *Fmt, FormatEscapeMode EscapeMode,
+                         Ts &&... Vals)
+    -> formatv_object<decltype(std::make_tuple(
+        detail::build_format_adapter(std::forward<Ts>(Vals))...))> {
   using ParamTuple = decltype(
       std::make_tuple(detail::build_format_adapter(std::forward<Ts>(Vals))...));
   return formatv_object<ParamTuple>(
       Fmt,
-      std::make_tuple(detail::build_format_adapter(std::forward<Ts>(Vals))...));
+      std::make_tuple(detail::build_format_adapter(std::forward<Ts>(Vals))...),
+      EscapeMode);
+}
+
+} // end namespace detail
+
+template <typename... Ts>
+inline auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object<decltype(
+    std::make_tuple(detail::build_format_adapter(std::forward<Ts>(Vals))...))> {
+  return detail::formatv_impl(Fmt, FormatEscapeMode::Legacy,
+                              std::forward<Ts>(Vals)...);
+}
+
+template <typename... Ts>
+inline auto formatv_strict(const char *Fmt, Ts &&... Vals)
+    -> formatv_object<decltype(std::make_tuple(
+        detail::build_format_adapter(std::forward<Ts>(Vals))...))> {
+  return detail::formatv_impl(Fmt, FormatEscapeMode::Strict,
+                              std::forward<Ts>(Vals)...);
 }
 
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_FORMATVARIADIC_H

llvm/lib/Support/FormatVariadic.cpp

formatv_object_base::parseReplacementItem(StringRef Spec) {
   RepString = RepString.trim();
   if (!RepString.empty()) {
     assert(false && "Unexpected characters found in replacement string!");
   }
 
   return ReplacementItem{Spec, Index, Align, Where, Pad, Options};
 }
 
-std::pair<ReplacementItem, StringRef>
-formatv_object_base::splitLiteralAndReplacement(StringRef Fmt) {
-  std::size_t From = 0;
-  while (From < Fmt.size() && From != StringRef::npos) {
-    std::size_t BO = Fmt.find_first_of('{', From);
-    // Everything up until the first brace is a literal.
-    if (BO != 0)
-      return std::make_pair(ReplacementItem{Fmt.substr(0, BO)}, Fmt.substr(BO));
-
-    StringRef Braces =
-        Fmt.drop_front(BO).take_while([](char C) { return C == '{'; });
-    // If there is more than one brace, then some of them are escaped.  Treat
-    // these as replacements.
-    if (Braces.size() > 1) {
-      size_t NumEscapedBraces = Braces.size() / 2;
-      StringRef Middle = Fmt.substr(BO, NumEscapedBraces);
-      StringRef Right = Fmt.drop_front(BO + NumEscapedBraces * 2);
-      return std::make_pair(ReplacementItem{Middle}, Right);
-    }
+/// Parse the prefix of the string containing the first (open or close) brace
+/// including any escaped braces following it.
+static Optional<std::pair<ReplacementItem, StringRef>>
+parseBracePrefix(StringRef Fmt, std::size_t Pos, char Brace) {
+  // If the brace is not at the start, then everything up until the brace is a
+  // literal.
+  if (Pos != 0)
+    return std::make_pair(ReplacementItem{Fmt.substr(0, Pos)}, Fmt.substr(Pos));
+
+  // If there is one or more brace, then some of them may be escaped. Treat
+  StringRef Braces = Fmt.take_while([=](char C) { return C == Brace; });
+    StringRef Middle = Fmt.substr(Pos, NumEscapedBraces);
+    StringRef Right = Fmt.drop_front(Pos + NumEscapedBraces * 2);
+
+  // Found a single brace. Let the caller handle this case.
+  return llvm::None;
+}
+
+std::pair<ReplacementItem, StringRef>
+formatv_object_base::splitLiteralAndReplacement(StringRef Fmt,
+                                                FormatEscapeMode EscapeMode) {
+  std::size_t From = 0;
+  while (From < Fmt.size() && From != StringRef::npos) {
+    std::size_t BO = Fmt.find_first_of('{', From);
+
+    if (EscapeMode == FormatEscapeMode::Strict) {
+      std::size_t BC = Fmt.find_first_of('}', From);
+      // Found a closing brace before an opening brace.
+      if (BC < BO) {
+        auto replacement = parseBracePrefix(Fmt, BC, '}');
+        if (replacement)
+          return replacement.getValue();
+        // Found a closing brace without a matching opening brace before it. We
+        // treat the rest of the string as a literal replacement, but we assert
+        // to indicate that this is undefined and that we consider it an error.
+        assert(false && "Unterminated brace sequence.  Escape with }} for a "
+                        "literal brace.");
+        return std::make_pair(ReplacementItem{Fmt}, StringRef());
+      }
+    }
+
+    auto replacement = parseBracePrefix(Fmt, BO, '{');
+    if (replacement)
+      return replacement.getValue();
+
     // An unterminated open brace is undefined.  We treat the rest of the string
     // as a literal replacement, but we assert to indicate that this is
     // undefined and that we consider it an error.
     std::size_t BC = Fmt.find_first_of('}', BO);
     if (BC == StringRef::npos) {
       assert(
           false &&
           "Unterminated brace sequence.  Escape with {{ for a literal brace.");
while (From < Fmt.size() && From != StringRef::npos) {
     // If there was an error parsing the replacement item, treat it as an
     // invalid replacement spec, and just continue.
     From = BC + 1;
   }
   return std::make_pair(ReplacementItem{Fmt}, StringRef());
 }
 
 SmallVector<ReplacementItem, 2>
-formatv_object_base::parseFormatString(StringRef Fmt) {
+formatv_object_base::parseFormatString(StringRef Fmt,
+                                       FormatEscapeMode EscapeMode) {
   SmallVector<ReplacementItem, 2> Replacements;
   ReplacementItem I;
   while (!Fmt.empty()) {
-    std::tie(I, Fmt) = splitLiteralAndReplacement(Fmt);
+    std::tie(I, Fmt) = splitLiteralAndReplacement(Fmt, EscapeMode);
     if (I.Type != ReplacementType::Empty)
       Replacements.push_back(I);
   }
   return Replacements;
 }
 
 void detail::format_adapter::anchor() { }

llvm/unittests/Analysis/ProfileSummaryInfoTest.cpp

std::unique_ptr<Module> makeLLVMModule(const char *ProfKind = nullptr,
                                          uint64_t NumCounts = 3,
                                          uint64_t IsPartialProfile = 0,
                                          double PartialProfileRatio = 0.0,
                                          uint64_t HotNumCounts = 3,
                                          uint64_t ColdNumCounts = 10) {
     const char *ModuleString =
         "define i32 @g(i32 %x) !prof !21 {{\n"
         "  ret i32 0\n"
-        "}\n"
+        "}}\n"
         "define i32 @h(i32 %x) !prof !22 {{\n"
         "  ret i32 0\n"
-        "}\n"
+        "}}\n"
         "define i32 @f(i32 %x) !prof !20 {{\n"
         "bb0:\n"
         "  %y1 = icmp eq i32 %x, 0 \n"
         "  br i1 %y1, label %bb1, label %bb2, !prof !23 \n"
         "bb1:\n"
         "  %z1 = call i32 @g(i32 %x)\n"
         "  br label %bb3\n"
         "bb2:\n"
         "  %z2 = call i32 @h(i32 %x)\n"
         "  br label %bb3\n"
         "bb3:\n"
         "  %y2 = phi i32 [0, %bb1], [1, %bb2] \n"
         "  ret i32 %y2\n"
-        "}\n"
+        "}}\n"
         "define i32 @l(i32 %x) {{\n"
         "bb0:\n"
         "  %y1 = icmp eq i32 %x, 0 \n"
         "  br i1 %y1, label %bb1, label %bb2, !prof !23 \n"
         "bb1:\n"
         "  %z1 = call i32 @g(i32 %x)\n"
         "  br label %bb3\n"
         "bb2:\n"
         "  %z2 = call i32 @h(i32 %x)\n"
         "  br label %bb3\n"
         "bb3:\n"
         "  %y2 = phi i32 [0, %bb1], [1, %bb2] \n"
         "  ret i32 %y2\n"
-        "}\n"
-        "!20 = !{{!\"function_entry_count\", i64 400}\n"
-        "!21 = !{{!\"function_entry_count\", i64 1}\n"
-        "!22 = !{{!\"function_entry_count\", i64 100}\n"
-        "!23 = !{{!\"branch_weights\", i32 64, i32 4}\n"
+        "}}\n"
+        "!20 = !{{!\"function_entry_count\", i64 400}}\n"
+        "!21 = !{{!\"function_entry_count\", i64 1}}\n"
+        "!22 = !{{!\"function_entry_count\", i64 100}}\n"
+        "!23 = !{{!\"branch_weights\", i32 64, i32 4}}\n"
         "{0}";
     const char *SummaryString =
-        "!llvm.module.flags = !{{!1}\n"
-        "!1 = !{{i32 1, !\"ProfileSummary\", !2}\n"
-        "!2 = !{{!3, !4, !5, !6, !7, !8, !9, !10, !11, !12}\n"
-        "!3 = !{{!\"ProfileFormat\", !\"{0}\"}\n"
-        "!4 = !{{!\"TotalCount\", i64 10000}\n"
-        "!5 = !{{!\"MaxCount\", i64 10}\n"
-        "!6 = !{{!\"MaxInternalCount\", i64 1}\n"
-        "!7 = !{{!\"MaxFunctionCount\", i64 1000}\n"
-        "!8 = !{{!\"NumCounts\", i64 {1}}\n"
-        "!9 = !{{!\"NumFunctions\", i64 3}\n"
-        "!10 = !{{!\"IsPartialProfile\", i64 {2}}\n"
-        "!11 = !{{!\"PartialProfileRatio\", double {3}}\n"
-        "!12 = !{{!\"DetailedSummary\", !13}\n"
-        "!13 = !{{!14, !15, !16}\n"
-        "!14 = !{{i32 10000, i64 1000, i32 1}\n"
-        "!15 = !{{i32 990000, i64 300, i32 {4}}\n"
-        "!16 = !{{i32 999999, i64 5, i32 {5}}\n";
+        "!llvm.module.flags = !{{!1}}\n"
+        "!1 = !{{i32 1, !\"ProfileSummary\", !2}}\n"
+        "!2 = !{{!3, !4, !5, !6, !7, !8, !9, !10, !11, !12}}\n"
+        "!3 = !{{!\"ProfileFormat\", !\"{0}\"}}\n"
+        "!4 = !{{!\"TotalCount\", i64 10000}}\n"
+        "!5 = !{{!\"MaxCount\", i64 10}}\n"
+        "!6 = !{{!\"MaxInternalCount\", i64 1}}\n"
+        "!7 = !{{!\"MaxFunctionCount\", i64 1000}}\n"
+        "!8 = !{{!\"NumCounts\", i64 {1}}}\n"
+        "!9 = !{{!\"NumFunctions\", i64 3}}\n"
+        "!10 = !{{!\"IsPartialProfile\", i64 {2}}}\n"
+        "!11 = !{{!\"PartialProfileRatio\", double {3}}}\n"
+        "!12 = !{{!\"DetailedSummary\", !13}}\n"
+        "!13 = !{{!14, !15, !16}}\n"
+        "!14 = !{{i32 10000, i64 1000, i32 1}}\n"
+        "!15 = !{{i32 990000, i64 300, i32 {4}}}\n"
+        "!16 = !{{i32 999999, i64 5, i32 {5}}}\n";
     SMDiagnostic Err;
     if (ProfKind) {
       auto Summary =
-          formatv(SummaryString, ProfKind, NumCounts, IsPartialProfile,
+          formatv_strict(SummaryString, ProfKind, NumCounts, IsPartialProfile,
                          PartialProfileRatio, HotNumCounts, ColdNumCounts)
               .str();
-      return parseAssemblyString(formatv(ModuleString, Summary).str(), Err, C);
+      return parseAssemblyString(formatv_strict(ModuleString, Summary).str(),
+                                 Err, C);
     } else
-      return parseAssemblyString(formatv(ModuleString, "").str(), Err, C);
+      return parseAssemblyString(formatv_strict(ModuleString, "").str(), Err,
+                                 C);
   }
 };
 
 TEST_F(ProfileSummaryInfoTest, TestNoProfile) {
   auto M = makeLLVMModule(/*ProfKind=*/nullptr);
   Function *F = M->getFunction("f");
 
   ProfileSummaryInfo PSI = buildPSI(M.get());

llvm/unittests/Support/FormatVariadicTest.cpp

TEST(FormatVariadicTest, EscapedBrace) {
   EXPECT_EQ("{", Replacements[0].Spec);
   EXPECT_EQ(ReplacementType::Literal, Replacements[0].Type);
 
   // An even number N of braces should be replaced with N/2 braces.
   Replacements = formatv_object_base::parseFormatString("{{{{{{");
   ASSERT_EQ(1u, Replacements.size());
   EXPECT_EQ("{{{", Replacements[0].Spec);
   EXPECT_EQ(ReplacementType::Literal, Replacements[0].Type);
+
+  // }} should be replaced with }
+  Replacements =
+      formatv_object_base::parseFormatString("}}", FormatEscapeMode::Strict);
+  ASSERT_EQ(1u, Replacements.size());
+  EXPECT_EQ("}", Replacements[0].Spec);
+  EXPECT_EQ(ReplacementType::Literal, Replacements[0].Type);
+
+  // An even number N of braces should be replaced with N/2 braces.
+  Replacements = formatv_object_base::parseFormatString(
+      "}}}}}}", FormatEscapeMode::Strict);
+  ASSERT_EQ(1u, Replacements.size());
+  EXPECT_EQ("}}}", Replacements[0].Spec);
+  EXPECT_EQ(ReplacementType::Literal, Replacements[0].Type);
 }
 
 TEST(FormatVariadicTest, ValidReplacementSequence) {
   // 1. Simple replacement - parameter index only
   auto Replacements = formatv_object_base::parseFormatString("{0}");
   ASSERT_EQ(1u, Replacements.size());
   EXPECT_EQ(ReplacementType::Format, Replacements[0].Type);
   EXPECT_EQ(0u, Replacements[0].Index);
TEST(FormatVariadicTest, BigTest) {
   Tuple Ts[] = {
       Tuple('a', 1, "Str", StringRef(), std::string(), 3.14159, -.17532f,
             (void *)nullptr, 123456, 6.02E23, -908234908423, 908234908422234,
             std::numeric_limits<double>::quiet_NaN(), 0xAB),
       Tuple('x', 0xDDB5B, "LongerStr", "StringRef", "std::string", -2.7,
             .08215f, (void *)nullptr, 0, 6.62E-34, -908234908423,
             908234908422234, std::numeric_limits<double>::infinity(), 0x0)};
   // Test long string formatting with many edge cases combined.
-  const char *Intro =
-      "There are {{{0}} items in the tuple, and {{{1}} tuple(s) in the array.";
+  const char *Intro = "There are {{{0}}} items in the tuple, and {{{1}}} "
+                      "tuple(s) in the array.";
   const char *Header =
       "{0,6}|{1,8}|{2,=10}|{3,=10}|{4,=13}|{5,7}|{6,7}|{7,10}|{8,"
       "-7}|{9,10}|{10,16}|{11,17}|{12,6}|{13,4}";
   const char *Line =
       "{0,6}|{1,8:X}|{2,=10}|{3,=10:5}|{4,=13}|{5,7:3}|{6,7:P2}|{7,"
       "10:X8}|{8,-7:N}|{9,10:E4}|{10,16:N}|{11,17:D}|{12,6}|{13,"
       "4:X}";
 
   std::string S;
   llvm::raw_string_ostream Stream(S);
-  Stream << formatv(Intro, std::tuple_size<Tuple>::value,
+  Stream << formatv_strict(Intro, std::tuple_size<Tuple>::value,
                            llvm::array_lengthof(Ts))
          << "\n";
   Stream << formatv(Header, "Char", "HexInt", "Str", "Ref", "std::str",
                     "double", "float", "pointer", "comma", "exp", "bigint",
                     "bigint2", "limit", "byte")
          << "\n";
   for (auto &Item : Ts) {
     Stream << llvm::apply_tuple(format_tuple(Line), Item) << "\n";
   }