From af34749a6b47ff8f9b4cb55d9ea65e1235d63b68 Mon Sep 17 00:00:00 2001 From: obscuren Date: Fri, 31 Oct 2014 14:45:03 +0100 Subject: ethtrie => trie --- chain/block.go | 8 +- chain/derive_sha.go | 4 +- ethtrie/encoding.go | 76 ------ ethtrie/encoding_test.go | 68 ------ ethtrie/iterator.go | 143 ----------- ethtrie/slice.go | 53 ---- ethtrie/trie.go | 620 ----------------------------------------------- ethtrie/trie_test.go | 434 --------------------------------- state/state.go | 8 +- state/state_object.go | 12 +- trie/encoding.go | 76 ++++++ trie/encoding_test.go | 68 ++++++ trie/iterator.go | 143 +++++++++++ trie/slice.go | 53 ++++ trie/trie.go | 620 +++++++++++++++++++++++++++++++++++++++++++++++ trie/trie_test.go | 434 +++++++++++++++++++++++++++++++++ 16 files changed, 1410 insertions(+), 1410 deletions(-) delete mode 100644 ethtrie/encoding.go delete mode 100644 ethtrie/encoding_test.go delete mode 100644 ethtrie/iterator.go delete mode 100644 ethtrie/slice.go delete mode 100644 ethtrie/trie.go delete mode 100644 ethtrie/trie_test.go create mode 100644 trie/encoding.go create mode 100644 trie/encoding_test.go create mode 100644 trie/iterator.go create mode 100644 trie/slice.go create mode 100644 trie/trie.go create mode 100644 trie/trie_test.go diff --git a/chain/block.go b/chain/block.go index 7e39aa2c9..16975a2fe 100644 --- a/chain/block.go +++ b/chain/block.go @@ -8,9 +8,9 @@ import ( "time" "github.com/ethereum/go-ethereum/crypto" - "github.com/ethereum/go-ethereum/ethtrie" "github.com/ethereum/go-ethereum/ethutil" "github.com/ethereum/go-ethereum/state" + "github.com/ethereum/go-ethereum/trie" ) type BlockInfo struct { @@ -137,7 +137,7 @@ func CreateBlock(root interface{}, } block.SetUncles([]*Block{}) - block.state = state.New(ethtrie.New(ethutil.Config.Db, root)) + block.state = state.New(trie.New(ethutil.Config.Db, root)) return block } @@ -294,7 +294,7 @@ func (self *Block) setHeader(header *ethutil.Value) { self.PrevHash = header.Get(0).Bytes() self.UncleSha = header.Get(1).Bytes() self.Coinbase = header.Get(2).Bytes() - self.state = state.New(ethtrie.New(ethutil.Config.Db, header.Get(3).Val)) + self.state = state.New(trie.New(ethutil.Config.Db, header.Get(3).Val)) self.TxSha = header.Get(4).Bytes() self.ReceiptSha = header.Get(5).Bytes() self.LogsBloom = header.Get(6).Bytes() @@ -315,7 +315,7 @@ func NewUncleBlockFromValue(header *ethutil.Value) *Block { return block } -func (block *Block) Trie() *ethtrie.Trie { +func (block *Block) Trie() *trie.Trie { return block.state.Trie } diff --git a/chain/derive_sha.go b/chain/derive_sha.go index 92db90d95..4246aeb02 100644 --- a/chain/derive_sha.go +++ b/chain/derive_sha.go @@ -1,8 +1,8 @@ package chain import ( - "github.com/ethereum/go-ethereum/ethtrie" "github.com/ethereum/go-ethereum/ethutil" + "github.com/ethereum/go-ethereum/trie" ) type DerivableList interface { @@ -11,7 +11,7 @@ type DerivableList interface { } func DeriveSha(list DerivableList) []byte { - trie := ethtrie.New(ethutil.Config.Db, "") + trie := trie.New(ethutil.Config.Db, "") for i := 0; i < list.Len(); i++ { trie.Update(string(ethutil.NewValue(i).Encode()), string(list.GetRlp(i))) } diff --git a/ethtrie/encoding.go b/ethtrie/encoding.go deleted file mode 100644 index bcf2c5669..000000000 --- a/ethtrie/encoding.go +++ /dev/null @@ -1,76 +0,0 @@ -package ethtrie - -import ( - "bytes" - "encoding/hex" - "strings" -) - -func CompactEncode(hexSlice []byte) string { - terminator := 0 - if hexSlice[len(hexSlice)-1] == 16 { - terminator = 1 - } - - if terminator == 1 { - hexSlice = hexSlice[:len(hexSlice)-1] - } - - oddlen := len(hexSlice) % 2 - flags := byte(2*terminator + oddlen) - if oddlen != 0 { - hexSlice = append([]byte{flags}, hexSlice...) - } else { - hexSlice = append([]byte{flags, 0}, hexSlice...) - } - - var buff bytes.Buffer - for i := 0; i < len(hexSlice); i += 2 { - buff.WriteByte(byte(16*hexSlice[i] + hexSlice[i+1])) - } - - return buff.String() -} - -func CompactDecode(str string) []byte { - base := CompactHexDecode(str) - base = base[:len(base)-1] - if base[0] >= 2 { - base = append(base, 16) - } - if base[0]%2 == 1 { - base = base[1:] - } else { - base = base[2:] - } - - return base -} - -func CompactHexDecode(str string) []byte { - base := "0123456789abcdef" - hexSlice := make([]byte, 0) - - enc := hex.EncodeToString([]byte(str)) - for _, v := range enc { - hexSlice = append(hexSlice, byte(strings.IndexByte(base, byte(v)))) - } - hexSlice = append(hexSlice, 16) - - return hexSlice -} - -func DecodeCompact(key []byte) string { - base := "0123456789abcdef" - var str string - - for _, v := range key { - if v < 16 { - str += string(base[v]) - } - } - - res, _ := hex.DecodeString(str) - - return string(res) -} diff --git a/ethtrie/encoding_test.go b/ethtrie/encoding_test.go deleted file mode 100644 index 0cceef792..000000000 --- a/ethtrie/encoding_test.go +++ /dev/null @@ -1,68 +0,0 @@ -package ethtrie - -import ( - "bytes" - "fmt" - "testing" -) - -func TestCompactEncode(t *testing.T) { - test1 := []byte{1, 2, 3, 4, 5} - if res := CompactEncode(test1); res != "\x11\x23\x45" { - t.Error(fmt.Sprintf("even compact encode failed. Got: %q", res)) - } - - test2 := []byte{0, 1, 2, 3, 4, 5} - if res := CompactEncode(test2); res != "\x00\x01\x23\x45" { - t.Error(fmt.Sprintf("odd compact encode failed. Got: %q", res)) - } - - test3 := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16} - if res := CompactEncode(test3); res != "\x20\x0f\x1c\xb8" { - t.Error(fmt.Sprintf("odd terminated compact encode failed. Got: %q", res)) - } - - test4 := []byte{15, 1, 12, 11, 8 /*term*/, 16} - if res := CompactEncode(test4); res != "\x3f\x1c\xb8" { - t.Error(fmt.Sprintf("even terminated compact encode failed. Got: %q", res)) - } -} - -func TestCompactHexDecode(t *testing.T) { - exp := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16} - res := CompactHexDecode("verb") - - if !bytes.Equal(res, exp) { - t.Error("Error compact hex decode. Expected", exp, "got", res) - } -} - -func TestCompactDecode(t *testing.T) { - exp := []byte{1, 2, 3, 4, 5} - res := CompactDecode("\x11\x23\x45") - - if !bytes.Equal(res, exp) { - t.Error("odd compact decode. Expected", exp, "got", res) - } - - exp = []byte{0, 1, 2, 3, 4, 5} - res = CompactDecode("\x00\x01\x23\x45") - - if !bytes.Equal(res, exp) { - t.Error("even compact decode. Expected", exp, "got", res) - } - - exp = []byte{0, 15, 1, 12, 11, 8 /*term*/, 16} - res = CompactDecode("\x20\x0f\x1c\xb8") - - if !bytes.Equal(res, exp) { - t.Error("even terminated compact decode. Expected", exp, "got", res) - } - - exp = []byte{15, 1, 12, 11, 8 /*term*/, 16} - res = CompactDecode("\x3f\x1c\xb8") - - if !bytes.Equal(res, exp) { - t.Error("even terminated compact decode. Expected", exp, "got", res) - } -} diff --git a/ethtrie/iterator.go b/ethtrie/iterator.go deleted file mode 100644 index 43f497416..000000000 --- a/ethtrie/iterator.go +++ /dev/null @@ -1,143 +0,0 @@ -package ethtrie - -import ( - "bytes" - - "github.com/ethereum/go-ethereum/ethutil" -) - -type NodeType byte - -const ( - EmptyNode NodeType = iota - BranchNode - LeafNode - ExtNode -) - -func getType(node *ethutil.Value) NodeType { - if node.Len() == 0 { - return EmptyNode - } - - if node.Len() == 2 { - k := CompactDecode(node.Get(0).Str()) - if HasTerm(k) { - return LeafNode - } - - return ExtNode - } - - return BranchNode -} - -type Iterator struct { - Path [][]byte - trie *Trie - - Key []byte - Value *ethutil.Value -} - -func NewIterator(trie *Trie) *Iterator { - return &Iterator{trie: trie} -} - -func (self *Iterator) key(node *ethutil.Value, path [][]byte) []byte { - switch getType(node) { - case LeafNode: - k := RemTerm(CompactDecode(node.Get(0).Str())) - - self.Path = append(path, k) - self.Value = node.Get(1) - - return k - case BranchNode: - if node.Get(16).Len() > 0 { - return []byte{16} - } - - for i := byte(0); i < 16; i++ { - o := self.key(self.trie.getNode(node.Get(int(i)).Raw()), append(path, []byte{i})) - if o != nil { - return append([]byte{i}, o...) - } - } - case ExtNode: - currKey := node.Get(0).Bytes() - - return self.key(self.trie.getNode(node.Get(1).Raw()), append(path, currKey)) - } - - return nil -} - -func (self *Iterator) next(node *ethutil.Value, key []byte, path [][]byte) []byte { - switch typ := getType(node); typ { - case EmptyNode: - return nil - case BranchNode: - if len(key) > 0 { - subNode := self.trie.getNode(node.Get(int(key[0])).Raw()) - - o := self.next(subNode, key[1:], append(path, key[:1])) - if o != nil { - return append([]byte{key[0]}, o...) - } - } - - var r byte = 0 - if len(key) > 0 { - r = key[0] + 1 - } - - for i := r; i < 16; i++ { - subNode := self.trie.getNode(node.Get(int(i)).Raw()) - o := self.key(subNode, append(path, []byte{i})) - if o != nil { - return append([]byte{i}, o...) - } - } - case LeafNode, ExtNode: - k := RemTerm(CompactDecode(node.Get(0).Str())) - if typ == LeafNode { - if bytes.Compare([]byte(k), []byte(key)) > 0 { - self.Value = node.Get(1) - self.Path = append(path, k) - - return k - } - } else { - subNode := self.trie.getNode(node.Get(1).Raw()) - subKey := key[len(k):] - var ret []byte - if BeginsWith(key, k) { - ret = self.next(subNode, subKey, append(path, k)) - } else if bytes.Compare(k, key[:len(k)]) > 0 { - ret = self.key(node, append(path, k)) - } else { - ret = nil - } - - if ret != nil { - return append(k, ret...) - } - } - } - - return nil -} - -// Get the next in keys -func (self *Iterator) Next(key string) []byte { - self.trie.mut.Lock() - defer self.trie.mut.Unlock() - - k := RemTerm(CompactHexDecode(key)) - n := self.next(self.trie.getNode(self.trie.Root), k, nil) - - self.Key = []byte(DecodeCompact(n)) - - return self.Key -} diff --git a/ethtrie/slice.go b/ethtrie/slice.go deleted file mode 100644 index f0edc9532..000000000 --- a/ethtrie/slice.go +++ /dev/null @@ -1,53 +0,0 @@ -package ethtrie - -import ( - "bytes" - "math" -) - -// Helper function for comparing slices -func CompareIntSlice(a, b []int) bool { - if len(a) != len(b) { - return false - } - for i, v := range a { - if v != b[i] { - return false - } - } - return true -} - -// Returns the amount of nibbles that match each other from 0 ... -func MatchingNibbleLength(a, b []byte) int { - var i, length = 0, int(math.Min(float64(len(a)), float64(len(b)))) - - for i < length { - if a[i] != b[i] { - break - } - i++ - } - - return i -} - -func HasTerm(s []byte) bool { - return s[len(s)-1] == 16 -} - -func RemTerm(s []byte) []byte { - if HasTerm(s) { - return s[:len(s)-1] - } - - return s -} - -func BeginsWith(a, b []byte) bool { - if len(b) > len(a) { - return false - } - - return bytes.Equal(a[:len(b)], b) -} diff --git a/ethtrie/trie.go b/ethtrie/trie.go deleted file mode 100644 index 4a6613b9d..000000000 --- a/ethtrie/trie.go +++ /dev/null @@ -1,620 +0,0 @@ -package ethtrie - -import ( - "bytes" - "fmt" - "sync" - - "github.com/ethereum/go-ethereum/crypto" - "github.com/ethereum/go-ethereum/ethutil" -) - -func ParanoiaCheck(t1 *Trie) (bool, *Trie) { - t2 := New(ethutil.Config.Db, "") - - t1.NewIterator().Each(func(key string, v *ethutil.Value) { - t2.Update(key, v.Str()) - }) - - a := ethutil.NewValue(t2.Root).Bytes() - b := ethutil.NewValue(t1.Root).Bytes() - - return bytes.Compare(a, b) == 0, t2 -} - -func (s *Cache) Len() int { - return len(s.nodes) -} - -// TODO -// A StateObject is an object that has a state root -// This is goig to be the object for the second level caching (the caching of object which have a state such as contracts) -type StateObject interface { - State() *Trie - Sync() - Undo() -} - -type Node struct { - Key []byte - Value *ethutil.Value - Dirty bool -} - -func NewNode(key []byte, val *ethutil.Value, dirty bool) *Node { - return &Node{Key: key, Value: val, Dirty: dirty} -} - -func (n *Node) Copy() *Node { - return NewNode(n.Key, n.Value, n.Dirty) -} - -type Cache struct { - nodes map[string]*Node - db ethutil.Database - IsDirty bool -} - -func NewCache(db ethutil.Database) *Cache { - return &Cache{db: db, nodes: make(map[string]*Node)} -} - -func (cache *Cache) PutValue(v interface{}, force bool) interface{} { - value := ethutil.NewValue(v) - - enc := value.Encode() - if len(enc) >= 32 || force { - sha := crypto.Sha3(enc) - - cache.nodes[string(sha)] = NewNode(sha, value, true) - cache.IsDirty = true - - return sha - } - - return v -} - -func (cache *Cache) Put(v interface{}) interface{} { - return cache.PutValue(v, false) -} - -func (cache *Cache) Get(key []byte) *ethutil.Value { - // First check if the key is the cache - if cache.nodes[string(key)] != nil { - return cache.nodes[string(key)].Value - } - - // Get the key of the database instead and cache it - data, _ := cache.db.Get(key) - // Create the cached value - value := ethutil.NewValueFromBytes(data) - - defer func() { - if r := recover(); r != nil { - fmt.Println("RECOVER GET", cache, cache.nodes) - panic("bye") - } - }() - // Create caching node - cache.nodes[string(key)] = NewNode(key, value, false) - - return value -} - -func (cache *Cache) Delete(key []byte) { - delete(cache.nodes, string(key)) - - cache.db.Delete(key) -} - -func (cache *Cache) Commit() { - // Don't try to commit if it isn't dirty - if !cache.IsDirty { - return - } - - for key, node := range cache.nodes { - if node.Dirty { - cache.db.Put([]byte(key), node.Value.Encode()) - node.Dirty = false - } - } - cache.IsDirty = false - - // If the nodes grows beyond the 200 entries we simple empty it - // FIXME come up with something better - if len(cache.nodes) > 200 { - cache.nodes = make(map[string]*Node) - } -} - -func (cache *Cache) Undo() { - for key, node := range cache.nodes { - if node.Dirty { - delete(cache.nodes, key) - } - } - cache.IsDirty = false -} - -// A (modified) Radix Trie implementation. The Trie implements -// a caching mechanism and will used cached values if they are -// present. If a node is not present in the cache it will try to -// fetch it from the database and store the cached value. -// Please note that the data isn't persisted unless `Sync` is -// explicitly called. -type Trie struct { - mut sync.RWMutex - prevRoot interface{} - Root interface{} - //db Database - cache *Cache -} - -func copyRoot(root interface{}) interface{} { - var prevRootCopy interface{} - if b, ok := root.([]byte); ok { - prevRootCopy = ethutil.CopyBytes(b) - } else { - prevRootCopy = root - } - - return prevRootCopy -} - -func New(db ethutil.Database, Root interface{}) *Trie { - // Make absolute sure the root is copied - r := copyRoot(Root) - p := copyRoot(Root) - - trie := &Trie{cache: NewCache(db), Root: r, prevRoot: p} - trie.setRoot(Root) - - return trie -} - -func (self *Trie) setRoot(root interface{}) { - switch t := root.(type) { - case string: - if t == "" { - root = crypto.Sha3([]byte("")) - } - self.Root = root - case []byte: - self.Root = root - default: - self.Root = self.cache.PutValue(root, true) - } -} - -/* - * Public (query) interface functions - */ - -func (t *Trie) Update(key, value string) { - t.mut.Lock() - defer t.mut.Unlock() - - k := CompactHexDecode(key) - - root := t.UpdateState(t.Root, k, value) - t.setRoot(root) -} - -func (t *Trie) Get(key string) string { - t.mut.Lock() - defer t.mut.Unlock() - - k := CompactHexDecode(key) - c := ethutil.NewValue(t.getState(t.Root, k)) - - return c.Str() -} - -func (t *Trie) Delete(key string) { - t.mut.Lock() - defer t.mut.Unlock() - - k := CompactHexDecode(key) - - root := t.deleteState(t.Root, k) - t.setRoot(root) -} - -func (self *Trie) GetRoot() []byte { - switch self.Root.(type) { - case string: - return []byte(self.Root.(string)) - case []byte: - return self.Root.([]byte) - default: - panic(fmt.Sprintf("invalid root type %T", self.Root)) - } -} - -// Simple compare function which creates a rlp value out of the evaluated objects -func (t *Trie) Cmp(trie *Trie) bool { - return ethutil.NewValue(t.Root).Cmp(ethutil.NewValue(trie.Root)) -} - -// Returns a copy of this trie -func (t *Trie) Copy() *Trie { - trie := New(t.cache.db, t.Root) - for key, node := range t.cache.nodes { - trie.cache.nodes[key] = node.Copy() - } - - return trie -} - -// Save the cached value to the database. -func (t *Trie) Sync() { - t.cache.Commit() - t.prevRoot = copyRoot(t.Root) -} - -func (t *Trie) Undo() { - t.cache.Undo() - t.Root = t.prevRoot -} - -func (t *Trie) Cache() *Cache { - return t.cache -} - -func (t *Trie) getState(node interface{}, key []byte) interface{} { - n := ethutil.NewValue(node) - // Return the node if key is empty (= found) - if len(key) == 0 || n.IsNil() || n.Len() == 0 { - return node - } - - currentNode := t.getNode(node) - length := currentNode.Len() - - if length == 0 { - return "" - } else if length == 2 { - // Decode the key - k := CompactDecode(currentNode.Get(0).Str()) - v := currentNode.Get(1).Raw() - - if len(key) >= len(k) && bytes.Equal(k, key[:len(k)]) { //CompareIntSlice(k, key[:len(k)]) { - return t.getState(v, key[len(k):]) - } else { - return "" - } - } else if length == 17 { - return t.getState(currentNode.Get(int(key[0])).Raw(), key[1:]) - } - - // It shouldn't come this far - panic("unexpected return") -} - -func (t *Trie) getNode(node interface{}) *ethutil.Value { - n := ethutil.NewValue(node) - - if !n.Get(0).IsNil() { - return n - } - - str := n.Str() - if len(str) == 0 { - return n - } else if len(str) < 32 { - return ethutil.NewValueFromBytes([]byte(str)) - } - - data := t.cache.Get(n.Bytes()) - - return data -} - -func (t *Trie) UpdateState(node interface{}, key []byte, value string) interface{} { - return t.InsertState(node, key, value) -} - -func (t *Trie) Put(node interface{}) interface{} { - return t.cache.Put(node) - -} - -func EmptyStringSlice(l int) []interface{} { - slice := make([]interface{}, l) - for i := 0; i < l; i++ { - slice[i] = "" - } - return slice -} - -func (t *Trie) InsertState(node interface{}, key []byte, value interface{}) interface{} { - if len(key) == 0 { - return value - } - - // New node - n := ethutil.NewValue(node) - if node == nil || n.Len() == 0 { - newNode := []interface{}{CompactEncode(key), value} - - return t.Put(newNode) - } - - currentNode := t.getNode(node) - // Check for "special" 2 slice type node - if currentNode.Len() == 2 { - // Decode the key - - k := CompactDecode(currentNode.Get(0).Str()) - v := currentNode.Get(1).Raw() - - // Matching key pair (ie. there's already an object with this key) - if bytes.Equal(k, key) { //CompareIntSlice(k, key) { - newNode := []interface{}{CompactEncode(key), value} - return t.Put(newNode) - } - - var newHash interface{} - matchingLength := MatchingNibbleLength(key, k) - if matchingLength == len(k) { - // Insert the hash, creating a new node - newHash = t.InsertState(v, key[matchingLength:], value) - } else { - // Expand the 2 length slice to a 17 length slice - oldNode := t.InsertState("", k[matchingLength+1:], v) - newNode := t.InsertState("", key[matchingLength+1:], value) - // Create an expanded slice - scaledSlice := EmptyStringSlice(17) - // Set the copied and new node - scaledSlice[k[matchingLength]] = oldNode - scaledSlice[key[matchingLength]] = newNode - - newHash = t.Put(scaledSlice) - } - - if matchingLength == 0 { - // End of the chain, return - return newHash - } else { - newNode := []interface{}{CompactEncode(key[:matchingLength]), newHash} - return t.Put(newNode) - } - } else { - - // Copy the current node over to the new node and replace the first nibble in the key - newNode := EmptyStringSlice(17) - - for i := 0; i < 17; i++ { - cpy := currentNode.Get(i).Raw() - if cpy != nil { - newNode[i] = cpy - } - } - - newNode[key[0]] = t.InsertState(currentNode.Get(int(key[0])).Raw(), key[1:], value) - - return t.Put(newNode) - } - - panic("unexpected end") -} - -func (t *Trie) deleteState(node interface{}, key []byte) interface{} { - if len(key) == 0 { - 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.Len() == 0 { - //return nil - //fmt.Printf(" %x %d\n", n, len(n.Bytes())) - - return "" - } - - currentNode := t.getNode(node) - // Check for "special" 2 slice type node - if currentNode.Len() == 2 { - // Decode the key - k := CompactDecode(currentNode.Get(0).Str()) - v := currentNode.Get(1).Raw() - - // Matching key pair (ie. there's already an object with this key) - if bytes.Equal(k, key) { //CompareIntSlice(k, key) { - //fmt.Printf(" %x\n", v) - - return "" - } else if bytes.Equal(key[:len(k)], k) { //CompareIntSlice(key[:len(k)], k) { - hash := t.deleteState(v, key[len(k):]) - child := t.getNode(hash) - - var newNode []interface{} - if child.Len() == 2 { - newKey := append(k, CompactDecode(child.Get(0).Str())...) - newNode = []interface{}{CompactEncode(newKey), child.Get(1).Raw()} - } else { - newNode = []interface{}{currentNode.Get(0).Str(), hash} - } - - //fmt.Printf("%x\n", newNode) - - return t.Put(newNode) - } else { - return node - } - } else { - // Copy the current node over to the new node and replace the first nibble in the key - n := EmptyStringSlice(17) - var newNode []interface{} - - for i := 0; i < 17; i++ { - cpy := currentNode.Get(i).Raw() - if cpy != nil { - n[i] = cpy - } - } - - n[key[0]] = t.deleteState(n[key[0]], key[1:]) - amount := -1 - for i := 0; i < 17; i++ { - if n[i] != "" { - if amount == -1 { - amount = i - } else { - amount = -2 - } - } - } - if amount == 16 { - newNode = []interface{}{CompactEncode([]byte{16}), n[amount]} - } else if amount >= 0 { - child := t.getNode(n[amount]) - if child.Len() == 17 { - newNode = []interface{}{CompactEncode([]byte{byte(amount)}), n[amount]} - } else if child.Len() == 2 { - key := append([]byte{byte(amount)}, CompactDecode(child.Get(0).Str())...) - newNode = []interface{}{CompactEncode(key), child.Get(1).Str()} - } - - } else { - newNode = n - } - - //fmt.Printf("%x\n", newNode) - return t.Put(newNode) - } - - panic("unexpected return") -} - -type TrieIterator struct { - trie *Trie - key string - value string - - shas [][]byte - values []string - - lastNode []byte -} - -func (t *Trie) NewIterator() *TrieIterator { - return &TrieIterator{trie: t} -} - -func (self *Trie) Iterator() *Iterator { - return NewIterator(self) -} - -// Some time in the near future this will need refactoring :-) -// XXX Note to self, IsSlice == inline node. Str == sha3 to node -func (it *TrieIterator) workNode(currentNode *ethutil.Value) { - if currentNode.Len() == 2 { - k := CompactDecode(currentNode.Get(0).Str()) - - if currentNode.Get(1).Str() == "" { - it.workNode(currentNode.Get(1)) - } else { - if k[len(k)-1] == 16 { - it.values = append(it.values, currentNode.Get(1).Str()) - } else { - it.shas = append(it.shas, currentNode.Get(1).Bytes()) - it.getNode(currentNode.Get(1).Bytes()) - } - } - } else { - for i := 0; i < currentNode.Len(); i++ { - if i == 16 && currentNode.Get(i).Len() != 0 { - it.values = append(it.values, currentNode.Get(i).Str()) - } else { - if currentNode.Get(i).Str() == "" { - it.workNode(currentNode.Get(i)) - } else { - val := currentNode.Get(i).Str() - if val != "" { - it.shas = append(it.shas, currentNode.Get(1).Bytes()) - it.getNode([]byte(val)) - } - } - } - } - } -} - -func (it *TrieIterator) getNode(node []byte) { - currentNode := it.trie.cache.Get(node) - it.workNode(currentNode) -} - -func (it *TrieIterator) Collect() [][]byte { - if it.trie.Root == "" { - return nil - } - - it.getNode(ethutil.NewValue(it.trie.Root).Bytes()) - - return it.shas -} - -func (it *TrieIterator) Purge() int { - shas := it.Collect() - for _, sha := range shas { - it.trie.cache.Delete(sha) - } - return len(it.values) -} - -func (it *TrieIterator) Key() string { - return "" -} - -func (it *TrieIterator) Value() string { - return "" -} - -type EachCallback func(key string, node *ethutil.Value) - -func (it *TrieIterator) Each(cb EachCallback) { - it.fetchNode(nil, ethutil.NewValue(it.trie.Root).Bytes(), cb) -} - -func (it *TrieIterator) fetchNode(key []byte, node []byte, cb EachCallback) { - it.iterateNode(key, it.trie.cache.Get(node), cb) -} - -func (it *TrieIterator) iterateNode(key []byte, currentNode *ethutil.Value, cb EachCallback) { - if currentNode.Len() == 2 { - k := CompactDecode(currentNode.Get(0).Str()) - - pk := append(key, k...) - if currentNode.Get(1).Len() != 0 && currentNode.Get(1).Str() == "" { - it.iterateNode(pk, currentNode.Get(1), cb) - } else { - if k[len(k)-1] == 16 { - cb(DecodeCompact(pk), currentNode.Get(1)) - } else { - it.fetchNode(pk, currentNode.Get(1).Bytes(), cb) - } - } - } else { - for i := 0; i < currentNode.Len(); i++ { - pk := append(key, byte(i)) - if i == 16 && currentNode.Get(i).Len() != 0 { - cb(DecodeCompact(pk), currentNode.Get(i)) - } else { - if currentNode.Get(i).Len() != 0 && currentNode.Get(i).Str() == "" { - it.iterateNode(pk, currentNode.Get(i), cb) - } else { - val := currentNode.Get(i).Str() - if val != "" { - it.fetchNode(pk, []byte(val), cb) - } - } - } - } - } -} diff --git a/ethtrie/trie_test.go b/ethtrie/trie_test.go deleted file mode 100644 index a70916483..000000000 --- a/ethtrie/trie_test.go +++ /dev/null @@ -1,434 +0,0 @@ -package ethtrie - -import ( - "bytes" - "encoding/hex" - "encoding/json" - "fmt" - "io/ioutil" - "math/rand" - "net/http" - "reflect" - "testing" - "time" - - "github.com/ethereum/go-ethereum/ethutil" -) - -const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ" - -type MemDatabase struct { - db map[string][]byte -} - -func NewMemDatabase() (*MemDatabase, error) { - db := &MemDatabase{db: make(map[string][]byte)} - return db, nil -} -func (db *MemDatabase) Put(key []byte, value []byte) { - db.db[string(key)] = value -} -func (db *MemDatabase) Get(key []byte) ([]byte, error) { - return db.db[string(key)], nil -} -func (db *MemDatabase) Delete(key []byte) error { - delete(db.db, string(key)) - return nil -} -func (db *MemDatabase) Print() {} -func (db *MemDatabase) Close() {} -func (db *MemDatabase) LastKnownTD() []byte { return nil } - -func NewTrie() (*MemDatabase, *Trie) { - db, _ := NewMemDatabase() - return db, New(db, "") -} - -func TestTrieSync(t *testing.T) { - db, trie := NewTrie() - - trie.Update("dog", LONG_WORD) - if len(db.db) != 0 { - t.Error("Expected no data in database") - } - - trie.Sync() - if len(db.db) == 0 { - t.Error("Expected data to be persisted") - } -} - -func TestTrieDirtyTracking(t *testing.T) { - _, trie := NewTrie() - trie.Update("dog", LONG_WORD) - if !trie.cache.IsDirty { - t.Error("Expected trie to be dirty") - } - - trie.Sync() - if trie.cache.IsDirty { - t.Error("Expected trie not to be dirty") - } - - trie.Update("test", LONG_WORD) - trie.cache.Undo() - if trie.cache.IsDirty { - t.Error("Expected trie not to be dirty") - } - -} - -func TestTrieReset(t *testing.T) { - _, trie := NewTrie() - - trie.Update("cat", LONG_WORD) - if len(trie.cache.nodes) == 0 { - t.Error("Expected cached nodes") - } - - trie.cache.Undo() - - if len(trie.cache.nodes) != 0 { - t.Error("Expected no nodes after undo") - } -} - -func TestTrieGet(t *testing.T) { - _, trie := NewTrie() - - trie.Update("cat", LONG_WORD) - x := trie.Get("cat") - if x != LONG_WORD { - t.Error("expected %s, got %s", LONG_WORD, x) - } -} - -func TestTrieUpdating(t *testing.T) { - _, trie := NewTrie() - trie.Update("cat", LONG_WORD) - trie.Update("cat", LONG_WORD+"1") - x := trie.Get("cat") - if x != LONG_WORD+"1" { - t.Error("expected %S, got %s", LONG_WORD+"1", x) - } -} - -func TestTrieCmp(t *testing.T) { - _, trie1 := NewTrie() - _, trie2 := NewTrie() - - trie1.Update("doge", LONG_WORD) - trie2.Update("doge", LONG_WORD) - if !trie1.Cmp(trie2) { - t.Error("Expected tries to be equal") - } - - trie1.Update("dog", LONG_WORD) - trie2.Update("cat", LONG_WORD) - if trie1.Cmp(trie2) { - t.Errorf("Expected tries not to be equal %x %x", trie1.Root, trie2.Root) - } -} - -func TestTrieDelete(t *testing.T) { - _, trie := NewTrie() - trie.Update("cat", LONG_WORD) - exp := trie.Root - trie.Update("dog", LONG_WORD) - trie.Delete("dog") - if !reflect.DeepEqual(exp, trie.Root) { - t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) - } - - trie.Update("dog", LONG_WORD) - exp = trie.Root - trie.Update("dude", LONG_WORD) - trie.Delete("dude") - if !reflect.DeepEqual(exp, trie.Root) { - t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) - } -} - -func TestTrieDeleteWithValue(t *testing.T) { - _, trie := NewTrie() - trie.Update("c", LONG_WORD) - exp := trie.Root - trie.Update("ca", LONG_WORD) - trie.Update("cat", LONG_WORD) - trie.Delete("ca") - trie.Delete("cat") - if !reflect.DeepEqual(exp, trie.Root) { - t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) - } - -} - -func TestTriePurge(t *testing.T) { - _, trie := NewTrie() - trie.Update("c", LONG_WORD) - trie.Update("ca", LONG_WORD) - trie.Update("cat", LONG_WORD) - - lenBefore := len(trie.cache.nodes) - it := trie.NewIterator() - if num := it.Purge(); num != 3 { - t.Errorf("Expected purge to return 3, got %d", num) - } - - if lenBefore == len(trie.cache.nodes) { - t.Errorf("Expected cached nodes to be deleted") - } -} - -func h(str string) string { - d, err := hex.DecodeString(str) - if err != nil { - panic(err) - } - - return string(d) -} - -func get(in string) (out string) { - if len(in) > 2 && in[:2] == "0x" { - out = h(in[2:]) - } else { - out = in - } - - 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) - } - - return t, nil -} - -func CreateTests(uri string, cb func(Test)) map[string]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) - } - - tests := make(map[string]Test) - for name, testData := range objmap { - test, err := CreateTest(name, *testData) - if err != nil { - panic(err) - } - - if cb != nil { - cb(test) - } - tests[name] = test - } - - return tests -} - -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 := NewTrie() - data := RandomData() - - for _, test := range data { - trie.Update(test[0], test[1]) - } - trie.Delete("0x4e616d6552656700000000000000000000000000000000000000000000000000") - - roots[string(trie.Root.([]byte))] += 1 - } - - if len(roots) > 1 { - for root, num := range roots { - t.Errorf("%x => %d\n", root, num) - } - } -} - -func TestDelete(t *testing.T) { - _, trie := NewTrie() - - 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") - - _, t2 := NewTrie() - 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() - - if bytes.Compare(a, b) != 0 { - t.Errorf("Expected %x and %x to be equal", a, b) - } -} - -func TestTerminator(t *testing.T) { - key := CompactDecode("hello") - if !HasTerm(key) { - t.Errorf("Expected %v to have a terminator", key) - } -} - -func TestIt(t *testing.T) { - _, trie := NewTrie() - trie.Update("cat", "cat") - trie.Update("doge", "doge") - trie.Update("wallace", "wallace") - it := trie.Iterator() - - inputs := []struct { - In, Out string - }{ - {"", "cat"}, - {"bobo", "cat"}, - {"c", "cat"}, - {"car", "cat"}, - {"catering", "doge"}, - {"w", "wallace"}, - {"wallace123", ""}, - } - - for _, test := range inputs { - res := string(it.Next(test.In)) - if res != test.Out { - t.Errorf(test.In, "failed. Got", res, "Expected", test.Out) - } - } -} - -func TestBeginsWith(t *testing.T) { - a := CompactDecode("hello") - b := CompactDecode("hel") - - if BeginsWith(a, b) { - t.Errorf("Expected %x to begin with %x", a, b) - } - - if BeginsWith(b, a) { - t.Errorf("Expected %x not to begin with %x", b, a) - } -} - -/* -func TestRndCase(t *testing.T) { - _, trie := NewTrie() - - 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")))) -} -*/ diff --git a/state/state.go b/state/state.go index 298cf9680..e1b73a6ab 100644 --- a/state/state.go +++ b/state/state.go @@ -3,9 +3,9 @@ package state import ( "math/big" - "github.com/ethereum/go-ethereum/ethtrie" "github.com/ethereum/go-ethereum/ethutil" "github.com/ethereum/go-ethereum/logger" + "github.com/ethereum/go-ethereum/trie" ) var statelogger = logger.NewLogger("STATE") @@ -17,7 +17,7 @@ var statelogger = logger.NewLogger("STATE") // * Accounts type State struct { // The trie for this structure - Trie *ethtrie.Trie + Trie *trie.Trie stateObjects map[string]*StateObject @@ -29,7 +29,7 @@ type State struct { } // Create a new state from a given trie -func New(trie *ethtrie.Trie) *State { +func New(trie *trie.Trie) *State { return &State{Trie: trie, stateObjects: make(map[string]*StateObject), manifest: NewManifest(), refund: make(map[string]*big.Int)} } @@ -300,7 +300,7 @@ func (self *State) Update() { // FIXME trie delete is broken if deleted { - valid, t2 := ethtrie.ParanoiaCheck(self.Trie) + valid, t2 := trie.ParanoiaCheck(self.Trie) if !valid { statelogger.Infof("Warn: PARANOIA: Different state root during copy %x vs %x\n", self.Trie.Root, t2.Root) diff --git a/state/state_object.go b/state/state_object.go index fb568e543..aa5c13678 100644 --- a/state/state_object.go +++ b/state/state_object.go @@ -5,8 +5,8 @@ import ( "math/big" "github.com/ethereum/go-ethereum/crypto" - "github.com/ethereum/go-ethereum/ethtrie" "github.com/ethereum/go-ethereum/ethutil" + "github.com/ethereum/go-ethereum/trie" ) type Code []byte @@ -62,7 +62,7 @@ func NewStateObject(addr []byte) *StateObject { address := ethutil.Address(addr) object := &StateObject{address: address, balance: new(big.Int), gasPool: new(big.Int)} - object.State = New(ethtrie.New(ethutil.Config.Db, "")) + object.State = New(trie.New(ethutil.Config.Db, "")) object.storage = make(Storage) object.gasPool = new(big.Int) @@ -72,7 +72,7 @@ func NewStateObject(addr []byte) *StateObject { func NewContract(address []byte, balance *big.Int, root []byte) *StateObject { contract := NewStateObject(address) contract.balance = balance - contract.State = New(ethtrie.New(ethutil.Config.Db, string(root))) + contract.State = New(trie.New(ethutil.Config.Db, string(root))) return contract } @@ -129,7 +129,7 @@ func (self *StateObject) SetState(k []byte, value *ethutil.Value) { } // Iterate over each storage address and yield callback -func (self *StateObject) EachStorage(cb ethtrie.EachCallback) { +func (self *StateObject) EachStorage(cb trie.EachCallback) { // First loop over the uncommit/cached values in storage for key, value := range self.storage { // XXX Most iterators Fns as it stands require encoded values @@ -158,7 +158,7 @@ func (self *StateObject) Sync() { self.SetAddr([]byte(key), value) } - valid, t2 := ethtrie.ParanoiaCheck(self.State.Trie) + valid, t2 := trie.ParanoiaCheck(self.State.Trie) if !valid { statelogger.Infof("Warn: PARANOIA: Different state storage root during copy %x vs %x\n", self.State.Trie.Root, t2.Root) @@ -321,7 +321,7 @@ func (c *StateObject) RlpDecode(data []byte) { c.Nonce = decoder.Get(0).Uint() c.balance = decoder.Get(1).BigInt() - c.State = New(ethtrie.New(ethutil.Config.Db, decoder.Get(2).Interface())) + c.State = New(trie.New(ethutil.Config.Db, decoder.Get(2).Interface())) c.storage = make(map[string]*ethutil.Value) c.gasPool = new(big.Int) diff --git a/trie/encoding.go b/trie/encoding.go new file mode 100644 index 000000000..4906bc90b --- /dev/null +++ b/trie/encoding.go @@ -0,0 +1,76 @@ +package trie + +import ( + "bytes" + "encoding/hex" + "strings" +) + +func CompactEncode(hexSlice []byte) string { + terminator := 0 + if hexSlice[len(hexSlice)-1] == 16 { + terminator = 1 + } + + if terminator == 1 { + hexSlice = hexSlice[:len(hexSlice)-1] + } + + oddlen := len(hexSlice) % 2 + flags := byte(2*terminator + oddlen) + if oddlen != 0 { + hexSlice = append([]byte{flags}, hexSlice...) + } else { + hexSlice = append([]byte{flags, 0}, hexSlice...) + } + + var buff bytes.Buffer + for i := 0; i < len(hexSlice); i += 2 { + buff.WriteByte(byte(16*hexSlice[i] + hexSlice[i+1])) + } + + return buff.String() +} + +func CompactDecode(str string) []byte { + base := CompactHexDecode(str) + base = base[:len(base)-1] + if base[0] >= 2 { + base = append(base, 16) + } + if base[0]%2 == 1 { + base = base[1:] + } else { + base = base[2:] + } + + return base +} + +func CompactHexDecode(str string) []byte { + base := "0123456789abcdef" + hexSlice := make([]byte, 0) + + enc := hex.EncodeToString([]byte(str)) + for _, v := range enc { + hexSlice = append(hexSlice, byte(strings.IndexByte(base, byte(v)))) + } + hexSlice = append(hexSlice, 16) + + return hexSlice +} + +func DecodeCompact(key []byte) string { + base := "0123456789abcdef" + var str string + + for _, v := range key { + if v < 16 { + str += string(base[v]) + } + } + + res, _ := hex.DecodeString(str) + + return string(res) +} diff --git a/trie/encoding_test.go b/trie/encoding_test.go new file mode 100644 index 000000000..c9bc113c9 --- /dev/null +++ b/trie/encoding_test.go @@ -0,0 +1,68 @@ +package trie + +import ( + "bytes" + "fmt" + "testing" +) + +func TestCompactEncode(t *testing.T) { + test1 := []byte{1, 2, 3, 4, 5} + if res := CompactEncode(test1); res != "\x11\x23\x45" { + t.Error(fmt.Sprintf("even compact encode failed. Got: %q", res)) + } + + test2 := []byte{0, 1, 2, 3, 4, 5} + if res := CompactEncode(test2); res != "\x00\x01\x23\x45" { + t.Error(fmt.Sprintf("odd compact encode failed. Got: %q", res)) + } + + test3 := []byte{0, 15, 1, 12, 11, 8 /*term*/, 16} + if res := CompactEncode(test3); res != "\x20\x0f\x1c\xb8" { + t.Error(fmt.Sprintf("odd terminated compact encode failed. Got: %q", res)) + } + + test4 := []byte{15, 1, 12, 11, 8 /*term*/, 16} + if res := CompactEncode(test4); res != "\x3f\x1c\xb8" { + t.Error(fmt.Sprintf("even terminated compact encode failed. Got: %q", res)) + } +} + +func TestCompactHexDecode(t *testing.T) { + exp := []byte{7, 6, 6, 5, 7, 2, 6, 2, 16} + res := CompactHexDecode("verb") + + if !bytes.Equal(res, exp) { + t.Error("Error compact hex decode. Expected", exp, "got", res) + } +} + +func TestCompactDecode(t *testing.T) { + exp := []byte{1, 2, 3, 4, 5} + res := CompactDecode("\x11\x23\x45") + + if !bytes.Equal(res, exp) { + t.Error("odd compact decode. Expected", exp, "got", res) + } + + exp = []byte{0, 1, 2, 3, 4, 5} + res = CompactDecode("\x00\x01\x23\x45") + + if !bytes.Equal(res, exp) { + t.Error("even compact decode. Expected", exp, "got", res) + } + + exp = []byte{0, 15, 1, 12, 11, 8 /*term*/, 16} + res = CompactDecode("\x20\x0f\x1c\xb8") + + if !bytes.Equal(res, exp) { + t.Error("even terminated compact decode. Expected", exp, "got", res) + } + + exp = []byte{15, 1, 12, 11, 8 /*term*/, 16} + res = CompactDecode("\x3f\x1c\xb8") + + if !bytes.Equal(res, exp) { + t.Error("even terminated compact decode. Expected", exp, "got", res) + } +} diff --git a/trie/iterator.go b/trie/iterator.go new file mode 100644 index 000000000..53d099a0c --- /dev/null +++ b/trie/iterator.go @@ -0,0 +1,143 @@ +package trie + +import ( + "bytes" + + "github.com/ethereum/go-ethereum/ethutil" +) + +type NodeType byte + +const ( + EmptyNode NodeType = iota + BranchNode + LeafNode + ExtNode +) + +func getType(node *ethutil.Value) NodeType { + if node.Len() == 0 { + return EmptyNode + } + + if node.Len() == 2 { + k := CompactDecode(node.Get(0).Str()) + if HasTerm(k) { + return LeafNode + } + + return ExtNode + } + + return BranchNode +} + +type Iterator struct { + Path [][]byte + trie *Trie + + Key []byte + Value *ethutil.Value +} + +func NewIterator(trie *Trie) *Iterator { + return &Iterator{trie: trie} +} + +func (self *Iterator) key(node *ethutil.Value, path [][]byte) []byte { + switch getType(node) { + case LeafNode: + k := RemTerm(CompactDecode(node.Get(0).Str())) + + self.Path = append(path, k) + self.Value = node.Get(1) + + return k + case BranchNode: + if node.Get(16).Len() > 0 { + return []byte{16} + } + + for i := byte(0); i < 16; i++ { + o := self.key(self.trie.getNode(node.Get(int(i)).Raw()), append(path, []byte{i})) + if o != nil { + return append([]byte{i}, o...) + } + } + case ExtNode: + currKey := node.Get(0).Bytes() + + return self.key(self.trie.getNode(node.Get(1).Raw()), append(path, currKey)) + } + + return nil +} + +func (self *Iterator) next(node *ethutil.Value, key []byte, path [][]byte) []byte { + switch typ := getType(node); typ { + case EmptyNode: + return nil + case BranchNode: + if len(key) > 0 { + subNode := self.trie.getNode(node.Get(int(key[0])).Raw()) + + o := self.next(subNode, key[1:], append(path, key[:1])) + if o != nil { + return append([]byte{key[0]}, o...) + } + } + + var r byte = 0 + if len(key) > 0 { + r = key[0] + 1 + } + + for i := r; i < 16; i++ { + subNode := self.trie.getNode(node.Get(int(i)).Raw()) + o := self.key(subNode, append(path, []byte{i})) + if o != nil { + return append([]byte{i}, o...) + } + } + case LeafNode, ExtNode: + k := RemTerm(CompactDecode(node.Get(0).Str())) + if typ == LeafNode { + if bytes.Compare([]byte(k), []byte(key)) > 0 { + self.Value = node.Get(1) + self.Path = append(path, k) + + return k + } + } else { + subNode := self.trie.getNode(node.Get(1).Raw()) + subKey := key[len(k):] + var ret []byte + if BeginsWith(key, k) { + ret = self.next(subNode, subKey, append(path, k)) + } else if bytes.Compare(k, key[:len(k)]) > 0 { + ret = self.key(node, append(path, k)) + } else { + ret = nil + } + + if ret != nil { + return append(k, ret...) + } + } + } + + return nil +} + +// Get the next in keys +func (self *Iterator) Next(key string) []byte { + self.trie.mut.Lock() + defer self.trie.mut.Unlock() + + k := RemTerm(CompactHexDecode(key)) + n := self.next(self.trie.getNode(self.trie.Root), k, nil) + + self.Key = []byte(DecodeCompact(n)) + + return self.Key +} diff --git a/trie/slice.go b/trie/slice.go new file mode 100644 index 000000000..f53b6c749 --- /dev/null +++ b/trie/slice.go @@ -0,0 +1,53 @@ +package trie + +import ( + "bytes" + "math" +) + +// Helper function for comparing slices +func CompareIntSlice(a, b []int) bool { + if len(a) != len(b) { + return false + } + for i, v := range a { + if v != b[i] { + return false + } + } + return true +} + +// Returns the amount of nibbles that match each other from 0 ... +func MatchingNibbleLength(a, b []byte) int { + var i, length = 0, int(math.Min(float64(len(a)), float64(len(b)))) + + for i < length { + if a[i] != b[i] { + break + } + i++ + } + + return i +} + +func HasTerm(s []byte) bool { + return s[len(s)-1] == 16 +} + +func RemTerm(s []byte) []byte { + if HasTerm(s) { + return s[:len(s)-1] + } + + return s +} + +func BeginsWith(a, b []byte) bool { + if len(b) > len(a) { + return false + } + + return bytes.Equal(a[:len(b)], b) +} diff --git a/trie/trie.go b/trie/trie.go new file mode 100644 index 000000000..b442abfe3 --- /dev/null +++ b/trie/trie.go @@ -0,0 +1,620 @@ +package trie + +import ( + "bytes" + "fmt" + "sync" + + "github.com/ethereum/go-ethereum/crypto" + "github.com/ethereum/go-ethereum/ethutil" +) + +func ParanoiaCheck(t1 *Trie) (bool, *Trie) { + t2 := New(ethutil.Config.Db, "") + + t1.NewIterator().Each(func(key string, v *ethutil.Value) { + t2.Update(key, v.Str()) + }) + + a := ethutil.NewValue(t2.Root).Bytes() + b := ethutil.NewValue(t1.Root).Bytes() + + return bytes.Compare(a, b) == 0, t2 +} + +func (s *Cache) Len() int { + return len(s.nodes) +} + +// TODO +// A StateObject is an object that has a state root +// This is goig to be the object for the second level caching (the caching of object which have a state such as contracts) +type StateObject interface { + State() *Trie + Sync() + Undo() +} + +type Node struct { + Key []byte + Value *ethutil.Value + Dirty bool +} + +func NewNode(key []byte, val *ethutil.Value, dirty bool) *Node { + return &Node{Key: key, Value: val, Dirty: dirty} +} + +func (n *Node) Copy() *Node { + return NewNode(n.Key, n.Value, n.Dirty) +} + +type Cache struct { + nodes map[string]*Node + db ethutil.Database + IsDirty bool +} + +func NewCache(db ethutil.Database) *Cache { + return &Cache{db: db, nodes: make(map[string]*Node)} +} + +func (cache *Cache) PutValue(v interface{}, force bool) interface{} { + value := ethutil.NewValue(v) + + enc := value.Encode() + if len(enc) >= 32 || force { + sha := crypto.Sha3(enc) + + cache.nodes[string(sha)] = NewNode(sha, value, true) + cache.IsDirty = true + + return sha + } + + return v +} + +func (cache *Cache) Put(v interface{}) interface{} { + return cache.PutValue(v, false) +} + +func (cache *Cache) Get(key []byte) *ethutil.Value { + // First check if the key is the cache + if cache.nodes[string(key)] != nil { + return cache.nodes[string(key)].Value + } + + // Get the key of the database instead and cache it + data, _ := cache.db.Get(key) + // Create the cached value + value := ethutil.NewValueFromBytes(data) + + defer func() { + if r := recover(); r != nil { + fmt.Println("RECOVER GET", cache, cache.nodes) + panic("bye") + } + }() + // Create caching node + cache.nodes[string(key)] = NewNode(key, value, false) + + return value +} + +func (cache *Cache) Delete(key []byte) { + delete(cache.nodes, string(key)) + + cache.db.Delete(key) +} + +func (cache *Cache) Commit() { + // Don't try to commit if it isn't dirty + if !cache.IsDirty { + return + } + + for key, node := range cache.nodes { + if node.Dirty { + cache.db.Put([]byte(key), node.Value.Encode()) + node.Dirty = false + } + } + cache.IsDirty = false + + // If the nodes grows beyond the 200 entries we simple empty it + // FIXME come up with something better + if len(cache.nodes) > 200 { + cache.nodes = make(map[string]*Node) + } +} + +func (cache *Cache) Undo() { + for key, node := range cache.nodes { + if node.Dirty { + delete(cache.nodes, key) + } + } + cache.IsDirty = false +} + +// A (modified) Radix Trie implementation. The Trie implements +// a caching mechanism and will used cached values if they are +// present. If a node is not present in the cache it will try to +// fetch it from the database and store the cached value. +// Please note that the data isn't persisted unless `Sync` is +// explicitly called. +type Trie struct { + mut sync.RWMutex + prevRoot interface{} + Root interface{} + //db Database + cache *Cache +} + +func copyRoot(root interface{}) interface{} { + var prevRootCopy interface{} + if b, ok := root.([]byte); ok { + prevRootCopy = ethutil.CopyBytes(b) + } else { + prevRootCopy = root + } + + return prevRootCopy +} + +func New(db ethutil.Database, Root interface{}) *Trie { + // Make absolute sure the root is copied + r := copyRoot(Root) + p := copyRoot(Root) + + trie := &Trie{cache: NewCache(db), Root: r, prevRoot: p} + trie.setRoot(Root) + + return trie +} + +func (self *Trie) setRoot(root interface{}) { + switch t := root.(type) { + case string: + if t == "" { + root = crypto.Sha3([]byte("")) + } + self.Root = root + case []byte: + self.Root = root + default: + self.Root = self.cache.PutValue(root, true) + } +} + +/* + * Public (query) interface functions + */ + +func (t *Trie) Update(key, value string) { + t.mut.Lock() + defer t.mut.Unlock() + + k := CompactHexDecode(key) + + root := t.UpdateState(t.Root, k, value) + t.setRoot(root) +} + +func (t *Trie) Get(key string) string { + t.mut.Lock() + defer t.mut.Unlock() + + k := CompactHexDecode(key) + c := ethutil.NewValue(t.getState(t.Root, k)) + + return c.Str() +} + +func (t *Trie) Delete(key string) { + t.mut.Lock() + defer t.mut.Unlock() + + k := CompactHexDecode(key) + + root := t.deleteState(t.Root, k) + t.setRoot(root) +} + +func (self *Trie) GetRoot() []byte { + switch self.Root.(type) { + case string: + return []byte(self.Root.(string)) + case []byte: + return self.Root.([]byte) + default: + panic(fmt.Sprintf("invalid root type %T", self.Root)) + } +} + +// Simple compare function which creates a rlp value out of the evaluated objects +func (t *Trie) Cmp(trie *Trie) bool { + return ethutil.NewValue(t.Root).Cmp(ethutil.NewValue(trie.Root)) +} + +// Returns a copy of this trie +func (t *Trie) Copy() *Trie { + trie := New(t.cache.db, t.Root) + for key, node := range t.cache.nodes { + trie.cache.nodes[key] = node.Copy() + } + + return trie +} + +// Save the cached value to the database. +func (t *Trie) Sync() { + t.cache.Commit() + t.prevRoot = copyRoot(t.Root) +} + +func (t *Trie) Undo() { + t.cache.Undo() + t.Root = t.prevRoot +} + +func (t *Trie) Cache() *Cache { + return t.cache +} + +func (t *Trie) getState(node interface{}, key []byte) interface{} { + n := ethutil.NewValue(node) + // Return the node if key is empty (= found) + if len(key) == 0 || n.IsNil() || n.Len() == 0 { + return node + } + + currentNode := t.getNode(node) + length := currentNode.Len() + + if length == 0 { + return "" + } else if length == 2 { + // Decode the key + k := CompactDecode(currentNode.Get(0).Str()) + v := currentNode.Get(1).Raw() + + if len(key) >= len(k) && bytes.Equal(k, key[:len(k)]) { //CompareIntSlice(k, key[:len(k)]) { + return t.getState(v, key[len(k):]) + } else { + return "" + } + } else if length == 17 { + return t.getState(currentNode.Get(int(key[0])).Raw(), key[1:]) + } + + // It shouldn't come this far + panic("unexpected return") +} + +func (t *Trie) getNode(node interface{}) *ethutil.Value { + n := ethutil.NewValue(node) + + if !n.Get(0).IsNil() { + return n + } + + str := n.Str() + if len(str) == 0 { + return n + } else if len(str) < 32 { + return ethutil.NewValueFromBytes([]byte(str)) + } + + data := t.cache.Get(n.Bytes()) + + return data +} + +func (t *Trie) UpdateState(node interface{}, key []byte, value string) interface{} { + return t.InsertState(node, key, value) +} + +func (t *Trie) Put(node interface{}) interface{} { + return t.cache.Put(node) + +} + +func EmptyStringSlice(l int) []interface{} { + slice := make([]interface{}, l) + for i := 0; i < l; i++ { + slice[i] = "" + } + return slice +} + +func (t *Trie) InsertState(node interface{}, key []byte, value interface{}) interface{} { + if len(key) == 0 { + return value + } + + // New node + n := ethutil.NewValue(node) + if node == nil || n.Len() == 0 { + newNode := []interface{}{CompactEncode(key), value} + + return t.Put(newNode) + } + + currentNode := t.getNode(node) + // Check for "special" 2 slice type node + if currentNode.Len() == 2 { + // Decode the key + + k := CompactDecode(currentNode.Get(0).Str()) + v := currentNode.Get(1).Raw() + + // Matching key pair (ie. there's already an object with this key) + if bytes.Equal(k, key) { //CompareIntSlice(k, key) { + newNode := []interface{}{CompactEncode(key), value} + return t.Put(newNode) + } + + var newHash interface{} + matchingLength := MatchingNibbleLength(key, k) + if matchingLength == len(k) { + // Insert the hash, creating a new node + newHash = t.InsertState(v, key[matchingLength:], value) + } else { + // Expand the 2 length slice to a 17 length slice + oldNode := t.InsertState("", k[matchingLength+1:], v) + newNode := t.InsertState("", key[matchingLength+1:], value) + // Create an expanded slice + scaledSlice := EmptyStringSlice(17) + // Set the copied and new node + scaledSlice[k[matchingLength]] = oldNode + scaledSlice[key[matchingLength]] = newNode + + newHash = t.Put(scaledSlice) + } + + if matchingLength == 0 { + // End of the chain, return + return newHash + } else { + newNode := []interface{}{CompactEncode(key[:matchingLength]), newHash} + return t.Put(newNode) + } + } else { + + // Copy the current node over to the new node and replace the first nibble in the key + newNode := EmptyStringSlice(17) + + for i := 0; i < 17; i++ { + cpy := currentNode.Get(i).Raw() + if cpy != nil { + newNode[i] = cpy + } + } + + newNode[key[0]] = t.InsertState(currentNode.Get(int(key[0])).Raw(), key[1:], value) + + return t.Put(newNode) + } + + panic("unexpected end") +} + +func (t *Trie) deleteState(node interface{}, key []byte) interface{} { + if len(key) == 0 { + 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.Len() == 0 { + //return nil + //fmt.Printf(" %x %d\n", n, len(n.Bytes())) + + return "" + } + + currentNode := t.getNode(node) + // Check for "special" 2 slice type node + if currentNode.Len() == 2 { + // Decode the key + k := CompactDecode(currentNode.Get(0).Str()) + v := currentNode.Get(1).Raw() + + // Matching key pair (ie. there's already an object with this key) + if bytes.Equal(k, key) { //CompareIntSlice(k, key) { + //fmt.Printf(" %x\n", v) + + return "" + } else if bytes.Equal(key[:len(k)], k) { //CompareIntSlice(key[:len(k)], k) { + hash := t.deleteState(v, key[len(k):]) + child := t.getNode(hash) + + var newNode []interface{} + if child.Len() == 2 { + newKey := append(k, CompactDecode(child.Get(0).Str())...) + newNode = []interface{}{CompactEncode(newKey), child.Get(1).Raw()} + } else { + newNode = []interface{}{currentNode.Get(0).Str(), hash} + } + + //fmt.Printf("%x\n", newNode) + + return t.Put(newNode) + } else { + return node + } + } else { + // Copy the current node over to the new node and replace the first nibble in the key + n := EmptyStringSlice(17) + var newNode []interface{} + + for i := 0; i < 17; i++ { + cpy := currentNode.Get(i).Raw() + if cpy != nil { + n[i] = cpy + } + } + + n[key[0]] = t.deleteState(n[key[0]], key[1:]) + amount := -1 + for i := 0; i < 17; i++ { + if n[i] != "" { + if amount == -1 { + amount = i + } else { + amount = -2 + } + } + } + if amount == 16 { + newNode = []interface{}{CompactEncode([]byte{16}), n[amount]} + } else if amount >= 0 { + child := t.getNode(n[amount]) + if child.Len() == 17 { + newNode = []interface{}{CompactEncode([]byte{byte(amount)}), n[amount]} + } else if child.Len() == 2 { + key := append([]byte{byte(amount)}, CompactDecode(child.Get(0).Str())...) + newNode = []interface{}{CompactEncode(key), child.Get(1).Str()} + } + + } else { + newNode = n + } + + //fmt.Printf("%x\n", newNode) + return t.Put(newNode) + } + + panic("unexpected return") +} + +type TrieIterator struct { + trie *Trie + key string + value string + + shas [][]byte + values []string + + lastNode []byte +} + +func (t *Trie) NewIterator() *TrieIterator { + return &TrieIterator{trie: t} +} + +func (self *Trie) Iterator() *Iterator { + return NewIterator(self) +} + +// Some time in the near future this will need refactoring :-) +// XXX Note to self, IsSlice == inline node. Str == sha3 to node +func (it *TrieIterator) workNode(currentNode *ethutil.Value) { + if currentNode.Len() == 2 { + k := CompactDecode(currentNode.Get(0).Str()) + + if currentNode.Get(1).Str() == "" { + it.workNode(currentNode.Get(1)) + } else { + if k[len(k)-1] == 16 { + it.values = append(it.values, currentNode.Get(1).Str()) + } else { + it.shas = append(it.shas, currentNode.Get(1).Bytes()) + it.getNode(currentNode.Get(1).Bytes()) + } + } + } else { + for i := 0; i < currentNode.Len(); i++ { + if i == 16 && currentNode.Get(i).Len() != 0 { + it.values = append(it.values, currentNode.Get(i).Str()) + } else { + if currentNode.Get(i).Str() == "" { + it.workNode(currentNode.Get(i)) + } else { + val := currentNode.Get(i).Str() + if val != "" { + it.shas = append(it.shas, currentNode.Get(1).Bytes()) + it.getNode([]byte(val)) + } + } + } + } + } +} + +func (it *TrieIterator) getNode(node []byte) { + currentNode := it.trie.cache.Get(node) + it.workNode(currentNode) +} + +func (it *TrieIterator) Collect() [][]byte { + if it.trie.Root == "" { + return nil + } + + it.getNode(ethutil.NewValue(it.trie.Root).Bytes()) + + return it.shas +} + +func (it *TrieIterator) Purge() int { + shas := it.Collect() + for _, sha := range shas { + it.trie.cache.Delete(sha) + } + return len(it.values) +} + +func (it *TrieIterator) Key() string { + return "" +} + +func (it *TrieIterator) Value() string { + return "" +} + +type EachCallback func(key string, node *ethutil.Value) + +func (it *TrieIterator) Each(cb EachCallback) { + it.fetchNode(nil, ethutil.NewValue(it.trie.Root).Bytes(), cb) +} + +func (it *TrieIterator) fetchNode(key []byte, node []byte, cb EachCallback) { + it.iterateNode(key, it.trie.cache.Get(node), cb) +} + +func (it *TrieIterator) iterateNode(key []byte, currentNode *ethutil.Value, cb EachCallback) { + if currentNode.Len() == 2 { + k := CompactDecode(currentNode.Get(0).Str()) + + pk := append(key, k...) + if currentNode.Get(1).Len() != 0 && currentNode.Get(1).Str() == "" { + it.iterateNode(pk, currentNode.Get(1), cb) + } else { + if k[len(k)-1] == 16 { + cb(DecodeCompact(pk), currentNode.Get(1)) + } else { + it.fetchNode(pk, currentNode.Get(1).Bytes(), cb) + } + } + } else { + for i := 0; i < currentNode.Len(); i++ { + pk := append(key, byte(i)) + if i == 16 && currentNode.Get(i).Len() != 0 { + cb(DecodeCompact(pk), currentNode.Get(i)) + } else { + if currentNode.Get(i).Len() != 0 && currentNode.Get(i).Str() == "" { + it.iterateNode(pk, currentNode.Get(i), cb) + } else { + val := currentNode.Get(i).Str() + if val != "" { + it.fetchNode(pk, []byte(val), cb) + } + } + } + } + } +} diff --git a/trie/trie_test.go b/trie/trie_test.go new file mode 100644 index 000000000..5f3975915 --- /dev/null +++ b/trie/trie_test.go @@ -0,0 +1,434 @@ +package trie + +import ( + "bytes" + "encoding/hex" + "encoding/json" + "fmt" + "io/ioutil" + "math/rand" + "net/http" + "reflect" + "testing" + "time" + + "github.com/ethereum/go-ethereum/ethutil" +) + +const LONG_WORD = "1234567890abcdefghijklmnopqrstuvwxxzABCEFGHIJKLMNOPQRSTUVWXYZ" + +type MemDatabase struct { + db map[string][]byte +} + +func NewMemDatabase() (*MemDatabase, error) { + db := &MemDatabase{db: make(map[string][]byte)} + return db, nil +} +func (db *MemDatabase) Put(key []byte, value []byte) { + db.db[string(key)] = value +} +func (db *MemDatabase) Get(key []byte) ([]byte, error) { + return db.db[string(key)], nil +} +func (db *MemDatabase) Delete(key []byte) error { + delete(db.db, string(key)) + return nil +} +func (db *MemDatabase) Print() {} +func (db *MemDatabase) Close() {} +func (db *MemDatabase) LastKnownTD() []byte { return nil } + +func NewTrie() (*MemDatabase, *Trie) { + db, _ := NewMemDatabase() + return db, New(db, "") +} + +func TestTrieSync(t *testing.T) { + db, trie := NewTrie() + + trie.Update("dog", LONG_WORD) + if len(db.db) != 0 { + t.Error("Expected no data in database") + } + + trie.Sync() + if len(db.db) == 0 { + t.Error("Expected data to be persisted") + } +} + +func TestTrieDirtyTracking(t *testing.T) { + _, trie := NewTrie() + trie.Update("dog", LONG_WORD) + if !trie.cache.IsDirty { + t.Error("Expected trie to be dirty") + } + + trie.Sync() + if trie.cache.IsDirty { + t.Error("Expected trie not to be dirty") + } + + trie.Update("test", LONG_WORD) + trie.cache.Undo() + if trie.cache.IsDirty { + t.Error("Expected trie not to be dirty") + } + +} + +func TestTrieReset(t *testing.T) { + _, trie := NewTrie() + + trie.Update("cat", LONG_WORD) + if len(trie.cache.nodes) == 0 { + t.Error("Expected cached nodes") + } + + trie.cache.Undo() + + if len(trie.cache.nodes) != 0 { + t.Error("Expected no nodes after undo") + } +} + +func TestTrieGet(t *testing.T) { + _, trie := NewTrie() + + trie.Update("cat", LONG_WORD) + x := trie.Get("cat") + if x != LONG_WORD { + t.Error("expected %s, got %s", LONG_WORD, x) + } +} + +func TestTrieUpdating(t *testing.T) { + _, trie := NewTrie() + trie.Update("cat", LONG_WORD) + trie.Update("cat", LONG_WORD+"1") + x := trie.Get("cat") + if x != LONG_WORD+"1" { + t.Error("expected %S, got %s", LONG_WORD+"1", x) + } +} + +func TestTrieCmp(t *testing.T) { + _, trie1 := NewTrie() + _, trie2 := NewTrie() + + trie1.Update("doge", LONG_WORD) + trie2.Update("doge", LONG_WORD) + if !trie1.Cmp(trie2) { + t.Error("Expected tries to be equal") + } + + trie1.Update("dog", LONG_WORD) + trie2.Update("cat", LONG_WORD) + if trie1.Cmp(trie2) { + t.Errorf("Expected tries not to be equal %x %x", trie1.Root, trie2.Root) + } +} + +func TestTrieDelete(t *testing.T) { + _, trie := NewTrie() + trie.Update("cat", LONG_WORD) + exp := trie.Root + trie.Update("dog", LONG_WORD) + trie.Delete("dog") + if !reflect.DeepEqual(exp, trie.Root) { + t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) + } + + trie.Update("dog", LONG_WORD) + exp = trie.Root + trie.Update("dude", LONG_WORD) + trie.Delete("dude") + if !reflect.DeepEqual(exp, trie.Root) { + t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) + } +} + +func TestTrieDeleteWithValue(t *testing.T) { + _, trie := NewTrie() + trie.Update("c", LONG_WORD) + exp := trie.Root + trie.Update("ca", LONG_WORD) + trie.Update("cat", LONG_WORD) + trie.Delete("ca") + trie.Delete("cat") + if !reflect.DeepEqual(exp, trie.Root) { + t.Errorf("Expected tries to be equal %x : %x", exp, trie.Root) + } + +} + +func TestTriePurge(t *testing.T) { + _, trie := NewTrie() + trie.Update("c", LONG_WORD) + trie.Update("ca", LONG_WORD) + trie.Update("cat", LONG_WORD) + + lenBefore := len(trie.cache.nodes) + it := trie.NewIterator() + if num := it.Purge(); num != 3 { + t.Errorf("Expected purge to return 3, got %d", num) + } + + if lenBefore == len(trie.cache.nodes) { + t.Errorf("Expected cached nodes to be deleted") + } +} + +func h(str string) string { + d, err := hex.DecodeString(str) + if err != nil { + panic(err) + } + + return string(d) +} + +func get(in string) (out string) { + if len(in) > 2 && in[:2] == "0x" { + out = h(in[2:]) + } else { + out = in + } + + 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) + } + + return t, nil +} + +func CreateTests(uri string, cb func(Test)) map[string]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) + } + + tests := make(map[string]Test) + for name, testData := range objmap { + test, err := CreateTest(name, *testData) + if err != nil { + panic(err) + } + + if cb != nil { + cb(test) + } + tests[name] = test + } + + return tests +} + +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 := NewTrie() + data := RandomData() + + for _, test := range data { + trie.Update(test[0], test[1]) + } + trie.Delete("0x4e616d6552656700000000000000000000000000000000000000000000000000") + + roots[string(trie.Root.([]byte))] += 1 + } + + if len(roots) > 1 { + for root, num := range roots { + t.Errorf("%x => %d\n", root, num) + } + } +} + +func TestDelete(t *testing.T) { + _, trie := NewTrie() + + 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") + + _, t2 := NewTrie() + 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() + + if bytes.Compare(a, b) != 0 { + t.Errorf("Expected %x and %x to be equal", a, b) + } +} + +func TestTerminator(t *testing.T) { + key := CompactDecode("hello") + if !HasTerm(key) { + t.Errorf("Expected %v to have a terminator", key) + } +} + +func TestIt(t *testing.T) { + _, trie := NewTrie() + trie.Update("cat", "cat") + trie.Update("doge", "doge") + trie.Update("wallace", "wallace") + it := trie.Iterator() + + inputs := []struct { + In, Out string + }{ + {"", "cat"}, + {"bobo", "cat"}, + {"c", "cat"}, + {"car", "cat"}, + {"catering", "doge"}, + {"w", "wallace"}, + {"wallace123", ""}, + } + + for _, test := range inputs { + res := string(it.Next(test.In)) + if res != test.Out { + t.Errorf(test.In, "failed. Got", res, "Expected", test.Out) + } + } +} + +func TestBeginsWith(t *testing.T) { + a := CompactDecode("hello") + b := CompactDecode("hel") + + if BeginsWith(a, b) { + t.Errorf("Expected %x to begin with %x", a, b) + } + + if BeginsWith(b, a) { + t.Errorf("Expected %x not to begin with %x", b, a) + } +} + +/* +func TestRndCase(t *testing.T) { + _, trie := NewTrie() + + 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