Skip to content

Commit 817c01f

Browse files
BrunoQuaresmaBrunoQuaresma
committed
Merge branch 'main' of https://github.com/coder/coder into bq/improve-template-empty
2 parents 250f764 + 0cb875c commit 817c01f

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

47 files changed

+2020
-321
lines changed

‎.devcontainer/devcontainer.json

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,13 @@
11
{
22
"name": "Development environments on your infrastructure",
3-
"image": "codercom/oss-dogfood:latest",
3+
"image": "codercom/oss-dogfood:pre-nix",
44

55
"features": {
66
// See all possible options here https://github.com/devcontainers/features/tree/main/src/docker-in-docker
7-
"ghcr.io/devcontainers/features/docker-in-docker:2": {}
7+
"ghcr.io/devcontainers/features/docker-in-docker:2": {
8+
"moby": "false"
9+
}
810
},
911
// SYS_PTRACE to enable go debugging
10-
// without --priviliged the Github Codespace build fails (not required otherwise)
11-
"runArgs": ["--cap-add=SYS_PTRACE", "--privileged"]
12+
"runArgs": ["--cap-add=SYS_PTRACE"]
1213
}

‎cli/cliutil/levenshtein/levenshtein.go

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
package levenshtein
2+
3+
import (
4+
"golang.org/x/exp/constraints"
5+
"golang.org/x/xerrors"
6+
)
7+
8+
// Matches returns the closest matches to the needle from the haystack.
9+
// The maxDistance parameter is the maximum Matches distance to consider.
10+
// If no matches are found, an empty slice is returned.
11+
func Matches(needle string, maxDistance int, haystack ...string) (matches []string) {
12+
for _, hay := range haystack {
13+
if d, err := Distance(needle, hay, maxDistance); err == nil && d <= maxDistance {
14+
matches = append(matches, hay)
15+
}
16+
}
17+
18+
return matches
19+
}
20+
21+
var ErrMaxDist = xerrors.New("levenshtein: maxDist exceeded")
22+
23+
// Distance returns the edit distance between a and b using the
24+
// Wagner-Fischer algorithm.
25+
// A and B must be less than 255 characters long.
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) {
29+
if len(a) > 255 {
30+
return 0, xerrors.Errorf("levenshtein: a must be less than 255 characters long")
31+
}
32+
if len(b) > 255 {
33+
return 0, xerrors.Errorf("levenshtein: b must be less than 255 characters long")
34+
}
35+
m := uint8(len(a))
36+
n := uint8(len(b))
37+
38+
// Special cases for empty strings
39+
if m == 0 {
40+
return int(n), nil
41+
}
42+
if n == 0 {
43+
return int(m), nil
44+
}
45+
46+
// Allocate a matrix of size m+1 * n+1
47+
d := make([][]uint8, 0)
48+
var i, j uint8
49+
for i = 0; i < m+1; i++ {
50+
di := make([]uint8, n+1)
51+
d = append(d, di)
52+
}
53+
54+
// Source prefixes
55+
for i = 1; i < m+1; i++ {
56+
d[i][0] = i
57+
}
58+
59+
// Target prefixes
60+
for j = 1; j < n; j++ {
61+
d[0][j] = j // nolint:gosec // this cannot overflow
62+
}
63+
64+
// Compute the distance
65+
for j = 0; j < n; j++ {
66+
for i = 0; i < m; i++ {
67+
var subCost uint8
68+
// Equal
69+
if a[i] != b[j] {
70+
subCost = 1
71+
}
72+
// Don't forget: matrix is +1 size
73+
d[i+1][j+1] = min(
74+
d[i][j+1]+1, // deletion
75+
d[i+1][j]+1, // insertion
76+
d[i][j]+subCost, // substitution
77+
)
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+
}
82+
}
83+
}
84+
85+
return int(d[m][n]), nil
86+
}
87+
88+
func min[T constraints.Ordered](ts ...T) T {
89+
if len(ts) == 0 {
90+
panic("min: no arguments")
91+
}
92+
m := ts[0]
93+
for _, t := range ts[1:] {
94+
if t < m {
95+
m = t
96+
}
97+
}
98+
return m
99+
}

‎cli/cliutil/levenshtein/levenshtein_test.go

