1*38fd1498Szrj /* Find near-matches for identifiers.
2*38fd1498Szrj Copyright (C) 2015-2018 Free Software Foundation, Inc.
3*38fd1498Szrj
4*38fd1498Szrj This file is part of GCC.
5*38fd1498Szrj
6*38fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
7*38fd1498Szrj the terms of the GNU General Public License as published by the Free
8*38fd1498Szrj Software Foundation; either version 3, or (at your option) any later
9*38fd1498Szrj version.
10*38fd1498Szrj
11*38fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12*38fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
13*38fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14*38fd1498Szrj for more details.
15*38fd1498Szrj
16*38fd1498Szrj You should have received a copy of the GNU General Public License
17*38fd1498Szrj along with GCC; see the file COPYING3. If not see
18*38fd1498Szrj <http://www.gnu.org/licenses/>. */
19*38fd1498Szrj
20*38fd1498Szrj #include "config.h"
21*38fd1498Szrj #include "system.h"
22*38fd1498Szrj #include "coretypes.h"
23*38fd1498Szrj #include "tm.h"
24*38fd1498Szrj #include "tree.h"
25*38fd1498Szrj #include "cpplib.h"
26*38fd1498Szrj #include "spellcheck-tree.h"
27*38fd1498Szrj #include "selftest.h"
28*38fd1498Szrj #include "stringpool.h"
29*38fd1498Szrj
30*38fd1498Szrj /* Calculate Levenshtein distance between two identifiers. */
31*38fd1498Szrj
32*38fd1498Szrj edit_distance_t
levenshtein_distance(tree ident_s,tree ident_t)33*38fd1498Szrj levenshtein_distance (tree ident_s, tree ident_t)
34*38fd1498Szrj {
35*38fd1498Szrj gcc_assert (TREE_CODE (ident_s) == IDENTIFIER_NODE);
36*38fd1498Szrj gcc_assert (TREE_CODE (ident_t) == IDENTIFIER_NODE);
37*38fd1498Szrj
38*38fd1498Szrj return levenshtein_distance (IDENTIFIER_POINTER (ident_s),
39*38fd1498Szrj IDENTIFIER_LENGTH (ident_s),
40*38fd1498Szrj IDENTIFIER_POINTER (ident_t),
41*38fd1498Szrj IDENTIFIER_LENGTH (ident_t));
42*38fd1498Szrj }
43*38fd1498Szrj
44*38fd1498Szrj /* Given TARGET, an identifier, and CANDIDATES, a vec of identifiers,
45*38fd1498Szrj determine which element within CANDIDATES has the lowest edit
46*38fd1498Szrj distance to TARGET. If there are multiple elements with the
47*38fd1498Szrj same minimal distance, the first in the vector wins.
48*38fd1498Szrj
49*38fd1498Szrj If more than half of the letters were misspelled, the suggestion is
50*38fd1498Szrj likely to be meaningless, so return NULL_TREE for this case. */
51*38fd1498Szrj
52*38fd1498Szrj tree
find_closest_identifier(tree target,const auto_vec<tree> * candidates)53*38fd1498Szrj find_closest_identifier (tree target, const auto_vec<tree> *candidates)
54*38fd1498Szrj {
55*38fd1498Szrj gcc_assert (TREE_CODE (target) == IDENTIFIER_NODE);
56*38fd1498Szrj
57*38fd1498Szrj best_match<tree, tree> bm (target);
58*38fd1498Szrj int i;
59*38fd1498Szrj tree identifier;
60*38fd1498Szrj FOR_EACH_VEC_ELT (*candidates, i, identifier)
61*38fd1498Szrj {
62*38fd1498Szrj gcc_assert (TREE_CODE (identifier) == IDENTIFIER_NODE);
63*38fd1498Szrj bm.consider (identifier);
64*38fd1498Szrj }
65*38fd1498Szrj
66*38fd1498Szrj return bm.get_best_meaningful_candidate ();
67*38fd1498Szrj }
68*38fd1498Szrj
69*38fd1498Szrj #if CHECKING_P
70*38fd1498Szrj
71*38fd1498Szrj namespace selftest {
72*38fd1498Szrj
73*38fd1498Szrj /* Selftests. */
74*38fd1498Szrj
75*38fd1498Szrj /* Verify that find_closest_identifier is sane. */
76*38fd1498Szrj
77*38fd1498Szrj static void
test_find_closest_identifier()78*38fd1498Szrj test_find_closest_identifier ()
79*38fd1498Szrj {
80*38fd1498Szrj auto_vec<tree> candidates;
81*38fd1498Szrj
82*38fd1498Szrj /* Verify that it can handle an empty vec. */
83*38fd1498Szrj ASSERT_EQ (NULL, find_closest_identifier (get_identifier (""), &candidates));
84*38fd1498Szrj
85*38fd1498Szrj /* Verify that it works sanely for non-empty vecs. */
86*38fd1498Szrj tree apple = get_identifier ("apple");
87*38fd1498Szrj tree banana = get_identifier ("banana");
88*38fd1498Szrj tree cherry = get_identifier ("cherry");
89*38fd1498Szrj candidates.safe_push (apple);
90*38fd1498Szrj candidates.safe_push (banana);
91*38fd1498Szrj candidates.safe_push (cherry);
92*38fd1498Szrj
93*38fd1498Szrj ASSERT_EQ (apple, find_closest_identifier (get_identifier ("app"),
94*38fd1498Szrj &candidates));
95*38fd1498Szrj ASSERT_EQ (banana, find_closest_identifier (get_identifier ("banyan"),
96*38fd1498Szrj &candidates));
97*38fd1498Szrj ASSERT_EQ (cherry, find_closest_identifier (get_identifier ("berry"),
98*38fd1498Szrj &candidates));
99*38fd1498Szrj ASSERT_EQ (NULL,
100*38fd1498Szrj find_closest_identifier (get_identifier ("not like the others"),
101*38fd1498Szrj &candidates));
102*38fd1498Szrj }
103*38fd1498Szrj
104*38fd1498Szrj /* Run all of the selftests within this file. */
105*38fd1498Szrj
106*38fd1498Szrj void
spellcheck_tree_c_tests()107*38fd1498Szrj spellcheck_tree_c_tests ()
108*38fd1498Szrj {
109*38fd1498Szrj test_find_closest_identifier ();
110*38fd1498Szrj }
111*38fd1498Szrj
112*38fd1498Szrj } // namespace selftest
113*38fd1498Szrj
114*38fd1498Szrj #endif /* #if CHECKING_P */
115