Add a limit to __make_integer_seq builtin.

[erichkeane]

Summary

As brought up in PR48246, passing a large value to __make_integer_seq
results in the compiler getting stuck in a large loop and potentially
crashing if it runs out of memory as a result.

This patch puts a command-line configurable limit in place to limit the
size to something reasonable.

I chose 2^24 as default after a brief experimentation with the debug compiler,
which made it take a few minutes. On a release build, a program with a 2^24
value takes roughly 30 seconds, and uses about 3.3GB of ram.

[erichkeane]

Some additional data on a release build (on my quite recent Xeon 8260M):
2^24: 27 sec, ~3.3GB
2^25: 49 sec, ~6.4GB

It follows a pretty linear pattern from there. I'm open to choosing a different limit if we find one more reasonable for some reason or another (@ldionne opinion?).

[rsmith]

I wonder if more generally we should have a limit on either the size of a pack or the number of template arguments in a template specialization, rather than limiting only __make_integer_seq? I think a hand-rolled make_integer_sequence implementation should also be limited in the same way. Eg: https://godbolt.org/z/Yhb6E4vTG

I'd also be inclined to pick a smaller default limit for the more general constraint. Maybe 64K? I think we should be aiming to pick a limit that causes template argument list explosions to be caught before the compiler runs out of memory and dies and before the user gets bored and interrupts the compilation, and 16M seems a bit high for both. For the above example, we take 6s on godbolt for 64K, and ~30s for 512K.

[erichkeane]

In D112659#3091501, @rsmith wrote:

I wonder if more generally we should have a limit on either the size of a pack or the number of template arguments in a template specialization, rather than limiting only __make_integer_seq? I think a hand-rolled make_integer_sequence implementation should also be limited in the same way. Eg: https://godbolt.org/z/Yhb6E4vTG

That seems like a reasonable error, I agree. I looked into the number of template arguments in a specialization, however, i've been looking through all the places that TemplateArgumentListInfo::addArgument is called, and it seems that we do this kind of all over the place... I would imagine we would want to catch this as we are adding, since if we wait until after (when it is converted to a ASTTemplateArgumentListInfo or something), the damage has already been done, right?

Or am I taking this too literally?

I'd also be inclined to pick a smaller default limit for the more general constraint. Maybe 64K? I think we should be aiming to pick a limit that causes template argument list explosions to be caught before the compiler runs out of memory and dies and before the user gets bored and interrupts the compilation, and 16M seems a bit high for both. For the above example, we take 6s on godbolt for 64K, and ~30s for 512K.

I don't mind a 64k default, I was concerned with what I did (16 million) being too small of a limit, but I don't have a good idea of the scale of what library folks end up doing for this.

clang/include/clang/Basic/DiagnosticSemaKinds.td

def err_function_template_partial_spec : Error<
     "function template partial specialization is not allowed">;
 
 // C++ Template Instantiation
 def err_template_recursion_depth_exceeded : Error<
   "recursive template instantiation exceeded maximum depth of %0">,
   DefaultFatal, NoSFINAE;
 def note_template_recursion_depth : Note<
   "use -ftemplate-depth=N to increase recursive template instantiation depth">;
+def err_integer_sequence_length_exceeded
+    : Error<"'__make_integer_seq' exceeded maximum limit of %0">;
+def note_integer_sequence_length_exceeded
+    : Note<"use -fint-seq-limit=N to increase '__make_integer_seq' "
+           "limit">;
 
 def err_template_instantiate_within_definition : Error<
   "%select{implicit|explicit}0 instantiation of template %1 within its"
   " own definition">;
 def err_template_instantiate_undefined : Error<
   "%select{implicit|explicit}0 instantiation of undefined template %1">;
 def err_implicit_instantiate_member_undefined : Error<
   "implicit instantiation of undefined member %0">;

clang/include/clang/Basic/LangOptions.def

 BENIGN_LANGOPT(ArrowDepth, 32, 256,
                "maximum number of operator->s to follow")
 BENIGN_LANGOPT(InstantiationDepth, 32, 1024,
                "maximum template instantiation depth")
 BENIGN_LANGOPT(ConstexprCallDepth, 32, 512,
                "maximum constexpr call depth")
 BENIGN_LANGOPT(ConstexprStepLimit, 32, 1048576,
                "maximum constexpr evaluation steps")
