Infcall of a template function in a C++ program

Infcall of a template function in a C++ program

[Aktemur, Tankut Baris]

Dear All,

Suppose we have the following small C++ program:

~~~
#include <iostream>

template <typename T>
T foo (T t)
{
  return t;
}

int main (void)
{
  std::cout << foo (5) << std::endl;
  std::cout << foo ('a') << std::endl;

  return 0;
}
~~~

The compiler is able to do the type inference, template function
instantiation, and function invocation based on the expressions `foo (5)`
and `foo ('a')`.  When we start GDB and attempt to evaluate these
expressions, the corresponding functions are not resolved, though.
Here is a sample session:

~~~
(gdb) start
...
(gdb) print foo(5)
No symbol "foo" in current context.
(gdb) print foo<int>(5)
$1 = 5
(gdb) print foo<char>('a')
$2 = 97 'a'
~~~

The DWARF info contains DIE's for the subprograms named "foo<int>" and
"foo<char>":

0x00002849:   DW_TAG_subprogram
                DW_AT_name      ("foo<char>")
...
0x00002882:   DW_TAG_subprogram
                DW_AT_name      ("foo<int>")
...

Is there any on-going or planned work to add type inference/resolution
capability to GDB so that an expression such as `foo (5)` would be evaluated
correctly? This might not be possible in general, but does GDB try any heuristics
to find the right template instance?

Regards,
-Tankut Baris Aktemur

Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Gary Kershaw
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928

RE: Infcall of a template function in a C++ program

[Aktemur, Tankut Baris]

[-- Attachment #1: Type: text/plain, Size: 7635 bytes --]

* On Fri, 7 Jun 2019 14:45:40 +0000, "Aktemur, Tankut Baris" wrote:
> 
> Dear All,
> 
> Suppose we have the following small C++ program:
> 
> ~~~
> #include <iostream>
> 
> template <typename T>
> T foo (T t)
> {
>   return t;
> }
> 
> int main (void)
> {
>   std::cout << foo (5) << std::endl;
>   std::cout << foo ('a') << std::endl;
> 
>   return 0;
> }
> ~~~
> 
> The compiler is able to do the type inference, template function
> instantiation, and function invocation based on the expressions `foo (5)`
> and `foo ('a')`.  When we start GDB and attempt to evaluate these
> expressions, the corresponding functions are not resolved, though.
> Here is a sample session:
> 
> ~~~
> (gdb) start
> ...
> (gdb) print foo(5)
> No symbol "foo" in current context.
> (gdb) print foo<int>(5)
> $1 = 5
> (gdb) print foo<char>('a')
> $2 = 97 'a'
> ~~~
> 
> The DWARF info contains DIE's for the subprograms named "foo<int>" and
> "foo<char>":
> 
> 0x00002849:   DW_TAG_subprogram
>                 DW_AT_name      ("foo<char>")
> ...
> 0x00002882:   DW_TAG_subprogram
>                 DW_AT_name      ("foo<int>")
> ...
> 
> Is there any on-going or planned work to add type inference/resolution
> capability to GDB so that an expression such as `foo (5)` would be evaluated
> correctly? This might not be possible in general, but does GDB try any heuristics
> to find the right template instance?

I've evaluated the following straightforward idea to address this problem:
When looking up function names, ignore the template arguments if the user
did not enter them explicitly.  This way, all the function instances can be
found.  GDB already does overload resolution.  After finding the potential
set of function symbols, the overload resolution mechanism can take over to
pick the best match.

E.g.  Consider the example above.  If the user enters `foo(5)`, we
can look up symbols matching `foo`.  Ignoring template arguments would
yield `foo<char>` and `foo<int>`.  Because the argument 5 is an int,
overload resolution can pick `foo<int>` successfully among these
candidates.  If the user enters template arguments explicitly as in
`foo<char>(5)`, then we would look up `foo<char>`, find only `foo<char>`,
and proceed with that.

1. To look up symbols, GDB retains a hash map.  It calculates the hash of
   the search phrase, finds the corresponding bucket, and then performs a
   linear search in the bucket.  To make sure that all the template
   instances of a function fall into the same bucket, we should ignore
   template arguments when calculating the hash of a function name.

2. When comparing two symbols, we must ignore template arguments
   if the search phrase does not contain them.  Otherwise, they
   must be taken into account.

The patch given at the end of this email does these two things
(also attached as a file).  So far so good.  There is a remaining problem,
though.  For expression evaluation, GDB does the following:

1. parse the input string, obtain an expression (a flattened abstract
   syntax tree).

2. evaluate the expression.

In step 1, while parsing, the function name is converted to a symbol
by performing a lookup and picking the first match (no overload
resolution).  In this step, the search phrase is the function name
input by the user.  In step 2, GDB does a lookup (again) followed by
overload resolution, but this time the search phrase is the name of
the symbol found in step 1.  This means the information about whether
the user originally entered template arguments explicitly is lost!
Moreover, this could lead to incorrect deduction.

Example: User enters `foo(5)`.  Step 1 looks up "foo", finds and picks
`foo<char>` as the first match.  In step 2, the function name to be
used for lookup is `foo<char>`.  There is only one match for that.
So GDB picks `foo<char>` for execution.

Opinions on how to address this problem properly are welcome.

Regards,
-Baris

~~~
diff --git a/gdb/cp-support.c b/gdb/cp-support.c
index 3ce5f60b12c..f27f04b8999 100644
--- a/gdb/cp-support.c
+++ b/gdb/cp-support.c
@@ -1642,6 +1642,17 @@ cp_search_name_hash (const char *search_name)
          && string[5] != ':')
        break;

