gcc/spellcheck.c

   1 /* Find near-matches for strings.
   2    Copyright (C) 2015-2016 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "tree.h"
  25 #include "spellcheck.h"
  26 #include "selftest.h"
  27
  28 /* The Levenshtein distance is an "edit-distance": the minimal
  29    number of one-character insertions, removals or substitutions
  30    that are needed to change one string into another.
  31
  32    This implementation uses the Wagner-Fischer algorithm.  */
  33
  34 edit_distance_t
  35 levenshtein_distance (const char *s, int len_s,
  36                       const char *t, int len_t)
  37 {
  38   const bool debug = false;
  39
  40   if (debug)
  41     {
  42       printf ("s: \"%s\" (len_s=%i)\n", s, len_s);
  43       printf ("t: \"%s\" (len_t=%i)\n", t, len_t);
  44     }
  45
  46   if (len_s == 0)
  47     return len_t;
  48   if (len_t == 0)
  49     return len_s;
  50
  51   /* We effectively build a matrix where each (i, j) contains the
  52      Levenshtein distance between the prefix strings s[0:j]
  53      and t[0:i].
  54      Rather than actually build an (len_t + 1) * (len_s + 1) matrix,
  55      we simply keep track of the last row, v0 and a new row, v1,
  56      which avoids an (len_t + 1) * (len_s + 1) allocation and memory accesses
  57      in favor of two (len_s + 1) allocations.  These could potentially be
  58      statically-allocated if we impose a maximum length on the
  59      strings of interest.  */
  60   edit_distance_t *v0 = new edit_distance_t[len_s + 1];
  61   edit_distance_t *v1 = new edit_distance_t[len_s + 1];
  62
  63   /* The first row is for the case of an empty target string, which
  64      we can reach by deleting every character in the source string.  */
  65   for (int i = 0; i < len_s + 1; i++)
  66     v0[i] = i;
  67
  68   /* Build successive rows.  */
  69   for (int i = 0; i < len_t; i++)
  70     {
  71       if (debug)
  72         {
  73           printf ("i:%i v0 = ", i);
  74           for (int j = 0; j < len_s + 1; j++)
  75             printf ("%i ", v0[j]);
  76           printf ("\n");
  77         }
  78
  79       /* The initial column is for the case of an empty source string; we
  80          can reach prefixes of the target string of length i
  81          by inserting i characters.  */
  82       v1[0] = i + 1;
  83
  84       /* Build the rest of the row by considering neighbors to
  85          the north, west and northwest.  */
  86       for (int j = 0; j < len_s; j++)
  87         {
  88           edit_distance_t cost = (s[j] == t[i] ? 0 : 1);
  89           edit_distance_t deletion     = v1[j] + 1;
  90           edit_distance_t insertion    = v0[j + 1] + 1;
  91           edit_distance_t substitution = v0[j] + cost;
  92           edit_distance_t cheapest = MIN (deletion, insertion);
  93           cheapest = MIN (cheapest, substitution);
  94           v1[j + 1] = cheapest;
  95         }
  96
  97       /* Prepare to move on to next row.  */
  98       for (int j = 0; j < len_s + 1; j++)
  99         v0[j] = v1[j];
 100     }
 101
 102   if (debug)
 103     {
 104       printf ("final v1 = ");
 105       for (int j = 0; j < len_s + 1; j++)
 106         printf ("%i ", v1[j]);
 107       printf ("\n");
 108     }
 109
 110   edit_distance_t result = v1[len_s];
 111   delete[] v0;
 112   delete[] v1;
 113   return result;
 114 }
 115
 116 /* Calculate Levenshtein distance between two nil-terminated strings.  */
 117
 118 edit_distance_t
 119 levenshtein_distance (const char *s, const char *t)
 120 {
 121   return levenshtein_distance (s, strlen (s), t, strlen (t));
 122 }
 123
 124 /* Specialization of edit_distance_traits for C-style strings.  */
 125
 126 template <>
 127 struct edit_distance_traits<const char *>
 128 {
 129   static size_t get_length (const char *str)
 130   {
 131     gcc_assert (str);
 132     return strlen (str);
 133   }
 134
 135   static const char *get_string (const char *str)
 136   {
 137     gcc_assert (str);
 138     return str;
 139   }
 140 };
 141
 142 /* Given TARGET, a non-NULL string, and CANDIDATES, a non-NULL ptr to
 143    an autovec of non-NULL strings, determine which element within
 144    CANDIDATES has the lowest edit distance to TARGET.  If there are
 145    multiple elements with the same minimal distance, the first in the
 146    vector wins.
 147
 148    If more than half of the letters were misspelled, the suggestion is
 149    likely to be meaningless, so return NULL for this case.  */
 150
 151 const char *
 152 find_closest_string (const char *target,
 153                      const auto_vec<const char *> *candidates)
 154 {
 155   gcc_assert (target);
 156   gcc_assert (candidates);
 157
 158   int i;
 159   const char *candidate;
 160   best_match<const char *, const char *> bm (target);
 161   FOR_EACH_VEC_ELT (*candidates, i, candidate)
 162     {
 163       gcc_assert (candidate);
 164       bm.consider (candidate);
 165     }
 166
 167   return bm.get_best_meaningful_candidate ();
 168 }
 169
 170 #if CHECKING_P
 171
 172 namespace selftest {
 173
 174 /* Selftests.  */
 175
 176 /* Verify that the levenshtein_distance (A, B) equals the expected
 177    value.  */
 178
 179 static void
 180 levenshtein_distance_unit_test_oneway (const char *a, const char *b,
 181                                        edit_distance_t expected)
 182 {
 183   edit_distance_t actual = levenshtein_distance (a, b);
 184   ASSERT_EQ (actual, expected);
 185 }
 186
 187 /* Verify that both
 188      levenshtein_distance (A, B)
 189    and
 190      levenshtein_distance (B, A)
 191    equal the expected value, to ensure that the function is symmetric.  */
 192
 193 static void
 194 levenshtein_distance_unit_test (const char *a, const char *b,
 195                                 edit_distance_t expected)
 196 {
 197   levenshtein_distance_unit_test_oneway (a, b, expected);
 198   levenshtein_distance_unit_test_oneway (b, a, expected);
 199 }
 200
 201 /* Verify that find_closest_string is sane.  */
 202
 203 static void
 204 test_find_closest_string ()
 205 {
 206   auto_vec<const char *> candidates;
 207
 208   /* Verify that it can handle an empty vec.  */
 209   ASSERT_EQ (NULL, find_closest_string ("", &candidates));
 210
 211   /* Verify that it works sanely for non-empty vecs.  */
 212   candidates.safe_push ("apple");
 213   candidates.safe_push ("banana");
 214   candidates.safe_push ("cherry");
 215
 216   ASSERT_STREQ ("apple", find_closest_string ("app", &candidates));
 217   ASSERT_STREQ ("banana", find_closest_string ("banyan", &candidates));
 218   ASSERT_STREQ ("cherry", find_closest_string ("berry", &candidates));
 219   ASSERT_EQ (NULL, find_closest_string ("not like the others", &candidates));
 220
 221   /* The order of the vec can matter, but it should not matter for these
 222      inputs.  */
 223   candidates.truncate (0);
 224   candidates.safe_push ("cherry");
 225   candidates.safe_push ("banana");
 226   candidates.safe_push ("apple");
 227   ASSERT_STREQ ("apple", find_closest_string ("app", &candidates));
 228   ASSERT_STREQ ("banana", find_closest_string ("banyan", &candidates));
 229   ASSERT_STREQ ("cherry", find_closest_string ("berry", &candidates));
 230   ASSERT_EQ (NULL, find_closest_string ("not like the others", &candidates));
 231 }
 232
 233 /* Test data for test_metric_conditions.  */
 234
 235 static const char * const test_data[] = {
 236   "",
 237   "foo"
 238   "food",
 239   "boo",
 240   "1234567890123456789012345678901234567890123456789012345678901234567890"
 241 };
 242
 243 /* Verify that levenshtein_distance appears to be a sane distance function,
 244    i.e. the conditions for being a metric.  This is done directly for a
 245    small set of examples, using test_data above.  This is O(N^3) in the size
 246    of the array, due to the test for the triangle inequality, so we keep the
 247    array small.  */
 248
 249 static void
 250 test_metric_conditions ()
 251 {
 252   const int num_test_cases = sizeof (test_data) / sizeof (test_data[0]);
 253
 254   for (int i = 0; i < num_test_cases; i++)
 255     {
 256       for (int j = 0; j < num_test_cases; j++)
 257         {
 258           edit_distance_t dist_ij
 259             = levenshtein_distance (test_data[i], test_data[j]);
 260
 261           /* Identity of indiscernibles: d(i, j) > 0 iff i == j.  */
 262           if (i == j)
 263             ASSERT_EQ (dist_ij, 0);
 264           else
 265             ASSERT_TRUE (dist_ij > 0);
 266
 267           /* Symmetry: d(i, j) == d(j, i).  */
 268           edit_distance_t dist_ji
 269             = levenshtein_distance (test_data[j], test_data[i]);
 270           ASSERT_EQ (dist_ij, dist_ji);
 271
 272           /* Triangle inequality.  */
 273           for (int k = 0; k < num_test_cases; k++)
 274             {
 275               edit_distance_t dist_ik
 276                 = levenshtein_distance (test_data[i], test_data[k]);
 277               edit_distance_t dist_jk
 278                 = levenshtein_distance (test_data[j], test_data[k]);
 279               ASSERT_TRUE (dist_ik <= dist_ij + dist_jk);
 280             }
 281         }
 282     }
 283 }
 284
 285 /* Verify levenshtein_distance for a variety of pairs of pre-canned
 286    inputs, comparing against known-good values.  */
 287
 288 void
 289 spellcheck_c_tests ()
 290 {
 291   levenshtein_distance_unit_test ("", "nonempty", strlen ("nonempty"));
 292   levenshtein_distance_unit_test ("saturday", "sunday", 3);
 293   levenshtein_distance_unit_test ("foo", "m_foo", 2);
 294   levenshtein_distance_unit_test ("hello_world", "HelloWorld", 3);
 295   levenshtein_distance_unit_test
 296     ("the quick brown fox jumps over the lazy dog", "dog", 40);
 297   levenshtein_distance_unit_test
 298     ("the quick brown fox jumps over the lazy dog",
 299      "the quick brown dog jumps over the lazy fox",
 300      4);
 301   levenshtein_distance_unit_test
 302     ("Lorem ipsum dolor sit amet, consectetur adipiscing elit,",
 303      "All your base are belong to us",
 304      44);
 305   levenshtein_distance_unit_test ("foo", "FOO", 3);
 306
 307   test_find_closest_string ();
 308   test_metric_conditions ();
 309 }
 310
 311 } // namespace selftest
 312
 313 #endif /* #if CHECKING_P */