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