+      /* Skip template arguments such as "<int, std::vector<char>>".
+        This is needed in case the user enters the plain function name
+        without the explicit template arguments when evaluating an
+        expression, so that all the symbol candidates will be found in
+        the same bucket.  */
+      if (skip_template_args (&string))
+       {
+         string--; /* Adjust for the loop's post-expr.  */
+         continue;
+       }
+
       hash = SYMBOL_HASH_NEXT (hash, *string);
     }
   return hash;
diff --git a/gdb/utils.c b/gdb/utils.c
index 09381d9092d..89cccbbf1e9 100644
--- a/gdb/utils.c
+++ b/gdb/utils.c
@@ -2257,6 +2257,34 @@ skip_abi_tag (const char **name)

 /* See utils.h.  */
+bool
+skip_template_args (const char **name)
+{
+  const char *p = *name;
+
+  if (*p == '\0' || *p != '<')
+    return false;
+
+  p++;
+  int depth = 1;
+
+  while (*p != '\0' && depth > 0)
+    {
+      if (*p == '<')
+       depth++;
+      else if (*p == '>')
+       depth--;
+      p++;
+    }
+
+  if (depth == 0)
+    *name = p;
+
+  return (depth == 0);
+}
+
+/* See utils.h.  */
+
 int
 strncmp_iw_with_mode (const char *string1, const char *string2,
                      size_t string2_len, strncmp_iw_mode mode,
@@ -2311,6 +2339,26 @@ strncmp_iw_with_mode (const char *string1, const char *string2,
            string1++;
        }
+      /* Skip template args in the symbol name if the lookup name
+        doesn't include them.  E.g.:
+
+        string1: function<int, std::vector<int>>(int)
+        string2: function
+      */
+      if (language == language_cplus
+         && (string2 == end_str2 || *string2 != '<'))
+       {
+         const char *template_start = string1;
+
+         bool skipped = skip_template_args (&string1);
+
+         if (match_for_lcd != NULL && skipped)
+           match_for_lcd->mark_ignored_range (template_start, string1);
+
+         while (isspace (*string1))
+           string1++;
+       }
+
       if (*string1 == '\0' || string2 == end_str2)
        break;

diff --git a/gdb/utils.h b/gdb/utils.h
index c728449429e..21e34cfec6b 100644
--- a/gdb/utils.h
+++ b/gdb/utils.h
@@ -89,6 +89,19 @@ extern int strcmp_iw (const char *string1, const char *string2);

 extern int strcmp_iw_ordered (const char *, const char *);
+/* If *NAME points at template args, skip it and return true.  Otherwise
+   leave *NAME unmodified and return false.  E.g.,
+   Before:   "<int, std::vector<int>>(int)".
+      *NAME --^
+   After:    "<int, std::vector<int>>(int)".
+      *NAME -------------------------^
+
+   If the angle brackets are not balanced, *NAME is unmodified, and the
+   return value is false.  This could be the case, for instance, if *NAME
+   points to the first '<' inside "operator<<(...)".  */
+
+extern bool skip_template_args (const char **name);
+
 /* Return true if the strings are equal.  */

 extern bool streq (const char *, const char *);
~~~
Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Gary Kershaw
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928

[-- Attachment #2: template-args.patch --]
[-- Type: application/octet-stream, Size: 3016 bytes --]

diff --git a/gdb/cp-support.c b/gdb/cp-support.c
index 3ce5f60b12c..f27f04b8999 100644
--- a/gdb/cp-support.c
+++ b/gdb/cp-support.c
@@ -1642,6 +1642,17 @@ cp_search_name_hash (const char *search_name)
 	  && string[5] != ':')
 	break;
 
+      /* Skip template arguments such as "<int, std::vector<char>>".
+	 This is needed in case the user enters the plain function name
+	 without the explicit template arguments when evaluating an
+	 expression, so that all the symbol candidates will be found in
+	 the same bucket.  */
+      if (skip_template_args (&string))
+	{
+	  string--; /* Adjust for the loop's post-expr.  */
+	  continue;
+	}
+
       hash = SYMBOL_HASH_NEXT (hash, *string);
     }
   return hash;
