From d551a75c35027a3cf6344293923cdcdab61d5f38 Mon Sep 17 00:00:00 2001 From: zelig Date: Thu, 26 Jun 2014 21:20:02 +0100 Subject: bump v5.15 --- ethutil/config.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'ethutil') diff --git a/ethutil/config.go b/ethutil/config.go index aa4ae9c3e..b253aa203 100644 --- a/ethutil/config.go +++ b/ethutil/config.go @@ -44,7 +44,7 @@ func ReadConfig(ConfigFile string, Datadir string, Identifier string, EnvPrefix } else { g.ParseAll() } - Config = &config{ExecPath: Datadir, Debug: true, Ver: "0.5.14", conf: g, Identifier: Identifier} + Config = &config{ExecPath: Datadir, Debug: true, Ver: "0.5.15", conf: g, Identifier: Identifier} Config.SetClientString("Ethereum(G)") } return Config -- cgit v1.2.3 From 5a86892ecbd68c3d466cb1ef282c4cb81300abce Mon Sep 17 00:00:00 2001 From: obscuren Date: Mon, 30 Jun 2014 13:08:00 +0200 Subject: Using remote for test cases --- ethutil/trie.go | 17 ++++++-- ethutil/trie_test.go | 108 ++++++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 108 insertions(+), 17 deletions(-) (limited to 'ethutil') diff --git a/ethutil/trie.go b/ethutil/trie.go index 18d0a5f0a..ce9c2da27 100644 --- a/ethutil/trie.go +++ b/ethutil/trie.go @@ -43,11 +43,11 @@ func NewCache(db Database) *Cache { return &Cache{db: db, nodes: make(map[string]*Node)} } -func (cache *Cache) Put(v interface{}) interface{} { +func (cache *Cache) PutValue(v interface{}, force bool) interface{} { value := NewValue(v) enc := value.Encode() - if len(enc) >= 32 { + if len(enc) >= 32 || force { sha := Sha3Bin(enc) cache.nodes[string(sha)] = NewNode(sha, value, true) @@ -59,6 +59,10 @@ func (cache *Cache) Put(v interface{}) interface{} { return v } +func (cache *Cache) Put(v interface{}) interface{} { + return cache.PutValue(v, false) +} + func (cache *Cache) Get(key []byte) *Value { // First check if the key is the cache if cache.nodes[string(key)] != nil { @@ -168,7 +172,12 @@ func (t *Trie) Update(key string, value string) { k := CompactHexDecode(key) - t.Root = t.UpdateState(t.Root, k, value) + root := t.UpdateState(t.Root, k, value) + if _, ok := root.([]byte); !ok { + t.Root = t.cache.PutValue(root, true) + } else { + t.Root = root + } } func (t *Trie) Get(key string) string { @@ -527,6 +536,8 @@ func (it *TrieIterator) fetchNode(key []int, node []byte, cb EachCallback) { } func (it *TrieIterator) iterateNode(key []int, currentNode *Value, cb EachCallback) { + //fmt.Println("node", currentNode) + if currentNode.Len() == 2 { k := CompactDecode(currentNode.Get(0).Str()) diff --git a/ethutil/trie_test.go b/ethutil/trie_test.go index 2937b1525..3ee955b11 100644 --- a/ethutil/trie_test.go +++ b/ethutil/trie_test.go @@ -1,7 +1,12 @@ package ethutil import ( + "bytes" + "encoding/hex" + "encoding/json" "fmt" + "io/ioutil" + "net/http" "reflect" "testing" ) @@ -171,23 +176,98 @@ func TestTriePurge(t *testing.T) { } } -func TestTrieIt(t *testing.T) { - _, trie := New() +func h(str string) string { + d, err := hex.DecodeString(str) + if err != nil { + panic(err) + } + + return string(d) +} - data := [][]string{ - {"do", "verb"}, - {"ether", "wookiedoo"}, - {"horse", "stallion"}, - {"shaman", "horse"}, - {"doge", "coin"}, - {"ether", ""}, - {"dog", "puppy"}, - {"shaman", ""}, +func get(in string) (out string) { + if len(in) > 2 && in[:2] == "0x" { + out = h(in[2:]) + } else { + out = in } - for _, item := range data { - trie.Update(item[0], item[1]) + 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) } - fmt.Printf("root %x", trie.Root) + return t, nil +} + +func CreateTests(uri string, cb func(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) + } + + for name, testData := range objmap { + test, err := CreateTest(name, *testData) + if err != nil { + panic(err) + } + + cb(test) + } +} + +func TestRemote(t *testing.T) { + CreateTests("https://raw.githubusercontent.com/ethereum/tests/develop/trietest.json", func(test Test) { + _, trie := New() + for key, value := range test.In { + trie.Update(get(key), get(value)) + } + fmt.Printf("%-15s: %x\n", test.Name, trie.Root) + + a := NewValue(h(test.Root)).Bytes() + b := NewValue(trie.Root).Bytes() + if bytes.Compare(a, b) != 0 { + t.Errorf("%-10s: %x %x", test.Name, a, b) + } + }) +} + +func TestTrieReplay(t *testing.T) { + CreateTests("https://raw.githubusercontent.com/ethereum/tests/develop/trietest.json", func(test Test) { + _, trie := New() + for key, value := range test.In { + trie.Update(get(key), get(value)) + } + + _, trie2 := New() + trie.NewIterator().Each(func(key string, v *Value) { + trie2.Update(key, string(v.Str())) + }) + + a := NewValue(trie.Root).Bytes() + b := NewValue(trie2.Root).Bytes() + if bytes.Compare(a, b) != 0 { + t.Errorf("root %x %x\n", trie.Root, trie2.Root) + } + }) } -- cgit v1.2.3 From 8ddd4c4c52eef9f382a321fa880adba4a1e35ee2 Mon Sep 17 00:00:00 2001 From: obscuren Date: Mon, 30 Jun 2014 13:09:04 +0200 Subject: wip --- ethutil/value.go | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'ethutil') diff --git a/ethutil/value.go b/ethutil/value.go index ddd864d8a..b37b33c28 100644 --- a/ethutil/value.go +++ b/ethutil/value.go @@ -116,6 +116,8 @@ func (val *Value) Bytes() []byte { return a } else if s, ok := val.Val.(byte); ok { return []byte{s} + } else if s, ok := val.Val.(string); ok { + return []byte(s) } return []byte{} @@ -196,6 +198,12 @@ func (val *Value) Encode() []byte { return Encode(val.Val) } +// Assume that the data we have is encoded +func (self *Value) Decode() { + v, _ := Decode(self.Bytes(), 0) + self.Val = v +} + func NewValueFromBytes(data []byte) *Value { if len(data) != 0 { data, _ := Decode(data, 0) -- cgit v1.2.3 From 9ed0d389b2402baf2dbc90fe12e9b4695ee22858 Mon Sep 17 00:00:00 2001 From: obscuren Date: Mon, 30 Jun 2014 13:34:47 +0200 Subject: Generic trie --- ethutil/trie.go | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) (limited to 'ethutil') diff --git a/ethutil/trie.go b/ethutil/trie.go index ce9c2da27..26a27a901 100644 --- a/ethutil/trie.go +++ b/ethutil/trie.go @@ -191,7 +191,17 @@ func (t *Trie) Get(key string) string { } func (t *Trie) Delete(key string) { - t.Update(key, "") + t.mut.Lock() + defer t.mut.Unlock() + + k := CompactHexDecode(key) + + root := t.DeleteState(t.Root, k) + if _, ok := root.([]byte); !ok { + t.Root = t.cache.PutValue(root, true) + } else { + t.Root = root + } } func (t *Trie) GetState(node interface{}, key []int) interface{} { @@ -243,15 +253,7 @@ func (t *Trie) GetNode(node interface{}) *Value { } func (t *Trie) UpdateState(node interface{}, key []int, value string) interface{} { - - if value != "" { - return t.InsertState(node, key, value) - } else { - // delete it - return t.DeleteState(node, key) - } - - return t.Root + return t.InsertState(node, key, value) } func (t *Trie) Put(node interface{}) interface{} { -- cgit v1.2.3 From 82272ee08a7d72be1cc0947b6a0e8096a0353362 Mon Sep 17 00:00:00 2001 From: obscuren Date: Mon, 30 Jun 2014 14:28:54 +0200 Subject: Iterator fix --- ethutil/trie.go | 10 ++++------ ethutil/trie_test.go | 4 ++-- 2 files changed, 6 insertions(+), 8 deletions(-) (limited to 'ethutil') diff --git a/ethutil/trie.go b/ethutil/trie.go index 26a27a901..c669bdcb0 100644 --- a/ethutil/trie.go +++ b/ethutil/trie.go @@ -538,15 +538,13 @@ func (it *TrieIterator) fetchNode(key []int, node []byte, cb EachCallback) { } func (it *TrieIterator) iterateNode(key []int, currentNode *Value, cb EachCallback) { - //fmt.Println("node", currentNode) - if currentNode.Len() == 2 { k := CompactDecode(currentNode.Get(0).Str()) - if currentNode.Get(1).Str() == "" { - it.iterateNode(key, currentNode.Get(1), cb) + pk := append(key, k...) + if currentNode.Get(1).Len() != 0 && currentNode.Get(1).Str() == "" { + it.iterateNode(pk, currentNode.Get(1), cb) } else { - pk := append(key, k...) if k[len(k)-1] == 16 { cb(DecodeCompact(pk), currentNode.Get(1)) @@ -560,7 +558,7 @@ func (it *TrieIterator) iterateNode(key []int, currentNode *Value, cb EachCallba if i == 16 && currentNode.Get(i).Len() != 0 { cb(DecodeCompact(pk), currentNode.Get(i)) } else { - if currentNode.Get(i).Str() == "" { + if currentNode.Get(i).Len() != 0 && currentNode.Get(i).Str() == "" { it.iterateNode(pk, currentNode.Get(i), cb) } else { val := currentNode.Get(i).Str() diff --git a/ethutil/trie_test.go b/ethutil/trie_test.go index 3ee955b11..d8db8a0d6 100644 --- a/ethutil/trie_test.go +++ b/ethutil/trie_test.go @@ -261,13 +261,13 @@ func TestTrieReplay(t *testing.T) { _, trie2 := New() trie.NewIterator().Each(func(key string, v *Value) { - trie2.Update(key, string(v.Str())) + trie2.Update(key, v.Str()) }) a := NewValue(trie.Root).Bytes() b := NewValue(trie2.Root).Bytes() if bytes.Compare(a, b) != 0 { - t.Errorf("root %x %x\n", trie.Root, trie2.Root) + t.Errorf("%s %x %x\n", test.Name, trie.Root, trie2.Root) } }) } -- cgit v1.2.3 From ed276cd7c241749a9cf8add4e2fae3d3608a7ea4 Mon Sep 17 00:00:00 2001 From: obscuren Date: Mon, 30 Jun 2014 20:03:31 +0200 Subject: Added Paranoia check for VM execution --- ethutil/trie.go | 18 ++++++++++++------ ethutil/trie_test.go | 21 ++++++++++++++++++++- 2 files changed, 32 insertions(+), 7 deletions(-) (limited to 'ethutil') diff --git a/ethutil/trie.go b/ethutil/trie.go index c669bdcb0..56f1648a6 100644 --- a/ethutil/trie.go +++ b/ethutil/trie.go @@ -173,10 +173,13 @@ func (t *Trie) Update(key string, value string) { k := CompactHexDecode(key) root := t.UpdateState(t.Root, k, value) - if _, ok := root.([]byte); !ok { - t.Root = t.cache.PutValue(root, true) - } else { + switch root.(type) { + case string: t.Root = root + case []byte: + t.Root = root + default: + t.Root = t.cache.PutValue(root, true) } } @@ -197,10 +200,13 @@ func (t *Trie) Delete(key string) { k := CompactHexDecode(key) root := t.DeleteState(t.Root, k) - if _, ok := root.([]byte); !ok { - t.Root = t.cache.PutValue(root, true) - } else { + switch root.(type) { + case string: t.Root = root + case []byte: + t.Root = root + default: + t.Root = t.cache.PutValue(root, true) } } diff --git a/ethutil/trie_test.go b/ethutil/trie_test.go index d8db8a0d6..542af5504 100644 --- a/ethutil/trie_test.go +++ b/ethutil/trie_test.go @@ -242,7 +242,6 @@ func TestRemote(t *testing.T) { for key, value := range test.In { trie.Update(get(key), get(value)) } - fmt.Printf("%-15s: %x\n", test.Name, trie.Root) a := NewValue(h(test.Root)).Bytes() b := NewValue(trie.Root).Bytes() @@ -271,3 +270,23 @@ func TestTrieReplay(t *testing.T) { } }) } + +func TestIt(t *testing.T) { + _, trie := New() + + test := map[string]string{ + "0x000000000000000000000000ec4f34c97e43fbb2816cfd95e388353c7181dab1": "0x4e616d6552656700000000000000000000000000000000000000000000000000", + "0x0000000000000000000000000000000000000000000000000000000000000045": "0x22b224a1420a802ab51d326e29fa98e34c4f24ea", + "0x0000000000000000000000000000000000000000000000000000000000000046": "0x67706c2076330000000000000000000000000000000000000000000000000000", + "0x000000000000000000000000697c7b8c961b56f675d570498424ac8de1a918f6": "0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000", + "0x0000000000000000000000007ef9e639e2733cb34e4dfc576d4b23f72db776b2": "0x4655474156000000000000000000000000000000000000000000000000000000", + "0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000": "0x697c7b8c961b56f675d570498424ac8de1a918f6", + "0x4655474156000000000000000000000000000000000000000000000000000000": "0x7ef9e639e2733cb34e4dfc576d4b23f72db776b2", + "0x4e616d6552656700000000000000000000000000000000000000000000000000": "0xec4f34c97e43fbb2816cfd95e388353c7181dab1", + } + + for k, v := range test { + trie.Update(k, v) + } + fmt.Printf("root : %x\n", trie.Root) +} -- cgit v1.2.3 From 5f5910c603c107ceaf5f240f9ca23cbf9c951f67 Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 1 Jul 2014 09:55:20 +0200 Subject: Regression test for trie --- ethutil/trie_test.go | 70 ++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 54 insertions(+), 16 deletions(-) (limited to 'ethutil') diff --git a/ethutil/trie_test.go b/ethutil/trie_test.go index 542af5504..85d81b6f4 100644 --- a/ethutil/trie_test.go +++ b/ethutil/trie_test.go @@ -6,9 +6,11 @@ import ( "encoding/json" "fmt" "io/ioutil" + "math/rand" "net/http" "reflect" "testing" + "time" ) const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ" @@ -211,7 +213,7 @@ func CreateTest(name string, data []byte) (Test, error) { return t, nil } -func CreateTests(uri string, cb func(Test)) { +func CreateTests(uri string, cb func(Test)) map[string]Test { resp, err := http.Get(uri) if err != nil { panic(err) @@ -226,14 +228,20 @@ func CreateTests(uri string, cb func(Test)) { panic(err) } + tests := make(map[string]Test) for name, testData := range objmap { test, err := CreateTest(name, *testData) if err != nil { panic(err) } - cb(test) + if cb != nil { + cb(test) + } + tests[name] = test } + + return tests } func TestRemote(t *testing.T) { @@ -271,22 +279,52 @@ func TestTrieReplay(t *testing.T) { }) } -func TestIt(t *testing.T) { - _, trie := New() +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 := New() + data := RandomData() + + for _, test := range data { + trie.Update(test[0], test[1]) + } - test := map[string]string{ - "0x000000000000000000000000ec4f34c97e43fbb2816cfd95e388353c7181dab1": "0x4e616d6552656700000000000000000000000000000000000000000000000000", - "0x0000000000000000000000000000000000000000000000000000000000000045": "0x22b224a1420a802ab51d326e29fa98e34c4f24ea", - "0x0000000000000000000000000000000000000000000000000000000000000046": "0x67706c2076330000000000000000000000000000000000000000000000000000", - "0x000000000000000000000000697c7b8c961b56f675d570498424ac8de1a918f6": "0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000", - "0x0000000000000000000000007ef9e639e2733cb34e4dfc576d4b23f72db776b2": "0x4655474156000000000000000000000000000000000000000000000000000000", - "0x6f6f6f6820736f2067726561742c207265616c6c6c793f000000000000000000": "0x697c7b8c961b56f675d570498424ac8de1a918f6", - "0x4655474156000000000000000000000000000000000000000000000000000000": "0x7ef9e639e2733cb34e4dfc576d4b23f72db776b2", - "0x4e616d6552656700000000000000000000000000000000000000000000000000": "0xec4f34c97e43fbb2816cfd95e388353c7181dab1", + roots[string(trie.Root.([]byte))] += 1 } - for k, v := range test { - trie.Update(k, v) + if len(roots) > 1 { + for root, num := range roots { + t.Errorf("%x => %d\n", root, num) + } } - fmt.Printf("root : %x\n", trie.Root) } -- cgit v1.2.3 From 39263b674c1a8a13a1c29349a48b3cdc4c5948db Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 1 Jul 2014 09:56:10 +0200 Subject: Paranoia --- ethutil/config.go | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'ethutil') diff --git a/ethutil/config.go b/ethutil/config.go index b253aa203..6ebb5e8cd 100644 --- a/ethutil/config.go +++ b/ethutil/config.go @@ -14,6 +14,7 @@ type config struct { ExecPath string Debug bool + Paranoia bool Ver string ClientString string Pubkey []byte @@ -44,7 +45,7 @@ func ReadConfig(ConfigFile string, Datadir string, Identifier string, EnvPrefix } else { g.ParseAll() } - Config = &config{ExecPath: Datadir, Debug: true, Ver: "0.5.15", conf: g, Identifier: Identifier} + Config = &config{ExecPath: Datadir, Debug: true, Ver: "0.5.15", conf: g, Identifier: Identifier, Paranoia: true} Config.SetClientString("Ethereum(G)") } return Config -- cgit v1.2.3 From 92693e44599c44e606813d2c3259cc9f6f81a644 Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 1 Jul 2014 11:26:45 +0200 Subject: The dragon has been slain. Consensus reached! --- ethutil/trie_test.go | 1 + 1 file changed, 1 insertion(+) (limited to 'ethutil') diff --git a/ethutil/trie_test.go b/ethutil/trie_test.go index 85d81b6f4..01207dbc3 100644 --- a/ethutil/trie_test.go +++ b/ethutil/trie_test.go @@ -318,6 +318,7 @@ func TestRegression(t *testing.T) { for _, test := range data { trie.Update(test[0], test[1]) } + trie.Delete("0x4e616d6552656700000000000000000000000000000000000000000000000000") roots[string(trie.Root.([]byte))] += 1 } -- cgit v1.2.3