8000 add max distance limit · coder/coder@06fa1c3 · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit 06fa1c3

Browse files
johnstcnjohnstcn
committed
add max distance limit
1 parent 00a095b commit 06fa1c3

File tree

2 files changed

+35
-7
lines changed

2 files changed

+35
-7
lines changed

‎cli/cliutil/levenshtein/levenshtein.go

Lines changed: 11 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -10,18 +10,22 @@ import (
1010
// If no matches are found, an empty slice is returned.
1111
func Matches(needle string, maxDistance int, haystack ...string) (matches []string) {
1212
for _, hay := range haystack {
13-
if d, err := Distance(needle, hay); err == nil && d <= maxDistance {
13+
if d, err := Distance(needle, hay, maxDistance); err == nil && d <= maxDistance {
1414
matches = append(matches, hay)
1515
}
1616
}
1717

1818
return matches
1919
}
2020

21+
var ErrMaxDist error = xerrors.New("levenshtein: maxDist exceeded")
22+
2123
// Distance returns the edit distance between a and b using the
2224
// Wagner-Fischer algorithm.
2325
// A and B must be less than 255 characters long.
24-
func Distance(a, b string) (int, error) {
26+
// maxDist is the maximum distance to consider.
27+
// A value of -1 for maxDist means no maximum.
28+
func Distance(a, b string, maxDist int) (int, error) {
2529
if len(a) > 255 {
2630
return 0, xerrors.Errorf("levenshtein: a must be less than 255 characters long")
2731
}
@@ -54,7 +58,7 @@ func Distance(a, b string) (int, error) {
5458

5559
// Target prefixes
5660
for j = 1; j < n; j++ {
57-
d[0][j] = j
61+
d[0][j] = j // nolint:gosec // this cannot overflow
5862
}
5963

6064
// Compute the distance
@@ -71,12 +75,15 @@ func Distance(a, b string) (int, error) {
7175
d[i+1][j]+1, // insertion
7276
d[i][j]+subCost, // substitution
7377
)
78+
// check maxDist on the diagonal
79+
if maxDist > -1 && i == j && d[i+1][j+1] > uint8(maxDist) {
80+
return int(d[i+1][j+1]), ErrMaxDist
81+
}
7482
}
7583
}
7684

7785
return int(d[m][n]), nil
7886
}
79-
8087
func min[T constraints.Ordered](ts ...T) T {
8188
if len(ts) == 0 {
8289
panic("min: no arguments")

‎cli/cliutil/levenshtein/levenshtein_test.go

Lines changed: 24 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -104,63 +104,84 @@ func Test_Levenshtein_Distance(t *testing.T) {
104104
Name string
105105
A string
106106
B string
107+
MaxDist int
107108
Expected int
109+
Error string
108110
}{
109111
{
110112
Name: "empty",
111113
A: "",
112114
B: "",
115+
MaxDist: -1,
113116
Expected: 0,
114117
},
115118
{
116119
Name: "a empty",
117120
A: "",
118121
B: "foo",
122+
MaxDist: -1,
119123
Expected: 3,
120124
},
121125
{
122126
Name: "b empty",
123127
A: "foo",
124128
B: "",
129+
MaxDist: -1,
125130
Expected: 3,
126131
},
127132
{
128133
Name: "a is b",
129134
A: "foo",
130135
B: "foo",
136+
MaxDist: -1,
131137
Expected: 0,
132138
},
133139
{
134140
Name: "one addition",
135141
A: "foo",
136142
B: "fooo",
143+
MaxDist: -1,
137144
Expected: 1,
138145
},
139146
{
140147
Name: "one deletion",
141148
A: "fooo",
142149
B: "foo",
150+
MaxDist: -1,
143151
Expected: 1,
144152
},
145153
{
146154
Name: "one substitution",
147155
A: "foo",
148156
B: "fou",
157+
MaxDist: -1,
149158
Expected: 1,
150159
},
151160
{
152161
Name: "different strings entirely",
153162
A: "foo",
154163
B: "bar",
164+
MaxDist: -1,
155165
Expected: 3,
156166
},
167+
{
168+
Name: "different strings, max distance 2",
169+
A: "foo",
170+
B: "bar",
171+
MaxDist: 2,
172+
Error: levenshtein.ErrMaxDist.Error(),
173+
},
157174
} {
158175
tt := tt
159176
t.Run(tt.Name, func(t *testing.T) {
160177
t.Parallel()
161-
actual, err := levenshtein.Distance(tt.A, tt.B)
162-
require.NoError(t, err)
163-
require.Equal(t, tt.Expected, actual)
178+
actual, err := levenshtein.Distance(tt.A, tt.B, tt.MaxDist)
179+
if tt.Error == "" {
180+
require.NoError(t, err)
181+
require.Equal(t, tt.Expected, actual)
182+
} else {
183+
require.EqualError(t, err, tt.Error)
184+
}
164185
})
165186
}
166187
}

0 commit comments

Comments
 (0)
0