[PATCH] c/c++: Add fix-it hints for suggested missing #includes

[David Malcolm <dmalcolm@redhat.com>]

As of r247522, fix-it-hints can suggest the insertion of new lines.

This patch uses this to implement a new "maybe_add_include_fixit"
function in c-common.c and uses it in the two places where the C and C++
frontend can suggest missing #include directives. [1]

The idea is that the user can then click on the fix-it in an IDE
and have it add the #include for them (or use -fdiagnostics-generate-patch).

Examples can be seen in the test cases.

The function attempts to put the #include in a reasonable place:
immediately after the last #include within the file, or at the
top of the file.  It is idempotent, so -fdiagnostics-generate-patch
does the right thing if several such diagnostics are emitted.

Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

OK for trunk?

[1] I'm working on a followup which tweaks another diagnostic so that it
can suggest that a #include was missing, so I'll use it there as well.

gcc/c-family/ChangeLog:
	* c-common.c (try_to_locate_new_include_insertion_point): New
	function.
	(per_file_includes_t): New typedef.
	(added_includes_t): New typedef.
	(added_includes): New variable.
	(maybe_add_include_fixit): New function.
	* c-common.h (maybe_add_include_fixit): New decl.

gcc/c/ChangeLog:
	* c-decl.c (implicitly_declare): When suggesting a missing
	#include, provide a fix-it hint.

gcc/cp/ChangeLog:
	* name-lookup.c (get_std_name_hint): Add '<' and '>' around
	the header names.
	(maybe_suggest_missing_header): Update for addition of '<' and '>'
	to above.  Provide a fix-it hint.

gcc/testsuite/ChangeLog:
	* g++.dg/lookup/missing-std-include-2.C: New text case.
	* gcc.dg/missing-header-fixit-1.c: New test case.
---
 gcc/c-family/c-common.c                            | 117 +++++++++++++++++++++
 gcc/c-family/c-common.h                            |   2 +
 gcc/c/c-decl.c                                     |  10 +-
 gcc/cp/name-lookup.c                               |  94 +++++++++--------
 .../g++.dg/lookup/missing-std-include-2.C          |  55 ++++++++++
 gcc/testsuite/gcc.dg/missing-header-fixit-1.c      |  36 +++++++
 6 files changed, 267 insertions(+), 47 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/lookup/missing-std-include-2.C
 create mode 100644 gcc/testsuite/gcc.dg/missing-header-fixit-1.c

diff --git a/gcc/c-family/c-common.c b/gcc/c-family/c-common.c
index 0884922..19f7e60 100644
--- a/gcc/c-family/c-common.c
+++ b/gcc/c-family/c-common.c
@@ -7983,4 +7983,121 @@ c_flt_eval_method (bool maybe_c11_only_p)
     return c_ts18661_flt_eval_method ();
 }
 
