1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Kshitij Bansal, Tim King, Clark Barrett |
4 |
|
* |
5 |
|
* This file is part of the cvc5 project. |
6 |
|
* |
7 |
|
* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS |
8 |
|
* in the top-level source directory and their institutional affiliations. |
9 |
|
* All rights reserved. See the file COPYING in the top-level source |
10 |
|
* directory for licensing information. |
11 |
|
* **************************************************************************** |
12 |
|
* |
13 |
|
* Did-you-mean style suggestions. |
14 |
|
* |
15 |
|
* ``What do you mean? I don't understand.'' An attempt to be more |
16 |
|
* helpful than that. Similar to one in git. |
17 |
|
* |
18 |
|
* There are no dependencies on cvc5 (except namespace). |
19 |
|
*/ |
20 |
|
|
21 |
|
#include "options/didyoumean.h" |
22 |
|
|
23 |
|
#include <iostream> |
24 |
|
#include <set> |
25 |
|
#include <sstream> |
26 |
|
#include <string> |
27 |
|
#include <vector> |
28 |
|
|
29 |
|
namespace cvc5 { |
30 |
|
|
31 |
|
std::vector<std::string> DidYouMean::getMatch(const std::string& input) |
32 |
|
{ |
33 |
|
/** Magic numbers */ |
34 |
|
const int similarityThreshold = 7; |
35 |
|
const unsigned numMatchesThreshold = 10; |
36 |
|
|
37 |
|
typedef std::set<std::pair<int, std::string> > ScoreSet; |
38 |
|
ScoreSet scores; |
39 |
|
std::vector<std::string> ret; |
40 |
|
for (Words::const_iterator it = d_words.begin(); it != d_words.end(); ++it) { |
41 |
|
std::string s = (*it); |
42 |
|
if (s == input) { |
43 |
|
// if input matches AS-IS just return that |
44 |
|
ret.push_back(s); |
45 |
|
return ret; |
46 |
|
} |
47 |
|
int score; |
48 |
|
if (s.compare(0, input.size(), input) == 0) { |
49 |
|
score = 0; |
50 |
|
} else { |
51 |
|
score = editDistance(input, s) + 1; |
52 |
|
} |
53 |
|
scores.insert(make_pair(score, s)); |
54 |
|
} |
55 |
|
int min_score = scores.begin()->first; |
56 |
|
for (ScoreSet::const_iterator i = scores.begin(); i != scores.end(); ++i) { |
57 |
|
// add if score is overall not too big, and also not much close to |
58 |
|
// the score of the best suggestion |
59 |
|
if (i->first < similarityThreshold && i->first <= min_score + 1) { |
60 |
|
ret.push_back(i->second); |
61 |
|
#ifdef DIDYOUMEAN_DEBUG |
62 |
|
cout << i->second << ": " << i->first << std::endl; |
63 |
|
#endif |
64 |
|
} |
65 |
|
} |
66 |
|
if (ret.size() > numMatchesThreshold) { |
67 |
|
ret.resize(numMatchesThreshold); |
68 |
|
} |
69 |
|
return ret; |
70 |
|
} |
71 |
|
|
72 |
|
int DidYouMean::editDistance(const std::string& a, const std::string& b) { |
73 |
|
// input string: a |
74 |
|
// desired string: b |
75 |
|
|
76 |
|
const size_t swapCost = 0; |
77 |
|
const size_t substituteCost = 2; |
78 |
|
const size_t addCost = 1; |
79 |
|
const size_t deleteCost = 3; |
80 |
|
const size_t switchCaseCost = 0; |
81 |
|
|
82 |
|
size_t len1 = a.size(); |
83 |
|
size_t len2 = b.size(); |
84 |
|
|
85 |
|
size_t* C[3]; |
86 |
|
size_t ii; |
87 |
|
for (ii = 0; ii < 3; ++ii) { |
88 |
|
C[ii] = new size_t[len2 + 1]; |
89 |
|
} |
90 |
|
// int C[3][len2+1]; // cost |
91 |
|
|
92 |
|
for (size_t j = 0; j <= len2; ++j) |
93 |
|
{ |
94 |
|
C[0][j] = j * addCost; |
95 |
|
} |
96 |
|
|
97 |
|
for (size_t i = 1; i <= len1; ++i) |
98 |
|
{ |
99 |
|
size_t cur = i % 3; |
100 |
|
size_t prv = (i + 2) % 3; |
101 |
|
size_t pr2 = (i + 1) % 3; |
102 |
|
|
103 |
|
C[cur][0] = i * deleteCost; |
104 |
|
|
105 |
|
for (size_t j = 1; j <= len2; ++j) |
106 |
|
{ |
107 |
|
C[cur][j] = 100000000; // INF |
108 |
|
|
109 |
|
if (a[i - 1] == b[j - 1]) { |
110 |
|
// match |
111 |
|
C[cur][j] = std::min(C[cur][j], C[prv][j - 1]); |
112 |
|
} else if (tolower(a[i - 1]) == tolower(b[j - 1])) { |
113 |
|
// switch case |
114 |
|
C[cur][j] = std::min(C[cur][j], C[prv][j - 1] + switchCaseCost); |
115 |
|
} else { |
116 |
|
// substitute |
117 |
|
C[cur][j] = std::min(C[cur][j], C[prv][j - 1] + substituteCost); |
118 |
|
} |
119 |
|
|
120 |
|
// swap |
121 |
|
if (i >= 2 && j >= 2 && a[i - 1] == b[j - 2] && a[i - 2] == b[j - 1]) { |
122 |
|
C[cur][j] = std::min(C[cur][j], C[pr2][j - 2] + swapCost); |
123 |
|
} |
124 |
|
|
125 |
|
// add |
126 |
|
C[cur][j] = std::min(C[cur][j], C[cur][j - 1] + addCost); |
127 |
|
|
128 |
|
// delete |
129 |
|
C[cur][j] = std::min(C[cur][j], C[prv][j] + deleteCost); |
130 |
|
|
131 |
|
#ifdef DIDYOUMEAN_DEBUG1 |
132 |
|
std::cout << "C[" << cur << "][" << 0 << "] = " << C[cur][0] << std::endl; |
133 |
|
#endif |
134 |
|
} |
135 |
|
} |
136 |
|
int result = C[len1 % 3][len2]; |
137 |
|
for (ii = 0; ii < 3; ++ii) { |
138 |
|
delete[] C[ii]; |
139 |
|
} |
140 |
|
return result; |
141 |
|
} |
142 |
|
|
143 |
|
std::string DidYouMean::getMatchAsString(const std::string& input, |
144 |
|
uint64_t prefixNewLines, |
145 |
|
uint64_t suffixNewLines) |
146 |
|
{ |
147 |
|
std::vector<std::string> matches = getMatch(input); |
148 |
|
std::ostringstream oss; |
149 |
|
if (matches.size() > 0) { |
150 |
|
while (prefixNewLines-- > 0) { |
151 |
|
oss << std::endl; |
152 |
|
} |
153 |
|
if (matches.size() == 1) { |
154 |
|
oss << "Did you mean this?"; |
155 |
|
} else { |
156 |
|
oss << "Did you mean any of these?"; |
157 |
|
} |
158 |
|
for (size_t i = 0; i < matches.size(); ++i) |
159 |
|
{ |
160 |
|
oss << "\n " << matches[i]; |
161 |
|
} |
162 |
|
while (suffixNewLines-- > 0) { |
163 |
|
oss << std::endl; |
164 |
|
} |
165 |
|
} |
166 |
|
return oss.str(); |
167 |
|
} |
168 |
|
|
169 |
29322 |
} // namespace cvc5 |