Mercurial > hg > CbC > CbC_gcc

comparison gcc/spellcheck.h @ 131:84e7813d76e9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-8.2
author mir3636
date Thu, 25 Oct 2018 07:37:49 +0900
parents 04ced10e8804
children 1830386684a0
comparison
equal deleted inserted replaced
111:04ced10e8804 131:84e7813d76e9
1 /* Find near-matches for strings and identifiers. 1 /* Find near-matches for strings and identifiers.
2 Copyright (C) 2015-2017 Free Software Foundation, Inc. 2 Copyright (C) 2015-2018 Free Software Foundation, Inc.
3 3
4 This file is part of GCC. 4 This file is part of GCC.
5 5
6 GCC is free software; you can redistribute it and/or modify it under 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 7 the terms of the GNU General Public License as published by the Free
23 typedef unsigned int edit_distance_t; 23 typedef unsigned int edit_distance_t;
24 const edit_distance_t MAX_EDIT_DISTANCE = UINT_MAX; 24 const edit_distance_t MAX_EDIT_DISTANCE = UINT_MAX;
25 25
26 /* spellcheck.c */ 26 /* spellcheck.c */
27 extern edit_distance_t 27 extern edit_distance_t
28 levenshtein_distance (const char *s, int len_s, 28 get_edit_distance (const char *s, int len_s,
29 const char *t, int len_t); 29 const char *t, int len_t);
30 30
31 extern edit_distance_t 31 extern edit_distance_t
32 levenshtein_distance (const char *s, const char *t); 32 get_edit_distance (const char *s, const char *t);
33 33
34 extern const char * 34 extern const char *
35 find_closest_string (const char *target, 35 find_closest_string (const char *target,
36 const auto_vec<const char *> *candidates); 36 const auto_vec<const char *> *candidates);
37 37
64 gcc_assert (str); 64 gcc_assert (str);
65 return str; 65 return str;
66 } 66 }
67 }; 67 };
68 68
69 extern edit_distance_t get_edit_distance_cutoff (size_t goal_len,
70 size_t candidate_len);
71
69 /* A type for use when determining the best match against a string, 72 /* A type for use when determining the best match against a string,
70 expressed as a template so that we can match against various 73 expressed as a template so that we can match against various
71 string-like types (const char *, frontend identifiers, and preprocessor 74 string-like types (const char *, frontend identifiers, and preprocessor
72 macros). 75 macros).
73 76
74 This type accumulates the best possible match against GOAL_TYPE for 77 This type accumulates the best possible match against GOAL_TYPE for
75 a sequence of elements of CANDIDATE_TYPE, whilst minimizing the 78 a sequence of elements of CANDIDATE_TYPE, whilst minimizing the
76 number of calls to levenshtein_distance and to 79 number of calls to get_edit_distance and to
77 edit_distance_traits<T>::get_length. */ 80 edit_distance_traits<T>::get_length. */
78 81
79 template <typename GOAL_TYPE, typename CANDIDATE_TYPE> 82 template <typename GOAL_TYPE, typename CANDIDATE_TYPE>
80 class best_match 83 class best_match
81 { 84 {
117 return; 120 return;
118 121
119 /* If the candidate will be unable to beat the criterion in 122 /* If the candidate will be unable to beat the criterion in
120 get_best_meaningful_candidate, reject it without computing 123 get_best_meaningful_candidate, reject it without computing
121 the exact distance. */ 124 the exact distance. */
122 unsigned int cutoff = MAX (m_goal_len, candidate_len) / 2; 125 edit_distance_t cutoff = get_cutoff (candidate_len);
123 if (min_candidate_distance > cutoff) 126 if (min_candidate_distance > cutoff)
124 return; 127 return;
125 128
126 /* Otherwise, compute the distance and see if the candidate 129 /* Otherwise, compute the distance and see if the candidate
127 has beaten the previous best value. */ 130 has beaten the previous best value. */
128 edit_distance_t dist 131 edit_distance_t dist
129 = levenshtein_distance (m_goal, m_goal_len, 132 = get_edit_distance (m_goal, m_goal_len,
130 candidate_traits::get_string (candidate), 133 candidate_traits::get_string (candidate),
131 candidate_len); 134 candidate_len);
132 if (dist < m_best_distance) 135 if (dist < m_best_distance)
133 { 136 {
134 m_best_distance = dist; 137 m_best_distance = dist;
135 m_best_candidate = candidate; 138 m_best_candidate = candidate;
136 m_best_candidate_len = candidate_len; 139 m_best_candidate_len = candidate_len;
149 m_best_candidate = best_candidate; 152 m_best_candidate = best_candidate;
150 m_best_distance = best_distance; 153 m_best_distance = best_distance;
151 m_best_candidate_len = best_candidate_len; 154 m_best_candidate_len = best_candidate_len;
152 } 155 }
153 156
157 /* Generate the maximum edit distance for which we consider a suggestion
158 to be meaningful, given a candidate of length CANDIDATE_LEN. */
159
160 edit_distance_t get_cutoff (size_t candidate_len) const
161 {
162 return ::get_edit_distance_cutoff (m_goal_len, candidate_len);
163 }
164
154 /* Get the best candidate so far, but applying a filter to ensure 165 /* Get the best candidate so far, but applying a filter to ensure
155 that we return NULL if none of the candidates are close to the goal, 166 that we return NULL if none of the candidates are close to the goal,
156 to avoid offering nonsensical suggestions to the user. */ 167 to avoid offering nonsensical suggestions to the user. */
157 168
158 candidate_t get_best_meaningful_candidate () const 169 candidate_t get_best_meaningful_candidate () const
159 { 170 {
160 /* If more than half of the letters were misspelled, the suggestion is 171 /* If the edit distance is too high, the suggestion is likely to be
161 likely to be meaningless. */ 172 meaningless. */
162 if (m_best_candidate) 173 if (m_best_candidate)
163 { 174 {
164 unsigned int cutoff = MAX (m_goal_len, m_best_candidate_len) / 2; 175 edit_distance_t cutoff = get_cutoff (m_best_candidate_len);
165 if (m_best_distance > cutoff) 176 if (m_best_distance > cutoff)
166 return NULL; 177 return NULL;
167 } 178 }
168 179
169 /* If the goal string somehow makes it into the candidate list, offering 180 /* If the goal string somehow makes it into the candidate list, offering
176 return NULL; 187 return NULL;
177 188
178 return m_best_candidate; 189 return m_best_candidate;
179 } 190 }
180 191
192 /* Get the closest candidate so far, without applying any filtering. */
193
194 candidate_t blithely_get_best_candidate () const
195 {
196 return m_best_candidate;
197 }
198
181 edit_distance_t get_best_distance () const { return m_best_distance; } 199 edit_distance_t get_best_distance () const { return m_best_distance; }
182 size_t get_best_candidate_length () const { return m_best_candidate_len; } 200 size_t get_best_candidate_length () const { return m_best_candidate_len; }
183 201
184 private: 202 private:
185 const char *m_goal; 203 const char *m_goal;