Levenshtein distance for near-miss flag suggestions (two-row DP; inputs * are schema property names, well under the buffer sizes used here). */
| 12439 | /* Levenshtein distance for near-miss flag suggestions (two-row DP; inputs |
| 12440 | * are schema property names, well under the buffer sizes used here). */ |
| 12441 | static int cli_edit_distance(const char *a, const char *b) { |
| 12442 | enum { CLI_ED_MAX = 128 }; |
| 12443 | size_t la = strlen(a); |
| 12444 | size_t lb = strlen(b); |
| 12445 | if (la >= CLI_ED_MAX || lb >= CLI_ED_MAX) { |
| 12446 | return CLI_ED_MAX; |
| 12447 | } |
| 12448 | int prev[CLI_ED_MAX + 1]; |
| 12449 | int cur[CLI_ED_MAX + 1]; |
| 12450 | for (size_t j = 0; j <= lb; j++) { |
| 12451 | prev[j] = (int)j; |
| 12452 | } |
| 12453 | for (size_t i = 1; i <= la; i++) { |
| 12454 | cur[0] = (int)i; |
| 12455 | for (size_t j = 1; j <= lb; j++) { |
| 12456 | int cost = (a[i - 1] == b[j - 1]) ? 0 : 1; |
| 12457 | int del = prev[j] + 1; |
| 12458 | int ins = cur[j - 1] + 1; |
| 12459 | int sub = prev[j - 1] + cost; |
| 12460 | int m = del < ins ? del : ins; |
| 12461 | cur[j] = m < sub ? m : sub; |
| 12462 | } |
| 12463 | memcpy(prev, cur, (lb + 1) * sizeof(int)); |
| 12464 | } |
| 12465 | return prev[lb]; |
| 12466 | } |
| 12467 | |
| 12468 | /* Closest schema property to `key` for a "did you mean" suggestion, or NULL |
| 12469 | * when nothing is plausibly near (distance > half the key length, min 2). */ |