Capstan is a Golang web framework that shares some similarities with others in its segment.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

787 lines
17 KiB

package capstan
import (
"bytes"
"fmt"
"math/rand"
"net/http"
"os"
"testing"
"time"
)
const (
MinLength = 5
GenerateRandomPrefixes = true
)
var rs = rand.NewSource(time.Now().Unix())
var rd = rand.New(rs)
type words []string
func (w words) RandomWord() string {
return w[rd.Intn(len(w)-1)]
}
var wordList words
var prefixList words
type offsetter interface {
Offset() int
}
type testHandler struct {
offset int
}
func (t *testHandler) Offset() int {
return t.offset
}
func (t *testHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
}
func initProxyTrie() error {
var err error
wordList, err = buildWordList(1000)
if err != nil {
return err
}
prefixList, err = buildWordList(1000)
if err != nil {
return err
}
prefixes, err := buildWordList(10)
if err != nil {
return err
}
for i, word := range prefixList {
word = prefixes[rd.Intn(len(prefixes)-1)] + word
prefixList[i] = word
}
return nil
}
func Test_BTree(t *testing.T) {
root := &binaryTree{}
a_node := NewTrieNode('a', "", DefaultMappableNodeFunc)
b_node := NewTrieNode('b', "", DefaultMappableNodeFunc)
c_node := NewTrieNode('c', "", DefaultMappableNodeFunc)
d_node := NewTrieNode('d', "", DefaultMappableNodeFunc)
e_node := NewTrieNode('e', "", DefaultMappableNodeFunc)
root.Insert(a_node)
root.Insert(b_node)
root.Insert(c_node)
root.Insert(d_node)
root.Insert(e_node)
node, err := root.Lookup('a')
if err != nil {
t.Error("error looking up 'a':", err)
}
if node.label != 'a' {
t.Errorf("expected 'a' but got %c", node.label)
}
node, err = root.Lookup('b')
if err != nil {
t.Error("error looking up 'ab:", err)
}
if node.label != 'b' {
t.Errorf("expected 'b' but got %c", node.label)
}
node, err = root.Lookup('c')
if err != nil {
t.Error("error looking up 'c':", err)
}
if node.label != 'c' {
t.Errorf("expected 'c' but got %c", node.label)
}
node, err = root.Lookup('d')
if err != nil {
t.Error("error looking up 'd':", err)
}
if node.label != 'd' {
t.Errorf("expected 'd' but got %c", node.label)
}
node, err = root.Lookup('e')
if err != nil {
t.Error("error looking up 'e':", err)
}
if node.label != 'e' {
t.Errorf("expected 'e' but got %c", node.label)
}
}
func Test_BTreeOverwrite(t *testing.T) {
root := &binaryTree{}
a_node := NewTrieNode('a', "", DefaultMappableNodeFunc)
b_node := NewTrieNode('b', "", DefaultMappableNodeFunc)
c_node := NewTrieNode('c', "", DefaultMappableNodeFunc)
d_node := NewTrieNode('d', "", DefaultMappableNodeFunc)
e_node := NewTrieNode('e', "", DefaultMappableNodeFunc)
a_node.handler = &testHandler{1}
root.Insert(a_node)
root.Insert(b_node)
root.Insert(c_node)
root.Insert(d_node)
root.Insert(e_node)
a_overwrite := NewTrieNode('a', "", DefaultMappableNodeFunc)
a_overwrite.handler = &testHandler{2}
root.Insert(a_overwrite)
node, err := root.Lookup('a')
if err != nil {
t.Error("error looking up 'a':", err)
}
if node.label != 'a' {
t.Errorf("expected 'a' but got %c", node.label)
}
if node.handler != nil {
if h, ok := node.handler.(offsetter); ok {
if h.Offset() != 2 {
t.Errorf("expected offset of 2; received %d", h.Offset())
}
} else {
t.Error("node.handler not of type offsetter")
}
} else {
t.Error("node handler should not be nil")
}
}
func Test_LongestPrefix(t *testing.T) {
s := longestPrefix("test", "testing")
if s != "test" {
t.Error("expected longest prefix 'test' but got:", s)
}
s = longestPrefix("", "test")
if s != "" {
t.Error("expected empty string; got:", s)
}
}
func Test_TrieInsert(t *testing.T) {
node := NewProxyTrie()
node.Insert("testing", &testHandler{1})
node.Insert("test", &testHandler{2})
node.Insert("testings", &testHandler{3})
node.Insert("testify", &testHandler{4})
node.Insert("tester", &testHandler{5})
node.Insert("testee", &testHandler{6})
node.Insert("testament", &testHandler{7})
node.Insert("testable", &testHandler{8})
node.Insert("not a test at all", &testHandler{9})
if n := node.Lookup("testing"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 1 {
t.Errorf("'testing' expected 1 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
if n := node.Lookup("test"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 2 {
t.Errorf("'test' expected 2 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
if n := node.Lookup("testings"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 3 {
t.Errorf("'testings' expected 3 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
if n := node.Lookup("testify"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 4 {
t.Errorf("'testify' expected 4 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
if n := node.Lookup("tester"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 5 {
t.Errorf("'tester' expected 5 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
if n := node.Lookup("testee"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 6 {
t.Errorf("'testee' expected 6 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
if n := node.Lookup("testament"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 7 {
t.Errorf("'testament' expected 7 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
if n := node.Lookup("testable"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 8 {
t.Errorf("'testable' expected 8 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
if n := node.Lookup("not a test at all"); n != nil {
if no, ok := n.(offsetter); ok {
if no.Offset() != 9 {
t.Errorf("'not a test at all' expected 9 but received %d", no.Offset())
}
} else {
t.Error("handler not of type `offsetter`")
}
} else {
t.Error("unable to lookup node: nil returned")
}
}
func buildWordList(count int) ([]string, error) {
fp, err := os.Open("/usr/share/dict/words")
if err != nil {
return nil, err
}
words := make([]string, 0)
i := 0
for {
buf := make([]byte, 4096)
n, err := fp.Read(buf)
if err != nil {
return nil, err
}
if n == 0 {
break
}
offset := 0
for {
offset = bytes.Index(buf, []byte{'\n'})
if offset < 0 {
break
}
word := string(buf[:offset])
if len(word) > MinLength {
words = append(words, word)
i++
}
if len(buf) >= offset+1 {
buf = buf[offset+1:]
} else {
break
}
// Double breaking doesn't require label.
if i >= count {
break
}
}
if i >= count {
break
}
}
return words, nil
}
func Test_RadixTrieLongestMatch(t *testing.T) {
node := NewProxyTrie()
node.Insert("subapp.example.com/testing", &testHandler{0})
node.Insert("subapp.example.com/testing/again", &testHandler{1})
// Validate handlers are present.
handler := node.Lookup("subapp.example.com/testing")
if h, ok := handler.(offsetter); ok {
if h.Offset() != 0 {
t.Errorf("expected offset 0, got %d", h.Offset())
}
}
handler = node.Lookup("subapp.example.com/testing/again")
if h, ok := handler.(offsetter); ok {
if h.Offset() != 1 {
t.Errorf("expected offset 1, got %d", h.Offset())
}
}
handler = node.LongestMatch("subapp.example.com/testing")
if h, ok := handler.(offsetter); ok {
if h.Offset() != 0 {
t.Errorf("expected offset 0, got %d", h.Offset())
}
}
handler = node.LongestMatch("subapp.example.com/testing/again")
if h, ok := handler.(offsetter); ok {
if h.Offset() != 1 {
t.Errorf("expected offset 1, got %d", h.Offset())
}
}
handler = node.LongestMatch("subapp.example.com/testing/")
if handler == nil {
t.Error("handler should not be nil")
}
if h, ok := handler.(offsetter); ok {
if h.Offset() != 0 {
t.Errorf("expected offset 1, got %d", h.Offset())
}
}
}
// Test_RadixTrieLongestMatch2 is similar to Test_RadixTrieLongestMatch but
// tests multiple possible prefixes and duplicate characters. This test also
// uses the radix trie directly and doesn't bind to a server instance.
func Test_RadixTrieLongestMatch2(t *testing.T) {
node := NewProxyTrie()
patterns := []string{
"app.example.com/a",
"app.example.com/aa",
"app.example.com/aaa",
"app.example.com/ads",
"ape.example.com/bananas",
}
for i, v := range patterns {
node.Insert(v, &testHandler{i})
}
// Test additions work.
for i, v := range patterns {
handler := node.LongestMatch(v)
if h, ok := handler.(offsetter); ok {
if h.Offset() != i {
t.Errorf("offset %d expected but received %d for pattern %s",
i, h.Offset(), v)
}
} else {
t.Errorf("pattern %s not bound to handler type `offsetter`", v)
}
}
// Path testing.
handler := node.LongestMatch("app.example.com/aaa/testing/a/aa/aaa")
if handler == nil {
t.Error("handler for `app.example.com/aaa/testing/a/aa/aaa` is nil")
}
if h, ok := handler.(offsetter); ok {
if h.Offset() != 2 {
t.Errorf("offset 2 expected but received 2 for `app.example.com/aaa/testing/a/aa/aaa`")
}
}
handler = node.LongestMatch("ope.example.com/bananas")
if handler != nil {
t.Error("handler should be nil")
}
// Counter-intuitive, but the LongestMatch algorithm is path agnostic. This
// WILL match the longest possible prefix, which is
// "ape.example.com/bananas".
handler = node.LongestMatch("ape.example.com/bananass")
if handler == nil {
t.Error("handler should not be nil")
}
handler = node.LongestMatch("ape.example.com/banana/testing")
if handler != nil {
t.Error("handler should be nil")
}
}
func Test_TrieTester(t *testing.T) {
return // skip
words := []string{
//"abc", // abc
//"ab", // ab -> c
//"a", // a -> b -> c
//"aardvark",
//"aardvark's",
//"aardvarks",
//"aa",
//"a",
//"aaa",
//"ah",
//"aah",
//"a", // ah => h <- a -> ah ah <- a <- a
//"aa",
//"aaah",
//"aaaah",
//"aaaaah",
//"aaaa",
//"ar",
//"art",
//"artys",
//"arts",
//"ar",
//"art",
//"ars",
//"aarts",
//"aartt",
//"aars",
//"aart",
//"a",
//"aa",
//"aaa",
//"example.com",
//"test.example.com",
//"example.com/app",
}
node := NewProxyTrie()
for i, word := range words {
node.Insert(word, &testHandler{i})
}
for i, word := range words {
fmt.Printf("offset %d; handler: %v\n", i, node.Lookup(word))
}
}
func Test_DictionaryInsertAndLookup(t *testing.T) {
node := NewProxyTrie()
for i, word := range wordList {
node.Insert(word, &testHandler{i})
}
for i, word := range wordList {
handler := node.Lookup(word)
if no, ok := handler.(offsetter); ok {
if no.Offset() != i {
t.Errorf("expected %d but got %d", i, no.Offset())
}
} else {
if handler == nil {
t.Error("received nil for word:", word)
}
}
}
}
func Test_RadixTrieInsertOverwrite(t *testing.T) {
// Overwrite not currently supported.
return
node := NewProxyTrie()
handler := &testHandler{1}
node.Insert("testing", handler)
node.Insert("testing", handler)
if h := node.Lookup("testing"); h == nil {
t.Error("handler not added")
} else {
if ht, ok := h.(offsetter); !ok {
t.Error("handler not of type offsetter")
} else {
if ht.Offset() != 1 {
t.Errorf("expected offset 1 but got %d", ht.Offset())
}
}
}
node = NewProxyTrie()
node.Insert("testing", &testHandler{0})
node.Insert("testing", &testHandler{1})
fmt.Println(node)
if h := node.Lookup("testing"); h == nil {
t.Error("handler not added")
} else {
if ht, ok := h.(offsetter); !ok {
t.Error("handler not of type offsetter")
} else {
if ht.Offset() != 1 {
t.Errorf("expected offset 1 but got %d", ht.Offset())
}
}
}
}
func Benchmark_RadixTrieLookupMap(b *testing.B) {
node := NewProxyTrie()
for i, word := range wordList {
node.Insert(word, &testHandler{i})
}
word := wordList.RandomWord()
for i := 0; i < b.N; i++ {
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_RadixTrieLookupBinaryTree(b *testing.B) {
node := NewProxyTrie()
node.KeyFunc = BinaryTreeMapperFunc
for i, word := range wordList {
node.Insert(word, &testHandler{i})
}
word := wordList.RandomWord()
for i := 0; i < b.N; i++ {
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_RadixTrieLookupArray(b *testing.B) {
node := NewProxyTrie()
node.KeyFunc = ArrayMapperFunc
for i, word := range wordList {
node.Insert(word, &testHandler{i})
}
word := wordList.RandomWord()
for i := 0; i < b.N; i++ {
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_MapLookup(b *testing.B) {
wordMap := make(map[string]*testHandler)
for i, word := range wordList {
wordMap[word] = &testHandler{i}
}
word := wordList.RandomWord()
for i := 0; i < b.N; i++ {
handler, ok := wordMap[word]
if !ok {
b.Fatalf("handler for word %s not found", word)
}
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_RadixTrieHugeLookupMap(b *testing.B) {
node := NewProxyTrie()
var list words
list, _ = buildWordList(100000)
for i, word := range list {
node.Insert(word, &testHandler{i})
}
word := list.RandomWord()
for i := 0; i < b.N; i++ {
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_RadixTrieHugeLookupBinaryTree(b *testing.B) {
node := NewProxyTrie()
node.KeyFunc = BinaryTreeMapperFunc
var list words
list, _ = buildWordList(100000)
for i, word := range list {
node.Insert(word, &testHandler{i})
}
word := list.RandomWord()
for i := 0; i < b.N; i++ {
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_RadixTrieHugeLookupArray(b *testing.B) {
node := NewProxyTrie()
node.KeyFunc = ArrayMapperFunc
var list words
list, _ = buildWordList(100000)
for i, word := range list {
node.Insert(word, &testHandler{i})
}
for i := 0; i < b.N; i++ {
word := list.RandomWord()
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_HugeMapLookup(b *testing.B) {
wordMap := make(map[string]*testHandler)
var list words
list, _ = buildWordList(100000)
for i, word := range list {
wordMap[word] = &testHandler{i}
}
word := list.RandomWord()
for i := 0; i < b.N; i++ {
handler, ok := wordMap[word]
if !ok {
b.Fatalf("handler for word %s not found", word)
}
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_RadixTriePrefixLookupMap(b *testing.B) {
node := NewProxyTrie()
for i, word := range prefixList {
node.Insert(word, &testHandler{i})
}
word := prefixList.RandomWord()
for i := 0; i < b.N; i++ {
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_RadixTriePrefixLookupBinaryTree(b *testing.B) {
node := NewProxyTrie()
node.KeyFunc = BinaryTreeMapperFunc
for i, word := range prefixList {
node.Insert(word, &testHandler{i})
}
word := prefixList.RandomWord()
for i := 0; i < b.N; i++ {
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_RadixTriePrefixLookupArray(b *testing.B) {
node := NewProxyTrie()
node.KeyFunc = ArrayMapperFunc
for i, word := range prefixList {
node.Insert(word, &testHandler{i})
}
word := prefixList.RandomWord()
for i := 0; i < b.N; i++ {
handler := node.Lookup(word)
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}
func Benchmark_PrefixMapLookup(b *testing.B) {
wordMap := make(map[string]*testHandler)
for i, word := range prefixList {
wordMap[word] = &testHandler{i}
}
word := prefixList.RandomWord()
for i := 0; i < b.N; i++ {
handler, ok := wordMap[word]
if !ok {
b.Fatalf("handler for word %s not found", word)
}
if handler == nil {
b.Fatalf("handler for word %s should not be nil", word)
}
}
}