routing_tree_test.go

     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  
     5  package http
     6  
     7  import (
     8  	"fmt"
     9  	"io"
    10  	"maps"
    11  	"strings"
    12  	"testing"
    13  
    14  	"slices"
    15  )
    16  
    17  func 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
    42  var testTree *routingNode
    43  
    44  func 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  
    53  func 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  
    65  func 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  
    97  type testCase struct {
    98  	method, host, path string
    99  	wantPat            string // "" for nil (no match)
   100  	wantMatches        []string
   101  }
   102  
   103  func 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  
   216  func 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  
   273  func (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
View as plain text