func levenshtein()

in internal/spell/spell.go [43:91]

• 39 lines of code
• 10 McCabe index (conditional complexity)

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)]
}