Lines changed: 194 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,194 @@
1+
package levenshtein_test
2+
3+
import (
4+
"testing"
5+
6+
"github.com/stretchr/testify/require"
7+
8+
"github.com/coder/coder/v2/cli/cliutil/levenshtein"
9+
)
10+
11+
func Test_Levenshtein_Matches(t *testing.T) {
12+
t.Parallel()
13+
for _, tt := range []struct {
14+
Name string
15+
Needle string
16+
MaxDistance int
17+
Haystack []string
18+
Expected []string
19+
}{
20+
{
21+
Name: "empty",
22+
Needle: "",
23+
MaxDistance: 0,
24+
Haystack: []string{},
25+
Expected: []string{},
26+
},
27+
{
28+
Name: "empty haystack",
29+
Needle: "foo",
30+
MaxDistance: 0,
31+
Haystack: []string{},
32+
Expected: []string{},
33+
},
34+
{
35+
Name: "empty needle",
36+
Needle: "",
37+
MaxDistance: 0,
38+
Haystack: []string{"foo"},
39+
Expected: []string{},
40+
},
41+
{
42+
Name: "exact match distance 0",
43+
Needle: "foo",
44+
MaxDistance: 0,
45+
Haystack: []string{"foo", "fob"},
46+
Expected: []string{"foo"},
47+
},
48+
{
49+
Name: "exact match distance 1",
50+
Needle: "foo",
51+
MaxDistance: 1,
52+
Haystack: []string{"foo", "bar"},
53+
Expected: []string{"foo"},
54+
},
55+
{
56+
Name: "not found",
57+
Needle: "foo",
58+
MaxDistance: 1,
59+
Haystack: []string{"bar"},
60+
Expected: []string{},
61+
},
62+
{
63+
Name: "1 deletion",
64+
Needle: "foo",
65+
MaxDistance: 1,
66+
Haystack: []string{"bar", "fo"},
67+
Expected: []string{"fo"},
68+
},
69+
{
70+
Name: "one deletion, two matches",
71+
Needle: "foo",
72+
MaxDistance: 1,
73+
Haystack: []string{"bar", "fo", "fou"},
74+
Expected: []string{"fo", "fou"},
75+
},
76+
{
77+
Name: "one deletion, one addition",
78+
Needle: "foo",
79+
MaxDistance: 1,
80+
Haystack: []string{"bar", "fo", "fou", "f"},
81+
Expected: []string{"fo", "fou"},
82+
},
83+
{
84+
Name: "distance 2",
85+
Needle: "foo",
86+
MaxDistance: 2,
87+
Haystack: []string{"bar", "boo", "boof"},
88+
Expected: []string{"boo", "boof"},
89+
},
90+
{
91+
Name: "longer input",
92+
Needle: "kuberenetes",
93+
MaxDistance: 5,
94+
Haystack: []string{"kubernetes", "kubeconfig", "kubectl", "kube"},
95+
Expected: []string{"kubernetes"},
96+
},
97+
} {
98+
tt := tt
99+
t.Run(tt.Name, func(t *testing.T) {
100+
t.Parallel()
101+
actual := levenshtein.Matches(tt.Needle, tt.MaxDistance, tt.Haystack...)
102+
require.ElementsMatch(t, tt.Expected, actual)
103+
})
104+
}
105+
}
106+
107+
func Test_Levenshtein_Distance(t *testing.T) {
108+
t.Parallel()
109+
110+
for _, tt := range []struct {
111+
Name string
112+
A string
113+
B string
114+
MaxDist int
115+
Expected int
116+
Error string
117+
}{
118+
{
119+
Name: "empty",
120+
A: "",
121+
B: "",
122+
MaxDist: -1,
123+
Expected: 0,
124+
},
125+
{
126+
Name: "a empty",
127+
A: "",
128+
B: "foo",
129+
MaxDist: -1,
130+
Expected: 3,
131+
},
132+
{
133+
Name: "b empty",
134+
A: "foo",
135+
B: "",
136+
MaxDist: -1,
137+
Expected: 3,
138+
},
139+
{
140+
Name: "a is b",
141+
A: "foo",
142+
B: "foo",
143+
MaxDist: -1,
144+
Expected: 0,
145+
},
146+
{
147+
Name: "one addition",
148+
A: "foo",
149+
B: "fooo",
150+
MaxDist: -1,
151+
Expected: 1,
152+
},
153+
{
154+
Name: "one deletion",
155+
A: "fooo",
156+
B: "foo",
157+
MaxDist: -1,
158+
Expected: 1,
159+
},
160+
{
161+
Name: "one substitution",
162+
A: "foo",
163+
B: "fou",
164+
MaxDist: -1,
165+
Expected: 1,
166+
},
167+
{
168+
Name: "different strings entirely",
169+
A: "foo",
170+
B: "bar",
171+
MaxDist: -1,
172+
Expected: 3,
173+
},
174+
{
175+
Name: "different strings, max distance 2",
176+
A: "foo",
177+
B: "bar",
178+
MaxDist: 2,
179+
Error: levenshtein.ErrMaxDist.Error(),
180+
},
181+
} {
182+
tt := tt
183+
t.Run(tt.Name, func(t *testing.T) {
184+
t.Parallel()
185+
actual, err := levenshtein.Distance(tt.A, tt.B, tt.MaxDist)
186+
if tt.Error == "" {
187+
require.NoError(t, err)
188+
require.Equal(t, tt.Expected, actual)
189+
} else {
190+
require.EqualError(t, err, tt.Error)
191+
}
192+
})
193+
}
194+
}

0 commit comments

Comments
 (0)