C++ PATCH for c++/80290, memory-hog with nested std::pair

Message ID CADzB+2kiisuBUxapCUKfRwq0Y7BwecLywbsUpCRzK4hhzeBXyQ@mail.gmail.com
State New
Headers show
Series
  • C++ PATCH for c++/80290, memory-hog with nested std::pair
Related show

Commit Message

Jason Merrill June 27, 2018, 2:59 a.m.
When the std::pair constructors got more complex to handle, it
aggravated a preexisting algorithmic problem in template overload
resolution:

As part of template argument deduction in a call, once we've deduced
all the template arguments we can but before we substitute them to
form an actual declaration, for any function parameters that don't
involve template parameters we need to check that it's possible to
convert the argument to the parameter type (wg21.link/cwg1391).

As a result, we end up calculating the conversion twice: once here,
and then again in add_function_candidate as part of normal overload
resolution.  Normally this isn't a big deal, but when the argument is
a multiply-nested initializer list, doubling the conversion processing
at each level leads to combinatorial explosion.

The patch for GCC 8 just disables the deduction-time check for a
multiply nested initializer list.  This is a small correctness
regression, but is unlikely to affect real code.

The patch for trunk avoids the duplication by remembering the
conversion we calculate at deduction time and then reusing it in
overload resolution rather than calculating it again.

Tested x86_64-pc-linux-gnu, applying to trunk and 8 (respectively).

Patch

commit b8f9db98f696ec175e4e9896904c2673b031fc51
Author: Jason Merrill <jason@redhat.com>
Date:   Mon Jun 25 17:07:21 2018 -0400

            PR c++/80290 - memory-hog with std::pair.
    
            * pt.c (type_unification_real): Skip non-dependent conversion
            check for a nested list argument.
            (braced_init_depth): New.

diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index c0f0b428d49..9a8ce883acd 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -20145,6 +20145,24 @@  try_array_deduction (tree tparms, tree targs, tree parm)
 			  /*nondeduced*/false, array_deduction_r);
 }
 
+/* Returns how many levels of { } INIT contains.  */
+
+static int
+braced_init_depth (tree init)
+{
+  if (!init || !BRACE_ENCLOSED_INITIALIZER_P (init))
+    return 0;
+  unsigned i; tree val;
+  unsigned max = 0;
+  FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), i, val)
+    {
+      unsigned elt_d = braced_init_depth (val);
+      if (elt_d > max)
+	max = elt_d;
+    }
+  return max + 1;
+}
+
 /* Most parms like fn_type_unification.
 
    If SUBR is 1, we're being called recursively (to unify the
@@ -20380,6 +20398,10 @@  type_unification_real (tree tparms,
 
 	    if (uses_template_parms (parm))
 	      continue;
+	    /* Workaround for c++/80290: avoid combinatorial explosion on
+	       deeply nested braced init-lists.  */
+	    if (braced_init_depth (arg) > 2)
+	      continue;
 	    if (check_non_deducible_conversion (parm, arg, strict, flags,
 						explain_p))
 	      return 1;