1// Copyright 2023 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package http
6
7import (
8	"fmt"
9	"io"
10	"maps"
11	"strings"
12	"testing"
13
14	"slices"
15)
16
17func TestRoutingFirstSegment(t *testing.T) {
18	for _, test := range []struct {
19		in   string
20		want []string
21	}{
22		{"/a/b/c", []string{"a", "b", "c"}},
23		{"/a/b/", []string{"a", "b", "/"}},
24		{"/", []string{"/"}},
25		{"/a/%62/c", []string{"a", "b", "c"}},
26		{"/a%2Fb%2fc", []string{"a/b/c"}},
27	} {
28		var got []string
29		rest := test.in
30		for len(rest) > 0 {
31			var seg string
32			seg, rest = firstSegment(rest)
33			got = append(got, seg)
34		}
35		if !slices.Equal(got, test.want) {
36			t.Errorf("%q: got %v, want %v", test.in, got, test.want)
37		}
38	}
39}
40
41// TODO: test host and method
42var testTree *routingNode
43
44func getTestTree() *routingNode {
45	if testTree == nil {
46		testTree = buildTree("/a", "/a/b", "/a/{x}",
47			"/g/h/i", "/g/{x}/j",
48			"/a/b/{x...}", "/a/b/{y}", "/a/b/{$}")
49	}
50	return testTree
51}
52
53func buildTree(pats ...string) *routingNode {
54	root := &routingNode{}
55	for _, p := range pats {
56		pat, err := parsePattern(p)
57		if err != nil {
58			panic(err)
59		}
60		root.addPattern(pat, nil)
61	}
62	return root
63}
64
65func TestRoutingAddPattern(t *testing.T) {
66	want := `"":
67    "":
68        "a":
69            "/a"
70            "":
71                "/a/{x}"
72            "b":
73                "/a/b"
74                "":
75                    "/a/b/{y}"
76                "/":
77                    "/a/b/{$}"
78                MULTI:
79                    "/a/b/{x...}"
80        "g":
81            "":
82                "j":
83                    "/g/{x}/j"
84            "h":
85                "i":
86                    "/g/h/i"
87`
88
89	var b strings.Builder
90	getTestTree().print(&b, 0)
91	got := b.String()
92	if got != want {
93		t.Errorf("got\n%s\nwant\n%s", got, want)
94	}
95}
96
97type testCase struct {
98	method, host, path string
99	wantPat            string // "" for nil (no match)
100	wantMatches        []string
101}
102
103func TestRoutingNodeMatch(t *testing.T) {
104
105	test := func(tree *routingNode, tests []testCase) {
106		t.Helper()
107		for _, test := range tests {
108			gotNode, gotMatches := tree.match(test.host, test.method, test.path)
109			got := ""
110			if gotNode != nil {
111				got = gotNode.pattern.String()
112			}
113			if got != test.wantPat {
114				t.Errorf("%s, %s, %s: got %q, want %q", test.host, test.method, test.path, got, test.wantPat)
115			}
116			if !slices.Equal(gotMatches, test.wantMatches) {
117				t.Errorf("%s, %s, %s: got matches %v, want %v", test.host, test.method, test.path, gotMatches, test.wantMatches)
118			}
119		}
120	}
121
122	test(getTestTree(), []testCase{
123		{"GET", "", "/a", "/a", nil},
124		{"Get", "", "/b", "", nil},
125		{"Get", "", "/a/b", "/a/b", nil},
126		{"Get", "", "/a/c", "/a/{x}", []string{"c"}},
127		{"Get", "", "/a/b/", "/a/b/{$}", nil},
128		{"Get", "", "/a/b/c", "/a/b/{y}", []string{"c"}},
129		{"Get", "", "/a/b/c/d", "/a/b/{x...}", []string{"c/d"}},
130		{"Get", "", "/g/h/i", "/g/h/i", nil},
131		{"Get", "", "/g/h/j", "/g/{x}/j", []string{"h"}},
132	})
133
134	tree := buildTree(
135		"/item/",
136		"POST /item/{user}",
137		"GET /item/{user}",
138		"/item/{user}",
139		"/item/{user}/{id}",
140		"/item/{user}/new",
141		"/item/{$}",
142		"POST alt.com/item/{user}",
143		"GET /headwins",
144		"HEAD /headwins",
145		"/path/{p...}")
146
147	test(tree, []testCase{
148		{"GET", "", "/item/jba",
149			"GET /item/{user}", []string{"jba"}},
150		{"POST", "", "/item/jba",
151			"POST /item/{user}", []string{"jba"}},
152		{"HEAD", "", "/item/jba",
153			"GET /item/{user}", []string{"jba"}},
154		{"get", "", "/item/jba",
155			"/item/{user}", []string{"jba"}}, // method matches are case-sensitive
156		{"POST", "", "/item/jba/17",
157			"/item/{user}/{id}", []string{"jba", "17"}},
158		{"GET", "", "/item/jba/new",
159			"/item/{user}/new", []string{"jba"}},
160		{"GET", "", "/item/",
161			"/item/{$}", []string{}},
162		{"GET", "", "/item/jba/17/line2",
163			"/item/", nil},
164		{"POST", "alt.com", "/item/jba",
165			"POST alt.com/item/{user}", []string{"jba"}},
166		{"GET", "alt.com", "/item/jba",
167			"GET /item/{user}", []string{"jba"}},
168		{"GET", "", "/item",
169			"", nil}, // does not match
170		{"GET", "", "/headwins",
171			"GET /headwins", nil},
172		{"HEAD", "", "/headwins", // HEAD is more specific than GET
173			"HEAD /headwins", nil},
174		{"GET", "", "/path/to/file",
175			"/path/{p...}", []string{"to/file"}},
176		{"GET", "", "/path/*",
177			"/path/{p...}", []string{"*"}},
178	})
179
180	// A pattern ending in {$} should only match URLS with a trailing slash.
181	pat1 := "/a/b/{$}"
182	test(buildTree(pat1), []testCase{
183		{"GET", "", "/a/b", "", nil},
184		{"GET", "", "/a/b/", pat1, nil},
185		{"GET", "", "/a/b/c", "", nil},
186		{"GET", "", "/a/b/c/d", "", nil},
187	})
188
189	// A pattern ending in a single wildcard should not match a trailing slash URL.
190	pat2 := "/a/b/{w}"
191	test(buildTree(pat2), []testCase{
192		{"GET", "", "/a/b", "", nil},
193		{"GET", "", "/a/b/", "", nil},
194		{"GET", "", "/a/b/c", pat2, []string{"c"}},
195		{"GET", "", "/a/b/c/d", "", nil},
196	})
197
198	// A pattern ending in a multi wildcard should match both URLs.
199	pat3 := "/a/b/{w...}"
200	test(buildTree(pat3), []testCase{
201		{"GET", "", "/a/b", "", nil},
202		{"GET", "", "/a/b/", pat3, []string{""}},
203		{"GET", "", "/a/b/c", pat3, []string{"c"}},
204		{"GET", "", "/a/b/c/d", pat3, []string{"c/d"}},
205	})
206
207	// All three of the above should work together.
208	test(buildTree(pat1, pat2, pat3), []testCase{
209		{"GET", "", "/a/b", "", nil},
210		{"GET", "", "/a/b/", pat1, nil},
211		{"GET", "", "/a/b/c", pat2, []string{"c"}},
212		{"GET", "", "/a/b/c/d", pat3, []string{"c/d"}},
213	})
214}
215
216func TestMatchingMethods(t *testing.T) {
217	hostTree := buildTree("GET a.com/", "PUT b.com/", "POST /foo/{x}")
218	for _, test := range []struct {
219		name       string
220		tree       *routingNode
221		host, path string
222		want       string
223	}{
224		{
225			"post",
226			buildTree("POST /"), "", "/foo",
227			"POST",
228		},
229		{
230			"get",
231			buildTree("GET /"), "", "/foo",
232			"GET,HEAD",
233		},
234		{
235			"host",
236			hostTree, "", "/foo",
237			"",
238		},
239		{
240			"host",
241			hostTree, "", "/foo/bar",
242			"POST",
243		},
244		{
245			"host2",
246			hostTree, "a.com", "/foo/bar",
247			"GET,HEAD,POST",
248		},
249		{
250			"host3",
251			hostTree, "b.com", "/bar",
252			"PUT",
253		},
254		{
255			// This case shouldn't come up because we only call matchingMethods
256			// when there was no match, but we include it for completeness.
257			"empty",
258			buildTree("/"), "", "/",
259			"",
260		},
261	} {
262		t.Run(test.name, func(t *testing.T) {
263			ms := map[string]bool{}
264			test.tree.matchingMethods(test.host, test.path, ms)
265			got := strings.Join(slices.Sorted(maps.Keys(ms)), ",")
266			if got != test.want {
267				t.Errorf("got %s, want %s", got, test.want)
268			}
269		})
270	}
271}
272
273func (n *routingNode) print(w io.Writer, level int) {
274	indent := strings.Repeat("    ", level)
275	if n.pattern != nil {
276		fmt.Fprintf(w, "%s%q\n", indent, n.pattern)
277	}
278	if n.emptyChild != nil {
279		fmt.Fprintf(w, "%s%q:\n", indent, "")
280		n.emptyChild.print(w, level+1)
281	}
282
283	var keys []string
284	n.children.eachPair(func(k string, _ *routingNode) bool {
285		keys = append(keys, k)
286		return true
287	})
288	slices.Sort(keys)
289
290	for _, k := range keys {
291		fmt.Fprintf(w, "%s%q:\n", indent, k)
292		n, _ := n.children.find(k)
293		n.print(w, level+1)
294	}
295
296	if n.multiChild != nil {
297		fmt.Fprintf(w, "%sMULTI:\n", indent)
298		n.multiChild.print(w, level+1)
299	}
300}
301