GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/options/didyoumean.cpp Lines: 1 68 1.5 %
Date: 2021-09-22 Branches: 2 96 2.1 %

Line Exec Source
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
29598
}  // namespace cvc5