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