1// Package spell file defines a simple spelling checker for use in attribute errors 2// such as "no such field .foo; did you mean .food?". 3package spell 4 5import ( 6 "strings" 7 "unicode" 8) 9 10// Nearest returns the element of candidates 11// nearest to x using the Levenshtein metric, 12// or "" if none were promising. 13func Nearest(x string, candidates []string) string { 14 // Ignore underscores and case when matching. 15 fold := func(s string) string { 16 return strings.Map(func(r rune) rune { 17 if r == '_' { 18 return -1 19 } 20 return unicode.ToLower(r) 21 }, s) 22 } 23 24 x = fold(x) 25 26 var best string 27 bestD := (len(x) + 1) / 2 // allow up to 50% typos 28 for _, c := range candidates { 29 d := levenshtein(x, fold(c), bestD) 30 if d < bestD { 31 bestD = d 32 best = c 33 } 34 } 35 return best 36} 37 38// levenshtein returns the non-negative Levenshtein edit distance 39// between the byte strings x and y. 40// 41// If the computed distance exceeds max, 42// the function may return early with an approximate value > max. 43func levenshtein(x, y string, max int) int { 44 // This implementation is derived from one by Laurent Le Brun in 45 // Bazel that uses the single-row space efficiency trick 46 // described at bitbucket.org/clearer/iosifovich. 47 48 // Let x be the shorter string. 49 if len(x) > len(y) { 50 x, y = y, x 51 } 52 53 // Remove common prefix. 54 for i := 0; i < len(x); i++ { 55 if x[i] != y[i] { 56 x = x[i:] 57 y = y[i:] 58 break 59 } 60 } 61 if x == "" { 62 return len(y) 63 } 64 65 if d := abs(len(x) - len(y)); d > max { 66 return d // excessive length divergence 67 } 68 69 row := make([]int, len(y)+1) 70 for i := range row { 71 row[i] = i 72 } 73 74 for i := 1; i <= len(x); i++ { 75 row[0] = i 76 best := i 77 prev := i - 1 78 for j := 1; j <= len(y); j++ { 79 a := prev + b2i(x[i-1] != y[j-1]) // substitution 80 b := 1 + row[j-1] // deletion 81 c := 1 + row[j] // insertion 82 k := min(a, min(b, c)) 83 prev, row[j] = row[j], k 84 best = min(best, k) 85 } 86 if best > max { 87 return best 88 } 89 } 90 return row[len(y)] 91} 92 93func b2i(b bool) int { 94 if b { 95 return 1 96 } else { 97 return 0 98 } 99} 100 101func min(x, y int) int { 102 if x < y { 103 return x 104 } else { 105 return y 106 } 107} 108 109func abs(x int) int { 110 if x >= 0 { 111 return x 112 } else { 113 return -x 114 } 115} 116