[PATCH 2/2] C FE: suggest corrections for misspelled field names

[David Malcolm <dmalcolm@redhat.com>]

This is similar to the field-name part of the v2 patch:
 https://gcc.gnu.org/ml/gcc-patches/2015-09/msg01090.html
with the following changes:
  - don't call unit tests from lookup_field_fuzzy
    (instead, see patch 1 in the kit)
  - use a cutoff: if more than half of the letters
    were misspelled, the suggestion is likely to
    be meaningless, so don't offer it.
  - more test coverage
  - deferral of the hints for type-name lookup (this can
    wait to a later patch, since it seemed more
    controversial)

gcc/c/ChangeLog:
	* c-typeck.c: Include spellcheck.h.
	(lookup_field_fuzzy_find_candidates): New function.
	(lookup_field_fuzzy): New function.
	(build_component_ref): If the field was not found, try using
	lookup_field_fuzzy and potentially offer a suggestion.

gcc/testsuite/ChangeLog:
	* gcc.dg/spellcheck-fields.c: New file.
---
 gcc/c/c-typeck.c                         | 74 +++++++++++++++++++++++++++++++-
 gcc/testsuite/gcc.dg/spellcheck-fields.c | 63 +++++++++++++++++++++++++++
 2 files changed, 136 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/spellcheck-fields.c

diff --git a/gcc/c/c-typeck.c b/gcc/c/c-typeck.c
index 61c5313..0660610 100644
--- a/gcc/c/c-typeck.c
+++ b/gcc/c/c-typeck.c
@@ -54,6 +54,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "c-family/c-ubsan.h"
 #include "cilk.h"
 #include "gomp-constants.h"
+#include "spellcheck.h"
 
 /* Possible cases of implicit bad conversions.  Used to select
    diagnostic messages in convert_for_assignment.  */
@@ -2249,6 +2250,72 @@ lookup_field (tree type, tree component)
   return tree_cons (NULL_TREE, field, NULL_TREE);
 }
 
+/* Recursively append candidate IDENTIFIER_NODEs to CANDIDATES.  */
+
+static void
+lookup_field_fuzzy_find_candidates (tree type, tree component,
+				    vec<tree> *candidates)
+{
+  tree field;
+  for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
+    {
+      if (DECL_NAME (field) == NULL_TREE
+	  && (TREE_CODE (TREE_TYPE (field)) == RECORD_TYPE
+	      || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
+	{
+	  lookup_field_fuzzy_find_candidates (TREE_TYPE (field),
+					      component,
+					      candidates);
+	}
+
+      if (DECL_NAME (field))
+	candidates->safe_push (DECL_NAME (field));
+    }
+}
+
+/* Like "lookup_field", but find the closest matching IDENTIFIER_NODE,
+   rather than returning a TREE_LIST for an exact match.  */
+
+static tree
+lookup_field_fuzzy (tree type, tree component)
+{
+  gcc_assert (TREE_CODE (component) == IDENTIFIER_NODE);
+
+  /* First, gather a list of candidates.  */
+  auto_vec <tree> candidates;
+
+  lookup_field_fuzzy_find_candidates (type, component,
+				      &candidates);
+
+  /* Now determine which is closest.  */
+  int i;
+  tree identifier;
+  tree best_identifier = NULL;
+  edit_distance_t best_distance = MAX_EDIT_DISTANCE;
+  FOR_EACH_VEC_ELT (candidates, i, identifier)
+    {
+      gcc_assert (TREE_CODE (identifier) == IDENTIFIER_NODE);
+      edit_distance_t dist = levenshtein_distance (component, identifier);
+      if (dist < best_distance)
+	{
+	  best_distance = dist;
+	  best_identifier = identifier;
+	}
+    }
+
+  /* If more than half of the letters were misspelled, the suggestion is
+     likely to be meaningless.  */
+  if (best_identifier)
+    {
+      unsigned int cutoff = MAX (IDENTIFIER_LENGTH (component),
+				 IDENTIFIER_LENGTH (best_identifier)) / 2;
+      if (best_distance > cutoff)
+	return NULL;
+    }
+
+  return best_identifier;
+}
+
 /* Make an expression to refer to the COMPONENT field of structure or
    union value DATUM.  COMPONENT is an IDENTIFIER_NODE.  LOC is the
    location of the COMPONENT_REF.  */
@@ -2284,7 +2351,12 @@ build_component_ref (location_t loc, tree datum, tree component)
 
       if (!field)
 	{
-	  error_at (loc, "%qT has no member named %qE", type, component);
+	  tree guessed_id = lookup_field_fuzzy (type, component);
+	  if (guessed_id)
+	    error_at (loc, "%qT has no member named %qE; did you mean %qE?",
+		      type, component, guessed_id);
+	  else
+	    error_at (loc, "%qT has no member named %qE", type, component);
 	  return error_mark_node;
 	}
 
diff --git a/gcc/testsuite/gcc.dg/spellcheck-fields.c b/gcc/testsuite/gcc.dg/spellcheck-fields.c
new file mode 100644
index 0000000..01be550
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/spellcheck-fields.c
@@ -0,0 +1,63 @@
+/* { dg-do compile } */
+
+struct foo
+{
+  int foo;
+  int bar;
+  int baz;
+};
+
+int test (struct foo *ptr)
+{
+  return ptr->m_bar; /* { dg-error "'struct foo' has no member named 'm_bar'; did you mean 'bar'?" } */
+}
+
+int test2 (void)
+{
+  struct foo instance = {0, 0, 0};
+  return instance.m_bar; /* { dg-error "'struct foo' has no member named 'm_bar'; did you mean 'bar'?" } */
+}
+
+struct s {
+    struct j { int aa; } kk;
+    int ab;
+};
+
+void test3 (struct s x)
+{
+  x.ac;  /* { dg-error "'struct s' has no member named 'ac'; did you mean 'ab'?" } */
+}
+
+int test4 (struct foo *ptr)
+{
+  return sizeof (ptr->foa); /* { dg-error "'struct foo' has no member named 'foa'; did you mean 'foo'?" } */
+}
+
+/* Verify that we don't offer nonsensical suggestions.  */
+
+int test5 (struct foo *ptr)
+{
+  return ptr->this_is_unlike_any_of_the_fields;   /* { dg-bogus "did you mean" } */
+  /* { dg-error "has no member named" "" { target *-*-* } 40 } */
+}
+
+union u
+{
+  int color;
+  int shape;
+};
+
+int test6 (union u *ptr)
+{
+  return ptr->colour; /* { dg-error "'union u' has no member named 'colour'; did you mean 'color'?" } */
+}
+
+struct has_anon
+{
+  struct { int color; } s;
+};
+
+int test7 (struct has_anon *ptr)
+{
+  return ptr->s.colour; /* { dg-error "'struct <anonymous>' has no member named 'colour'; did you mean 'color'?" } */
+}
-- 
1.8.5.3