LCOV - code coverage report
Current view: top level - gcc - spellcheck.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 184 186 98.9 %
Date: 2020-04-04 11:58:09 Functions: 13 15 86.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Find near-matches for strings.
       2                 :            :    Copyright (C) 2015-2020 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                 :            : /* Get the edit distance between the two strings: the minimal
      29                 :            :    number of edits that are needed to change one string into another,
      30                 :            :    where edits can be one-character insertions, removals, or substitutions,
      31                 :            :    or transpositions of two adjacent characters (counting as one "edit").
      32                 :            : 
      33                 :            :    This implementation uses the Wagner-Fischer algorithm for the
      34                 :            :    Damerau-Levenshtein distance; specifically, the "optimal string alignment
      35                 :            :    distance" or "restricted edit distance" variant.  */
      36                 :            : 
      37                 :            : edit_distance_t
      38                 :    1969950 : get_edit_distance (const char *s, int len_s,
      39                 :            :                    const char *t, int len_t)
      40                 :            : {
      41                 :    1969950 :   const bool debug = false;
      42                 :            : 
      43                 :    1969950 :   if (debug)
      44                 :            :     {
      45                 :            :       printf ("s: \"%s\" (len_s=%i)\n", s, len_s);
      46                 :            :       printf ("t: \"%s\" (len_t=%i)\n", t, len_t);
      47                 :            :     }
      48                 :            : 
      49                 :    1969950 :   if (len_s == 0)
      50                 :        122 :     return len_t;
      51                 :    1969820 :   if (len_t == 0)
      52                 :         98 :     return len_s;
      53                 :            : 
      54                 :            :   /* We effectively build a matrix where each (i, j) contains the
      55                 :            :      distance between the prefix strings s[0:j] and t[0:i].
      56                 :            :      Rather than actually build an (len_t + 1) * (len_s + 1) matrix,
      57                 :            :      we simply keep track of the last two rows, v_one_ago and v_two_ago,
      58                 :            :      and a new row, v_next, which avoids an (len_t + 1) * (len_s + 1)
      59                 :            :      allocation and memory accesses in favor of three (len_s + 1)
      60                 :            :      allocations.  These could potentially be
      61                 :            :      statically-allocated if we impose a maximum length on the
      62                 :            :      strings of interest.  */
      63                 :    1969730 :   edit_distance_t *v_two_ago = new edit_distance_t[len_s + 1];
      64                 :    1969730 :   edit_distance_t *v_one_ago = new edit_distance_t[len_s + 1];
      65                 :    1969730 :   edit_distance_t *v_next = new edit_distance_t[len_s + 1];
      66                 :            : 
      67                 :            :   /* The first row is for the case of an empty target string, which
      68                 :            :      we can reach by deleting every character in the source string.  */
      69                 :   40527500 :   for (int i = 0; i < len_s + 1; i++)
      70                 :   38557800 :     v_one_ago[i] = i;
      71                 :            : 
      72                 :            :   /* Build successive rows.  */
      73                 :   37869800 :   for (int i = 0; i < len_t; i++)
      74                 :            :     {
      75                 :   35900100 :       if (debug)
      76                 :            :         {
      77                 :            :           printf ("i:%i v_one_ago = ", i);
      78                 :            :           for (int j = 0; j < len_s + 1; j++)
      79                 :            :             printf ("%i ", v_one_ago[j]);
      80                 :            :           printf ("\n");
      81                 :            :         }
      82                 :            : 
      83                 :            :       /* The initial column is for the case of an empty source string; we
      84                 :            :          can reach prefixes of the target string of length i
      85                 :            :          by inserting i characters.  */
      86                 :   35900100 :       v_next[0] = i + 1;
      87                 :            : 
      88                 :            :       /* Build the rest of the row by considering neighbors to
      89                 :            :          the north, west and northwest.  */
      90                 :  729999000 :       for (int j = 0; j < len_s; j++)
      91                 :            :         {
      92                 :  694099000 :           edit_distance_t cost = (s[j] == t[i] ? 0 : 1);
      93                 :  694099000 :           edit_distance_t deletion     = v_next[j] + 1;
      94                 :  694099000 :           edit_distance_t insertion    = v_one_ago[j + 1] + 1;
      95                 :  694099000 :           edit_distance_t substitution = v_one_ago[j] + cost;
      96                 :  694099000 :           edit_distance_t cheapest = MIN (deletion, insertion);
      97                 :  694099000 :           cheapest = MIN (cheapest, substitution);
      98                 :  694099000 :           if (i > 0 && j > 0 && s[j] == t[i - 1] && s[j - 1] == t[i])
      99                 :            :             {
     100                 :    3257790 :               edit_distance_t transposition = v_two_ago[j - 1] + 1;
     101                 :    3257790 :               cheapest = MIN (cheapest, transposition);
     102                 :            :             }
     103                 :  694099000 :           v_next[j + 1] = cheapest;
     104                 :            :         }
     105                 :            : 
     106                 :            :       /* Prepare to move on to next row.  */
     107                 :  765899000 :       for (int j = 0; j < len_s + 1; j++)
     108                 :            :         {
     109                 :  729999000 :           v_two_ago[j] = v_one_ago[j];
     110                 :  729999000 :           v_one_ago[j] = v_next[j];
     111                 :            :         }
     112                 :            :     }
     113                 :            : 
     114                 :    1969730 :   if (debug)
     115                 :            :     {
     116                 :            :       printf ("final v_next = ");
     117                 :            :       for (int j = 0; j < len_s + 1; j++)
     118                 :            :         printf ("%i ", v_next[j]);
     119                 :            :       printf ("\n");
     120                 :            :     }
     121                 :            : 
     122                 :    1969730 :   edit_distance_t result = v_next[len_s];
     123                 :    1969730 :   delete[] v_two_ago;
     124                 :    1969730 :   delete[] v_one_ago;
     125                 :    1969730 :   delete[] v_next;
     126                 :    1969730 :   return result;
     127                 :            : }
     128                 :            : 
     129                 :            : /* Get the edit distance between two nil-terminated strings.  */
     130                 :            : 
     131                 :            : edit_distance_t
     132                 :        720 : get_edit_distance (const char *s, const char *t)
     133                 :            : {
     134                 :        720 :   return get_edit_distance (s, strlen (s), t, strlen (t));
     135                 :            : }
     136                 :            : 
     137                 :            : /* Given TARGET, a non-NULL string, and CANDIDATES, a non-NULL ptr to
     138                 :            :    an autovec of non-NULL strings, determine which element within
     139                 :            :    CANDIDATES has the lowest edit distance to TARGET.  If there are
     140                 :            :    multiple elements with the same minimal distance, the first in the
     141                 :            :    vector wins.
     142                 :            : 
     143                 :            :    If more than half of the letters were misspelled, the suggestion is
     144                 :            :    likely to be meaningless, so return NULL for this case.  */
     145                 :            : 
     146                 :            : const char *
     147                 :        410 : find_closest_string (const char *target,
     148                 :            :                      const auto_vec<const char *> *candidates)
     149                 :            : {
     150                 :        410 :   gcc_assert (target);
     151                 :        410 :   gcc_assert (candidates);
     152                 :            : 
     153                 :        410 :   int i;
     154                 :        410 :   const char *candidate;
     155                 :        410 :   best_match<const char *, const char *> bm (target);
     156                 :    2611670 :   FOR_EACH_VEC_ELT (*candidates, i, candidate)
     157                 :            :     {
     158                 :    2611260 :       gcc_assert (candidate);
     159                 :    2611260 :       bm.consider (candidate);
     160                 :            :     }
     161                 :            : 
     162                 :        410 :   return bm.get_best_meaningful_candidate ();
     163                 :            : }
     164                 :            : 
     165                 :            : /* Generate the maximum edit distance for which we consider a suggestion
     166                 :            :    to be meaningful, given a goal of length GOAL_LEN and a candidate of
     167                 :            :    length CANDIDATE_LEN.
     168                 :            : 
     169                 :            :    This is a third of the length of the candidate or of the goal,
     170                 :            :    whichever is bigger.  */
     171                 :            : 
     172                 :            : edit_distance_t
     173                 :    2468650 : get_edit_distance_cutoff (size_t goal_len, size_t candidate_len)
     174                 :            : {
     175                 :    2468650 :   size_t max_length = MAX (goal_len, candidate_len);
     176                 :    2468650 :   size_t min_length = MIN (goal_len, candidate_len);
     177                 :            : 
     178                 :    2468650 :   gcc_assert (max_length >= min_length);
     179                 :            : 
     180                 :            :   /* Special case: don't offer suggestions for a pair of
     181                 :            :      length == 1 strings (or empty strings).  */
     182                 :    2468650 :   if (max_length <= 1)
     183                 :            :     return 0;
     184                 :            : 
     185                 :            :   /* If the lengths are close, then round down.  */
     186                 :    2460690 :   if (max_length - min_length <= 1)
     187                 :            :     /* ...but allow an edit distance of at least 1.  */
     188                 :     388041 :     return MAX (max_length / 3, 1);
     189                 :            : 
     190                 :            :   /* Otherwise, round up (thus giving a little extra leeway to some cases
     191                 :            :      involving insertions/deletions).  */
     192                 :    2072650 :   return (max_length + 2) / 3;
     193                 :            : }
     194                 :            : 
     195                 :            : #if CHECKING_P
     196                 :            : 
     197                 :            : namespace selftest {
     198                 :            : 
     199                 :            : /* Selftests.  */
     200                 :            : 
     201                 :            : /* Verify that get_edit_distance (A, B) equals the expected value.  */
     202                 :            : 
     203                 :            : static void
     204                 :        120 : test_get_edit_distance_one_way (const char *a, const char *b,
     205                 :            :                                 edit_distance_t expected)
     206                 :            : {
     207                 :        120 :   edit_distance_t actual = get_edit_distance (a, b);
     208                 :        120 :   ASSERT_EQ (actual, expected);
     209                 :        120 : }
     210                 :            : 
     211                 :            : /* Verify that both
     212                 :            :      get_edit_distance (A, B)
     213                 :            :    and
     214                 :            :      get_edit_distance (B, A)
     215                 :            :    equal the expected value, to ensure that the function is symmetric.  */
     216                 :            : 
     217                 :            : static void
     218                 :         60 : test_get_edit_distance_both_ways (const char *a, const char *b,
     219                 :            :                              edit_distance_t expected)
     220                 :            : {
     221                 :          0 :   test_get_edit_distance_one_way (a, b, expected);
     222                 :         60 :   test_get_edit_distance_one_way (b, a, expected);
     223                 :          0 : }
     224                 :            : 
     225                 :            : /* Verify get_edit_distance for a variety of pairs of pre-canned
     226                 :            :    inputs, comparing against known-good values.  */
     227                 :            : 
     228                 :            : static void
     229                 :          2 : test_edit_distances ()
     230                 :            : {
     231                 :          2 :   test_get_edit_distance_both_ways ("", "nonempty", strlen ("nonempty"));
     232                 :          2 :   test_get_edit_distance_both_ways ("saturday", "sunday", 3);
     233                 :          2 :   test_get_edit_distance_both_ways ("foo", "m_foo", 2);
     234                 :          2 :   test_get_edit_distance_both_ways ("hello_world", "HelloWorld", 3);
     235                 :          2 :   test_get_edit_distance_both_ways
     236                 :          2 :     ("the quick brown fox jumps over the lazy dog", "dog", 40);
     237                 :          2 :   test_get_edit_distance_both_ways
     238                 :          2 :     ("the quick brown fox jumps over the lazy dog",
     239                 :            :      "the quick brown dog jumps over the lazy fox",
     240                 :            :      4);
     241                 :          2 :   test_get_edit_distance_both_ways
     242                 :          2 :     ("Lorem ipsum dolor sit amet, consectetur adipiscing elit,",
     243                 :            :      "All your base are belong to us",
     244                 :            :      44);
     245                 :          2 :   test_get_edit_distance_both_ways ("foo", "FOO", 3);
     246                 :          2 :   test_get_edit_distance_both_ways ("fee", "deed", 2);
     247                 :          2 :   test_get_edit_distance_both_ways ("coorzd1", "coordx1", 2);
     248                 :          2 :   test_get_edit_distance_both_ways ("assert", "sqrt", 3);
     249                 :          2 :   test_get_edit_distance_both_ways ("PATH_MAX", "INT8_MAX", 3);
     250                 :          2 :   test_get_edit_distance_both_ways ("time", "nice", 2);
     251                 :          2 :   test_get_edit_distance_both_ways ("bar", "carg", 2);
     252                 :          2 :   test_get_edit_distance_both_ways ("gtk_widget_show_all",
     253                 :            :                                     "GtkWidgetShowAll", 7);
     254                 :          2 :   test_get_edit_distance_both_ways ("m_bar", "bar", 2);
     255                 :          2 :   test_get_edit_distance_both_ways ("MACRO", "MACRAME", 3);
     256                 :          2 :   test_get_edit_distance_both_ways ("ab", "ac", 1);
     257                 :          2 :   test_get_edit_distance_both_ways ("ab", "a", 1);
     258                 :          2 :   test_get_edit_distance_both_ways ("a", "b", 1);
     259                 :          2 :   test_get_edit_distance_both_ways ("nanl", "name", 2);
     260                 :          2 :   test_get_edit_distance_both_ways ("char", "bar", 2);
     261                 :          2 :   test_get_edit_distance_both_ways ("-optimize", "fsanitize", 5);
     262                 :          2 :   test_get_edit_distance_both_ways ("__DATE__", "__i386__", 4);
     263                 :            : 
     264                 :            :   /* Examples where transposition helps.  */
     265                 :          2 :   test_get_edit_distance_both_ways ("ab", "ba", 1);
     266                 :          2 :   test_get_edit_distance_both_ways ("ba", "abc", 2);
     267                 :          2 :   test_get_edit_distance_both_ways ("coorzd1", "coordz1", 1);
     268                 :          2 :   test_get_edit_distance_both_ways ("abcdefghijklmnopqrstuvwxyz",
     269                 :            :                                     "bacdefghijklmnopqrstuvwxzy", 2);
     270                 :          2 :   test_get_edit_distance_both_ways ("saturday", "sundya", 4);
     271                 :          2 :   test_get_edit_distance_both_ways ("signed", "singed", 1);
     272                 :          2 : }
     273                 :            : 
     274                 :            : /* Subroutine of test_get_edit_distance_cutoff, for emulating the
     275                 :            :    spellchecking cutoff in up to GCC 8.  */
     276                 :            : 
     277                 :            : static edit_distance_t
     278                 :       1800 : get_old_cutoff (size_t goal_len, size_t candidate_len)
     279                 :            : {
     280                 :       1800 :   return MAX (goal_len, candidate_len) / 2;
     281                 :            : }
     282                 :            : 
     283                 :            : /* Verify that the cutoff for "meaningfulness" of suggestions is at least as
     284                 :            :    conservative as in older GCC releases.
     285                 :            : 
     286                 :            :    This should ensure that we don't offer additional meaningless
     287                 :            :    suggestions (apart from those for which transposition has helped).  */
     288                 :            : 
     289                 :            : static void
     290                 :          2 : test_get_edit_distance_cutoff ()
     291                 :            : {
     292                 :         62 :   for (size_t goal_len = 0; goal_len < 30; goal_len++)
     293                 :       1860 :     for (size_t candidate_len = 0; candidate_len < 30; candidate_len++)
     294                 :       3600 :       ASSERT_TRUE (get_edit_distance_cutoff (goal_len, candidate_len)
     295                 :            :                    <= get_old_cutoff (goal_len, candidate_len));
     296                 :          2 : }
     297                 :            : 
     298                 :            : /* Assert that CANDIDATE is offered as a suggestion for TARGET.  */
     299                 :            : 
     300                 :            : static void
     301                 :         10 : assert_suggested_for (const location &loc, const char *candidate,
     302                 :            :                       const char *target)
     303                 :            : {
     304                 :         10 :   auto_vec<const char *> candidates;
     305                 :         10 :   candidates.safe_push (candidate);
     306                 :         10 :   ASSERT_EQ_AT (loc, candidate, find_closest_string (target, &candidates));
     307                 :         10 : }
     308                 :            : 
     309                 :            : /* Assert that CANDIDATE is offered as a suggestion for TARGET.  */
     310                 :            : 
     311                 :            : #define ASSERT_SUGGESTED_FOR(CANDIDATE, TARGET)                 \
     312                 :            :   SELFTEST_BEGIN_STMT                                                   \
     313                 :            :     assert_suggested_for (SELFTEST_LOCATION, CANDIDATE, TARGET);        \
     314                 :            :   SELFTEST_END_STMT
     315                 :            : 
     316                 :            : /* Assert that CANDIDATE is not offered as a suggestion for TARGET.  */
     317                 :            : 
     318                 :            : static void
     319                 :         20 : assert_not_suggested_for (const location &loc, const char *candidate,
     320                 :            :                           const char *target)
     321                 :            : {
     322                 :         20 :   auto_vec<const char *> candidates;
     323                 :         20 :   candidates.safe_push (candidate);
     324                 :         20 :   ASSERT_EQ_AT (loc, NULL, find_closest_string (target, &candidates));
     325                 :         20 : }
     326                 :            : 
     327                 :            : /* Assert that CANDIDATE is not offered as a suggestion for TARGET.  */
     328                 :            : 
     329                 :            : #define ASSERT_NOT_SUGGESTED_FOR(CANDIDATE, TARGET)                     \
     330                 :            :   SELFTEST_BEGIN_STMT                                                   \
     331                 :            :     assert_not_suggested_for (SELFTEST_LOCATION, CANDIDATE, TARGET);    \
     332                 :            :   SELFTEST_END_STMT
     333                 :            : 
     334                 :            : /* Verify that we offer varous suggestions that are meaningful,
     335                 :            :    and that we don't offer various other ones that aren't (PR c/82967).  */
     336                 :            : 
     337                 :            : static void
     338                 :          2 : test_suggestions ()
     339                 :            : {
     340                 :            :   /* Good suggestions.  */
     341                 :            : 
     342                 :          2 :   ASSERT_SUGGESTED_FOR ("m_bar", "bar");
     343                 :            :   // dist == 2, max_length == 5, min_length == 3
     344                 :            : 
     345                 :          2 :   ASSERT_SUGGESTED_FOR ("MACRO", "MACRAME");
     346                 :            :   // dist == 3, max_length == 7, min_length == 5
     347                 :            : 
     348                 :          2 :   ASSERT_SUGGESTED_FOR ("gtk_widget_show_all", "GtkWidgetShowAll");
     349                 :            :   // dist == 7, max_length == 16, min_length = 19
     350                 :            : 
     351                 :          2 :   ASSERT_SUGGESTED_FOR ("ab", "ac");
     352                 :            :   // dist == 1, max_length == min_length = 2
     353                 :            : 
     354                 :          2 :   ASSERT_SUGGESTED_FOR ("ab", "a");
     355                 :            :   // dist == 1, max_length == 2, min_length = 1
     356                 :            : 
     357                 :            :   /* Bad suggestions.  */
     358                 :            : 
     359                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("a", "b");
     360                 :            :   // dist == 1, max_length == min_length = 1
     361                 :            : 
     362                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("sqrt", "assert");
     363                 :            :   // dist == 3, max_length 6, min_length == 4
     364                 :            : 
     365                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("INT8_MAX", "PATH_MAX");
     366                 :            :   // dist == 3, max_length == min_length == 8
     367                 :            : 
     368                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("nice", "time");
     369                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("nanl", "name");
     370                 :            :   // dist == 2, max_length == min_length == 4
     371                 :            : 
     372                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("carg", "bar");
     373                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("char", "bar");
     374                 :            :   // dist == 2, max_length == 4, min_length == 3
     375                 :            : 
     376                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("-optimize", "fsanitize");
     377                 :            :   // dist == 5, max_length == min_length == 9
     378                 :            : 
     379                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("__DATE__", "__i386__");
     380                 :            :   // dist == 4, max_length == min_length == 8
     381                 :            : 
     382                 :          2 :   ASSERT_NOT_SUGGESTED_FOR ("start_input_device", "InputDevice");
     383                 :            :   // dist == 9, max_length == 18, min_length == 11
     384                 :          2 : }
     385                 :            : 
     386                 :            : /* Verify that find_closest_string is sane.  */
     387                 :            : 
     388                 :            : static void
     389                 :          2 : test_find_closest_string ()
     390                 :            : {
     391                 :          2 :   auto_vec<const char *> candidates;
     392                 :            : 
     393                 :            :   /* Verify that it can handle an empty vec.  */
     394                 :          2 :   ASSERT_EQ (NULL, find_closest_string ("", &candidates));
     395                 :            : 
     396                 :            :   /* Verify that it works sanely for non-empty vecs.  */
     397                 :          2 :   candidates.safe_push ("apple");
     398                 :          2 :   candidates.safe_push ("banana");
     399                 :          2 :   candidates.safe_push ("cherry");
     400                 :            : 
     401                 :          2 :   ASSERT_STREQ ("apple", find_closest_string ("app", &candidates));
     402                 :          2 :   ASSERT_STREQ ("banana", find_closest_string ("banyan", &candidates));
     403                 :          2 :   ASSERT_STREQ ("cherry", find_closest_string ("berry", &candidates));
     404                 :          2 :   ASSERT_EQ (NULL, find_closest_string ("not like the others", &candidates));
     405                 :            : 
     406                 :            :   /* The order of the vec can matter, but it should not matter for these
     407                 :            :      inputs.  */
     408                 :          2 :   candidates.truncate (0);
     409                 :          2 :   candidates.safe_push ("cherry");
     410                 :          2 :   candidates.safe_push ("banana");
     411                 :          2 :   candidates.safe_push ("apple");
     412                 :          2 :   ASSERT_STREQ ("apple", find_closest_string ("app", &candidates));
     413                 :          2 :   ASSERT_STREQ ("banana", find_closest_string ("banyan", &candidates));
     414                 :          2 :   ASSERT_STREQ ("cherry", find_closest_string ("berry", &candidates));
     415                 :          2 :   ASSERT_EQ (NULL, find_closest_string ("not like the others", &candidates));
     416                 :            : 
     417                 :            :   /* If the goal string somehow makes it into the candidate list, offering
     418                 :            :      it as a suggestion will be nonsensical.  Verify that we don't offer such
     419                 :            :      suggestions.  */
     420                 :          2 :   ASSERT_EQ (NULL, find_closest_string ("banana", &candidates));
     421                 :            : 
     422                 :            :   /* Example from PR 69968 where transposition helps.  */
     423                 :          2 :   candidates.truncate (0);
     424                 :          2 :   candidates.safe_push("coordx");
     425                 :          2 :   candidates.safe_push("coordy");
     426                 :          2 :   candidates.safe_push("coordz");
     427                 :          2 :   candidates.safe_push("coordx1");
     428                 :          2 :   candidates.safe_push("coordy1");
     429                 :          2 :   candidates.safe_push("coordz1");
     430                 :          2 :   ASSERT_STREQ ("coordz1", find_closest_string ("coorzd1", &candidates));
     431                 :          2 : }
     432                 :            : 
     433                 :            : /* Test data for test_metric_conditions.  */
     434                 :            : 
     435                 :            : static const char * const test_data[] = {
     436                 :            :   "",
     437                 :            :   "foo",
     438                 :            :   "food",
     439                 :            :   "boo",
     440                 :            :   "1234567890123456789012345678901234567890123456789012345678901234567890"
     441                 :            : };
     442                 :            : 
     443                 :            : /* Verify that get_edit_distance appears to be a sane distance function,
     444                 :            :    i.e. the conditions for being a metric.  This is done directly for a
     445                 :            :    small set of examples, using test_data above.  This is O(N^3) in the size
     446                 :            :    of the array, due to the test for the triangle inequality, so we keep the
     447                 :            :    array small.  */
     448                 :            : 
     449                 :            : static void
     450                 :          2 : test_metric_conditions ()
     451                 :            : {
     452                 :          2 :   const int num_test_cases = sizeof (test_data) / sizeof (test_data[0]);
     453                 :            : 
     454                 :         12 :   for (int i = 0; i < num_test_cases; i++)
     455                 :            :     {
     456                 :         60 :       for (int j = 0; j < num_test_cases; j++)
     457                 :            :         {
     458                 :         50 :           edit_distance_t dist_ij
     459                 :         50 :             = get_edit_distance (test_data[i], test_data[j]);
     460                 :            : 
     461                 :            :           /* Identity of indiscernibles: d(i, j) > 0 iff i == j.  */
     462                 :         50 :           if (i == j)
     463                 :         10 :             ASSERT_EQ (dist_ij, 0);
     464                 :            :           else
     465                 :         40 :             ASSERT_TRUE (dist_ij > 0);
     466                 :            : 
     467                 :            :           /* Symmetry: d(i, j) == d(j, i).  */
     468                 :         50 :           edit_distance_t dist_ji
     469                 :         50 :             = get_edit_distance (test_data[j], test_data[i]);
     470                 :         50 :           ASSERT_EQ (dist_ij, dist_ji);
     471                 :            : 
     472                 :            :           /* Triangle inequality.  */
     473                 :        300 :           for (int k = 0; k < num_test_cases; k++)
     474                 :            :             {
     475                 :        250 :               edit_distance_t dist_ik
     476                 :        250 :                 = get_edit_distance (test_data[i], test_data[k]);
     477                 :        250 :               edit_distance_t dist_jk
     478                 :        250 :                 = get_edit_distance (test_data[j], test_data[k]);
     479                 :        250 :               ASSERT_TRUE (dist_ik <= dist_ij + dist_jk);
     480                 :            :             }
     481                 :            :         }
     482                 :            :     }
     483                 :          2 : }
     484                 :            : 
     485                 :            : /* Run all of the selftests within this file.  */
     486                 :            : 
     487                 :            : void
     488                 :          2 : spellcheck_c_tests ()
     489                 :            : {
     490                 :          2 :   test_edit_distances ();
     491                 :          2 :   test_get_edit_distance_cutoff ();
     492                 :          2 :   test_suggestions ();
     493                 :          2 :   test_find_closest_string ();
     494                 :          2 :   test_metric_conditions ();
     495                 :          2 : }
     496                 :            : 
     497                 :            : } // namespace selftest
     498                 :            : 
     499                 :            : #endif /* #if CHECKING_P */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.