Branch data     Line data    Source code

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