Levenshtein distance for near-miss flag suggestions (two-row DP; inputs * are schema property names, well under the buffer sizes used here). */
| 11697 | /* Levenshtein distance for near-miss flag suggestions (two-row DP; inputs |
| 11698 | * are schema property names, well under the buffer sizes used here). */ |
| 11699 | static int cli_edit_distance(const char *a, const char *b) { |
| 11700 | enum { CLI_ED_MAX = 128 }; |
| 11701 | size_t la = strlen(a); |
| 11702 | size_t lb = strlen(b); |
| 11703 | if (la >= CLI_ED_MAX || lb >= CLI_ED_MAX) { |
| 11704 | return CLI_ED_MAX; |
| 11705 | } |
| 11706 | int prev[CLI_ED_MAX + 1]; |
| 11707 | int cur[CLI_ED_MAX + 1]; |
| 11708 | for (size_t j = 0; j <= lb; j++) { |
| 11709 | prev[j] = (int)j; |
| 11710 | } |
| 11711 | for (size_t i = 1; i <= la; i++) { |
| 11712 | cur[0] = (int)i; |
| 11713 | for (size_t j = 1; j <= lb; j++) { |
| 11714 | int cost = (a[i - 1] == b[j - 1]) ? 0 : 1; |
| 11715 | int del = prev[j] + 1; |
| 11716 | int ins = cur[j - 1] + 1; |
| 11717 | int sub = prev[j - 1] + cost; |
| 11718 | int m = del < ins ? del : ins; |
| 11719 | cur[j] = m < sub ? m : sub; |
| 11720 | } |
| 11721 | memcpy(prev, cur, (lb + 1) * sizeof(int)); |
| 11722 | } |
| 11723 | return prev[lb]; |
| 11724 | } |
| 11725 | |
| 11726 | /* Closest schema property to `key` for a "did you mean" suggestion, or NULL |
| 11727 | * when nothing is plausibly near (distance > half the key length, min 2). */ |