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	"fmt"
9	"slices"
10	"strings"
11	"testing"
12)
13
14func TestIndex(t *testing.T) {
15	// Generate every kind of pattern up to some number of segments,
16	// and compare conflicts found during indexing with those found
17	// by exhaustive comparison.
18	patterns := generatePatterns()
19	var idx routingIndex
20	for i, pat := range patterns {
21		got := indexConflicts(pat, &idx)
22		want := trueConflicts(pat, patterns[:i])
23		if !slices.Equal(got, want) {
24			t.Fatalf("%q:\ngot  %q\nwant %q", pat, got, want)
25		}
26		idx.addPattern(pat)
27	}
28}
29
30func trueConflicts(pat *pattern, pats []*pattern) []string {
31	var s []string
32	for _, p := range pats {
33		if pat.conflictsWith(p) {
34			s = append(s, p.String())
35		}
36	}
37	slices.Sort(s)
38	return s
39}
40
41func indexConflicts(pat *pattern, idx *routingIndex) []string {
42	var s []string
43	idx.possiblyConflictingPatterns(pat, func(p *pattern) error {
44		if pat.conflictsWith(p) {
45			s = append(s, p.String())
46		}
47		return nil
48	})
49	slices.Sort(s)
50	return slices.Compact(s)
51}
52
53// generatePatterns generates all possible patterns using a representative
54// sample of parts.
55func generatePatterns() []*pattern {
56	var pats []*pattern
57
58	collect := func(s string) {
59		// Replace duplicate wildcards with unique ones.
60		var b strings.Builder
61		wc := 0
62		for {
63			i := strings.Index(s, "{x}")
64			if i < 0 {
65				b.WriteString(s)
66				break
67			}
68			b.WriteString(s[:i])
69			fmt.Fprintf(&b, "{x%d}", wc)
70			wc++
71			s = s[i+3:]
72		}
73		pat, err := parsePattern(b.String())
74		if err != nil {
75			panic(err)
76		}
77		pats = append(pats, pat)
78	}
79
80	var (
81		methods   = []string{"", "GET ", "HEAD ", "POST "}
82		hosts     = []string{"", "h1", "h2"}
83		segs      = []string{"/a", "/b", "/{x}"}
84		finalSegs = []string{"/a", "/b", "/{f}", "/{m...}", "/{$}"}
85	)
86
87	g := genConcat(
88		genChoice(methods),
89		genChoice(hosts),
90		genStar(3, genChoice(segs)),
91		genChoice(finalSegs))
92	g(collect)
93	return pats
94}
95
96// A generator is a function that calls its argument with the strings that it
97// generates.
98type generator func(collect func(string))
99
100// genConst generates a single constant string.
101func genConst(s string) generator {
102	return func(collect func(string)) {
103		collect(s)
104	}
105}
106
107// genChoice generates all the strings in its argument.
108func genChoice(choices []string) generator {
109	return func(collect func(string)) {
110		for _, c := range choices {
111			collect(c)
112		}
113	}
114}
115
116// genConcat2 generates the cross product of the strings of g1 concatenated
117// with those of g2.
118func genConcat2(g1, g2 generator) generator {
119	return func(collect func(string)) {
120		g1(func(s1 string) {
121			g2(func(s2 string) {
122				collect(s1 + s2)
123			})
124		})
125	}
126}
127
128// genConcat generalizes genConcat2 to any number of generators.
129func genConcat(gs ...generator) generator {
130	if len(gs) == 0 {
131		return genConst("")
132	}
133	return genConcat2(gs[0], genConcat(gs[1:]...))
134}
135
136// genRepeat generates strings of exactly n copies of g's strings.
137func genRepeat(n int, g generator) generator {
138	if n == 0 {
139		return genConst("")
140	}
141	return genConcat(g, genRepeat(n-1, g))
142}
143
144// genStar (named after the Kleene star) generates 0, 1, 2, ..., max
145// copies of the strings of g.
146func genStar(max int, g generator) generator {
147	return func(collect func(string)) {
148		for i := 0; i <= max; i++ {
149			genRepeat(i, g)(collect)
150		}
151	}
152}
153
154func BenchmarkMultiConflicts(b *testing.B) {
155	// How fast is indexing if the corpus is all multis?
156	const nMultis = 1000
157	var pats []*pattern
158	for i := 0; i < nMultis; i++ {
159		pats = append(pats, mustParsePattern(b, fmt.Sprintf("/a/b/{x}/d%d/", i)))
160	}
161	b.ResetTimer()
162	for i := 0; i < b.N; i++ {
163		var idx routingIndex
164		for _, p := range pats {
165			got := indexConflicts(p, &idx)
166			if len(got) != 0 {
167				b.Fatalf("got %d conflicts, want 0", len(got))
168			}
169			idx.addPattern(p)
170		}
171		if i == 0 {
172			// Confirm that all the multis ended up where they belong.
173			if g, w := len(idx.multis), nMultis; g != w {
174				b.Fatalf("got %d multis, want %d", g, w)
175			}
176		}
177	}
178}
179