+/* Attempt to locate a suitable location within FILE for a
+   #include directive to be inserted before.  FILE should
+   be a string from libcpp (pointer equality is used).
+
+   Attempt to return the location within FILE immediately
+   after the last #include within that file, or the start of
+   that file if it has no #include directives.
+
+   Return UNKNOWN_LOCATION if no suitable location is found,
+   or if an error occurs.  */
+
+static location_t
+try_to_locate_new_include_insertion_point (const char *file)
+{
+  /* Locate the last ordinary map within FILE that ended with a #include.  */
+  const line_map_ordinary *last_include_ord_map = NULL;
+
+  /* ...and the next ordinary map within FILE after that one.  */
+  const line_map_ordinary *last_ord_map_after_include = NULL;
+
+  /* ...and the first ordinary map within FILE.  */
+  const line_map_ordinary *first_ord_map_in_file = NULL;
+
+  for (unsigned int i = 0; i < LINEMAPS_ORDINARY_USED (line_table); i++)
+    {
+      const line_map_ordinary *ord_map
+	= LINEMAPS_ORDINARY_MAP_AT (line_table, i);
+
+      const line_map_ordinary *from = INCLUDED_FROM (line_table, ord_map);
+      if (from)
+	if (from->to_file == file)
+	  {
+	    last_include_ord_map = from;
+	    last_ord_map_after_include = NULL;
+	  }
+
+      if (ord_map->to_file == file)
+	{
+	  if (!first_ord_map_in_file)
+	    first_ord_map_in_file = ord_map;
+	  if (last_include_ord_map && !last_ord_map_after_include)
+	    last_ord_map_after_include = ord_map;
+	}
+    }
+
+  /* Determine where to insert the #include.  */
+  const line_map_ordinary *ord_map_for_insertion;
+
+  /* We want the next ordmap in the file after the last one that's a
+     #include, but failing that, the start of the file.  */
+  if (last_ord_map_after_include)
+    ord_map_for_insertion = last_ord_map_after_include;
+  else
+    ord_map_for_insertion = first_ord_map_in_file;
+
+  if (!ord_map_for_insertion)
+    return UNKNOWN_LOCATION;
+
+  /* The "start_location" is column 0, meaning "the whole line".
+     rich_location and edit_context can't cope with this, so use
+     column 1 instead.  */
+  location_t col_0 = ord_map_for_insertion->start_location;
+  return linemap_position_for_loc_and_offset (line_table, col_0, 1);
+}
+
+/* A map from filenames to sets of headers added to them, for
+   ensuring idempotency within maybe_add_include_fixit.  */
+
+/* The values within the map.  We need string comparison as there's
+   no guarantee that two different diagnostics that are recommending
+   adding e.g. "<stdio.h>" are using the same buffer.  */
+
+typedef hash_set <const char *, nofree_string_hash> per_file_includes_t;
+
+/* The map itself.  We don't need string comparison for the filename keys,
+   as they come from libcpp.  */
+
+typedef hash_map <const char *, per_file_includes_t *> added_includes_t;
+static added_includes_t *added_includes;
+
+/* Attempt to add a fix-it hint to RICHLOC, adding "#include HEADER\n"
+   in a suitable location within the file of RICHLOC's primary
+   location.
+
+   This function is idempotent: a header will be added at most once to
+   any given file.  */
+
+void
+maybe_add_include_fixit (rich_location *richloc, const char *header)
+{
+  const char *file = LOCATION_FILE (richloc->get_loc ());
+  if (!file)
+    return;
+
+  /* Idempotency: don't add the same header more than once to a given file.  */
+  if (!added_includes)
+    added_includes = new added_includes_t ();
+  per_file_includes_t *&set = added_includes->get_or_insert (file);
+  if (set)
+    if (set->contains (header))
+      /* ...then we've already added HEADER to that file.  */
+      return;
+  if (!set)
+    set = new per_file_includes_t ();
+  set->add (header);
+
+  /* Attempt to locate a suitable place for the new directive.  */
+  location_t include_insert_loc
+    = try_to_locate_new_include_insertion_point (file);
+  if (include_insert_loc == UNKNOWN_LOCATION)
+    return;
+
+  char *text = xasprintf ("#include %s\n", header);
+  richloc->add_fixit_insert_before (include_insert_loc, text);
+  free (text);
+}
+
 #include "gt-c-family-c-common.h"
diff --git a/gcc/c-family/c-common.h b/gcc/c-family/c-common.h
index 138a0a6..ac8b1bf 100644
--- a/gcc/c-family/c-common.h
+++ b/gcc/c-family/c-common.h
@@ -1554,6 +1554,8 @@ excess_precision_mode_join (enum flt_eval_method, enum flt_eval_method);
 
 extern int c_flt_eval_method (bool ts18661_p);
 
+extern void maybe_add_include_fixit (rich_location *, const char *);
+
 #if CHECKING_P
 namespace selftest {
   extern void c_format_c_tests (void);
diff --git a/gcc/c/c-decl.c b/gcc/c/c-decl.c
index 64a1107..41a1728 100644
--- a/gcc/c/c-decl.c
+++ b/gcc/c/c-decl.c
@@ -3412,8 +3412,14 @@ implicitly_declare (location_t loc, tree functionid)
 		  const char *header
 		    = header_for_builtin_fn (DECL_FUNCTION_CODE (decl));
 		  if (header != NULL && warned)
-		    inform (loc, "include %qs or provide a declaration of %qD",
-			    header, decl);
+		    {
+		      rich_location richloc (line_table, loc);
+		      maybe_add_include_fixit (&richloc, header);
+		      inform_at_rich_loc
+			(&richloc,
+			 "include %qs or provide a declaration of %qD",
+			 header, decl);
+		    }
 		  newtype = TREE_TYPE (decl);
 		}
 	    }
diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
index 0c5df93..e6463b8 100644
--- a/gcc/cp/name-lookup.c
+++ b/gcc/cp/name-lookup.c
@@ -4540,7 +4540,7 @@ suggest_alternatives_for (location_t location, tree name,
 /* Subroutine of maybe_suggest_missing_header for handling unrecognized names
    for some of the most common names within "std::".
    Given non-NULL NAME, a name for lookup within "std::", return the header
-   name defining it within the C++ Standard Library (without '<' and '>'),
+   name defining it within the C++ Standard Library (with '<' and '>'),
    or NULL.  */
 
 static const char *
@@ -4553,61 +4553,61 @@ get_std_name_hint (const char *name)
   };
   static const std_name_hint hints[] = {
     /* <array>.  */
-    {"array", "array"}, // C++11
+    {"array", "<array>"}, // C++11
     /* <deque>.  */
-    {"deque", "deque"},
+    {"deque", "<deque>"},
     /* <forward_list>.  */
-    {"forward_list", "forward_list"},  // C++11
+    {"forward_list", "<forward_list>"},  // C++11
     /* <fstream>.  */
-    {"basic_filebuf", "fstream"},
-    {"basic_ifstream", "fstream"},
-    {"basic_ofstream", "fstream"},
-    {"basic_fstream", "fstream"},
+    {"basic_filebuf", "<fstream>"},
+    {"basic_ifstream", "<fstream>"},
+    {"basic_ofstream", "<fstream>"},
+    {"basic_fstream", "<fstream>"},
     /* <iostream>.  */
-    {"cin", "iostream"},
-    {"cout", "iostream"},
-    {"cerr", "iostream"},
-    {"clog", "iostream"},
-    {"wcin", "iostream"},
-    {"wcout", "iostream"},
-    {"wclog", "iostream"},
+    {"cin", "<iostream>"},
+    {"cout", "<iostream>"},
+    {"cerr", "<iostream>"},
+    {"clog", "<iostream>"},
+    {"wcin", "<iostream>"},
+    {"wcout", "<iostream>"},
+    {"wclog", "<iostream>"},
     /* <list>.  */
-    {"list", "list"},
+    {"list", "<list>"},
     /* <map>.  */
-    {"map", "map"},
-    {"multimap", "map"},
+    {"map", "<map>"},
+    {"multimap", "<map>"},
     /* <queue>.  */
-    {"queue", "queue"},
-    {"priority_queue", "queue"},
+    {"queue", "<queue>"},
+    {"priority_queue", "<queue>"},
     /* <ostream>.  */
-    {"ostream", "ostream"},
-    {"wostream", "ostream"},
-    {"ends", "ostream"},
-    {"flush", "ostream"},
-    {"endl", "ostream"},
+    {"ostream", "<ostream>"},
+    {"wostream", "<ostream>"},
+    {"ends", "<ostream>"},
+    {"flush", "<ostream>"},
+    {"endl", "<ostream>"},
     /* <set>.  */
-    {"set", "set"},
-    {"multiset", "set"},
+    {"set", "<set>"},
+    {"multiset", "<set>"},
     /* <sstream>.  */
-    {"basic_stringbuf", "sstream"},
-    {"basic_istringstream", "sstream"},
-    {"basic_ostringstream", "sstream"},
-    {"basic_stringstream", "sstream"},
+    {"basic_stringbuf", "<sstream>"},
+    {"basic_istringstream", "<sstream>"},
+    {"basic_ostringstream", "<sstream>"},
+    {"basic_stringstream", "<sstream>"},
     /* <stack>.  */
-    {"stack", "stack"},
+    {"stack", "<stack>"},
     /* <string>.  */
-    {"string", "string"},
-    {"wstring", "string"},
-    {"u16string", "string"},
-    {"u32string", "string"},
+    {"string", "<string>"},
+    {"wstring", "<string>"},
+    {"u16string", "<string>"},
+    {"u32string", "<string>"},
     /* <unordered_map>.  */
-    {"unordered_map", "unordered_map"}, // C++11
-    {"unordered_multimap", "unordered_map"}, // C++11
+    {"unordered_map", "<unordered_map>"}, // C++11
+    {"unordered_multimap", "<unordered_map>"}, // C++11
     /* <unordered_set>.  */
-    {"unordered_set", "unordered_set"}, // C++11
-    {"unordered_multiset", "unordered_set"}, // C++11
+    {"unordered_set", "<unordered_set>"}, // C++11
+    {"unordered_multiset", "<unordered_set>"}, // C++11
     /* <vector>.  */
-    {"vector", "vector"},
+    {"vector", "<vector>"},
   };
   const size_t num_hints = sizeof (hints) / sizeof (hints[0]);
   for (size_t i = 0; i < num_hints; i++)
@@ -4638,10 +4638,14 @@ maybe_suggest_missing_header (location_t location, tree name, tree scope)
   const char *name_str = IDENTIFIER_POINTER (name);
   const char *header_hint = get_std_name_hint (name_str);
   if (header_hint)
