package misspell import ( "math" "testing" ) func TestAlmostEqual(t *testing.T) { t.Parallel() tcs := []struct { inA string inB string want bool }{ {"", "", true}, {"", "a", true}, {"a", "a", true}, {"a", "b", true}, {"hello", "hell", true}, {"hello", "jello", true}, {"hello", "helol", true}, {"hello", "jelol", false}, } for _, tc := range tcs { got := AlmostEqual(tc.inA, tc.inB) if got != tc.want { t.Errorf("AlmostEqual(%q, %q) = %v, want %v", tc.inA, tc.inB, got, tc.want) } // two tests for the price of one \o/ if got != AlmostEqual(tc.inB, tc.inA) { t.Errorf("AlmostEqual(%q, %q) == %v != AlmostEqual(%q, %q)", tc.inA, tc.inB, got, tc.inB, tc.inA) } } } func FuzzAlmostEqual(f *testing.F) { f.Add("", "") f.Add("", "a") f.Add("a", "a") f.Add("a", "b") f.Add("hello", "hell") f.Add("hello", "jello") f.Add("hello", "helol") f.Add("hello", "jelol") f.Fuzz(func(t *testing.T, a, b string) { if len(a) > 10 || len(b) > 10 { // longer strings won't add coverage, but take longer to check return } d := editDistance([]rune(a), []rune(b)) got := AlmostEqual(a, b) if want := d <= 1; got != want { t.Errorf("AlmostEqual(%q, %q) = %v, editDistance(%q, %q) = %d", a, b, got, a, b, d) } if got != AlmostEqual(b, a) { t.Errorf("AlmostEqual(%q, %q) == %v != AlmostEqual(%q, %q)", a, b, got, b, a) } }) } // editDistance returns the Damerau-Levenshtein distance between a and b. It is // inefficient, but by keeping almost verbatim to the recursive definition from // Wikipedia, hopefully "obviously correct" and thus suitable for the fuzzing // test of AlmostEqual. func editDistance(a, b []rune) int { i, j := len(a), len(b) m := math.MaxInt if i == 0 && j == 0 { return 0 } if i > 0 { m = min(m, editDistance(a[1:], b)+1) } if j > 0 { m = min(m, editDistance(a, b[1:])+1) } if i > 0 && j > 0 { d := editDistance(a[1:], b[1:]) if a[0] != b[0] { d += 1 } m = min(m, d) } if i > 1 && j > 1 && a[0] == b[1] && a[1] == b[0] { d := editDistance(a[2:], b[2:]) if a[0] != b[0] { d += 1 } m = min(m, d) } return m } func min(a, b int) int { if a < b { return a } return b }