core, trie: new trie

1 files changed, 140 insertions, 124 deletions

diff --git a/trie/trie_test.go b/trie/trie_test.go
index 607c96b0f..c96861bed 100644
--- a/trie/trie_test.go
+++ b/trie/trie_test.go
@@ -24,86 +24,103 @@ import (
 	"os"
 	"testing"
 
+	"github.com/davecgh/go-spew/spew"
 	"github.com/ethereum/go-ethereum/common"
-	"github.com/ethereum/go-ethereum/crypto"
 	"github.com/ethereum/go-ethereum/ethdb"
 )
 
-type Db map[string][]byte
-
-func (self Db) Get(k []byte) ([]byte, error) { return self[string(k)], nil }
-func (self Db) Put(k, v []byte) error        { self[string(k)] = v; return nil }
-
-// Used for testing
-func NewEmpty() *Trie {
-	return New(nil, make(Db))
+func init() {
+	spew.Config.Indent = "    "
+	spew.Config.DisableMethods = true
 }
 
-func NewEmptySecure() *SecureTrie {
-	return NewSecure(nil, make(Db))
+// Used for testing
+func newEmpty() *Trie {
+	db, _ := ethdb.NewMemDatabase()
+	trie, _ := New(common.Hash{}, db)
+	return trie
 }
 
 func TestEmptyTrie(t *testing.T) {
-	trie := NewEmpty()
+	var trie Trie
 	res := trie.Hash()
-	exp := crypto.Sha3(common.Encode(""))
-	if !bytes.Equal(res, exp) {
+	exp := emptyRoot
+	if res != common.Hash(exp) {
 		t.Errorf("expected %x got %x", exp, res)
 	}
 }
 
 func TestNull(t *testing.T) {
-	trie := NewEmpty()
-
+	var trie Trie
 	key := make([]byte, 32)
 	value := common.FromHex("0x823140710bf13990e4500136726d8b55")
 	trie.Update(key, value)
 	value = trie.Get(key)
 }
 
+func TestMissingRoot(t *testing.T) {
+	db, _ := ethdb.NewMemDatabase()
+	trie, err := New(common.HexToHash("0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33"), db)
+	if trie != nil {
+		t.Error("New returned non-nil trie for invalid root")
+	}
+	if err != ErrMissingRoot {
+		t.Error("New returned wrong error: %v", err)
+	}
+}
+
 func TestInsert(t *testing.T) {
-	trie := NewEmpty()
+	trie := newEmpty()
 
-	trie.UpdateString("doe", "reindeer")
-	trie.UpdateString("dog", "puppy")
-	trie.UpdateString("dogglesworth", "cat")
+	updateString(trie, "doe", "reindeer")
+	updateString(trie, "dog", "puppy")
+	updateString(trie, "dogglesworth", "cat")
 
-	exp := common.Hex2Bytes("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3")
+	exp := common.HexToHash("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3")
 	root := trie.Hash()
-	if !bytes.Equal(root, exp) {
+	if root != exp {
 		t.Errorf("exp %x got %x", exp, root)
 	}
 
-	trie = NewEmpty()
-	trie.UpdateString("A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
+	trie = newEmpty()
+	updateString(trie, "A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
 
-	exp = common.Hex2Bytes("d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab")
-	root = trie.Hash()
-	if !bytes.Equal(root, exp) {
+	exp = common.HexToHash("d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab")
+	root, err := trie.Commit()
+	if err != nil {
+		t.Fatalf("commit error: %v", err)
+	}
+	if root != exp {
 		t.Errorf("exp %x got %x", exp, root)
 	}
 }
 
 func TestGet(t *testing.T) {
-	trie := NewEmpty()
-
-	trie.UpdateString("doe", "reindeer")
-	trie.UpdateString("dog", "puppy")
-	trie.UpdateString("dogglesworth", "cat")
+	trie := newEmpty()
+	updateString(trie, "doe", "reindeer")
+	updateString(trie, "dog", "puppy")
+	updateString(trie, "dogglesworth", "cat")
+
+	for i := 0; i < 2; i++ {
+		res := getString(trie, "dog")
+		if !bytes.Equal(res, []byte("puppy")) {
+			t.Errorf("expected puppy got %x", res)
+		}
 
-	res := trie.GetString("dog")
-	if !bytes.Equal(res, []byte("puppy")) {
-		t.Errorf("expected puppy got %x", res)
-	}
+		unknown := getString(trie, "unknown")
+		if unknown != nil {
+			t.Errorf("expected nil got %x", unknown)
+		}
 
-	unknown := trie.GetString("unknown")
-	if unknown != nil {
-		t.Errorf("expected nil got %x", unknown)
+		if i == 1 {
+			return
+		}
+		trie.Commit()
 	}
 }
 
 func TestDelete(t *testing.T) {
-	trie := NewEmpty()
+	trie := newEmpty()
 	vals := []struct{ k, v string }{
 		{"do", "verb"},
 		{"ether", "wookiedoo"},
@@ -116,21 +133,21 @@ func TestDelete(t *testing.T) {
 	}
 	for _, val := range vals {
 		if val.v != "" {
-			trie.UpdateString(val.k, val.v)
+			updateString(trie, val.k, val.v)
 		} else {
-			trie.DeleteString(val.k)
+			deleteString(trie, val.k)
 		}
 	}
 
 	hash := trie.Hash()
-	exp := common.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
-	if !bytes.Equal(hash, exp) {
+	exp := common.HexToHash("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
+	if hash != exp {
 		t.Errorf("expected %x got %x", exp, hash)
 	}
 }
 
 func TestEmptyValues(t *testing.T) {
-	trie := NewEmpty()
+	trie := newEmpty()
 
 	vals := []struct{ k, v string }{
 		{"do", "verb"},
@@ -143,78 +160,85 @@ func TestEmptyValues(t *testing.T) {
 		{"shaman", ""},
 	}
 	for _, val := range vals {
-		trie.UpdateString(val.k, val.v)
+		updateString(trie, val.k, val.v)
 	}
 
 	hash := trie.Hash()
-	exp := common.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
-	if !bytes.Equal(hash, exp) {
+	exp := common.HexToHash("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
+	if hash != exp {
 		t.Errorf("expected %x got %x", exp, hash)
 	}
 }
 
 func TestReplication(t *testing.T) {
-	trie := NewEmpty()
+	trie := newEmpty()
 	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.UpdateString(val.k, val.v)
+		updateString(trie, val.k, val.v)
 	}
-	trie.Commit()
-
-	trie2 := New(trie.Root(), trie.cache.backend)
-	if string(trie2.GetString("horse")) != "stallion" {
-		t.Error("expected to have horse => stallion")
+	exp, err := trie.Commit()
+	if err != nil {
+		t.Fatalf("commit error: %v", err)
 	}
 
-	hash := trie2.Hash()
-	exp := trie.Hash()
-	if !bytes.Equal(hash, exp) {
+	// create a new trie on top of the database and check that lookups work.
+	trie2, err := New(exp, trie.db)
+	if err != nil {
+		t.Fatalf("can't recreate trie at %x: %v", exp, err)
+	}
+	for _, kv := range vals {
+		if string(getString(trie2, kv.k)) != kv.v {
+			t.Errorf("trie2 doesn't have %q => %q", kv.k, kv.v)
+		}
+	}
+	hash, err := trie2.Commit()
+	if err != nil {
+		t.Fatalf("commit error: %v", err)
+	}
+	if hash != exp {
 		t.Errorf("root failure. expected %x got %x", exp, hash)
 	}
 
-}
-
-func TestReset(t *testing.T) {
-	trie := NewEmpty()
-	vals := []struct{ k, v string }{
+	// perform some insertions on the new trie.
+	vals2 := []struct{ k, v string }{
 		{"do", "verb"},
 		{"ether", "wookiedoo"},
 		{"horse", "stallion"},
+		// {"shaman", "horse"},
+		// {"doge", "coin"},
+		// {"ether", ""},
+		// {"dog", "puppy"},
+		// {"somethingveryoddindeedthis is", "myothernodedata"},
+		// {"shaman", ""},
 	}
-	for _, val := range vals {
-		trie.UpdateString(val.k, val.v)
+	for _, val := range vals2 {
+		updateString(trie2, val.k, val.v)
 	}
-	trie.Commit()
-
-	before := common.CopyBytes(trie.roothash)
-	trie.UpdateString("should", "revert")
-	trie.Hash()
-	// Should have no effect
-	trie.Hash()
-	trie.Hash()
-	// ###
-
-	trie.Reset()
-	after := common.CopyBytes(trie.roothash)
+	if trie2.Hash() != exp {
+		t.Errorf("root failure. expected %x got %x", exp, hash)
+	}
+}
 
-	if !bytes.Equal(before, after) {
-		t.Errorf("expected roots to be equal. %x - %x", before, after)
+func paranoiaCheck(t1 *Trie) (bool, *Trie) {
+	t2 := new(Trie)
+	it := NewIterator(t1)
+	for it.Next() {
+		t2.Update(it.Key, it.Value)
 	}
+	return t2.Hash() == t1.Hash(), t2
 }
 
 func TestParanoia(t *testing.T) {
 	t.Skip()
-	trie := NewEmpty()
+	trie := newEmpty()
 
 	vals := []struct{ k, v string }{
 		{"do", "verb"},
@@ -228,13 +252,13 @@ func TestParanoia(t *testing.T) {
 		{"somethingveryoddindeedthis is", "myothernodedata"},
 	}
 	for _, val := range vals {
-		trie.UpdateString(val.k, val.v)
+		updateString(trie, val.k, val.v)
 	}
 	trie.Commit()
 
-	ok, t2 := ParanoiaCheck(trie, trie.cache.backend)
+	ok, t2 := paranoiaCheck(trie)
 	if !ok {
-		t.Errorf("trie paranoia check failed %x %x", trie.roothash, t2.roothash)
+		t.Errorf("trie paranoia check failed %x %x", trie.Hash(), t2.Hash())
 	}
 }
 
@@ -243,27 +267,35 @@ func TestOutput(t *testing.T) {
 	t.Skip()
 
 	base := "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
-	trie := NewEmpty()
+	trie := newEmpty()
 	for i := 0; i < 50; i++ {
-		trie.UpdateString(fmt.Sprintf("%s%d", base, i), "valueeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee")
+		updateString(trie, fmt.Sprintf("%s%d", base, i), "valueeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee")
 	}
 	fmt.Println("############################## FULL ################################")
 	fmt.Println(trie.root)
 
 	trie.Commit()
 	fmt.Println("############################## SMALL ################################")
-	trie2 := New(trie.roothash, trie.cache.backend)
-	trie2.GetString(base + "20")
+	trie2, _ := New(trie.Hash(), trie.db)
+	getString(trie2, base+"20")
 	fmt.Println(trie2.root)
 }
 
+func TestLargeValue(t *testing.T) {
+	trie := newEmpty()
+	trie.Update([]byte("key1"), []byte{99, 99, 99, 99})
+	trie.Update([]byte("key2"), bytes.Repeat([]byte{1}, 32))
+	trie.Hash()
+
+}
+
 type kv struct {
 	k, v []byte
 	t    bool
 }
 
 func TestLargeData(t *testing.T) {
-	trie := NewEmpty()
+	trie := newEmpty()
 	vals := make(map[string]*kv)
 
 	for i := byte(0); i < 255; i++ {
@@ -275,7 +307,7 @@ func TestLargeData(t *testing.T) {
 		vals[string(value2.k)] = value2
 	}
 
-	it := trie.Iterator()
+	it := NewIterator(trie)
 	for it.Next() {
 		vals[string(it.Key)].t = true
 	}
@@ -295,34 +327,6 @@ func TestLargeData(t *testing.T) {
 	}
 }
 
-func TestSecureDelete(t *testing.T) {
-	trie := NewEmptySecure()
-
-	vals := []struct{ k, v string }{
-		{"do", "verb"},
-		{"ether", "wookiedoo"},
-		{"horse", "stallion"},
-		{"shaman", "horse"},
-		{"doge", "coin"},
-		{"ether", ""},
-		{"dog", "puppy"},
-		{"shaman", ""},
-	}
-	for _, val := range vals {
-		if val.v != "" {
-			trie.UpdateString(val.k, val.v)
-		} else {
-			trie.DeleteString(val.k)
-		}
-	}
-
-	hash := trie.Hash()
-	exp := common.Hex2Bytes("29b235a58c3c25ab83010c327d5932bcf05324b7d6b1185e650798034783ca9d")
-	if !bytes.Equal(hash, exp) {
-		t.Errorf("expected %x got %x", exp, hash)
-	}
-}
-
 func BenchmarkGet(b *testing.B)      { benchGet(b, false) }
 func BenchmarkGetDB(b *testing.B)    { benchGet(b, true) }
 func BenchmarkUpdateBE(b *testing.B) { benchUpdate(b, binary.BigEndian) }
@@ -333,11 +337,11 @@ func BenchmarkHashLE(b *testing.B)   { benchHash(b, binary.LittleEndian) }
 const benchElemCount = 20000
 
 func benchGet(b *testing.B, commit bool) {
-	trie := New(nil, nil)
+	trie := new(Trie)
 	if commit {
 		dir, tmpdb := tempDB()
 		defer os.RemoveAll(dir)
-		trie = New(nil, tmpdb)
+		trie, _ = New(common.Hash{}, tmpdb)
 	}
 	k := make([]byte, 32)
 	for i := 0; i < benchElemCount; i++ {
@@ -356,7 +360,7 @@ func benchGet(b *testing.B, commit bool) {
 }
 
 func benchUpdate(b *testing.B, e binary.ByteOrder) *Trie {
-	trie := NewEmpty()
+	trie := newEmpty()
 	k := make([]byte, 32)
 	for i := 0; i < b.N; i++ {
 		e.PutUint64(k, uint64(i))
@@ -366,7 +370,7 @@ func benchUpdate(b *testing.B, e binary.ByteOrder) *Trie {
 }
 
 func benchHash(b *testing.B, e binary.ByteOrder) {
-	trie := NewEmpty()
+	trie := newEmpty()
 	k := make([]byte, 32)
 	for i := 0; i < benchElemCount; i++ {
 		e.PutUint64(k, uint64(i))
@@ -379,7 +383,7 @@ func benchHash(b *testing.B, e binary.ByteOrder) {
 	}
 }
 
-func tempDB() (string, Backend) {
+func tempDB() (string, Database) {
 	dir, err := ioutil.TempDir("", "trie-bench")
 	if err != nil {
 		panic(fmt.Sprintf("can't create temporary directory: %v", err))
@@ -390,3 +394,15 @@ func tempDB() (string, Backend) {
 	}
 	return dir, db
 }
+
+func getString(trie *Trie, k string) []byte {
+	return trie.Get([]byte(k))
+}
+
+func updateString(trie *Trie, k, v string) {
+	trie.Update([]byte(k), []byte(v))
+}
+
+func deleteString(trie *Trie, k string) {
+	trie.Delete([]byte(k))
+}