Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Gereon Kremer, Kshitij Bansal, Tim King
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2025 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 "util/didyoumean.h"
      22                 :            : 
      23                 :            : #include <algorithm>
      24                 :            : #include <array>
      25                 :            : #include <cstdint>
      26                 :            : #include <sstream>
      27                 :            : #include <string>
      28                 :            : #include <vector>
      29                 :            : 
      30                 :            : namespace cvc5::internal {
      31                 :            : 
      32                 :            : namespace {
      33                 :            : 
      34                 :        855 : uint64_t editDistance(const std::string& a, const std::string& b) {
      35                 :            :   // input string: a
      36                 :            :   // desired string: b
      37                 :            : 
      38                 :        855 :   constexpr uint64_t swapCost = 0;
      39                 :        855 :   constexpr uint64_t substituteCost = 2;
      40                 :        855 :   constexpr uint64_t addCost = 1;
      41                 :        855 :   constexpr uint64_t deleteCost = 2;
      42                 :        855 :   constexpr uint64_t switchCaseCost = 0;
      43                 :            : 
      44                 :        855 :   uint64_t len1 = a.size();
      45                 :        855 :   uint64_t len2 = b.size();
      46                 :            : 
      47                 :        855 :   std::array<std::vector<uint64_t>, 3> C;
      48         [ +  + ]:       3420 :   for (auto& c: C)
      49                 :            :   {
      50                 :       2565 :     c.resize(len2 + 1);
      51                 :            :   }
      52                 :            :   //  int C[3][len2+1];             // cost
      53                 :            : 
      54         [ +  + ]:      17587 :   for (uint64_t j = 0; j <= len2; ++j)
      55                 :            :   {
      56                 :      16732 :     C[0][j] = j * addCost;
      57                 :            :   }
      58                 :            : 
      59         [ +  + ]:      13506 :   for (uint64_t i = 1; i <= len1; ++i)
      60                 :            :   {
      61                 :      12651 :     uint64_t cur = i % 3;
      62                 :      12651 :     uint64_t prv = (i + 2) % 3;
      63                 :      12651 :     uint64_t pr2 = (i + 1) % 3;
      64                 :            : 
      65                 :      12651 :     C[cur][0] = i * deleteCost;
      66                 :            : 
      67         [ +  + ]:     249820 :     for (uint64_t j = 1; j <= len2; ++j)
      68                 :            :     {
      69                 :     237169 :       C[cur][j] = 100000000;  // INF
      70                 :            : 
      71         [ +  + ]:     237169 :       if (a[i - 1] == b[j - 1]) {
      72                 :            :         // match
      73                 :      19362 :         C[cur][j] = std::min(C[cur][j], C[prv][j - 1]);
      74         [ +  + ]:     217807 :       } else if (tolower(a[i - 1]) == tolower(b[j - 1])) {
      75                 :            :         // switch case
      76                 :          1 :         C[cur][j] = std::min(C[cur][j], C[prv][j - 1] + switchCaseCost);
      77                 :            :       } else {
      78                 :            :         // substitute
      79                 :     217806 :         C[cur][j] = std::min(C[cur][j], C[prv][j - 1] + substituteCost);
      80                 :            :       }
      81                 :            : 
      82                 :            :       // swap
      83 [ +  + ][ +  + ]:     237169 :       if (i >= 2 && j >= 2 && a[i - 1] == b[j - 2] && a[i - 2] == b[j - 1]) {
         [ +  + ][ +  + ]
                 [ +  + ]
      84                 :       1276 :         C[cur][j] = std::min(C[cur][j], C[pr2][j - 2] + swapCost);
      85                 :            :       }
      86                 :            : 
      87                 :            :       // add
      88                 :     237169 :       C[cur][j] = std::min(C[cur][j], C[cur][j - 1] + addCost);
      89                 :            : 
      90                 :            :       // delete
      91                 :     237169 :       C[cur][j] = std::min(C[cur][j], C[prv][j] + deleteCost);
      92                 :            :     }
      93                 :            :   }
      94                 :       1710 :   return C[len1 % 3][len2];
      95                 :            : }
      96                 :            : 
      97                 :            : }
      98                 :            : 
      99                 :         16 : std::vector<std::string> DidYouMean::getMatch(const std::string& input)
     100                 :            : {
     101                 :            :   {
     102                 :         16 :     std::sort(d_words.begin(), d_words.end());
     103                 :         16 :     auto it = std::unique(d_words.begin(), d_words.end());
     104                 :         16 :     d_words.erase(it, d_words.end());
     105                 :            :   }
     106                 :            : 
     107                 :            :   /** Magic numbers */
     108                 :         16 :   constexpr uint64_t similarityThreshold = 10;
     109                 :         16 :   constexpr uint64_t numMatchesThreshold = 10;
     110                 :            : 
     111                 :         32 :   std::vector<std::pair<uint64_t,std::string>> scores;
     112                 :         16 :   std::vector<std::string> ret;
     113         [ +  + ]:      12751 :   for (const auto& s: d_words) {
     114         [ +  + ]:      12736 :     if (s == input) {
     115                 :            :       // if input matches AS-IS just return that
     116                 :          1 :       ret.emplace_back(s);
     117                 :          1 :       return ret;
     118                 :            :     }
     119                 :      12735 :     uint64_t score = 0;
     120         [ +  + ]:      12735 :     if (s.compare(0, input.size(), input) != 0) {
     121                 :        855 :       score = editDistance(input, s) + 1;
     122                 :            :     }
     123                 :      12735 :     scores.emplace_back(std::make_pair(score, s));
     124                 :            :   }
     125                 :         15 :   std::sort(scores.begin(), scores.end());
     126                 :         15 :   const uint64_t min_score = scores.begin()->first;
     127         [ +  - ]:        102 :   for (const auto& score: scores) {
     128                 :            :     // from here on, matches are not similar enough
     129         [ +  + ]:        102 :     if (score.first > similarityThreshold) break;
     130                 :            :     // from here on, matches are way worse than the best one
     131         [ +  + ]:        100 :     if (score.first > min_score + 4) break;
     132                 :            :     // we already have enough matches
     133         [ +  + ]:         95 :     if (ret.size() >= numMatchesThreshold) break;
     134                 :         87 :     ret.push_back(score.second);
     135                 :            :   }
     136                 :         15 :   return ret;
     137                 :            : }
     138                 :            : 
     139                 :         12 : std::string DidYouMean::getMatchAsString(const std::string& input)
     140                 :            : {
     141                 :         24 :   std::vector<std::string> matches = getMatch(input);
     142                 :         24 :   std::ostringstream oss;
     143         [ +  + ]:         12 :   if (matches.size() > 0) {
     144                 :         11 :     oss << std::endl << std::endl;
     145         [ +  + ]:         11 :     if (matches.size() == 1) {
     146                 :          2 :       oss << "Did you mean this?";
     147                 :            :     } else {
     148                 :          9 :       oss << "Did you mean any of these?";
     149                 :            :     }
     150         [ +  + ]:         95 :     for (size_t i = 0; i < matches.size(); ++i)
     151                 :            :     {
     152                 :         84 :       oss << "\n        " << matches[i];
     153                 :            :     }
     154                 :            :   }
     155                 :         24 :   return oss.str();
     156                 :            : }
     157                 :            : 
     158                 :            : }  // namespace cvc5::internal