diff options
author | obscuren <geffobscura@gmail.com> | 2014-07-15 21:29:54 +0800 |
---|---|---|
committer | obscuren <geffobscura@gmail.com> | 2014-07-15 21:29:54 +0800 |
commit | 09bade64666f82a2580e7d24a8bc7655e2113287 (patch) | |
tree | f0014dd11139789289bb68ebee8d2da52078e12b /ethtrie | |
parent | 5ec62a51537dec6cd299dfc0ff1fbd0847338ff8 (diff) | |
download | go-tangerine-09bade64666f82a2580e7d24a8bc7655e2113287.tar go-tangerine-09bade64666f82a2580e7d24a8bc7655e2113287.tar.gz go-tangerine-09bade64666f82a2580e7d24a8bc7655e2113287.tar.bz2 go-tangerine-09bade64666f82a2580e7d24a8bc7655e2113287.tar.lz go-tangerine-09bade64666f82a2580e7d24a8bc7655e2113287.tar.xz go-tangerine-09bade64666f82a2580e7d24a8bc7655e2113287.tar.zst go-tangerine-09bade64666f82a2580e7d24a8bc7655e2113287.zip |
Fixed an issue where the trie might crash on missmatching lengths
Diffstat (limited to 'ethtrie')
-rw-r--r-- | ethtrie/trie.go | 19 | ||||
-rw-r--r-- | ethtrie/trie_test.go | 46 |
2 files changed, 55 insertions, 10 deletions
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) +} |