From 3602465954016ea1daef407764a7e4f23ab1c198 Mon Sep 17 00:00:00 2001 From: Jonathan Amsterdam Date: Fri, 8 Sep 2023 08:58:29 -0400 Subject: [PATCH] net/http: pattern.conflictsWith Add the conflictsWith method, which determines whether two patterns conflict with each other. Updates #61410. Change-Id: Id4f9a471dc9d0420d927a68d2864128a096b74f4 Reviewed-on: https://go-review.googlesource.com/c/go/+/526616 Run-TryBot: Jonathan Amsterdam Reviewed-by: Eli Bendersky Reviewed-by: Damien Neil TryBot-Result: Gopher Robot --- src/net/http/pattern.go | 188 +++++++++++++++++++++++++++++ src/net/http/pattern_test.go | 224 +++++++++++++++++++++++++++++++++++ 2 files changed, 412 insertions(+) diff --git a/src/net/http/pattern.go b/src/net/http/pattern.go index a04fd901ca..3fd20b711e 100644 --- a/src/net/http/pattern.go +++ b/src/net/http/pattern.go @@ -33,6 +33,12 @@ type pattern struct { loc string // source location of registering call, for helpful messages } +func (p *pattern) String() string { return p.str } + +func (p *pattern) lastSegment() segment { + return p.segments[len(p.segments)-1] +} + // A segment is a pattern piece that matches one or more path segments, or // a trailing slash. // @@ -185,3 +191,185 @@ func isValidWildcardName(s string) bool { } return true } + +// relationship is a relationship between two patterns, p1 and p2. +type relationship string + +const ( + equivalent relationship = "equivalent" // both match the same requests + moreGeneral relationship = "moreGeneral" // p1 matches everything p2 does & more + moreSpecific relationship = "moreSpecific" // p2 matches everything p1 does & more + disjoint relationship = "disjoint" // there is no request that both match + overlaps relationship = "overlaps" // there is a request that both match, but neither is more specific +) + +// conflictsWith reports whether p1 conflicts with p2, that is, whether +// there is a request that both match but where neither is higher precedence +// than the other. +// +// Precedence is defined by two rules: +// 1. Patterns with a host win over patterns without a host. +// 2. Patterns whose method and path is more specific win. One pattern is more +// specific than another if the second matches all the (method, path) pairs +// of the first and more. +// +// If rule 1 doesn't apply, then two patterns conflict if their relationship +// is either equivalence (they match the same set of requests) or overlap +// (they both match some requests, but neither is more specific than the other). +func (p1 *pattern) conflictsWith(p2 *pattern) bool { + if p1.host != p2.host { + // Either one host is empty and the other isn't, in which case the + // one with the host wins by rule 1, or neither host is empty + // and they differ, so they won't match the same paths. + return false + } + rel := p1.comparePathsAndMethods(p2) + return rel == equivalent || rel == overlaps +} + +func (p1 *pattern) comparePathsAndMethods(p2 *pattern) relationship { + mrel := p1.compareMethods(p2) + // Optimization: avoid a call to comparePaths. + if mrel == disjoint { + return disjoint + } + prel := p1.comparePaths(p2) + return combineRelationships(mrel, prel) +} + +// compareMethods determines the relationship between the method +// part of patterns p1 and p2. +// +// A method can either be empty, "GET", or something else. +// The empty string matches any method, so it is the most general. +// "GET" matches both GET and HEAD. +// Anything else matches only itself. +func (p1 *pattern) compareMethods(p2 *pattern) relationship { + if p1.method == p2.method { + return equivalent + } + if p1.method == "" { + // p1 matches any method, but p2 does not, so p1 is more general. + return moreGeneral + } + if p2.method == "" { + return moreSpecific + } + if p1.method == "GET" && p2.method == "HEAD" { + // p1 matches GET and HEAD; p2 matches only HEAD. + return moreGeneral + } + if p2.method == "GET" && p1.method == "HEAD" { + return moreSpecific + } + return disjoint +} + +// comparePaths determines the relationship between the path +// part of two patterns. +func (p1 *pattern) comparePaths(p2 *pattern) relationship { + // Optimization: if a path pattern doesn't end in a multi ("...") wildcard, then it + // can only match paths with the same number of segments. + if len(p1.segments) != len(p2.segments) && !p1.lastSegment().multi && !p2.lastSegment().multi { + return disjoint + } + var segs1, segs2 []segment + // Look at corresponding segments in the two path patterns. + rel := equivalent + for segs1, segs2 = p1.segments, p2.segments; len(segs1) > 0 && len(segs2) > 0; segs1, segs2 = segs1[1:], segs2[1:] { + rel = combineRelationships(rel, compareSegments(segs1[0], segs2[0])) + if rel == disjoint || rel == overlaps { + return rel + } + } + // We've reached the end of the corresponding segments of the patterns. + // If they have the same number of segments, then we've already determined + // their relationship. + if len(segs1) == 0 && len(segs2) == 0 { + return rel + } + // Otherwise, the only way they could fail to be disjoint is if the shorter + // pattern ends in a multi and is more general. + if len(segs1) < len(segs2) && p1.lastSegment().multi && rel == moreGeneral { + return moreGeneral + } + if len(segs2) < len(segs1) && p2.lastSegment().multi && rel == moreSpecific { + return moreSpecific + } + return disjoint +} + +// compareSegments determines the relationship between two segments. +func compareSegments(s1, s2 segment) relationship { + if s1.multi && s2.multi { + return equivalent + } + if s1.multi { + return moreGeneral + } + if s2.multi { + return moreSpecific + } + if s1.wild && s2.wild { + return equivalent + } + if s1.wild { + if s2.s == "/" { + // A single wildcard doesn't match a trailing slash. + return disjoint + } + return moreGeneral + } + if s2.wild { + if s1.s == "/" { + return disjoint + } + return moreSpecific + } + // Both literals. + if s1.s == s2.s { + return equivalent + } + return disjoint +} + +// combineRelationships determines the overall relationship of two patterns +// given the relationships of a partition of the patterns into two parts. +// +// For example, if p1 is more general than p2 in one way but equivalent +// in the other, then it is more general overall. +// +// Or if p1 is more general in one way and more specific in the other, then +// they overlap. +func combineRelationships(r1, r2 relationship) relationship { + switch r1 { + case equivalent: + return r2 + case disjoint, overlaps: + return r1 + case moreGeneral, moreSpecific: + switch r2 { + case equivalent: + return r1 + case inverseRelationship(r1): + return overlaps + default: + return r2 + } + default: + panic(fmt.Sprintf("unknown relationship %q", r1)) + } +} + +// If p1 has relationship `r` to p2, then +// p2 has inverseRelationship(r) to p1. +func inverseRelationship(r relationship) relationship { + switch r { + case moreSpecific: + return moreGeneral + case moreGeneral: + return moreSpecific + default: + return r + } +} diff --git a/src/net/http/pattern_test.go b/src/net/http/pattern_test.go index 759e1267f9..cd27cd8db8 100644 --- a/src/net/http/pattern_test.go +++ b/src/net/http/pattern_test.go @@ -165,3 +165,227 @@ func mustParsePattern(t *testing.T, s string) *pattern { } return p } + +func TestCompareMethods(t *testing.T) { + for _, test := range []struct { + p1, p2 string + want relationship + }{ + {"/", "/", equivalent}, + {"GET /", "GET /", equivalent}, + {"HEAD /", "HEAD /", equivalent}, + {"POST /", "POST /", equivalent}, + {"GET /", "POST /", disjoint}, + {"GET /", "/", moreSpecific}, + {"HEAD /", "/", moreSpecific}, + {"GET /", "HEAD /", moreGeneral}, + } { + pat1 := mustParsePattern(t, test.p1) + pat2 := mustParsePattern(t, test.p2) + got := pat1.compareMethods(pat2) + if got != test.want { + t.Errorf("%s vs %s: got %s, want %s", test.p1, test.p2, got, test.want) + } + got2 := pat2.compareMethods(pat1) + want2 := inverseRelationship(test.want) + if got2 != want2 { + t.Errorf("%s vs %s: got %s, want %s", test.p2, test.p1, got2, want2) + } + } +} + +func TestComparePaths(t *testing.T) { + for _, test := range []struct { + p1, p2 string + want relationship + }{ + // A non-final pattern segment can have one of two values: literal or + // single wildcard. A final pattern segment can have one of 5: empty + // (trailing slash), literal, dollar, single wildcard, or multi + // wildcard. Trailing slash and multi wildcard are the same. + + // A literal should be more specific than anything it overlaps, except itself. + {"/a", "/a", equivalent}, + {"/a", "/b", disjoint}, + {"/a", "/", moreSpecific}, + {"/a", "/{$}", disjoint}, + {"/a", "/{x}", moreSpecific}, + {"/a", "/{x...}", moreSpecific}, + + // Adding a segment doesn't change that. + {"/b/a", "/b/a", equivalent}, + {"/b/a", "/b/b", disjoint}, + {"/b/a", "/b/", moreSpecific}, + {"/b/a", "/b/{$}", disjoint}, + {"/b/a", "/b/{x}", moreSpecific}, + {"/b/a", "/b/{x...}", moreSpecific}, + {"/{z}/a", "/{z}/a", equivalent}, + {"/{z}/a", "/{z}/b", disjoint}, + {"/{z}/a", "/{z}/", moreSpecific}, + {"/{z}/a", "/{z}/{$}", disjoint}, + {"/{z}/a", "/{z}/{x}", moreSpecific}, + {"/{z}/a", "/{z}/{x...}", moreSpecific}, + + // Single wildcard on left. + {"/{z}", "/a", moreGeneral}, + {"/{z}", "/a/b", disjoint}, + {"/{z}", "/{$}", disjoint}, + {"/{z}", "/{x}", equivalent}, + {"/{z}", "/", moreSpecific}, + {"/{z}", "/{x...}", moreSpecific}, + {"/b/{z}", "/b/a", moreGeneral}, + {"/b/{z}", "/b/a/b", disjoint}, + {"/b/{z}", "/b/{$}", disjoint}, + {"/b/{z}", "/b/{x}", equivalent}, + {"/b/{z}", "/b/", moreSpecific}, + {"/b/{z}", "/b/{x...}", moreSpecific}, + + // Trailing slash on left. + {"/", "/a", moreGeneral}, + {"/", "/a/b", moreGeneral}, + {"/", "/{$}", moreGeneral}, + {"/", "/{x}", moreGeneral}, + {"/", "/", equivalent}, + {"/", "/{x...}", equivalent}, + + {"/b/", "/b/a", moreGeneral}, + {"/b/", "/b/a/b", moreGeneral}, + {"/b/", "/b/{$}", moreGeneral}, + {"/b/", "/b/{x}", moreGeneral}, + {"/b/", "/b/", equivalent}, + {"/b/", "/b/{x...}", equivalent}, + + {"/{z}/", "/{z}/a", moreGeneral}, + {"/{z}/", "/{z}/a/b", moreGeneral}, + {"/{z}/", "/{z}/{$}", moreGeneral}, + {"/{z}/", "/{z}/{x}", moreGeneral}, + {"/{z}/", "/{z}/", equivalent}, + {"/{z}/", "/a/", moreGeneral}, + {"/{z}/", "/{z}/{x...}", equivalent}, + {"/{z}/", "/a/{x...}", moreGeneral}, + {"/a/{z}/", "/{z}/a/", overlaps}, + {"/a/{z}/b/", "/{x}/c/{y...}", overlaps}, + + // Multi wildcard on left. + {"/{m...}", "/a", moreGeneral}, + {"/{m...}", "/a/b", moreGeneral}, + {"/{m...}", "/{$}", moreGeneral}, + {"/{m...}", "/{x}", moreGeneral}, + {"/{m...}", "/", equivalent}, + {"/{m...}", "/{x...}", equivalent}, + + {"/b/{m...}", "/b/a", moreGeneral}, + {"/b/{m...}", "/b/a/b", moreGeneral}, + {"/b/{m...}", "/b/{$}", moreGeneral}, + {"/b/{m...}", "/b/{x}", moreGeneral}, + {"/b/{m...}", "/b/", equivalent}, + {"/b/{m...}", "/b/{x...}", equivalent}, + {"/b/{m...}", "/a/{x...}", disjoint}, + + {"/{z}/{m...}", "/{z}/a", moreGeneral}, + {"/{z}/{m...}", "/{z}/a/b", moreGeneral}, + {"/{z}/{m...}", "/{z}/{$}", moreGeneral}, + {"/{z}/{m...}", "/{z}/{x}", moreGeneral}, + {"/{z}/{m...}", "/{w}/", equivalent}, + {"/{z}/{m...}", "/a/", moreGeneral}, + {"/{z}/{m...}", "/{z}/{x...}", equivalent}, + {"/{z}/{m...}", "/a/{x...}", moreGeneral}, + {"/a/{m...}", "/a/b/{y...}", moreGeneral}, + {"/a/{m...}", "/a/{x}/{y...}", moreGeneral}, + {"/a/{z}/{m...}", "/a/b/{y...}", moreGeneral}, + {"/a/{z}/{m...}", "/{z}/a/", overlaps}, + {"/a/{z}/{m...}", "/{z}/b/{y...}", overlaps}, + {"/a/{z}/b/{m...}", "/{x}/c/{y...}", overlaps}, + + // Dollar on left. + {"/{$}", "/a", disjoint}, + {"/{$}", "/a/b", disjoint}, + {"/{$}", "/{$}", equivalent}, + {"/{$}", "/{x}", disjoint}, + {"/{$}", "/", moreSpecific}, + {"/{$}", "/{x...}", moreSpecific}, + + {"/b/{$}", "/b", disjoint}, + {"/b/{$}", "/b/a", disjoint}, + {"/b/{$}", "/b/a/b", disjoint}, + {"/b/{$}", "/b/{$}", equivalent}, + {"/b/{$}", "/b/{x}", disjoint}, + {"/b/{$}", "/b/", moreSpecific}, + {"/b/{$}", "/b/{x...}", moreSpecific}, + {"/b/{$}", "/b/c/{x...}", disjoint}, + {"/b/{x}/a/{$}", "/{x}/c/{y...}", overlaps}, + + {"/{z}/{$}", "/{z}/a", disjoint}, + {"/{z}/{$}", "/{z}/a/b", disjoint}, + {"/{z}/{$}", "/{z}/{$}", equivalent}, + {"/{z}/{$}", "/{z}/{x}", disjoint}, + {"/{z}/{$}", "/{z}/", moreSpecific}, + {"/{z}/{$}", "/a/", overlaps}, + {"/{z}/{$}", "/a/{x...}", overlaps}, + {"/{z}/{$}", "/{z}/{x...}", moreSpecific}, + {"/a/{z}/{$}", "/{z}/a/", overlaps}, + } { + pat1 := mustParsePattern(t, test.p1) + pat2 := mustParsePattern(t, test.p2) + if g := pat1.comparePaths(pat1); g != equivalent { + t.Errorf("%s does not match itself; got %s", pat1, g) + } + if g := pat2.comparePaths(pat2); g != equivalent { + t.Errorf("%s does not match itself; got %s", pat2, g) + } + got := pat1.comparePaths(pat2) + if got != test.want { + t.Errorf("%s vs %s: got %s, want %s", test.p1, test.p2, got, test.want) + t.Logf("pat1: %+v\n", pat1.segments) + t.Logf("pat2: %+v\n", pat2.segments) + } + want2 := inverseRelationship(test.want) + got2 := pat2.comparePaths(pat1) + if got2 != want2 { + t.Errorf("%s vs %s: got %s, want %s", test.p2, test.p1, got2, want2) + } + } +} + +func TestConflictsWith(t *testing.T) { + for _, test := range []struct { + p1, p2 string + want bool + }{ + {"/a", "/a", true}, + {"/a", "/ab", false}, + {"/a/b/cd", "/a/b/cd", true}, + {"/a/b/cd", "/a/b/c", false}, + {"/a/b/c", "/a/c/c", false}, + {"/{x}", "/{y}", true}, + {"/{x}", "/a", false}, // more specific + {"/{x}/{y}", "/{x}/a", false}, + {"/{x}/{y}", "/{x}/a/b", false}, + {"/{x}", "/a/{y}", false}, + {"/{x}/{y}", "/{x}/a/", false}, + {"/{x}", "/a/{y...}", false}, // more specific + {"/{x}/a/{y}", "/{x}/a/{y...}", false}, // more specific + {"/{x}/{y}", "/{x}/a/{$}", false}, // more specific + {"/{x}/{y}/{$}", "/{x}/a/{$}", false}, + {"/a/{x}", "/{x}/b", true}, + {"/", "GET /", false}, + {"/", "GET /foo", false}, + {"GET /", "GET /foo", false}, + {"GET /", "/foo", true}, + {"GET /foo", "HEAD /", true}, + } { + pat1 := mustParsePattern(t, test.p1) + pat2 := mustParsePattern(t, test.p2) + got := pat1.conflictsWith(pat2) + if got != test.want { + t.Errorf("%q.ConflictsWith(%q) = %t, want %t", + test.p1, test.p2, got, test.want) + } + // conflictsWith should be commutative. + got = pat2.conflictsWith(pat1) + if got != test.want { + t.Errorf("%q.ConflictsWith(%q) = %t, want %t", + test.p2, test.p1, got, test.want) + } + } +} -- 2.50.0