[2nd PING] [C++ PATCH] demangler fix (take 2)

[Gary Benson <gbenson at redhat dot com>]

Hi all,

This is a resubmission of my previous demangler fix [1] rewritten
to avoid using hashtables and other libiberty features.

From the above referenced email:

d_print_comp maintains a certain amount of scope across calls (namely
a stack of templates) which is used when evaluating references in
template argument lists.  If such a reference is later used from a
subtitution then the scope in force at the time of the substitution is
used.  This appears to be wrong (I say appears because I couldn't find
anything in the API [2] to clarify this).

The attached patch causes the demangler to capture the scope the first
time such a reference is traversed, and to use that captured scope on
subsequent traversals.  This fixes GDB PR 14963 [3] whereby a
reference is resolved against the wrong template, causing an infinite
loop and eventual stack overflow and segmentation fault.

I've added the result to the demangler test suite, but I know of no
way to check the validity of the demangled symbol other than by
inspection (and I am no expert here!)  If anybody knows a way to
check this then please let me know!  Otherwise, I hope this
not-really-checked demangled version is acceptable.

Thanks,
Gary

[1] http://gcc.gnu.org/ml/gcc-patches/2013-09/msg00215.html
[2] http://mentorembedded.github.io/cxx-abi/abi.html#mangling
[3] http://sourceware.org/bugzilla/show_bug.cgi?id=14963

-- 
http://gbenson.net/


diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index 89e108a..2ff8216 100644
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -1,3 +1,20 @@
+2013-09-17  Gary Benson  <gbenson@redhat.com>
+
+	* cp-demangle.c (struct d_saved_scope): New structure.
+	(struct d_print_info): New fields saved_scopes and
+	num_saved_scopes.
+	(d_print_init): Initialize the above.
+	(d_print_free): New function.
+	(cplus_demangle_print_callback): Call the above.
+	(d_copy_templates): New function.
+	(d_print_comp): New variables saved_templates and
+	need_template_restore.
+	[DEMANGLE_COMPONENT_REFERENCE,
+	DEMANGLE_COMPONENT_RVALUE_REFERENCE]: Capture scope the first
+	time the component is traversed, and use the captured scope for
+	subsequent traversals.
+	* testsuite/demangle-expected: Add regression test.
+
 2013-09-10  Paolo Carlini  <paolo.carlini@oracle.com>
 
 	PR bootstrap/58386
diff --git a/libiberty/cp-demangle.c b/libiberty/cp-demangle.c
index 70f5438..a199f6d 100644
--- a/libiberty/cp-demangle.c
+++ b/libiberty/cp-demangle.c
@@ -275,6 +275,18 @@ struct d_growable_string
   int allocation_failure;
 };
 
+/* A demangle component and some scope captured when it was first
+   traversed.  */
+
+struct d_saved_scope
+{
+  /* The component whose scope this is.  */
+  const struct demangle_component *container;
+  /* The list of templates, if any, that was current when this
+     scope was captured.  */
+  struct d_print_template *templates;
+};
+
 enum { D_PRINT_BUFFER_LENGTH = 256 };
 struct d_print_info
 {
@@ -302,6 +314,10 @@ struct d_print_info
   int pack_index;
   /* Number of d_print_flush calls so far.  */
   unsigned long int flush_count;
+  /* Array of saved scopes for evaluating substitutions.  */
+  struct d_saved_scope *saved_scopes;
+  /* Number of saved scopes in the above array.  */
+  int num_saved_scopes;
 };
 
 #ifdef CP_DEMANGLE_DEBUG
@@ -3665,6 +3681,30 @@ d_print_init (struct d_print_info *dpi, demangle_callbackref callback,
   dpi->opaque = opaque;
 
   dpi->demangle_failure = 0;
+
+  dpi->saved_scopes = NULL;
+  dpi->num_saved_scopes = 0;
+}
+
+/* Free a print information structure.  */
+
+static void
+d_print_free (struct d_print_info *dpi)
+{
+  int i;
+
+  for (i = 0; i < dpi->num_saved_scopes; i++)
+    {
+      struct d_print_template *ts, *tn;
+
+      for (ts = dpi->saved_scopes[i].templates; ts != NULL; ts = tn)
+	{
+	  tn = ts->next;
+	  free (ts);
+	}
+    }
+
+  free (dpi->saved_scopes);
 }
 
 /* Indicate that an error occurred during printing, and test for error.  */