diff --git a/gdb/utils.c b/gdb/utils.c
index 09381d9092d..89cccbbf1e9 100644
--- a/gdb/utils.c
+++ b/gdb/utils.c
@@ -2257,6 +2257,34 @@ skip_abi_tag (const char **name)
 
 /* See utils.h.  */
 
+bool
+skip_template_args (const char **name)
+{
+  const char *p = *name;
+
+  if (*p == '\0' || *p != '<')
+    return false;
+
+  p++;
+  int depth = 1;
+
+  while (*p != '\0' && depth > 0)
+    {
+      if (*p == '<')
+	depth++;
+      else if (*p == '>')
+	depth--;
+      p++;
+    }
+
+  if (depth == 0)
+    *name = p;
+
+  return (depth == 0);
+}
+
+/* See utils.h.  */
+
 int
 strncmp_iw_with_mode (const char *string1, const char *string2,
 		      size_t string2_len, strncmp_iw_mode mode,
@@ -2311,6 +2339,26 @@ strncmp_iw_with_mode (const char *string1, const char *string2,
 	    string1++;
 	}
 
+      /* Skip template args in the symbol name if the lookup name
+	 doesn't include them.  E.g.:
+
+	 string1: function<int, std::vector<int>>(int)
+	 string2: function
+      */
+      if (language == language_cplus
+	  && (string2 == end_str2 || *string2 != '<'))
+	{
+	  const char *template_start = string1;
+
+	  bool skipped = skip_template_args (&string1);
+
+	  if (match_for_lcd != NULL && skipped)
+	    match_for_lcd->mark_ignored_range (template_start, string1);
+
+	  while (isspace (*string1))
+	    string1++;
+	}
+
       if (*string1 == '\0' || string2 == end_str2)
 	break;
 
diff --git a/gdb/utils.h b/gdb/utils.h
index c728449429e..21e34cfec6b 100644
--- a/gdb/utils.h
+++ b/gdb/utils.h
@@ -89,6 +89,19 @@ extern int strcmp_iw (const char *string1, const char *string2);
 
 extern int strcmp_iw_ordered (const char *, const char *);
 
+/* If *NAME points at template args, skip it and return true.  Otherwise
+   leave *NAME unmodified and return false.  E.g.,
+   Before:   "<int, std::vector<int>>(int)".
+      *NAME --^
+   After:    "<int, std::vector<int>>(int)".
+      *NAME -------------------------^
+
+   If the angle brackets are not balanced, *NAME is unmodified, and the
+   return value is false.  This could be the case, for instance, if *NAME
+   points to the first '<' inside "operator<<(...)".  */
+
+extern bool skip_template_args (const char **name);
+
 /* Return true if the strings are equal.  */
 
 extern bool streq (const char *, const char *);

Re: Infcall of a template function in a C++ program

[Tom Tromey]

>>>>> ">" == Aktemur, Tankut Baris <tankut.baris.aktemur@intel.com> writes:

>> The compiler is able to do the type inference, template function
>> instantiation, and function invocation based on the expressions `foo (5)`
>> and `foo ('a')`.  When we start GDB and attempt to evaluate these
>> expressions, the corresponding functions are not resolved, though.

>> Opinions on how to address this problem properly are welcome.

Once upon a time, Sami Wagiaalla wrote some patches to do this.
I don't believe they ever went in.  I don't remember why any more.
However, perhaps they could be resurrected.  They were sent to
gdb-patches, years ago now.

The "compile" command might also be promising here, though I don't know
how well the C++ support handles templates.  It's a difficult problem
given the way the "compile" command was designed, because the source
isn't available and DWARF doesn't represent templates, only
instantiations.

Tom

Re: Infcall of a template function in a C++ program

[Keith Seitz]

On 7/19/19 1:12 PM, Tom Tromey wrote:
> 
> The "compile" command might also be promising here, though I don't know
> how well the C++ support handles templates.  It's a difficult problem
> given the way the "compile" command was designed, because the source
> isn't available and DWARF doesn't represent templates, only
> instantiations.

For the record: the upstream C++ compile feature does not include any template
support at all. I do have some patches to start this process, but it
is stalled on a number of outstanding issues (unresolved bugs, unreviewed
patch(es?), etc).

Keith

Re: Infcall of a template function in a C++ program

[Tom Tromey]

>>>>> "Keith" == Keith Seitz <keiths@redhat.com> writes:

Keith> On 7/19/19 1:12 PM, Tom Tromey wrote:
>> 
>> The "compile" command might also be promising here, though I don't know
>> how well the C++ support handles templates.  It's a difficult problem
>> given the way the "compile" command was designed, because the source
>> isn't available and DWARF doesn't represent templates, only
>> instantiations.

Keith> For the record: the upstream C++ compile feature does not include any template
Keith> support at all. I do have some patches to start this process, but it
Keith> is stalled on a number of outstanding issues (unresolved bugs, unreviewed
Keith> patch(es?), etc).

If there are unreviewed gdb patches, please send a ping.  I'll take a
look.

thanks,
Tom

RE: Infcall of a template function in a C++ program

[Aktemur, Tankut Baris]

* On Friday, July 19, 2019 10:12 PM, Tom Tromey wrote:
> 
> >>>>> ">" == Aktemur, Tankut Baris <tankut.baris.aktemur@intel.com> writes:
> 
> >> The compiler is able to do the type inference, template function
> >> instantiation, and function invocation based on the expressions `foo (5)`
> >> and `foo ('a')`.  When we start GDB and attempt to evaluate these
> >> expressions, the corresponding functions are not resolved, though.
> 
> >> Opinions on how to address this problem properly are welcome.
> 
> Once upon a time, Sami Wagiaalla wrote some patches to do this.
> I don't believe they ever went in.  I don't remember why any more.
> However, perhaps they could be resurrected.  They were sent to
> gdb-patches, years ago now.
> 

Thank you for the pointer. I think this is the patch you're referring to:

https://sourceware.org/ml/gdb-patches/2010-07/msg00284.html

We'll check the contents.

-Baris

Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Gary Kershaw
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928

RE: Infcall of a template function in a C++ program

[Aktemur, Tankut Baris]

* On Tuesday, July 23, 2019 4:51 PM, Keith Seitz wrote:
> 
> On 7/19/19 1:12 PM, Tom Tromey wrote:
> >
> > The "compile" command might also be promising here, though I don't know
> > how well the C++ support handles templates.  It's a difficult problem
> > given the way the "compile" command was designed, because the source
> > isn't available and DWARF doesn't represent templates, only
> > instantiations.
> 
> For the record: the upstream C++ compile feature does not include any template
> support at all. I do have some patches to start this process, but it
> is stalled on a number of outstanding issues (unresolved bugs, unreviewed
> patch(es?), etc).
> 
> Keith

Are these patches available in some accessible branch?

-Baris

Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Gary Kershaw
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928

Re: Infcall of a template function in a C++ program

[Keith Seitz]

On 7/23/19 9:24 AM, Aktemur, Tankut Baris wrote:
> 
> Are these patches available in some accessible branch?
> 

I have a public branch that contains some or all of it?

  origin/users/keiths/c++compile-submit

But that branch has undoubtedly bitrotted a /lot/. [I might have more
recent update locally, I don't recall off the top of my head.]

I know that

https://sourceware.org/bugzilla/show_bug.cgi?id=23749

has prevented things from working for a while... It's not a difficult
thing to fix IIRC, but my changing job role has severely impacted my 
availability to do development work.

[Note that the C++ compile feature template support on that branch is
highly incomplete. It cannot handle libstdc++ yet -- just basic class
and function templates. There's a *lot* of work to be completed on that
before it will even be minimally useful.]

Keith