v2 Re: [PATCH] RFC: Use Levenshtein spelling suggestions in Fortran FE

On Sat, 2015-12-05 at 20:53 +0100, Mikael Morin wrote:
> Hello,
> 
> to get things moving again, a few comments on top of David Malcolm's:
> 
> Le 01/12/2015 13:55, Bernhard Reutner-Fischer a écrit :
> >
> > David Malcolm nice Levenshtein distance spelling check helpers
> > were used in some parts of other frontends. This proposed patch adds
> > some spelling corrections to the fortran frontend.
> >
> > Suggestions are printed if we can find a suitable name, currently
> > perusing a very simple cutoff factor:
> > /* If more than half of the letters were misspelled, the suggestion is
> >     likely to be meaningless.  */
> > cutoff = MAX (strlen (typo), strlen (best_guess)) / 2;
> > which effectively skips names with less than 4 characters.
> > For e.g. structures, one could try to be much smarter in an attempt to
> > also provide suggestions for single-letter members/components.
> >
> > This patch covers (at least partly):
> > - user-defined operators
> > - structures (types and their components)
> > - functions
> > - symbols (variables)
> >
> > I do not immediately see how to handle subroutines. Ideas?
> >
> Not sure what you are looking for; I can get an error generated in 
> gfc_procedure_use if using IMPLICIT NONE (EXTERNAL)
> 
> > If anybody has a testcase where a spelling-suggestion would make sense
> > then please pass it along so we maybe can add support for GCC-7.
> >
> 
> 
> > diff --git a/gcc/fortran/resolve.c b/gcc/fortran/resolve.c
> > index 685e3f5..6e1f63c 100644
> > --- a/gcc/fortran/resolve.c
> > +++ b/gcc/fortran/resolve.c
> > @@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.  If not see
> >   #include "data.h"
> >   #include "target-memory.h" /* for gfc_simplify_transfer */
> >   #include "constructor.h"
> > +#include "spellcheck.h"
> >
> >   /* Types used in equivalence statements.  */
> >
> > @@ -2682,6 +2683,61 @@ resolve_specific_f (gfc_expr *expr)
> >     return true;
> >   }
> >
> > +/* Recursively append candidate SYM to CANDIDATES.  */
> > +
> > +static void
> > +lookup_function_fuzzy_find_candidates (gfc_symtree *sym,
> > +                                       vec<const char *> *candidates)
> > +{
> > +  gfc_symtree *p;
> > +  for (p = sym->right; p; p = p->right)
> > +    {
> > +      lookup_function_fuzzy_find_candidates (p, candidates);
> > +      if (p->n.sym->ts.type != BT_UNKNOWN)
> > +	candidates->safe_push (p->name);
> > +    }
> > +  for (p = sym->left; p; p = p->left)
> > +    {
> > +      lookup_function_fuzzy_find_candidates (p, candidates);
> > +      if (p->n.sym->ts.type != BT_UNKNOWN)
> > +	candidates->safe_push (p->name);
> > +    }
> > +}
> 
> It seems you are considering some candidates more than once here.
> The first time through the recursive call you will consider say 
> sym->right->right, and with the loop, you'll consider it again after 
> returning from the recursive call.
> The usual way to traverse the whole tree is to handle the current 
> pointer and recurse on left and right pointers.  So without loop.
> There is gfc_traverse_ns that you might find handy to do that (no 
> obligation).
> 
> Same goes for the user operators below.
> 
> > +
> > +
> > +/* Lookup function FN fuzzily, taking names in FUN into account.  */
> > +
> > +const char*
> > +gfc_lookup_function_fuzzy (const char *fn, gfc_symtree *fun)
> > +{
> > +  auto_vec <const char *> candidates;
> > +  lookup_function_fuzzy_find_candidates (fun, &candidates);
> 
> You have to start the lookup with the current namespace's sym_root (not 
> with fun), otherwise you'll miss some candidates.
> You may also want to query parent namespaces for host-associated symbols.
> 
> > +
> > +  /* Determine closest match.  */
> > +  int i;
> > +  const char *name, *best = NULL;
> > +  edit_distance_t best_distance = MAX_EDIT_DISTANCE;
> > +
> 
> [...]
> 
> > diff --git a/gcc/fortran/symbol.c b/gcc/fortran/symbol.c
> > index ff9aff9..212f7d8 100644
> > --- a/gcc/fortran/symbol.c
> > +++ b/gcc/fortran/symbol.c
> > @@ -27,6 +27,7 @@ along with GCC; see the file COPYING3.  If not see
> >   #include "parse.h"
> >   #include "match.h"
> >   #include "constructor.h"
> > +#include "spellcheck.h"
> >
> >
> >   /* Strings for all symbol attributes.  We use these for dumping the
> > @@ -235,6 +236,62 @@ gfc_get_default_type (const char *name, gfc_namespace *ns)
> >   }
> >
> >
> > +/* Recursively append candidate SYM to CANDIDATES.  */
> > +
> > +static void
> > +lookup_symbol_fuzzy_find_candidates (gfc_symtree *sym,
> > +				        vec<const char *> *candidates)
> > +{
> > +  gfc_symtree *p;
> > +  for (p = sym->right; p; p = p->right)
> > +    {
> > +      lookup_symbol_fuzzy_find_candidates (p, candidates);
> > +      if (p->n.sym->ts.type != BT_UNKNOWN)
> > +	candidates->safe_push (p->name);
> > +    }
> > +  for (p = sym->left; p; p = p->left)
> > +    {
> > +      lookup_symbol_fuzzy_find_candidates (p, candidates);
> > +      if (p->n.sym->ts.type != BT_UNKNOWN)
> > +	candidates->safe_push (p->name);
> > +    }
> > +}
> This looks like the same as lookup_function_fuzzy_find_candidates, isn't it?
> Maybe have a general symbol traversal function with a selection callback 
> argument to test whether the symbol is what you want, depending on the 
> context (is it a function? a subroutine? etc).
> 
> > +
> > +
> > +/* Lookup symbol SYM fuzzily, taking names in SYMBOL into account.  */
> > +
> > +static const char*
> > +lookup_symbol_fuzzy (const char *sym, gfc_symbol *symbol)
> > +{
> > +  auto_vec <const char *> candidates;
> > +  lookup_symbol_fuzzy_find_candidates (symbol->ns->sym_root, &candidates);
> > +
> > +  /* Determine closest match.  */
> > +  int i;
> > +  const char *name, *best = NULL;
> > +  edit_distance_t best_distance = MAX_EDIT_DISTANCE;
> > +
> > +  FOR_EACH_VEC_ELT (candidates, i, name)
> > +    {
> > +      edit_distance_t dist = levenshtein_distance (sym, name);
> > +      if (dist < best_distance)
> > +	{
> > +	  best_distance = dist;
> > +	  best = name;
> > +	}
> > +    }
> > +  /* If more than half of the letters were misspelled, the suggestion is
> > +     likely to be meaningless.  */
> > +  if (best)
> > +    {
> > +      unsigned int cutoff = MAX (strlen (sym), strlen (best)) / 2;
> > +      if (best_distance > cutoff)
> > +	return NULL;
> > +    }
> > +  return best;
> > +}
> > +
> > +
> >   /* Given a pointer to a symbol, set its type according to the first
> >      letter of its name.  Fails if the letter in question has no default
> >      type.  */
> > @@ -253,8 +310,15 @@ gfc_set_default_type (gfc_symbol *sym, int error_flag, gfc_namespace *ns)
> >       {
> >         if (error_flag && !sym->attr.untyped)
> >   	{
> > -	  gfc_error ("Symbol %qs at %L has no IMPLICIT type",
> > -		     sym->name, &sym->declared_at);
> > +	  const char *guessed
> > +	    = lookup_symbol_fuzzy (sym->name, sym);
> > +	  if (guessed)
> > +	    gfc_error ("Symbol %qs at %L has no IMPLICIT type"
> > +		       "; did you mean %qs?",
> > +		       sym->name, &sym->declared_at, guessed);
> > +	  else
> > +	    gfc_error ("Symbol %qs at %L has no IMPLICIT type",
> > +		       sym->name, &sym->declared_at);
> >   	  sym->attr.untyped = 1; /* Ensure we only give an error once.  */
> >   	}
> >
> > @@ -2188,6 +2252,55 @@ bad:
> >   }
> >
> >
> > +/* Recursively append candidate COMPONENT structures to CANDIDATES.  */
> > +
> > +static void
> > +lookup_component_fuzzy_find_candidates (gfc_component *component,
> > +				        vec<const char *> *candidates)
> > +{
> > +  for (gfc_component *p = component; p; p = p->next)
> > +    {
> > +      if (00 && p->ts.type == BT_DERIVED)
> > +	/* ??? There's no (suitable) DERIVED_TYPE which would come in
> > +	   handy throughout the frontend; Use CLASS_DATA here for brevity.  */
> > +	lookup_component_fuzzy_find_candidates (CLASS_DATA (p), candidates);
> I don't understand what you are looking for here.
> Are you trying to handle type extension?  Then I guess you would have to 
> pass the derived type symbol instead of its components, and use 
> gfc_get_derived_super_type to retrieve the parent type.

I can't comment on Mikael's observations, but here's an updated version
of Bernhard's patch which moves the duplicated code into a new
"find_closest_string" function in gcc/spellcheck.c.  
With that, the lookup_*_fuzzy functions are all of the form:

{
  auto_vec <const char *> candidates;

  /* call something to populate candidates e.g.: */
  lookup_function_fuzzy_find_candidates (fun, &candidates);

  return find_closest_string (fn, &candidates);
}

where, as before, the auto_vec is implicitly cleaned up via a
C++ destructor as the function exits.  Hopefully with this change it
reduces the amount of proposed C++ in the fortran subdirectory to an
palatable amount.

That's all I did; I didn't address the other issues seen in this thread
(e.g. Mikael's notes above).

Not yet well-tested; it compiles and passes the new test cases; I'm
posting it here in case someone more familiar with the Fortran FE wants
to take this forward (Bernhard?)

Hope this is constructive
Dave

v2 Re: [PATCH] RFC: Use Levenshtein spelling suggestions in Fortran FE

Commit Message

Comments

Patch