blob: d480cba021832159858a9227cb6871173006d71d [file] [log] [blame]
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package http
import (
"fmt"
"slices"
"strings"
"testing"
)
func TestIndex(t *testing.T) {
// Generate every kind of pattern up to some number of segments,
// and compare conflicts found during indexing with those found
// by exhaustive comparison.
patterns := generatePatterns()
var idx routingIndex
for i, pat := range patterns {
got := indexConflicts(pat, &idx)
want := trueConflicts(pat, patterns[:i])
if !slices.Equal(got, want) {
t.Fatalf("%q:\ngot %q\nwant %q", pat, got, want)
}
idx.addPattern(pat)
}
}
func trueConflicts(pat *pattern, pats []*pattern) []string {
var s []string
for _, p := range pats {
if pat.conflictsWith(p) {
s = append(s, p.String())
}
}
slices.Sort(s)
return s
}
func indexConflicts(pat *pattern, idx *routingIndex) []string {
var s []string
idx.possiblyConflictingPatterns(pat, func(p *pattern) error {
if pat.conflictsWith(p) {
s = append(s, p.String())
}
return nil
})
slices.Sort(s)
return slices.Compact(s)
}
// generatePatterns generates all possible patterns using a representative
// sample of parts.
func generatePatterns() []*pattern {
var pats []*pattern
collect := func(s string) {
// Replace duplicate wildcards with unique ones.
var b strings.Builder
wc := 0
for {
i := strings.Index(s, "{x}")
if i < 0 {
b.WriteString(s)
break
}
b.WriteString(s[:i])
fmt.Fprintf(&b, "{x%d}", wc)
wc++
s = s[i+3:]
}
pat, err := parsePattern(b.String())
if err != nil {
panic(err)
}
pats = append(pats, pat)
}
var (
methods = []string{"", "GET ", "HEAD ", "POST "}
hosts = []string{"", "h1", "h2"}
segs = []string{"/a", "/b", "/{x}"}
finalSegs = []string{"/a", "/b", "/{f}", "/{m...}", "/{$}"}
)
g := genConcat(
genChoice(methods),
genChoice(hosts),
genStar(3, genChoice(segs)),
genChoice(finalSegs))
g(collect)
return pats
}
// A generator is a function that calls its argument with the strings that it
// generates.
type generator func(collect func(string))
// genConst generates a single constant string.
func genConst(s string) generator {
return func(collect func(string)) {
collect(s)
}
}
// genChoice generates all the strings in its argument.
func genChoice(choices []string) generator {
return func(collect func(string)) {
for _, c := range choices {
collect(c)
}
}
}
// genConcat2 generates the cross product of the strings of g1 concatenated
// with those of g2.
func genConcat2(g1, g2 generator) generator {
return func(collect func(string)) {
g1(func(s1 string) {
g2(func(s2 string) {
collect(s1 + s2)
})
})
}
}
// genConcat generalizes genConcat2 to any number of generators.
func genConcat(gs ...generator) generator {
if len(gs) == 0 {
return genConst("")
}
return genConcat2(gs[0], genConcat(gs[1:]...))
}
// genRepeat generates strings of exactly n copies of g's strings.
func genRepeat(n int, g generator) generator {
if n == 0 {
return genConst("")
}
return genConcat(g, genRepeat(n-1, g))
}
// genStar (named after the Kleene star) generates 0, 1, 2, ..., max
// copies of the strings of g.
func genStar(max int, g generator) generator {
return func(collect func(string)) {
for i := 0; i <= max; i++ {
genRepeat(i, g)(collect)
}
}
}
func BenchmarkMultiConflicts(b *testing.B) {
// How fast is indexing if the corpus is all multis?
const nMultis = 1000
var pats []*pattern
for i := 0; i < nMultis; i++ {
pats = append(pats, mustParsePattern(b, fmt.Sprintf("/a/b/{x}/d%d/", i)))
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
var idx routingIndex
for _, p := range pats {
got := indexConflicts(p, &idx)
if len(got) != 0 {
b.Fatalf("got %d conflicts, want 0", len(got))
}
idx.addPattern(p)
}
if i == 0 {
// Confirm that all the multis ended up where they belong.
if g, w := len(idx.multis), nMultis; g != w {
b.Fatalf("got %d multis, want %d", g, w)
}
}
}
}