@@ -3749,6 +3789,7 @@ cplus_demangle_print_callback (int options,
                                demangle_callbackref callback, void *opaque)
 {
   struct d_print_info dpi;
+  int success;
 
   d_print_init (&dpi, callback, opaque);
 
@@ -3756,7 +3797,9 @@ cplus_demangle_print_callback (int options,
 
   d_print_flush (&dpi);
 
-  return ! d_print_saw_error (&dpi);
+  success = ! d_print_saw_error (&dpi);
+  d_print_free (&dpi);
+  return success;
 }
 
 /* Turn components into a human readable string.  OPTIONS is the
@@ -3913,6 +3956,36 @@ d_print_subexpr (struct d_print_info *dpi, int options,
     d_append_char (dpi, ')');
 }
 
+/* Return a shallow copy of the current list of templates.
+   On error d_print_error is called and a partial list may
+   be returned.  Whatever is returned must be freed.  */
+
+static struct d_print_template *
+d_copy_templates (struct d_print_info *dpi)
+{
+  struct d_print_template *src, *result, **link = &result;
+
+  for (src = dpi->templates; src != NULL; src = src->next)
+    {
+      struct d_print_template *dst =
+	malloc (sizeof (struct d_print_template));
+
+      if (dst == NULL)
+	{
+	  d_print_error (dpi);
+	  break;
+	}
+
+      dst->template_decl = src->template_decl;
+      *link = dst;
+      link = &dst->next;
+    }
+
+  *link = NULL;
+
+  return result;
+}
+
 /* Subroutine to handle components.  */
 
 static void
@@ -3923,6 +3996,13 @@ d_print_comp (struct d_print_info *dpi, int options,
      without needing to modify *dc.  */
   const struct demangle_component *mod_inner = NULL;
 
+  /* Variable used to store the current templates while a previously
+     captured scope is used.  */
+  struct d_print_template *saved_templates;
+
+  /* Nonzero if templates have been stored in the above variable.  */
+  int need_template_restore = 0;
+
   if (dc == NULL)
     {
       d_print_error (dpi);
@@ -4291,12 +4371,56 @@ d_print_comp (struct d_print_info *dpi, int options,
 	const struct demangle_component *sub = d_left (dc);
 	if (sub->type == DEMANGLE_COMPONENT_TEMPLATE_PARAM)
 	  {
-	    struct demangle_component *a = d_lookup_template_argument (dpi, sub);
+	    struct demangle_component *a;
+	    struct d_saved_scope *scope = NULL, *scopes;
+	    int i;
+
+	    for (i = 0; i < dpi->num_saved_scopes; i++)
+	      if (dpi->saved_scopes[i].container == sub)
+		scope = &dpi->saved_scopes[i];
+
+	    if (scope == NULL)
+	      {
+		/* This is the first time SUB has been traversed.
+		   We need to capture the current templates so
+		   they can be restored if SUB is reentered as a
+		   substitution.  */
+		++dpi->num_saved_scopes;
+		scopes = realloc (dpi->saved_scopes,
+				  sizeof (struct d_saved_scope)
+				  * dpi->num_saved_scopes);
+		if (scopes == NULL)
+		  {
+		    d_print_error (dpi);
+		    return;
+		  }
+
+		dpi->saved_scopes = scopes;
+		scope = dpi->saved_scopes + (dpi->num_saved_scopes - 1);
+
+		scope->container = sub;
+		scope->templates = d_copy_templates (dpi);
+		if (d_print_saw_error (dpi))
+		  return;
+	      }
+	    else
+	      {
+		/* This traversal is reentering SUB as a substition.
+		   Restore the original templates temporarily.  */
+		saved_templates = dpi->templates;
+		dpi->templates = scope->templates;
+		need_template_restore = 1;
+	      }
+
+	    a = d_lookup_template_argument (dpi, sub);
 	    if (a && a->type == DEMANGLE_COMPONENT_TEMPLATE_ARGLIST)
 	      a = d_index_template_argument (a, dpi->pack_index);
 
 	    if (a == NULL)
 	      {
+		if (need_template_restore)
+		  dpi->templates = saved_templates;
+
 		d_print_error (dpi);
 		return;
 	      }
@@ -4344,6 +4468,9 @@ d_print_comp (struct d_print_info *dpi, int options,
 
 	dpi->modifiers = dpm.next;
 
+	if (need_template_restore)
+	  dpi->templates = saved_templates;
+
 	return;
       }
 
diff --git a/libiberty/testsuite/demangle-expected b/libiberty/testsuite/demangle-expected
index 1259e4a..d3a3603 100644
--- a/libiberty/testsuite/demangle-expected
+++ b/libiberty/testsuite/demangle-expected
@@ -4291,3 +4291,6 @@ void m<void () &&>(void (A::*)() &&)
 --format=gnu-v3
 _Z1nIM1AKFvvREEvT_
 void n<void (A::*)() const &>(void (A::*)() const &)
+--format=gnu-v3
+_ZSt7forwardIRN1x14refobjiteratorINS0_3refINS0_4mime30multipart_section_processorObjIZ15get_body_parserIZZN14mime_processor21make_section_iteratorERKNS2_INS3_10sectionObjENS0_10ptrrefBaseEEEbENKUlvE_clEvEUlSB_bE_ZZNS6_21make_section_iteratorESB_bENKSC_clEvEUlSB_E0_ENS1_INS2_INS0_20outputrefiteratorObjIiEES8_EEEERKSsSB_OT_OT0_EUlmE_NS3_32make_multipart_default_discarderISP_EEEES8_EEEEEOT_RNSt16remove_referenceISW_E4typeE
+x::refobjiterator<x::ref<x::mime::multipart_section_processorObj<x::refobjiterator<x::ref<x::outputrefiteratorObj<int>, x::ptrrefBase> > get_body_parser<mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&)#2}>(std::string const&, x::ref<x::mime::sectionObj, x::ptrrefBase> const&, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}&&, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&)#2}&&)::{lambda(unsigned long)#1}, x::mime::make_multipart_default_discarder<mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}&&> >, x::ptrrefBase> >& std::forward<x::refobjiterator<x::ref<x::mime::multipart_section_processorObj<x::refobjiterator<x::ref<x::outputrefiteratorObj<int>, x::ptrrefBase> > get_body_parser<mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&)#2}>(std::string const&, x::ref<x::mime::sectionObj, x::ptrrefBase> const&, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}&&, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&)#2}&&)::{lambda(unsigned long)#1}, x::mime::make_multipart_default_discarder<mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}&&> >, x::ptrrefBase> >&>(std::remove_reference<x::mime::multipart_section_processorObj<x::refobjiterator<x::ref<x::outputrefiteratorObj<int>, x::ptrrefBase> > get_body_parser<mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&)#2}>(std::string const&, x::ref<x::mime::sectionObj, x::ptrrefBase> const&, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}&&, mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&)#2}&&)::{lambda(unsigned long)#1}, x::mime::make_multipart_default_discarder<mime_processor::make_section_iterator(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)::{lambda()#1}::operator()() const::{lambda(x::ref<x::mime::sectionObj, x::ptrrefBase> const&, bool)#1}&&> > >::type&)
diff --git a/test.c b/test.c
new file mode 100644
index 0000000..8eb753b
--- /dev/null
+++ b/test.c
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <demangle.h>
+
+const char *mangled = "_ZSt7forwardIRN1x14refobjiteratorINS0_3refINS0_" \
+  "4mime30multipart_section_processorObjIZ15get_body_parserIZZN14mime" \
+  "_processor21make_section_iteratorERKNS2_INS3_10sectionObjENS0_10pt" \
+  "rrefBaseEEEbENKUlvE_clEvEUlSB_bE_ZZNS6_21make_section_iteratorESB_" \
+  "bENKSC_clEvEUlSB_E0_ENS1_INS2_INS0_20outputrefiteratorObjIiEES8_EE" \
+  "EERKSsSB_OT_OT0_EUlmE_NS3_32make_multipart_default_discarderISP_EE" \
+  "EES8_EEEEEOT_RNSt16remove_referenceISW_E4typeE";
+
+int
+main (int argc, char *argv[])
+{
+  const char *demangled;
+  FILE *fp;
+
+  fp = fopen ("test.in", "w");
+  if (fp != NULL)
+    {
+      fputs (mangled, fp);
+      fclose (fp);
+    }
+
+  demangled = cplus_demangle (mangled, DMGL_AUTO | DMGL_ANSI | DMGL_PARAMS);
+
+  if (demangled == NULL)
+    {
+      puts ("Demangler failed");
+      exit (EXIT_FAILURE);
+    }
+  puts (demangled);
+
+  fp = fopen ("test.out", "w");
+  if (fp != NULL)
+    {
+      fputs (demangled, fp);
+      fclose (fp);
+    }
+
+  exit (EXIT_SUCCESS);
+}