+BENIGN_LANGOPT(MakeIntSeqSize, 32, 16777216,
+               "maximum value for __make_integer_seq")
 BENIGN_LANGOPT(EnableNewConstInterp, 1, 0,
                "enable the experimental new constant interpreter")
 BENIGN_LANGOPT(BracketDepth, 32, 256,
                "maximum bracket nesting depth")
 BENIGN_LANGOPT(NumLargeByValueCopy, 32, 0,
         "if non-zero, warn about parameter or return Warn if parameter/return value is larger in bytes than this setting. 0 is no check.")
 VALUE_LANGOPT(MSCompatibilityVersion, 32, 0, "Microsoft Visual C/C++ Version")
 ENUM_LANGOPT(VtorDispMode, MSVtorDispMode, 2, MSVtorDispMode::ForVBaseOverride,

clang/include/clang/Driver/Options.td

def fsyntax_only : Flag<["-"], "fsyntax-only">,
   Flags<[NoXarchOption,CoreOption,CC1Option,FC1Option]>, Group<Action_Group>;
 def ftabstop_EQ : Joined<["-"], "ftabstop=">, Group<f_Group>;
 def ftemplate_depth_EQ : Joined<["-"], "ftemplate-depth=">, Group<f_Group>;
 def ftemplate_depth_ : Joined<["-"], "ftemplate-depth-">, Group<f_Group>;
 def ftemplate_backtrace_limit_EQ : Joined<["-"], "ftemplate-backtrace-limit=">,
                                    Group<f_Group>;
 def foperator_arrow_depth_EQ : Joined<["-"], "foperator-arrow-depth=">,
                                Group<f_Group>;
+def fint_seq_limit_EQ : Joined<["-"], "fint-seq-limit=">, Group<f_Group>;
 
 def fsave_optimization_record : Flag<["-"], "fsave-optimization-record">,
   Group<f_Group>, HelpText<"Generate a YAML optimization record file">;
 def fsave_optimization_record_EQ : Joined<["-"], "fsave-optimization-record=">,
   Group<f_Group>, HelpText<"Generate an optimization record file in a specific format">,
   MetaVarName<"<format>">;
 def fno_save_optimization_record : Flag<["-"], "fno-save-optimization-record">,
   Group<f_Group>, Flags<[NoArgumentUnused]>;
def fapply_global_visibility_to_externs : Flag<["-"], "fapply-global-visibility-to-externs">,
   HelpText<"Apply global symbol visibility to external declarations without an explicit visibility">,
   MarshallingInfoFlag<LangOpts<"SetVisibilityForExternDecls">>;
 def ftemplate_depth : Separate<["-"], "ftemplate-depth">,
   HelpText<"Maximum depth of recursive template instantiation">,
   MarshallingInfoInt<LangOpts<"InstantiationDepth">, "1024">;
 def foperator_arrow_depth : Separate<["-"], "foperator-arrow-depth">,
   HelpText<"Maximum number of 'operator->'s to call for a member access">,
   MarshallingInfoInt<LangOpts<"ArrowDepth">, "256">;
+def fint_seq_limit : Separate<["-"], "fint-seq-limit">,
+  HelpText<"Maximum value of the __make_integer_seq builtin">,
+  MarshallingInfoInt<LangOpts<"MakeIntSeqSize">, "16777216">;
 def fconstexpr_depth : Separate<["-"], "fconstexpr-depth">,
   HelpText<"Maximum depth of recursive constexpr function calls">,
   MarshallingInfoInt<LangOpts<"ConstexprCallDepth">, "512">;
 def fconstexpr_steps : Separate<["-"], "fconstexpr-steps">,
   HelpText<"Maximum number of steps in constexpr function evaluation">,
   MarshallingInfoInt<LangOpts<"ConstexprStepLimit">, "1048576">;
 def fbracket_depth : Separate<["-"], "fbracket-depth">,
   HelpText<"Maximum nesting level for parentheses, brackets, and braces">,

clang/lib/Driver/ToolChains/Clang.cpp

if (Arg *A = Args.getLastArg(options::OPT_ftemplate_depth_,
     CmdArgs.push_back(A->getValue());
   }
 
   if (Arg *A = Args.getLastArg(options::OPT_foperator_arrow_depth_EQ)) {
     CmdArgs.push_back("-foperator-arrow-depth");
     CmdArgs.push_back(A->getValue());
   }
 
+  if (Arg *A = Args.getLastArg(options::OPT_fint_seq_limit_EQ)) {
+    CmdArgs.push_back("-fint-seq-limit");
+    CmdArgs.push_back(A->getValue());
+  }
+
   if (Arg *A = Args.getLastArg(options::OPT_fconstexpr_depth_EQ)) {
     CmdArgs.push_back("-fconstexpr-depth");
     CmdArgs.push_back(A->getValue());
   }
 
   if (Arg *A = Args.getLastArg(options::OPT_fconstexpr_steps_EQ)) {
     CmdArgs.push_back("-fconstexpr-steps");
     CmdArgs.push_back(A->getValue());

clang/lib/Sema/SemaTemplate.cpp

case BTK__make_integer_seq: {
     TemplateArgument NumArgsArg = Converted[2];
     llvm::APSInt NumArgs = NumArgsArg.getAsIntegral();
     if (NumArgs < 0) {
       SemaRef.Diag(TemplateArgs[2].getLocation(),
                    diag::err_integer_sequence_negative_length);
       return QualType();
     }
 
+    // The below loop ends up taking a very long time and causing an OOM crash
+    // if 'N' is too large.  Limit to a command-line specified value.
+    if (NumArgs > SemaRef.getLangOpts().MakeIntSeqSize) {
+      SemaRef.Diag(TemplateArgs[2].getLocation(),
+                   diag::err_integer_sequence_length_exceeded)
+          << SemaRef.getLangOpts().MakeIntSeqSize;
+      SemaRef.Diag(TemplateArgs[2].getLocation(),
+                   diag::note_integer_sequence_length_exceeded)
+          << SemaRef.getLangOpts().MakeIntSeqSize;
+      return QualType();
+    }
+
     QualType ArgTy = NumArgsArg.getIntegralType();
     TemplateArgumentListInfo SyntheticTemplateArgs;
     // The type argument gets reused as the first template argument in the
     // synthetic template argument list.
     SyntheticTemplateArgs.addArgument(TemplateArgs[1]);
     // Expand N into 0 ... N-1.
     for (llvm::APSInt I(NumArgs.getBitWidth(), NumArgs.isUnsigned());
          I < NumArgs; ++I) {

clang/test/SemaCXX/make_integer_seq.cpp

 // RUN: %clang_cc1 -fsyntax-only -verify -std=c++11 %s
+// RUN: %clang_cc1 -fsyntax-only -verify=expected,smalllimit -fint-seq-limit 500 -std=c++11 %s
 
 static_assert(__has_builtin(__make_integer_seq), "");
 
 template <class T, T... I>
 struct Seq {
   static constexpr T PackSize = sizeof...(I);
 };
 

 using illformed2 = ErrorSeq<int, -5>; // expected-note{{in instantiation}}
 
 template <typename T, T N> void f() {}
 __make_integer_seq<f, int, 0> x; // expected-error{{template template parameter must be a class template or type alias template}}
 
 __make_integer_seq<__make_integer_seq, int, 10> PR28494; // expected-error{{different template parameters}}
 // expected-note@make_integer_seq.cpp:* {{template parameter has a different kind}}
 // expected-note@make_integer_seq.cpp:* {{previous template template parameter is here}}
+
+__make_integer_seq<Seq, int, 1200> PR48246;
+// smalllimit-error@-1{{'__make_integer_seq' exceeded maximum limit of 500}}
+// smalllimit-note@-2 {{use -fint-seq-limit=N to increase '__make_integer_seq' limit}}
+
+// Default value is ~16.7 million, so without the command line option, fail.
+__make_integer_seq<Seq, int, 16800000> PR48246_b;
+// expected-error@-1{{'__make_integer_seq' exceeded maximum limit of}}
+// expected-note@-2 {{use -fint-seq-limit=N to increase '__make_integer_seq' limit}}
+
+using size_t = unsigned long long;
+
+__make_integer_seq<Seq, size_t, ((size_t)1) - 2> PR48246_c;
+// expected-error@-1{{'__make_integer_seq' exceeded maximum limit of}}
+// expected-note@-2 {{use -fint-seq-limit=N to increase '__make_integer_seq' limit}}