routing_index_test.go

     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  
     5  package http
     6  
     7  import (
     8  	"fmt"
     9  	"slices"
    10  	"strings"
    11  	"testing"
    12  )
    13  
    14  func 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  
    30  func 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  
    41  func 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.
    55  func 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.
    98  type generator func(collect func(string))
    99  
   100  // genConst generates a single constant string.
   101  func 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.
   108  func 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.
   118  func 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.
   129  func 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.
   137  func 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.
   146  func 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  
   154  func 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
View as plain text