GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/options/didyoumean.cpp Lines: 1 68 1.5 %
Date: 2021-03-23 Branches: 2 98 2.0 %

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