spell.go

Documentation: go.starlark.net/internal/spell

     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?".
     3  package spell
     4  
     5  import (
     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.
    13  func 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.
    43  func 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  
    93  func b2i(b bool) int {
    94  	if b {
    95  		return 1
    96  	} else {
    97  		return 0
    98  	}
    99  }
   100  
   101  func min(x, y int) int {
   102  	if x < y {
   103  		return x
   104  	} else {
   105  		return y
   106  	}
   107  }
   108  
   109  func abs(x int) int {
   110  	if x >= 0 {
   111  		return x
   112  	} else {
   113  		return -x
   114  	}
   115  }
   116
View as plain text