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