diff options
Diffstat (limited to 'internal/spell/spell.go')
-rw-r--r-- | internal/spell/spell.go | 115 |
1 files changed, 115 insertions, 0 deletions
diff --git a/internal/spell/spell.go b/internal/spell/spell.go new file mode 100644 index 0000000..7739fab --- /dev/null +++ b/internal/spell/spell.go @@ -0,0 +1,115 @@ +// Package spell file defines a simple spelling checker for use in attribute errors +// such as "no such field .foo; did you mean .food?". +package spell + +import ( + "strings" + "unicode" +) + +// Nearest returns the element of candidates +// nearest to x using the Levenshtein metric, +// or "" if none were promising. +func Nearest(x string, candidates []string) string { + // Ignore underscores and case when matching. + fold := func(s string) string { + return strings.Map(func(r rune) rune { + if r == '_' { + return -1 + } + return unicode.ToLower(r) + }, s) + } + + x = fold(x) + + var best string + bestD := (len(x) + 1) / 2 // allow up to 50% typos + for _, c := range candidates { + d := levenshtein(x, fold(c), bestD) + if d < bestD { + bestD = d + best = c + } + } + return best +} + +// levenshtein returns the non-negative Levenshtein edit distance +// between the byte strings x and y. +// +// If the computed distance exceeds max, +// the function may return early with an approximate value > max. +func levenshtein(x, y string, max int) int { + // This implementation is derived from one by Laurent Le Brun in + // Bazel that uses the single-row space efficiency trick + // described at bitbucket.org/clearer/iosifovich. + + // Let x be the shorter string. + if len(x) > len(y) { + x, y = y, x + } + + // Remove common prefix. + for i := 0; i < len(x); i++ { + if x[i] != y[i] { + x = x[i:] + y = y[i:] + break + } + } + if x == "" { + return len(y) + } + + if d := abs(len(x) - len(y)); d > max { + return d // excessive length divergence + } + + row := make([]int, len(y)+1) + for i := range row { + row[i] = i + } + + for i := 1; i <= len(x); i++ { + row[0] = i + best := i + prev := i - 1 + for j := 1; j <= len(y); j++ { + a := prev + b2i(x[i-1] != y[j-1]) // substitution + b := 1 + row[j-1] // deletion + c := 1 + row[j] // insertion + k := min(a, min(b, c)) + prev, row[j] = row[j], k + best = min(best, k) + } + if best > max { + return best + } + } + return row[len(y)] +} + +func b2i(b bool) int { + if b { + return 1 + } else { + return 0 + } +} + +func min(x, y int) int { + if x < y { + return x + } else { + return y + } +} + +func abs(x int) int { + if x >= 0 { + return x + } else { + return -x + } +} |