From 09bade64666f82a2580e7d24a8bc7655e2113287 Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 15 Jul 2014 15:29:54 +0200 Subject: Fixed an issue where the trie might crash on missmatching lengths --- ethtrie/trie.go | 19 ++++++++++++++----- ethtrie/trie_test.go | 46 +++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 55 insertions(+), 10 deletions(-) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 38c78e7f4..07720be54 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -9,6 +9,8 @@ import ( "sync" ) +func __ignore() { fmt.Println("") } + func ParanoiaCheck(t1 *Trie) (bool, *Trie) { t2 := NewTrie(ethutil.Config.Db, "") @@ -269,8 +271,7 @@ func (t *Trie) getState(node interface{}, key []int) interface{} { } // It shouldn't come this far - fmt.Println("getState unexpected return") - return "" + panic("unexpected return") } func (t *Trie) getNode(node interface{}) *ethutil.Value { @@ -287,7 +288,9 @@ func (t *Trie) getNode(node interface{}) *ethutil.Value { return ethutil.NewValueFromBytes([]byte(str)) } - return t.cache.Get(n.Bytes()) + data := t.cache.Get(n.Bytes()) + + return data } func (t *Trie) UpdateState(node interface{}, key []int, value string) interface{} { @@ -385,7 +388,7 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter return t.Put(newNode) } - return "" + panic("unexpected end") } func (t *Trie) deleteState(node interface{}, key []int) interface{} { @@ -396,6 +399,7 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { // New node n := ethutil.NewValue(node) if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 { + //return nil return "" } @@ -406,12 +410,17 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { k := CompactDecode(currentNode.Get(0).Str()) v := currentNode.Get(1).Raw() + matchingLength := MatchingNibbleLength(key, k) + // Matching key pair (ie. there's already an object with this key) if CompareIntSlice(k, key) { return "" - } else if CompareIntSlice(key[:len(k)], k) { + } else if CompareIntSlice(key[:matchingLength], k) { hash := t.deleteState(v, key[len(k):]) child := t.getNode(hash) + if child.IsNil() { + return node + } var newNode []interface{} if child.Len() == 2 { diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go index a3d4547d7..f39477ff9 100644 --- a/ethtrie/trie_test.go +++ b/ethtrie/trie_test.go @@ -5,6 +5,7 @@ import ( "encoding/hex" "encoding/json" "fmt" + "github.com/ethereum/eth-go/ethutil" "io/ioutil" "math/rand" "net/http" @@ -251,8 +252,8 @@ func TestRemote(t *testing.T) { trie.Update(get(key), get(value)) } - a := NewValue(h(test.Root)).Bytes() - b := NewValue(trie.Root).Bytes() + a := ethutil.NewValue(h(test.Root)).Bytes() + b := ethutil.NewValue(trie.Root).Bytes() if bytes.Compare(a, b) != 0 { t.Errorf("%-10s: %x %x", test.Name, a, b) } @@ -267,12 +268,12 @@ func TestTrieReplay(t *testing.T) { } _, trie2 := New() - trie.NewIterator().Each(func(key string, v *Value) { + trie.NewIterator().Each(func(key string, v *ethutil.Value) { trie2.Update(key, v.Str()) }) - a := NewValue(trie.Root).Bytes() - b := NewValue(trie2.Root).Bytes() + a := ethutil.NewValue(trie.Root).Bytes() + b := ethutil.NewValue(trie2.Root).Bytes() if bytes.Compare(a, b) != 0 { t.Errorf("%s %x %x\n", test.Name, trie.Root, trie2.Root) } @@ -329,3 +330,38 @@ func TestRegression(t *testing.T) { } } } + +func TestDelete(t *testing.T) { + _, trie := New() + + 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") + + fmt.Println("aa =>", trie.Get("aa")) + _, t2 := New() + 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() + + fmt.Printf("o: %x\nc: %x\n", a, b) +} -- cgit v1.2.3 From ed3424ff75b396360990725afc124326dea4ab45 Mon Sep 17 00:00:00 2001 From: obscuren Date: Thu, 17 Jul 2014 11:21:18 +0200 Subject: Trie fixes --- ethtrie/trie.go | 30 +++++++++++++++-------- ethtrie/trie_test.go | 69 ++++++++++++++++++++++++++++++++++++++++++++++------ 2 files changed, 81 insertions(+), 18 deletions(-) (limited to 'ethtrie') diff --git a/ethtrie/trie.go b/ethtrie/trie.go index 07720be54..f0f3fe5a8 100644 --- a/ethtrie/trie.go +++ b/ethtrie/trie.go @@ -5,7 +5,7 @@ import ( "fmt" "github.com/ethereum/eth-go/ethcrypto" "github.com/ethereum/eth-go/ethutil" - "reflect" + _ "reflect" "sync" ) @@ -326,7 +326,8 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter // New node n := ethutil.NewValue(node) - if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 { + if node == nil || n.Len() == 0 { + //if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 { newNode := []interface{}{CompactEncode(key), value} return t.Put(newNode) @@ -393,13 +394,17 @@ func (t *Trie) InsertState(node interface{}, key []int, value interface{}) inter func (t *Trie) deleteState(node interface{}, key []int) interface{} { if len(key) == 0 { + println("") return "" } // New node n := ethutil.NewValue(node) - if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 { + //if node == nil || (n.Type() == reflect.String && (n.Str() == "" || n.Get(0).IsNil())) || n.Len() == 0 { + if node == nil || n.Len() == 0 { //return nil + //fmt.Printf(" %x %d\n", n, len(n.Bytes())) + return "" } @@ -410,17 +415,19 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { k := CompactDecode(currentNode.Get(0).Str()) v := currentNode.Get(1).Raw() - matchingLength := MatchingNibbleLength(key, k) - // Matching key pair (ie. there's already an object with this key) if CompareIntSlice(k, key) { + //fmt.Printf(" %x\n", v) + return "" - } else if CompareIntSlice(key[:matchingLength], k) { + } else if CompareIntSlice(key[:len(k)], k) { hash := t.deleteState(v, key[len(k):]) child := t.getNode(hash) - if child.IsNil() { - return node - } + /* + if child.IsNil() { + return node + } + */ var newNode []interface{} if child.Len() == 2 { @@ -430,6 +437,8 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { newNode = []interface{}{currentNode.Get(0).Str(), hash} } + //fmt.Printf("%x\n", newNode) + return t.Put(newNode) } else { return node @@ -472,10 +481,11 @@ func (t *Trie) deleteState(node interface{}, key []int) interface{} { newNode = n } + //fmt.Printf("%x\n", newNode) return t.Put(newNode) } - return "" + panic("unexpected return") } type TrieIterator struct { diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go index f39477ff9..3989a8f45 100644 --- a/ethtrie/trie_test.go +++ b/ethtrie/trie_test.go @@ -1,17 +1,17 @@ package ethtrie import ( - "bytes" - "encoding/hex" - "encoding/json" + _ "bytes" + _ "encoding/hex" + _ "encoding/json" "fmt" "github.com/ethereum/eth-go/ethutil" - "io/ioutil" - "math/rand" - "net/http" - "reflect" + _ "io/ioutil" + _ "math/rand" + _ "net/http" + _ "reflect" "testing" - "time" + _ "time" ) const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ" @@ -43,6 +43,7 @@ func New() (*MemDatabase, *Trie) { return db, NewTrie(db, "") } +/* func TestTrieSync(t *testing.T) { db, trie := New() @@ -365,3 +366,55 @@ func TestDelete(t *testing.T) { fmt.Printf("o: %x\nc: %x\n", a, b) } +*/ + +func TestRndCase(t *testing.T) { + _, trie := New() + + 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")))) +} -- cgit v1.2.3