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 "slices" 9 "strings" 10 "testing" 11) 12 13func TestParsePattern(t *testing.T) { 14 lit := func(name string) segment { 15 return segment{s: name} 16 } 17 18 wild := func(name string) segment { 19 return segment{s: name, wild: true} 20 } 21 22 multi := func(name string) segment { 23 s := wild(name) 24 s.multi = true 25 return s 26 } 27 28 for _, test := range []struct { 29 in string 30 want pattern 31 }{ 32 {"/", pattern{segments: []segment{multi("")}}}, 33 {"/a", pattern{segments: []segment{lit("a")}}}, 34 { 35 "/a/", 36 pattern{segments: []segment{lit("a"), multi("")}}, 37 }, 38 {"/path/to/something", pattern{segments: []segment{ 39 lit("path"), lit("to"), lit("something"), 40 }}}, 41 { 42 "/{w1}/lit/{w2}", 43 pattern{ 44 segments: []segment{wild("w1"), lit("lit"), wild("w2")}, 45 }, 46 }, 47 { 48 "/{w1}/lit/{w2}/", 49 pattern{ 50 segments: []segment{wild("w1"), lit("lit"), wild("w2"), multi("")}, 51 }, 52 }, 53 { 54 "example.com/", 55 pattern{host: "example.com", segments: []segment{multi("")}}, 56 }, 57 { 58 "GET /", 59 pattern{method: "GET", segments: []segment{multi("")}}, 60 }, 61 { 62 "POST example.com/foo/{w}", 63 pattern{ 64 method: "POST", 65 host: "example.com", 66 segments: []segment{lit("foo"), wild("w")}, 67 }, 68 }, 69 { 70 "/{$}", 71 pattern{segments: []segment{lit("/")}}, 72 }, 73 { 74 "DELETE example.com/a/{foo12}/{$}", 75 pattern{method: "DELETE", host: "example.com", segments: []segment{lit("a"), wild("foo12"), lit("/")}}, 76 }, 77 { 78 "/foo/{$}", 79 pattern{segments: []segment{lit("foo"), lit("/")}}, 80 }, 81 { 82 "/{a}/foo/{rest...}", 83 pattern{segments: []segment{wild("a"), lit("foo"), multi("rest")}}, 84 }, 85 { 86 "//", 87 pattern{segments: []segment{lit(""), multi("")}}, 88 }, 89 { 90 "/foo///./../bar", 91 pattern{segments: []segment{lit("foo"), lit(""), lit(""), lit("."), lit(".."), lit("bar")}}, 92 }, 93 { 94 "a.com/foo//", 95 pattern{host: "a.com", segments: []segment{lit("foo"), lit(""), multi("")}}, 96 }, 97 { 98 "/%61%62/%7b/%", 99 pattern{segments: []segment{lit("ab"), lit("{"), lit("%")}}, 100 }, 101 // Allow multiple spaces matching regexp '[ \t]+' between method and path. 102 { 103 "GET\t /", 104 pattern{method: "GET", segments: []segment{multi("")}}, 105 }, 106 { 107 "POST \t example.com/foo/{w}", 108 pattern{ 109 method: "POST", 110 host: "example.com", 111 segments: []segment{lit("foo"), wild("w")}, 112 }, 113 }, 114 { 115 "DELETE \texample.com/a/{foo12}/{$}", 116 pattern{method: "DELETE", host: "example.com", segments: []segment{lit("a"), wild("foo12"), lit("/")}}, 117 }, 118 } { 119 got := mustParsePattern(t, test.in) 120 if !got.equal(&test.want) { 121 t.Errorf("%q:\ngot %#v\nwant %#v", test.in, got, &test.want) 122 } 123 } 124} 125 126func TestParsePatternError(t *testing.T) { 127 for _, test := range []struct { 128 in string 129 contains string 130 }{ 131 {"", "empty pattern"}, 132 {"A=B /", "at offset 0: invalid method"}, 133 {" ", "at offset 1: host/path missing /"}, 134 {"/{w}x", "at offset 1: bad wildcard segment"}, 135 {"/x{w}", "at offset 1: bad wildcard segment"}, 136 {"/{wx", "at offset 1: bad wildcard segment"}, 137 {"/a/{/}/c", "at offset 3: bad wildcard segment"}, 138 {"/a/{%61}/c", "at offset 3: bad wildcard name"}, // wildcard names aren't unescaped 139 {"/{a$}", "at offset 1: bad wildcard name"}, 140 {"/{}", "at offset 1: empty wildcard"}, 141 {"POST a.com/x/{}/y", "at offset 13: empty wildcard"}, 142 {"/{...}", "at offset 1: empty wildcard"}, 143 {"/{$...}", "at offset 1: bad wildcard"}, 144 {"/{$}/", "at offset 1: {$} not at end"}, 145 {"/{$}/x", "at offset 1: {$} not at end"}, 146 {"/abc/{$}/x", "at offset 5: {$} not at end"}, 147 {"/{a...}/", "at offset 1: {...} wildcard not at end"}, 148 {"/{a...}/x", "at offset 1: {...} wildcard not at end"}, 149 {"{a}/b", "at offset 0: host contains '{' (missing initial '/'?)"}, 150 {"/a/{x}/b/{x...}", "at offset 9: duplicate wildcard name"}, 151 {"GET //", "at offset 4: non-CONNECT pattern with unclean path"}, 152 } { 153 _, err := parsePattern(test.in) 154 if err == nil || !strings.Contains(err.Error(), test.contains) { 155 t.Errorf("%q:\ngot %v, want error containing %q", test.in, err, test.contains) 156 } 157 } 158} 159 160func (p1 *pattern) equal(p2 *pattern) bool { 161 return p1.method == p2.method && p1.host == p2.host && 162 slices.Equal(p1.segments, p2.segments) 163} 164 165func mustParsePattern(tb testing.TB, s string) *pattern { 166 tb.Helper() 167 p, err := parsePattern(s) 168 if err != nil { 169 tb.Fatal(err) 170 } 171 return p 172} 173 174func TestCompareMethods(t *testing.T) { 175 for _, test := range []struct { 176 p1, p2 string 177 want relationship 178 }{ 179 {"/", "/", equivalent}, 180 {"GET /", "GET /", equivalent}, 181 {"HEAD /", "HEAD /", equivalent}, 182 {"POST /", "POST /", equivalent}, 183 {"GET /", "POST /", disjoint}, 184 {"GET /", "/", moreSpecific}, 185 {"HEAD /", "/", moreSpecific}, 186 {"GET /", "HEAD /", moreGeneral}, 187 } { 188 pat1 := mustParsePattern(t, test.p1) 189 pat2 := mustParsePattern(t, test.p2) 190 got := pat1.compareMethods(pat2) 191 if got != test.want { 192 t.Errorf("%s vs %s: got %s, want %s", test.p1, test.p2, got, test.want) 193 } 194 got2 := pat2.compareMethods(pat1) 195 want2 := inverseRelationship(test.want) 196 if got2 != want2 { 197 t.Errorf("%s vs %s: got %s, want %s", test.p2, test.p1, got2, want2) 198 } 199 } 200} 201 202func TestComparePaths(t *testing.T) { 203 for _, test := range []struct { 204 p1, p2 string 205 want relationship 206 }{ 207 // A non-final pattern segment can have one of two values: literal or 208 // single wildcard. A final pattern segment can have one of 5: empty 209 // (trailing slash), literal, dollar, single wildcard, or multi 210 // wildcard. Trailing slash and multi wildcard are the same. 211 212 // A literal should be more specific than anything it overlaps, except itself. 213 {"/a", "/a", equivalent}, 214 {"/a", "/b", disjoint}, 215 {"/a", "/", moreSpecific}, 216 {"/a", "/{$}", disjoint}, 217 {"/a", "/{x}", moreSpecific}, 218 {"/a", "/{x...}", moreSpecific}, 219 220 // Adding a segment doesn't change that. 221 {"/b/a", "/b/a", equivalent}, 222 {"/b/a", "/b/b", disjoint}, 223 {"/b/a", "/b/", moreSpecific}, 224 {"/b/a", "/b/{$}", disjoint}, 225 {"/b/a", "/b/{x}", moreSpecific}, 226 {"/b/a", "/b/{x...}", moreSpecific}, 227 {"/{z}/a", "/{z}/a", equivalent}, 228 {"/{z}/a", "/{z}/b", disjoint}, 229 {"/{z}/a", "/{z}/", moreSpecific}, 230 {"/{z}/a", "/{z}/{$}", disjoint}, 231 {"/{z}/a", "/{z}/{x}", moreSpecific}, 232 {"/{z}/a", "/{z}/{x...}", moreSpecific}, 233 234 // Single wildcard on left. 235 {"/{z}", "/a", moreGeneral}, 236 {"/{z}", "/a/b", disjoint}, 237 {"/{z}", "/{$}", disjoint}, 238 {"/{z}", "/{x}", equivalent}, 239 {"/{z}", "/", moreSpecific}, 240 {"/{z}", "/{x...}", moreSpecific}, 241 {"/b/{z}", "/b/a", moreGeneral}, 242 {"/b/{z}", "/b/a/b", disjoint}, 243 {"/b/{z}", "/b/{$}", disjoint}, 244 {"/b/{z}", "/b/{x}", equivalent}, 245 {"/b/{z}", "/b/", moreSpecific}, 246 {"/b/{z}", "/b/{x...}", moreSpecific}, 247 248 // Trailing slash on left. 249 {"/", "/a", moreGeneral}, 250 {"/", "/a/b", moreGeneral}, 251 {"/", "/{$}", moreGeneral}, 252 {"/", "/{x}", moreGeneral}, 253 {"/", "/", equivalent}, 254 {"/", "/{x...}", equivalent}, 255 256 {"/b/", "/b/a", moreGeneral}, 257 {"/b/", "/b/a/b", moreGeneral}, 258 {"/b/", "/b/{$}", moreGeneral}, 259 {"/b/", "/b/{x}", moreGeneral}, 260 {"/b/", "/b/", equivalent}, 261 {"/b/", "/b/{x...}", equivalent}, 262 263 {"/{z}/", "/{z}/a", moreGeneral}, 264 {"/{z}/", "/{z}/a/b", moreGeneral}, 265 {"/{z}/", "/{z}/{$}", moreGeneral}, 266 {"/{z}/", "/{z}/{x}", moreGeneral}, 267 {"/{z}/", "/{z}/", equivalent}, 268 {"/{z}/", "/a/", moreGeneral}, 269 {"/{z}/", "/{z}/{x...}", equivalent}, 270 {"/{z}/", "/a/{x...}", moreGeneral}, 271 {"/a/{z}/", "/{z}/a/", overlaps}, 272 {"/a/{z}/b/", "/{x}/c/{y...}", overlaps}, 273 274 // Multi wildcard on left. 275 {"/{m...}", "/a", moreGeneral}, 276 {"/{m...}", "/a/b", moreGeneral}, 277 {"/{m...}", "/{$}", moreGeneral}, 278 {"/{m...}", "/{x}", moreGeneral}, 279 {"/{m...}", "/", equivalent}, 280 {"/{m...}", "/{x...}", equivalent}, 281 282 {"/b/{m...}", "/b/a", moreGeneral}, 283 {"/b/{m...}", "/b/a/b", moreGeneral}, 284 {"/b/{m...}", "/b/{$}", moreGeneral}, 285 {"/b/{m...}", "/b/{x}", moreGeneral}, 286 {"/b/{m...}", "/b/", equivalent}, 287 {"/b/{m...}", "/b/{x...}", equivalent}, 288 {"/b/{m...}", "/a/{x...}", disjoint}, 289 290 {"/{z}/{m...}", "/{z}/a", moreGeneral}, 291 {"/{z}/{m...}", "/{z}/a/b", moreGeneral}, 292 {"/{z}/{m...}", "/{z}/{$}", moreGeneral}, 293 {"/{z}/{m...}", "/{z}/{x}", moreGeneral}, 294 {"/{z}/{m...}", "/{w}/", equivalent}, 295 {"/{z}/{m...}", "/a/", moreGeneral}, 296 {"/{z}/{m...}", "/{z}/{x...}", equivalent}, 297 {"/{z}/{m...}", "/a/{x...}", moreGeneral}, 298 {"/a/{m...}", "/a/b/{y...}", moreGeneral}, 299 {"/a/{m...}", "/a/{x}/{y...}", moreGeneral}, 300 {"/a/{z}/{m...}", "/a/b/{y...}", moreGeneral}, 301 {"/a/{z}/{m...}", "/{z}/a/", overlaps}, 302 {"/a/{z}/{m...}", "/{z}/b/{y...}", overlaps}, 303 {"/a/{z}/b/{m...}", "/{x}/c/{y...}", overlaps}, 304 {"/a/{z}/a/{m...}", "/{x}/b", disjoint}, 305 306 // Dollar on left. 307 {"/{$}", "/a", disjoint}, 308 {"/{$}", "/a/b", disjoint}, 309 {"/{$}", "/{$}", equivalent}, 310 {"/{$}", "/{x}", disjoint}, 311 {"/{$}", "/", moreSpecific}, 312 {"/{$}", "/{x...}", moreSpecific}, 313 314 {"/b/{$}", "/b", disjoint}, 315 {"/b/{$}", "/b/a", disjoint}, 316 {"/b/{$}", "/b/a/b", disjoint}, 317 {"/b/{$}", "/b/{$}", equivalent}, 318 {"/b/{$}", "/b/{x}", disjoint}, 319 {"/b/{$}", "/b/", moreSpecific}, 320 {"/b/{$}", "/b/{x...}", moreSpecific}, 321 {"/b/{$}", "/b/c/{x...}", disjoint}, 322 {"/b/{x}/a/{$}", "/{x}/c/{y...}", overlaps}, 323 {"/{x}/b/{$}", "/a/{x}/{y}", disjoint}, 324 {"/{x}/b/{$}", "/a/{x}/c", disjoint}, 325 326 {"/{z}/{$}", "/{z}/a", disjoint}, 327 {"/{z}/{$}", "/{z}/a/b", disjoint}, 328 {"/{z}/{$}", "/{z}/{$}", equivalent}, 329 {"/{z}/{$}", "/{z}/{x}", disjoint}, 330 {"/{z}/{$}", "/{z}/", moreSpecific}, 331 {"/{z}/{$}", "/a/", overlaps}, 332 {"/{z}/{$}", "/a/{x...}", overlaps}, 333 {"/{z}/{$}", "/{z}/{x...}", moreSpecific}, 334 {"/a/{z}/{$}", "/{z}/a/", overlaps}, 335 } { 336 pat1 := mustParsePattern(t, test.p1) 337 pat2 := mustParsePattern(t, test.p2) 338 if g := pat1.comparePaths(pat1); g != equivalent { 339 t.Errorf("%s does not match itself; got %s", pat1, g) 340 } 341 if g := pat2.comparePaths(pat2); g != equivalent { 342 t.Errorf("%s does not match itself; got %s", pat2, g) 343 } 344 got := pat1.comparePaths(pat2) 345 if got != test.want { 346 t.Errorf("%s vs %s: got %s, want %s", test.p1, test.p2, got, test.want) 347 t.Logf("pat1: %+v\n", pat1.segments) 348 t.Logf("pat2: %+v\n", pat2.segments) 349 } 350 want2 := inverseRelationship(test.want) 351 got2 := pat2.comparePaths(pat1) 352 if got2 != want2 { 353 t.Errorf("%s vs %s: got %s, want %s", test.p2, test.p1, got2, want2) 354 } 355 } 356} 357 358func TestConflictsWith(t *testing.T) { 359 for _, test := range []struct { 360 p1, p2 string 361 want bool 362 }{ 363 {"/a", "/a", true}, 364 {"/a", "/ab", false}, 365 {"/a/b/cd", "/a/b/cd", true}, 366 {"/a/b/cd", "/a/b/c", false}, 367 {"/a/b/c", "/a/c/c", false}, 368 {"/{x}", "/{y}", true}, 369 {"/{x}", "/a", false}, // more specific 370 {"/{x}/{y}", "/{x}/a", false}, 371 {"/{x}/{y}", "/{x}/a/b", false}, 372 {"/{x}", "/a/{y}", false}, 373 {"/{x}/{y}", "/{x}/a/", false}, 374 {"/{x}", "/a/{y...}", false}, // more specific 375 {"/{x}/a/{y}", "/{x}/a/{y...}", false}, // more specific 376 {"/{x}/{y}", "/{x}/a/{$}", false}, // more specific 377 {"/{x}/{y}/{$}", "/{x}/a/{$}", false}, 378 {"/a/{x}", "/{x}/b", true}, 379 {"/", "GET /", false}, 380 {"/", "GET /foo", false}, 381 {"GET /", "GET /foo", false}, 382 {"GET /", "/foo", true}, 383 {"GET /foo", "HEAD /", true}, 384 } { 385 pat1 := mustParsePattern(t, test.p1) 386 pat2 := mustParsePattern(t, test.p2) 387 got := pat1.conflictsWith(pat2) 388 if got != test.want { 389 t.Errorf("%q.ConflictsWith(%q) = %t, want %t", 390 test.p1, test.p2, got, test.want) 391 } 392 // conflictsWith should be commutative. 393 got = pat2.conflictsWith(pat1) 394 if got != test.want { 395 t.Errorf("%q.ConflictsWith(%q) = %t, want %t", 396 test.p2, test.p1, got, test.want) 397 } 398 } 399} 400 401func TestRegisterConflict(t *testing.T) { 402 mux := NewServeMux() 403 pat1 := "/a/{x}/" 404 if err := mux.registerErr(pat1, NotFoundHandler()); err != nil { 405 t.Fatal(err) 406 } 407 pat2 := "/a/{y}/{z...}" 408 err := mux.registerErr(pat2, NotFoundHandler()) 409 var got string 410 if err == nil { 411 got = "<nil>" 412 } else { 413 got = err.Error() 414 } 415 want := "matches the same requests as" 416 if !strings.Contains(got, want) { 417 t.Errorf("got\n%s\nwant\n%s", got, want) 418 } 419} 420 421func TestDescribeConflict(t *testing.T) { 422 for _, test := range []struct { 423 p1, p2 string 424 want string 425 }{ 426 {"/a/{x}", "/a/{y}", "the same requests"}, 427 {"/", "/{m...}", "the same requests"}, 428 {"/a/{x}", "/{y}/b", "both match some paths"}, 429 {"/a", "GET /{x}", "matches more methods than GET /{x}, but has a more specific path pattern"}, 430 {"GET /a", "HEAD /", "matches more methods than HEAD /, but has a more specific path pattern"}, 431 {"POST /", "/a", "matches fewer methods than /a, but has a more general path pattern"}, 432 } { 433 got := describeConflict(mustParsePattern(t, test.p1), mustParsePattern(t, test.p2)) 434 if !strings.Contains(got, test.want) { 435 t.Errorf("%s vs. %s:\ngot:\n%s\nwhich does not contain %q", 436 test.p1, test.p2, got, test.want) 437 } 438 } 439} 440 441func TestCommonPath(t *testing.T) { 442 for _, test := range []struct { 443 p1, p2 string 444 want string 445 }{ 446 {"/a/{x}", "/{x}/a", "/a/a"}, 447 {"/a/{z}/", "/{z}/a/", "/a/a/"}, 448 {"/a/{z}/{m...}", "/{z}/a/", "/a/a/"}, 449 {"/{z}/{$}", "/a/", "/a/"}, 450 {"/{z}/{$}", "/a/{x...}", "/a/"}, 451 {"/a/{z}/{$}", "/{z}/a/", "/a/a/"}, 452 {"/a/{x}/b/{y...}", "/{x}/c/{y...}", "/a/c/b/"}, 453 {"/a/{x}/b/", "/{x}/c/{y...}", "/a/c/b/"}, 454 {"/a/{x}/b/{$}", "/{x}/c/{y...}", "/a/c/b/"}, 455 {"/a/{z}/{x...}", "/{z}/b/{y...}", "/a/b/"}, 456 } { 457 pat1 := mustParsePattern(t, test.p1) 458 pat2 := mustParsePattern(t, test.p2) 459 if pat1.comparePaths(pat2) != overlaps { 460 t.Fatalf("%s does not overlap %s", test.p1, test.p2) 461 } 462 got := commonPath(pat1, pat2) 463 if got != test.want { 464 t.Errorf("%s vs. %s: got %q, want %q", test.p1, test.p2, got, test.want) 465 } 466 } 467} 468 469func TestDifferencePath(t *testing.T) { 470 for _, test := range []struct { 471 p1, p2 string 472 want string 473 }{ 474 {"/a/{x}", "/{x}/a", "/a/x"}, 475 {"/{x}/a", "/a/{x}", "/x/a"}, 476 {"/a/{z}/", "/{z}/a/", "/a/z/"}, 477 {"/{z}/a/", "/a/{z}/", "/z/a/"}, 478 {"/{a}/a/", "/a/{z}/", "/ax/a/"}, 479 {"/a/{z}/{x...}", "/{z}/b/{y...}", "/a/z/"}, 480 {"/{z}/b/{y...}", "/a/{z}/{x...}", "/z/b/"}, 481 {"/a/b/", "/a/b/c", "/a/b/"}, 482 {"/a/b/{x...}", "/a/b/c", "/a/b/"}, 483 {"/a/b/{x...}", "/a/b/c/d", "/a/b/"}, 484 {"/a/b/{x...}", "/a/b/c/d/", "/a/b/"}, 485 {"/a/{z}/{m...}", "/{z}/a/", "/a/z/"}, 486 {"/{z}/a/", "/a/{z}/{m...}", "/z/a/"}, 487 {"/{z}/{$}", "/a/", "/z/"}, 488 {"/a/", "/{z}/{$}", "/a/x"}, 489 {"/{z}/{$}", "/a/{x...}", "/z/"}, 490 {"/a/{foo...}", "/{z}/{$}", "/a/foo"}, 491 {"/a/{z}/{$}", "/{z}/a/", "/a/z/"}, 492 {"/{z}/a/", "/a/{z}/{$}", "/z/a/x"}, 493 {"/a/{x}/b/{y...}", "/{x}/c/{y...}", "/a/x/b/"}, 494 {"/{x}/c/{y...}", "/a/{x}/b/{y...}", "/x/c/"}, 495 {"/a/{c}/b/", "/{x}/c/{y...}", "/a/cx/b/"}, 496 {"/{x}/c/{y...}", "/a/{c}/b/", "/x/c/"}, 497 {"/a/{x}/b/{$}", "/{x}/c/{y...}", "/a/x/b/"}, 498 {"/{x}/c/{y...}", "/a/{x}/b/{$}", "/x/c/"}, 499 } { 500 pat1 := mustParsePattern(t, test.p1) 501 pat2 := mustParsePattern(t, test.p2) 502 rel := pat1.comparePaths(pat2) 503 if rel != overlaps && rel != moreGeneral { 504 t.Fatalf("%s vs. %s are %s, need overlaps or moreGeneral", pat1, pat2, rel) 505 } 506 got := differencePath(pat1, pat2) 507 if got != test.want { 508 t.Errorf("%s vs. %s: got %q, want %q", test.p1, test.p2, got, test.want) 509 } 510 } 511} 512