-    inform (location,
-	    "%<std::%s%> is defined in header %<<%s>%>;"
-	    " did you forget to %<#include <%s>%>?",
-	    name_str, header_hint, header_hint);
+    {
+      gcc_rich_location richloc (location);
+      maybe_add_include_fixit (&richloc, header_hint);
+      inform_at_rich_loc (&richloc,
+			  "%<std::%s%> is defined in header %qs;"
+			  " did you forget to %<#include %s%>?",
+			  name_str, header_hint, header_hint);
+    }
 }
 
 /* Look for alternatives for NAME, an IDENTIFIER_NODE for which name
diff --git a/gcc/testsuite/g++.dg/lookup/missing-std-include-2.C b/gcc/testsuite/g++.dg/lookup/missing-std-include-2.C
new file mode 100644
index 0000000..ae918f8
--- /dev/null
+++ b/gcc/testsuite/g++.dg/lookup/missing-std-include-2.C
@@ -0,0 +1,55 @@
+/* Example of fix-it hints that add #include directives,
+   adding them after a pre-existing #include.  */
+
+/* { dg-options "-fdiagnostics-generate-patch" } */
+
+/* This is padding (to avoid the generated patch containing DejaGnu
+   directives).  */
+
+#include <stdio.h>
+
+void test (void)
+{
+  std::string s ("hello world"); // { dg-error ".string. is not a member of .std." }
+  // { dg-message ".std::string. is defined in header .<string>.; did you forget to .#include <string>.?" "" { target *-*-* } .-1 }
+
+  std::cout << 10; // { dg-error ".cout. is not a member of .std." }
+  // { dg-message ".std::cout. is defined in header .<iostream>.; did you forget to .#include <iostream>.?" "" { target *-*-* } .-1 }
+}
+
+/* Same again, to test idempotency of the added "#include" fix-it.  */
+
+void test_2 (void)
+{
+  std::string s ("hello again"); // { dg-error ".string. is not a member of .std." }
+  // { dg-message ".std::string. is defined in header .<string>.; did you forget to .#include <string>.?" "" { target *-*-* } .-1 }
+
+  std::cout << 10; // { dg-error ".cout. is not a member of .std." }
+  // { dg-message ".std::cout. is defined in header .<iostream>.; did you forget to .#include <iostream>.?" "" { target *-*-* } .-1 }
+}
+
+/* Verify the output from -fdiagnostics-generate-patch.
+   We expect the patch to begin with a header, containing this
+   source filename, via an absolute path.
+   Given the path, we can only capture it via regexps.  */
+/* { dg-regexp "\\-\\-\\- .*" } */
+/* { dg-regexp "\\+\\+\\+ .*" } */
+
+/* Verify the hunks within the patch.
+   Use #if 0/#endif rather than comments, to allow the text to contain
+   a comment.
+   We expect a "#include <string>" and "#include <iostream>" to each have been
+   added once, immediately below the last #include.  */
+#if 0
+{ dg-begin-multiline-output "" }
+@@ -7,6 +7,8 @@
+    directives).  */
+ 
+ #include <stdio.h>
++#include <string>
++#include <iostream>
+ 
+ void test (void)
+ {
+{ dg-end-multiline-output "" }
+#endif
diff --git a/gcc/testsuite/gcc.dg/missing-header-fixit-1.c b/gcc/testsuite/gcc.dg/missing-header-fixit-1.c
new file mode 100644
index 0000000..2b28357
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/missing-header-fixit-1.c
@@ -0,0 +1,36 @@
+/* Example of a fix-it hint that adds a #include directive,
+   adding them to the top of the file, given that there is no
+   pre-existing #include.  */
+
+/* This is padding (to avoid the generated patch containing DejaGnu
+   directives).  */
+
+/* { dg-options "-fdiagnostics-generate-patch" } */
+
+void test (int i, int j)
+{
+  printf ("%i of %i\n", i, j); /* { dg-warning "implicit declaration" } */
+  /* { dg-message "include '<stdio.h>' or provide a declaration of 'printf'" "" { target *-*-* } .-1 } */
+}
+
+/* Verify the output from -fdiagnostics-generate-patch.
+   We expect the patch to begin with a header, containing this
+   source filename, via an absolute path.
+   Given the path, we can only capture it via regexps.  */
+/* { dg-regexp "\\-\\-\\- .*" } */
+/* { dg-regexp "\\+\\+\\+ .*" } */
+/* Use #if 0/#endif rather than comments, to allow the text to contain
+   a comment.  */
+#if 0
+{ dg-begin-multiline-output "" }
+@@ -1,3 +1,4 @@
++#include <stdio.h>
+ /* Example of a fix-it hint that adds a #include directive,
+    adding them to the top of the file, given that there is no
+    pre-existing #include.  */
+{ dg-end-multiline-output "" }
+#endif
+
+/* FIXME: should we attempt to skip leading comments when determining the
+   insertion location?
+   Similarly, should we attempt to be within single-inclusion guards, etc?  */
-- 
1.8.5.3