1 // -*- mode: C++; c-file-style: "cc-mode" -*-
2 //*************************************************************************
3 // DESCRIPTION: Verilator: Options parsing
4 //
5 // Code available from: https://verilator.org
6 //
7 //*************************************************************************
8 //
9 // Copyright 2003-2021 by Wilson Snyder. This program is free software; you
10 // can redistribute it and/or modify it under the terms of either the GNU
11 // Lesser General Public License Version 3 or the Perl Artistic License
12 // Version 2.0.
13 // SPDX-License-Identifier: LGPL-3.0-only OR Artistic-2.0
14 //
15 //*************************************************************************
16
17 #include "config_build.h"
18 #include "verilatedos.h"
19
20 // Limited V3 headers here - this is a base class for Vlc etc
21 #include "V3String.h"
22 #include "V3Error.h"
23
24 #include <algorithm>
25
26 size_t VName::s_minLength = 32;
27 size_t VName::s_maxLength = 0; // Disabled
28 std::map<string, string> VName::s_dehashMap;
29
30 //######################################################################
31 // Wildcard
32
33 // Double procedures, inlined, unrolls loop much better
wildmatchi(const char * s,const char * p)34 inline bool VString::wildmatchi(const char* s, const char* p) {
35 for (; *p; s++, p++) {
36 if (*p != '*') {
37 if (((*s) != (*p)) && *p != '?') return false;
38 } else {
39 // Trailing star matches everything.
40 if (!*++p) return true;
41 while (!wildmatch(s, p)) {
42 if (*++s == '\0') return false;
43 }
44 return true;
45 }
46 }
47 return (*s == '\0');
48 }
49
wildmatch(const char * s,const char * p)50 bool VString::wildmatch(const char* s, const char* p) {
51 for (; *p; s++, p++) {
52 if (*p != '*') {
53 if (((*s) != (*p)) && *p != '?') return false;
54 } else {
55 // Trailing star matches everything.
56 if (!*++p) return true;
57 while (!wildmatchi(s, p)) {
58 if (*++s == '\0') return false;
59 }
60 return true;
61 }
62 }
63 return (*s == '\0');
64 }
65
wildmatch(const string & s,const string & p)66 bool VString::wildmatch(const string& s, const string& p) {
67 return wildmatch(s.c_str(), p.c_str());
68 }
69
dot(const string & a,const string & dot,const string & b)70 string VString::dot(const string& a, const string& dot, const string& b) {
71 if (b == "") return a;
72 if (a == "") return b;
73 return a + dot + b;
74 }
75
downcase(const string & str)76 string VString::downcase(const string& str) {
77 string out = str;
78 for (auto& cr : out) cr = tolower(cr);
79 return out;
80 }
81
upcase(const string & str)82 string VString::upcase(const string& str) {
83 string out = str;
84 for (auto& cr : out) cr = toupper(cr);
85 return out;
86 }
87
quoteAny(const string & str,char tgt,char esc)88 string VString::quoteAny(const string& str, char tgt, char esc) {
89 string out;
90 for (const char c : str) {
91 if (c == tgt) out += esc;
92 out += c;
93 }
94 return out;
95 }
96
quoteStringLiteralForShell(const string & str)97 string VString::quoteStringLiteralForShell(const string& str) {
98 string result;
99 const char dquote = '"';
100 const char escape = '\\';
101 result.push_back(dquote); // Start quoted string
102 result.push_back(escape);
103 result.push_back(dquote); // "
104 for (const char c : str) {
105 if (c == dquote || c == escape) result.push_back(escape);
106 result.push_back(c);
107 }
108 result.push_back(escape);
109 result.push_back(dquote); // "
110 result.push_back(dquote); // Terminate quoted string
111 return result;
112 }
113
spaceUnprintable(const string & str)114 string VString::spaceUnprintable(const string& str) {
115 string out;
116 for (const char c : str) {
117 if (isprint(c)) {
118 out += c;
119 } else {
120 out += ' ';
121 }
122 }
123 return out;
124 }
125
removeWhitespace(const string & str)126 string VString::removeWhitespace(const string& str) {
127 string out;
128 out.reserve(str.size());
129 for (const char c : str) {
130 if (!isspace(c)) out += c;
131 }
132 return out;
133 }
134
isWhitespace(const string & str)135 bool VString::isWhitespace(const string& str) {
136 for (const char c : str) {
137 if (!isspace(c)) return false;
138 }
139 return true;
140 }
141
parseDouble(const string & str,bool * successp)142 double VString::parseDouble(const string& str, bool* successp) {
143 char* const strgp = new char[str.size() + 1];
144 char* dp = strgp;
145 if (successp) *successp = true;
146 for (const char* sp = str.c_str(); *sp; ++sp) {
147 if (*sp != '_') *dp++ = *sp;
148 }
149 *dp++ = '\0';
150 char* endp = strgp;
151 const double d = strtod(strgp, &endp);
152 const size_t parsed_len = endp - strgp;
153 if (parsed_len != strlen(strgp)) {
154 if (successp) *successp = false;
155 }
156 VL_DO_DANGLING(delete[] strgp, strgp);
157 return d;
158 }
159
isWordChar(char c)160 static bool isWordChar(char c) { return isalnum(c) || c == '_'; }
161
replaceWord(const string & str,const string & from,const string & to)162 string VString::replaceWord(const string& str, const string& from, const string& to) {
163 string result = str;
164 const size_t len = from.size();
165 UASSERT_STATIC(len > 0, "Cannot replace empty string");
166 for (size_t pos = 0; (pos = result.find(from, pos)) != string::npos; pos += len) {
167 // Only replace whole words
168 if (((pos > 0) && isWordChar(result[pos - 1])) || //
169 ((pos + len < result.size()) && isWordChar(result[pos + len]))) {
170 continue;
171 }
172 result.replace(pos, len, to);
173 }
174 return result;
175 }
176
startsWith(const string & str,const string & prefix)177 bool VString::startsWith(const string& str, const string& prefix) {
178 return str.rfind(prefix, 0) == 0; // Faster than .find(_) == 0
179 }
180
181 //######################################################################
182 // VHashSha256
183
184 static const uint32_t sha256K[]
185 = {0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4,
186 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe,
187 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f,
188 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
189 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
190 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
191 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116,
192 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
193 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7,
194 0xc67178f2};
195
196 static inline uint32_t shaRotr32(uint32_t lhs, uint32_t rhs) VL_ATTR_ALWINLINE;
shaRotr32(uint32_t lhs,uint32_t rhs)197 static inline uint32_t shaRotr32(uint32_t lhs, uint32_t rhs) {
198 return lhs >> rhs | lhs << (32 - rhs);
199 }
200
201 static inline void sha256Block(uint32_t* h, const uint32_t* chunk) VL_ATTR_ALWINLINE;
sha256Block(uint32_t * h,const uint32_t * chunk)202 static inline void sha256Block(uint32_t* h, const uint32_t* chunk) {
203 uint32_t ah[8];
204 const uint32_t* p = chunk;
205
206 // Initialize working variables to current hash value
207 for (unsigned i = 0; i < 8; i++) ah[i] = h[i];
208 // Compression function main loop
209 for (unsigned i = 0; i < 4; ++i) {
210 uint32_t w[16];
211
212 for (unsigned j = 0; j < 16; ++j) {
213 if (i == 0) {
214 w[j] = *p++;
215 } else {
216 // Extend the first 16 words into the remaining
217 // 48 words w[16..63] of the message schedule array:
218 const uint32_t s0 = shaRotr32(w[(j + 1) & 0xf], 7)
219 ^ shaRotr32(w[(j + 1) & 0xf], 18) ^ (w[(j + 1) & 0xf] >> 3);
220 const uint32_t s1 = shaRotr32(w[(j + 14) & 0xf], 17)
221 ^ shaRotr32(w[(j + 14) & 0xf], 19) ^ (w[(j + 14) & 0xf] >> 10);
222 w[j] = w[j] + s0 + w[(j + 9) & 0xf] + s1;
223 }
224 const uint32_t s1 = shaRotr32(ah[4], 6) ^ shaRotr32(ah[4], 11) ^ shaRotr32(ah[4], 25);
225 const uint32_t ch = (ah[4] & ah[5]) ^ (~ah[4] & ah[6]);
226 const uint32_t temp1 = ah[7] + s1 + ch + sha256K[i << 4 | j] + w[j];
227 const uint32_t s0 = shaRotr32(ah[0], 2) ^ shaRotr32(ah[0], 13) ^ shaRotr32(ah[0], 22);
228 const uint32_t maj = (ah[0] & ah[1]) ^ (ah[0] & ah[2]) ^ (ah[1] & ah[2]);
229 const uint32_t temp2 = s0 + maj;
230
231 ah[7] = ah[6];
232 ah[6] = ah[5];
233 ah[5] = ah[4];
234 ah[4] = ah[3] + temp1;
235 ah[3] = ah[2];
236 ah[2] = ah[1];
237 ah[1] = ah[0];
238 ah[0] = temp1 + temp2;
239 }
240 }
241 for (unsigned i = 0; i < 8; ++i) h[i] += ah[i];
242 }
243
insert(const void * datap,size_t length)244 void VHashSha256::insert(const void* datap, size_t length) {
245 UASSERT(!m_final, "Called VHashSha256::insert after finalized the hash value");
246 m_totLength += length;
247
248 string tempData;
249 int chunkLen;
250 const uint8_t* chunkp;
251 if (m_remainder == "") {
252 chunkLen = length;
253 chunkp = static_cast<const uint8_t*>(datap);
254 } else {
255 // If there are large inserts it would be more efficient to avoid this copy
256 // by copying bytes in the loop below from either m_remainder or the data
257 // as appropriate.
258 tempData = m_remainder + string(static_cast<const char*>(datap), length);
259 chunkLen = tempData.length();
260 chunkp = reinterpret_cast<const uint8_t*>(tempData.data());
261 }
262
263 // See wikipedia SHA-1 algorithm summary
264 uint32_t w[64]; // Round buffer, [0..15] are input data, rest used by rounds
265 int posBegin = 0; // Position in buffer for start of this block
266 int posEnd = 0; // Position in buffer for end of this block
267
268 // Process complete 64-byte blocks
269 while (posBegin <= chunkLen - 64) {
270 posEnd = posBegin + 64;
271 // 64 byte round input data, being careful to swap on big, keep on little
272 for (int roundByte = 0; posBegin < posEnd; posBegin += 4) {
273 w[roundByte++] = (static_cast<uint32_t>(chunkp[posBegin + 3])
274 | (static_cast<uint32_t>(chunkp[posBegin + 2]) << 8)
275 | (static_cast<uint32_t>(chunkp[posBegin + 1]) << 16)
276 | (static_cast<uint32_t>(chunkp[posBegin]) << 24));
277 }
278 sha256Block(m_inthash, w);
279 }
280
281 m_remainder = string(reinterpret_cast<const char*>(chunkp + posBegin), chunkLen - posEnd);
282 }
283
finalize()284 void VHashSha256::finalize() {
285 if (!m_final) {
286 // Make sure no 64 byte blocks left
287 insert("");
288 m_final = true;
289
290 // Process final possibly non-complete 64-byte block
291 uint32_t w[16]; // Round buffer, [0..15] are input data
292 for (int i = 0; i < 16; ++i) w[i] = 0;
293 size_t blockPos = 0;
294 for (; blockPos < m_remainder.length(); ++blockPos) {
295 w[blockPos >> 2]
296 |= ((static_cast<uint32_t>(m_remainder[blockPos])) << ((3 - (blockPos & 3)) << 3));
297 }
298 w[blockPos >> 2] |= 0x80 << ((3 - (blockPos & 3)) << 3);
299 if (m_remainder.length() >= 56) {
300 sha256Block(m_inthash, w);
301 for (int i = 0; i < 16; ++i) w[i] = 0;
302 }
303 w[15] = m_totLength << 3;
304 sha256Block(m_inthash, w);
305
306 m_remainder.clear();
307 }
308 }
309
digestBinary()310 string VHashSha256::digestBinary() {
311 finalize();
312 string out;
313 out.reserve(32);
314 for (size_t i = 0; i < 32; ++i) {
315 out += (m_inthash[i >> 2] >> (((3 - i) & 0x3) << 3)) & 0xff;
316 }
317 return out;
318 }
319
digestUInt64()320 uint64_t VHashSha256::digestUInt64() {
321 const string& binhash = digestBinary();
322 uint64_t out = 0;
323 for (size_t byte = 0; byte < sizeof(uint64_t); ++byte) {
324 const unsigned char c = binhash[byte];
325 out = (out << 8) | c;
326 }
327 return out;
328 }
329
digestHex()330 string VHashSha256::digestHex() {
331 static const char* const digits = "0123456789abcdef";
332 const string& binhash = digestBinary();
333 string out;
334 out.reserve(70);
335 for (size_t byte = 0; byte < 32; ++byte) {
336 out += digits[(binhash[byte] >> 4) & 0xf];
337 out += digits[(binhash[byte] >> 0) & 0xf];
338 }
339 return out;
340 }
341
digestSymbol()342 string VHashSha256::digestSymbol() {
343 // Make a symbol name from hash. Similar to base64, however base 64
344 // has + and / for last two digits, but need C symbol, and we also
345 // avoid conflicts with use of _, so use "AB" at the end.
346 // Thus this function is non-reversible.
347 static const char* const digits
348 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789AB";
349 const string& binhash = digestBinary();
350 string out;
351 out.reserve(28);
352 int pos = 0;
353 for (; pos < (256 / 8) - 2; pos += 3) {
354 out += digits[((binhash[pos] >> 2) & 0x3f)];
355 out += digits[((binhash[pos] & 0x3) << 4)
356 | (static_cast<int>(binhash[pos + 1] & 0xf0) >> 4)];
357 out += digits[((binhash[pos + 1] & 0xf) << 2)
358 | (static_cast<int>(binhash[pos + 2] & 0xc0) >> 6)];
359 out += digits[((binhash[pos + 2] & 0x3f))];
360 }
361 // Any leftover bits don't matter for our purpose
362 return out;
363 }
364
selfTestOne(const string & data,const string & data2,const string & exp,const string & exp64)365 void VHashSha256::selfTestOne(const string& data, const string& data2, const string& exp,
366 const string& exp64) {
367 VHashSha256 digest(data);
368 if (data2 != "") digest.insert(data2);
369 if (VL_UNCOVERABLE(digest.digestHex() != exp)) {
370 std::cerr << "%Error: When hashing '" << data + data2 << "'\n" // LCOV_EXCL_LINE
371 << " ... got=" << digest.digestHex() << '\n' // LCOV_EXCL_LINE
372 << " ... exp=" << exp << endl; // LCOV_EXCL_LINE
373 }
374 if (VL_UNCOVERABLE(digest.digestSymbol() != exp64)) {
375 std::cerr << "%Error: When hashing '" << data + data2 << "'\n" // LCOV_EXCL_LINE
376 << " ... got=" << digest.digestSymbol() << '\n' // LCOV_EXCL_LINE
377 << " ... exp=" << exp64 << endl; // LCOV_EXCL_LINE
378 }
379 }
380
selfTest()381 void VHashSha256::selfTest() {
382 selfTestOne("", "", "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
383 "47DEQpj8HBSaABTImWA5JCeuQeRkm5NMpJWZG3hS");
384 selfTestOne("a", "", "ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb",
385 "ypeBEsobvcr6wjGzmiPcTaeG7BgUfE5yuYB3haBu");
386 selfTestOne("The quick brown fox jumps over the lazy dog", "",
387 "d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592",
388 "16j7swfXgJRpypq8sAguT41WUeRtPNt2LQLQvzfJ");
389 selfTestOne("The quick brown fox jumps over the lazy", " dog",
390 "d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592",
391 "16j7swfXgJRpypq8sAguT41WUeRtPNt2LQLQvzfJ");
392 selfTestOne("Test using larger than block-size key and larger than one block-size data", "",
393 "9dc35674a024b28e8440080b5331652e985f2d61d7a1fca80a648b7f9ffa0dd3",
394 "ncNWdKAkso6EQAgLUzFlLphfLWHXofyoCmSLf5B6");
395 selfTestOne("Test using", " larger than block-size key and larger than one block-size data",
396 "9dc35674a024b28e8440080b5331652e985f2d61d7a1fca80a648b7f9ffa0dd3",
397 "ncNWdKAkso6EQAgLUzFlLphfLWHXofyoCmSLf5B6");
398 }
399
400 //######################################################################
401 // VName
402
dehash(const string & in)403 string VName::dehash(const string& in) {
404 static const char VHSH[] = "__Vhsh";
405 static const size_t DOT_LEN = strlen("__DOT__");
406 std::string dehashed;
407
408 // Need to split 'in' into components separated by __DOT__, 'last_dot_pos'
409 // keeps track of the position after the most recently found instance of __DOT__
410 for (string::size_type last_dot_pos = 0; last_dot_pos < in.size();) {
411 const string::size_type next_dot_pos = in.find("__DOT__", last_dot_pos);
412 // Two iterators defining the range between the last and next dots.
413 const auto search_begin = std::begin(in) + last_dot_pos;
414 const auto search_end
415 = next_dot_pos == string::npos ? std::end(in) : std::begin(in) + next_dot_pos;
416
417 // Search for __Vhsh between the two dots.
418 const auto begin_vhsh
419 = std::search(search_begin, search_end, std::begin(VHSH), std::end(VHSH) - 1);
420 if (begin_vhsh != search_end) {
421 const std::string vhsh(begin_vhsh, search_end);
422 const auto& it = s_dehashMap.find(vhsh);
423 UASSERT(it != s_dehashMap.end(), "String not in reverse hash map '" << vhsh << "'");
424 // Is this not the first component, but the first to require dehashing?
425 if (last_dot_pos > 0 && dehashed.empty()) {
426 // Seed 'dehashed' with the previously processed components.
427 dehashed = in.substr(0, last_dot_pos);
428 }
429 // Append the unhashed part of the component.
430 dehashed += std::string(search_begin, begin_vhsh);
431 // Append the bit that was lost to truncation but retrieved from the dehash map.
432 dehashed += it->second;
433 }
434 // This component doesn't need dehashing but a previous one might have.
435 else if (!dehashed.empty()) {
436 dehashed += std::string(search_begin, search_end);
437 }
438
439 if (next_dot_pos != string::npos) {
440 // Is there a __DOT__ to add to the dehashed version of 'in'?
441 if (!dehashed.empty()) { dehashed += "__DOT__"; }
442 last_dot_pos = next_dot_pos + DOT_LEN;
443 } else {
444 last_dot_pos = string::npos;
445 }
446 }
447 return dehashed.empty() ? in : dehashed;
448 }
449
hashedName()450 string VName::hashedName() {
451 if (m_name == "") return "";
452 if (m_hashed != "") return m_hashed; // Memoized
453 if (s_maxLength == 0 || m_name.length() < s_maxLength) {
454 m_hashed = m_name;
455 return m_hashed;
456 } else {
457 VHashSha256 hash(m_name);
458 const string suffix = "__Vhsh" + hash.digestSymbol();
459 if (s_minLength < s_maxLength) {
460 s_dehashMap[suffix] = m_name.substr(s_minLength);
461 m_hashed = m_name.substr(0, s_minLength) + suffix;
462 } else {
463 s_dehashMap[suffix] = m_name;
464 m_hashed = suffix;
465 }
466 return m_hashed;
467 }
468 }
469
470 //######################################################################
471 // VSpellCheck - Algorithm same as GCC's spellcheck.c
472
editDistance(const string & s,const string & t)473 VSpellCheck::EditDistance VSpellCheck::editDistance(const string& s, const string& t) {
474 // Wagner-Fischer algorithm for the Damerau-Levenshtein distance
475 const size_t sLen = s.length();
476 const size_t tLen = t.length();
477 if (sLen == 0) return tLen;
478 if (tLen == 0) return sLen;
479 if (sLen >= LENGTH_LIMIT) return sLen;
480 if (tLen >= LENGTH_LIMIT) return tLen;
481
482 static std::array<EditDistance, LENGTH_LIMIT + 1> s_v_two_ago;
483 static std::array<EditDistance, LENGTH_LIMIT + 1> s_v_one_ago;
484 static std::array<EditDistance, LENGTH_LIMIT + 1> s_v_next;
485
486 for (size_t i = 0; i < sLen + 1; i++) s_v_one_ago[i] = i;
487
488 for (size_t i = 0; i < tLen; i++) {
489 s_v_next[0] = i + 1;
490 for (size_t j = 0; j < sLen; j++) {
491 const EditDistance cost = (s[j] == t[i] ? 0 : 1);
492 const EditDistance deletion = s_v_next[j] + 1;
493 const EditDistance insertion = s_v_one_ago[j + 1] + 1;
494 const EditDistance substitution = s_v_one_ago[j] + cost;
495 EditDistance cheapest = std::min(deletion, insertion);
496 cheapest = std::min(cheapest, substitution);
497 if (i > 0 && j > 0 && s[j] == t[i - 1] && s[j - 1] == t[i]) {
498 const EditDistance transposition = s_v_two_ago[j - 1] + 1;
499 cheapest = std::min(cheapest, transposition);
500 }
501 s_v_next[j + 1] = cheapest;
502 }
503 for (size_t j = 0; j < sLen + 1; j++) {
504 s_v_two_ago[j] = s_v_one_ago[j];
505 s_v_one_ago[j] = s_v_next[j];
506 }
507 }
508
509 const EditDistance result = s_v_next[sLen];
510 return result;
511 }
512
cutoffDistance(size_t goal_len,size_t candidate_len)513 VSpellCheck::EditDistance VSpellCheck::cutoffDistance(size_t goal_len, size_t candidate_len) {
514 // Return max acceptable edit distance
515 const size_t max_length = std::max(goal_len, candidate_len);
516 const size_t min_length = std::min(goal_len, candidate_len);
517 if (max_length <= 1) return 0;
518 if (max_length - min_length <= 1) return std::max(max_length / 3, static_cast<size_t>(1));
519 return (max_length + 2) / 3;
520 }
521
bestCandidateInfo(const string & goal,EditDistance & distancer) const522 string VSpellCheck::bestCandidateInfo(const string& goal, EditDistance& distancer) const {
523 string bestCandidate;
524 const size_t gLen = goal.length();
525 distancer = LENGTH_LIMIT * 10;
526 for (const string& candidate : m_candidates) {
527 const size_t cLen = candidate.length();
528
529 // Min distance must be inserting/deleting to make lengths match
530 const EditDistance min_distance = (cLen > gLen ? (cLen - gLen) : (gLen - cLen));
531 if (min_distance >= distancer) continue; // Short-circuit if already better
532
533 const EditDistance cutoff = cutoffDistance(gLen, cLen);
534 if (min_distance > cutoff) continue; // Short-circuit if already too bad
535
536 const EditDistance dist = editDistance(goal, candidate);
537 UINFO(9, "EditDistance dist=" << dist << " cutoff=" << cutoff << " goal=" << goal
538 << " candidate=" << candidate << endl);
539 if (dist < distancer && dist <= cutoff) {
540 distancer = dist;
541 bestCandidate = candidate;
542 }
543 }
544
545 // If goal matches candidate avoid suggesting replacing with self
546 if (distancer == 0) return "";
547 return bestCandidate;
548 }
549
selfTestDistanceOne(const string & a,const string & b,EditDistance expected)550 void VSpellCheck::selfTestDistanceOne(const string& a, const string& b, EditDistance expected) {
551 UASSERT_SELFTEST(EditDistance, editDistance(a, b), expected);
552 UASSERT_SELFTEST(EditDistance, editDistance(b, a), expected);
553 }
554
selfTestSuggestOne(bool matches,const string & c,const string & goal,EditDistance dist)555 void VSpellCheck::selfTestSuggestOne(bool matches, const string& c, const string& goal,
556 EditDistance dist) {
557 EditDistance gdist;
558 VSpellCheck speller;
559 speller.pushCandidate(c);
560 const string got = speller.bestCandidateInfo(goal, gdist /*ref*/);
561 if (matches) {
562 UASSERT_SELFTEST(const string&, got, c);
563 UASSERT_SELFTEST(EditDistance, gdist, dist);
564 } else {
565 UASSERT_SELFTEST(const string&, got, "");
566 }
567 }
568
selfTest()569 void VSpellCheck::selfTest() {
570 {
571 selfTestDistanceOne("ab", "ac", 1);
572 selfTestDistanceOne("ab", "a", 1);
573 selfTestDistanceOne("a", "b", 1);
574 }
575 {
576 selfTestSuggestOne(true, "DEL_ETE", "DELETE", 1);
577 selfTestSuggestOne(true, "abcdef", "acbdef", 1);
578 selfTestSuggestOne(true, "db", "dc", 1);
579 selfTestSuggestOne(true, "db", "dba", 1);
580 // Negative suggestions
581 selfTestSuggestOne(false, "x", "y", 1);
582 selfTestSuggestOne(false, "sqrt", "assert", 3);
583 }
584 {
585 const VSpellCheck speller;
586 UASSERT_SELFTEST(string, "", speller.bestCandidate(""));
587 }
588 {
589 VSpellCheck speller;
590 speller.pushCandidate("fred");
591 speller.pushCandidate("wilma");
592 speller.pushCandidate("barney");
593 UASSERT_SELFTEST(string, "fred", speller.bestCandidate("fre"));
594 UASSERT_SELFTEST(string, "wilma", speller.bestCandidate("whilma"));
595 UASSERT_SELFTEST(string, "barney", speller.bestCandidate("Barney"));
596 UASSERT_SELFTEST(string, "", speller.bestCandidate("nothing close"));
597 }
598 }
599