package trie import ( "bytes" "encoding/hex" "encoding/json" "fmt" "io/ioutil" "math/rand" "net/http" "reflect" "testing" "time" "github.com/ethereum/go-ethereum/ethutil" ) const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ" type MemDatabase struct { db map[string][]byte } func NewMemDatabase() (*MemDatabase, error) { db := &MemDatabase{db: make(map[string][]byte)} return db, nil } func (db *MemDatabase) Put(key []byte, value []byte) { db.db[string(key)] = value } func (db *MemDatabase) Get(key []byte) ([]byte, error) { return db.db[string(key)], nil } func (db *MemDatabase) Delete(key []byte) error { delete(db.db, string(key)) return nil } func (db *MemDatabase) Print() {} func (db *MemDatabase) Close() {} func (db *MemDatabase) LastKnownTD() []byte { return nil } func NewTrie() (*MemDatabase, *Trie) { db, _ := NewMemDatabase() return db, New(db, "") } func TestTrieSync(t *testing.T) { db, trie := NewTrie() trie.Update("dog", LONG_WORD) if len(db.db) != 0 { t.Error("Expected no data in database") } trie.Sync() if len(db.db) == 0 { t.Error("Expected data to be persisted") } } func TestTrieDirtyTracking(t *testing.T) { _, trie := NewTrie() trie.Update("dog", LONG_WORD) if !trie.cache.IsDirty { t.Error("Expected trie to be dirty") } trie.Sync() if trie.cache.IsDirty { t.Error("Expected trie not to be dirty") } trie.Update("test", LONG_WORD) trie.cache.Undo() if trie.cache.IsDirty { t.Error("Expected trie not to be dirty") } } func TestTrieReset(t *testing.T) { _, trie := NewTrie() trie.Update("cat", LONG_WORD) if len(trie.cache.nodes) == 0 { t.Error("Expected cached nodes") } trie.cache.Undo() if len(trie.cache.nodes) != 0 { t.Error("Expected no nodes after undo", len(trie.cache.nodes)) } } func TestTrieGet(t *testing.T) { _, trie := NewTrie() trie.Update("cat", LONG_WORD) x := trie.Get("cat") if x != LONG_WORD { t.Error("expected %s, got %s", LONG_WORD, x) } } func TestTrieUpdating(t *testing.T) { _, trie := NewTrie() trie.Update("cat", LONG_WORD) trie.Update("cat", LONG_WORD+"1") x := trie.Get("cat") if x != LONG_WORD+"1" { t.Error("expected %S, got %s", LONG_WORD+"1", x) } } func TestTrieCmp(t *testing.T) { _, trie1 := NewTrie() _, trie2 := NewTrie() trie1.Update("doge", LONG_WORD) trie2.Update("doge", LONG_WORD) if !trie1.Cmp(trie2) { t.Error("Expected tries to be equal") } trie1.Update("dog", LONG_WORD) trie2.Update("cat", LONG_WORD) if trie1.Cmp(trie2) { t.Errorf("Expected tries not to be equal %x %x", trie1.Root, trie2.Root) } } func TestTrieDelete(t *testing.T) { t.Skip() _, trie := NewTrie() trie.Update("cat", LONG_WORD) exp := trie.Root trie.Update("dog", LONG_WORD) trie.Delete("dog") if !reflect.DeepEqual(exp, trie.Root) { t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) } trie.Update("dog", LONG_WORD) exp = trie.Root trie.Update("dude", LONG_WORD) trie.Delete("dude") if !reflect.DeepEqual(exp, trie.Root) { t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) } } func TestTrieDeleteWithValue(t *testing.T) { t.Skip() _, trie := NewTrie() trie.Update("c", LONG_WORD) exp := trie.Root trie.Update("ca", LONG_WORD) trie.Update("cat", LONG_WORD) trie.Delete("ca") trie.Delete("cat") if !reflect.DeepEqual(exp, trie.Root) { t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) } } func TestTriePurge(t *testing.T) { _, trie := NewTrie() trie.Update("c", LONG_WORD) trie.Update("ca", LONG_WORD) trie.Update("cat", LONG_WORD) lenBefore := len(trie.cache.nodes) it := trie.NewIterator() if num := it.Purge(); num != 3 { t.Errorf("Expected purge to return 3, got %d", num) } if lenBefore == len(trie.cache.nodes) { t.Errorf("Expected cached nodes to be deleted") } } func h(str string) string { d, err := hex.DecodeString(str) if err != nil { panic(err) } return string(d) } func get(in string) (out string) { if len(in) > 2 && in[:2] == "0x" { out = h(in[2:]) } else { out = in } return } type Test struct { Name string In map[string]string Root string } func CreateTest(name string, data []byte) (Test, error) { t := Test{Name: name} err := json.Unmarshal(data, &t) if err != nil { return Test{}, fmt.Errorf("%v", err) } return t, nil } func CreateTests(uri string, cb func(Test)) map[string]Test { resp, err := http.Get(uri) if err != nil { panic(err) } defer resp.Body.Close() data, err := ioutil.ReadAll(resp.Body) var objmap map[string]*json.RawMessage err = json.Unmarshal(data, &objmap) if err != nil { panic(err) } tests := make(map[string]Test) for name, testData := range objmap { test, err := CreateTest(name, *testData) if err != nil { panic(err) } if cb != nil { cb(test) } tests[name] = test } return tests } func RandomData() [][]string { data := [][]string{ {"0x000000000000000000000000ec4f34c97e43fbb2816cfd95e388353c7181dab1", "0x4e616d6552656700000000000000000000000000000000000000000000000000"}, {"0x0000000000000000000000000000000000000000000000000000000000000045", "0x22b224a1420a802ab51d326e29fa98e34c4f24ea"}, {"0x0000000000000000000000000000000000000000000000000000000000000046", "0x67706c2076330000000000000000000000000000000000000000000000000000"}, {"0x000000000000000000000000697c7b8c961b56f675d570498424ac8de1a918f6", "0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000"}, {"0x0000000000000000000000007ef9e639e2733cb34e4dfc576d4b23f72db776b2", "0x4655474156000000000000000000000000000000000000000000000000000000"}, {"0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000", "0x697c7b8c961b56f675d570498424ac8de1a918f6"}, {"0x4655474156000000000000000000000000000000000000000000000000000000", "0x7ef9e639e2733cb34e4dfc576d4b23f72db776b2"}, {"0x4e616d6552656700000000000000000000000000000000000000000000000000", "0xec4f34c97e43fbb2816cfd95e388353c7181dab1"}, } var c [][]string for len(data) != 0 { e := rand.Intn(len(data)) c = append(c, data[e]) copy(data[e:], data[e+1:]) data[len(data)-1] = nil data = data[:len(data)-1] } return c } const MaxTest = 1000 // This test insert data in random order and seeks to find indifferences between the different tries func TestRegression(t *testing.T) { rand.Seed(time.Now().Unix()) roots := make(map[string]int) for i := 0; i < MaxTest; i++ { _, trie := NewTrie() data := RandomData() for _, test := range data { trie.Update(test[0], test[1]) } trie.Delete("0x4e616d6552656700000000000000000000000000000000000000000000000000") roots[string(trie.Root.([]byte))] += 1 } if len(roots) > 1 { for root, num := range roots { t.Errorf("%x => %d\n", root, num) } } } func TestDelete(t *testing.T) { _, trie := NewTrie() trie.Update("a", "jeffreytestlongstring") trie.Update("aa", "otherstring") trie.Update("aaa", "othermorestring") trie.Update("aabbbbccc", "hithere") trie.Update("abbcccdd", "hstanoehutnaheoustnh") trie.Update("rnthaoeuabbcccdd", "hstanoehutnaheoustnh") trie.Update("rneuabbcccdd", "hstanoehutnaheoustnh") trie.Update("rneuabboeusntahoeucccdd", "hstanoehutnaheoustnh") trie.Update("rnxabboeusntahoeucccdd", "hstanoehutnaheoustnh") trie.Delete("aaboaestnuhbccc") trie.Delete("a") trie.Update("a", "nthaonethaosentuh") trie.Update("c", "shtaosntehua") trie.Delete("a") trie.Update("aaaa", "testmegood") _, t2 := NewTrie() trie.NewIterator().Each(func(key string, v *ethutil.Value) { if key == "aaaa" { t2.Update(key, v.Str()) } else { t2.Update(key, v.Str()) } }) a := ethutil.NewValue(trie.Root).Bytes() b := ethutil.NewValue(t2.Root).Bytes() if bytes.Compare(a, b) != 0 { t.Errorf("Expected %x and %x to be equal", a, b) } } func TestTerminator(t *testing.T) { key := CompactDecode("hello") if !HasTerm(key) { t.Errorf("Expected %v to have a terminator", key) } } func TestIt(t *testing.T) { _, trie := NewTrie() trie.Update("cat", "cat") trie.Update("doge", "doge") trie.Update("wallace", "wallace") it := trie.Iterator() inputs := []struct { In, Out string }{ {"", "cat"}, {"bobo", "cat"}, {"c", "cat"}, {"car", "cat"}, {"catering", "doge"}, {"w", "wallace"}, {"wallace123", ""}, } for _, test := range inputs { res := string(it.Next(test.In)) if res != test.Out { t.Errorf(test.In, "failed. Got", res, "Expected", test.Out) } } } func TestBeginsWith(t *testing.T) { a := CompactDecode("hello") b := CompactDecode("hel") if BeginsWith(a, b) { t.Errorf("Expected %x to begin with %x", a, b) } if BeginsWith(b, a) { t.Errorf("Expected %x not to begin with %x", b, a) } } func TestItems(t *testing.T) { _, trie := NewTrie() trie.Update("A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") exp := "d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab" if bytes.Compare(trie.GetRoot(), ethutil.Hex2Bytes(exp)) != 0 { t.Errorf("Expected root to be %s but got", exp, trie.GetRoot()) } } /* func TestRndCase(t *testing.T) { _, trie := NewTrie() data := []struct{ k, v string }{ {"0000000000000000000000000000000000000000000000000000000000000001", "a07573657264617461000000000000000000000000000000000000000000000000"}, {"0000000000000000000000000000000000000000000000000000000000000003", "8453bb5b31"}, {"0000000000000000000000000000000000000000000000000000000000000004", "850218711a00"}, {"0000000000000000000000000000000000000000000000000000000000000005", "9462d7705bd0b3ecbc51a8026a25597cb28a650c79"}, {"0000000000000000000000000000000000000000000000000000000000000010", "947e70f9460402290a3e487dae01f610a1a8218fda"}, {"0000000000000000000000000000000000000000000000000000000000000111", "01"}, {"0000000000000000000000000000000000000000000000000000000000000112", "a053656e6174650000000000000000000000000000000000000000000000000000"}, {"0000000000000000000000000000000000000000000000000000000000000113", "a053656e6174650000000000000000000000000000000000000000000000000000"}, {"53656e6174650000000000000000000000000000000000000000000000000000", "94977e3f62f5e1ed7953697430303a3cfa2b5b736e"}, } for _, e := range data { trie.Update(string(ethutil.Hex2Bytes(e.k)), string(ethutil.Hex2Bytes(e.v))) } fmt.Printf("root after update %x\n", trie.Root) trie.NewIterator().Each(func(k string, v *ethutil.Value) { fmt.Printf("%x %x\n", k, v.Bytes()) }) data = []struct{ k, v string }{ {"0000000000000000000000000000000000000000000000000000000000000112", ""}, {"436974697a656e73000000000000000000000000000000000000000000000001", ""}, {"436f757274000000000000000000000000000000000000000000000000000002", ""}, {"53656e6174650000000000000000000000000000000000000000000000000000", ""}, {"436f757274000000000000000000000000000000000000000000000000000000", ""}, {"53656e6174650000000000000000000000000000000000000000000000000001", ""}, {"0000000000000000000000000000000000000000000000000000000000000113", ""}, {"436974697a656e73000000000000000000000000000000000000000000000000", ""}, {"436974697a656e73000000000000000000000000000000000000000000000002", ""}, {"436f757274000000000000000000000000000000000000000000000000000001", ""}, {"0000000000000000000000000000000000000000000000000000000000000111", ""}, {"53656e6174650000000000000000000000000000000000000000000000000002", ""}, } for _, e := range data { trie.Delete(string(ethutil.Hex2Bytes(e.k))) } fmt.Printf("root after delete %x\n", trie.Root) trie.NewIterator().Each(func(k string, v *ethutil.Value) { fmt.Printf("%x %x\n", k, v.Bytes()) }) fmt.Printf("%x\n", trie.Get(string(ethutil.Hex2Bytes("0000000000000000000000000000000000000000000000000000000000000001")))) } */ func TestOtherSomething(t *testing.T) { _, trie := NewTrie() vals := []struct{ k, v string }{ {"do", "verb"}, {"ether", "wookiedoo"}, {"horse", "stallion"}, {"shaman", "horse"}, {"doge", "coin"}, {"ether", ""}, {"dog", "puppy"}, {"shaman", ""}, } for _, val := range vals { trie.Update(val.k, val.v) } exp := ethutil.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84") hash := trie.Root.([]byte) if !bytes.Equal(hash, exp) { t.Errorf("expected %x got %x", exp, hash) } } func BenchmarkGets(b *testing.B) { _, trie := NewTrie() vals := []struct{ k, v string }{ {"do", "verb"}, {"ether", "wookiedoo"}, {"horse", "stallion"}, {"shaman", "horse"}, {"doge", "coin"}, {"ether", ""}, {"dog", "puppy"}, {"shaman", ""}, {"somethingveryoddindeedthis is", "myothernodedata"}, } for _, val := range vals { trie.Update(val.k, val.v) } b.ResetTimer() for i := 0; i < b.N; i++ { trie.Get("horse") } } func BenchmarkUpdate(b *testing.B) { _, trie := NewTrie() b.ResetTimer() for i := 0; i < b.N; i++ { trie.Update(fmt.Sprintf("aaaaaaaaaaaaaaa%d", i), "value") } }