net/http: index patterns for faster conflict detection
Add an index so that pattern registration isn't always quadratic.
If there were no index, then every pattern that was registered would
have to be compared to every existing pattern for conflicts. This
would make registration quadratic in the number of patterns, in every
case.
The index in this CL should help most of the time. If a pattern has a
literal segment, it will weed out all other patterns that have a
different literal in that position.
The worst case will still be quadratic, but it is unlikely that a set
of such patterns would arise naturally.
One novel (to me) aspect of the CL is the use of fuzz testing on data
that is neither a string nor a byte slice. The test uses fuzzing to
generate a byte slice, then decodes the byte slice into a valid
pattern (most of the time). This test actually caught a bug: see
https://go.dev/cl/529119.
Change-Id: Ice0be6547decb5ce75a8062e4e17227815d5d0b0
Reviewed-on: https://go-review.googlesource.com/c/go/+/529121
Run-TryBot: Jonathan Amsterdam <jba@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Damien Neil <dneil@google.com>