aboutsummaryrefslogtreecommitdiffstats
path: root/ethtrie
diff options
context:
space:
mode:
authorobscuren <geffobscura@gmail.com>2014-07-15 21:29:54 +0800
committerobscuren <geffobscura@gmail.com>2014-07-15 21:29:54 +0800
commit09bade64666f82a2580e7d24a8bc7655e2113287 (patch)
treef0014dd11139789289bb68ebee8d2da52078e12b /ethtrie
parent5ec62a51537dec6cd299dfc0ff1fbd0847338ff8 (diff)
downloadgo-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.go19
-rw-r--r--ethtrie/trie_test.go46
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)
+}