diff options
Diffstat (limited to 'trie')
| -rw-r--r-- | trie/iterator.go | 25 | ||||
| -rw-r--r-- | trie/iterator_test.go | 32 | ||||
| -rw-r--r-- | trie/sync_test.go | 3 |
3 files changed, 47 insertions, 13 deletions
diff --git a/trie/iterator.go b/trie/iterator.go index e79de2e4e..12ca96bd1 100644 --- a/trie/iterator.go +++ b/trie/iterator.go @@ -20,6 +20,7 @@ import ( "bytes" "fmt" + "github.com/ethereum/go-ethereum/common" "github.com/ethereum/go-ethereum/logger" "github.com/ethereum/go-ethereum/logger/glog" ) @@ -152,8 +153,9 @@ func (self *Iterator) key(node interface{}) []byte { // nodeIteratorState represents the iteration state at one particular node of the // trie, which can be resumed at a later invocation. type nodeIteratorState struct { - node node // Trie node being iterated - child int // Child to be processed next + hash common.Hash // Hash of the node being iterated (nil if not standalone) + node node // Trie node being iterated + child int // Child to be processed next } // NodeIterator is an iterator to traverse the trie post-order. @@ -161,9 +163,10 @@ type NodeIterator struct { trie *Trie // Trie being iterated stack []*nodeIteratorState // Hierarchy of trie nodes persisting the iteration state - Node node // Current node being iterated (internal representation) - Leaf bool // Flag whether the current node is a value (data) node - LeafBlob []byte // Data blob contained within a leaf (otherwise nil) + Hash common.Hash // Hash of the current node being iterated (nil if not standalone) + Node node // Current node being iterated (internal representation) + Leaf bool // Flag whether the current node is a value (data) node + LeafBlob []byte // Data blob contained within a leaf (otherwise nil) } // NewNodeIterator creates an post-order trie iterator. @@ -221,18 +224,18 @@ func (it *NodeIterator) step() { } parent.child++ it.stack = append(it.stack, &nodeIteratorState{node: node.Val, child: -1}) - } else if node, ok := parent.node.(hashNode); ok { + } else if hash, ok := parent.node.(hashNode); ok { // Hash node, resolve the hash child from the database, then the node itself if parent.child >= 0 { break } parent.child++ - node, err := it.trie.resolveHash(node, nil, nil) + node, err := it.trie.resolveHash(hash, nil, nil) if err != nil { panic(err) } - it.stack = append(it.stack, &nodeIteratorState{node: node, child: -1}) + it.stack = append(it.stack, &nodeIteratorState{hash: common.BytesToHash(hash), node: node, child: -1}) } else { break } @@ -246,14 +249,16 @@ func (it *NodeIterator) step() { // The method returns whether there are any more data left for inspection. func (it *NodeIterator) retrieve() bool { // Clear out any previously set values - it.Node, it.Leaf, it.LeafBlob = nil, false, nil + it.Hash, it.Node, it.Leaf, it.LeafBlob = common.Hash{}, nil, false, nil // If the iteration's done, return no available data if it.trie == nil { return false } // Otherwise retrieve the current node and resolve leaf accessors - it.Node = it.stack[len(it.stack)-1].node + state := it.stack[len(it.stack)-1] + + it.Hash, it.Node = state.hash, state.node if value, ok := it.Node.(valueNode); ok { it.Leaf, it.LeafBlob = true, []byte(value) } diff --git a/trie/iterator_test.go b/trie/iterator_test.go index fdc60b412..dc8276116 100644 --- a/trie/iterator_test.go +++ b/trie/iterator_test.go @@ -16,7 +16,12 @@ package trie -import "testing" +import ( + "testing" + + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/ethdb" +) func TestIterator(t *testing.T) { trie := newEmpty() @@ -47,3 +52,28 @@ func TestIterator(t *testing.T) { } } } + +// Tests that the node iterator indeed walks over the entire database contents. +func TestNodeIteratorCoverage(t *testing.T) { + // Create some arbitrary test trie to iterate + db, trie, _ := makeTestTrie() + + // Gather all the node hashes found by the iterator + hashes := make(map[common.Hash]struct{}) + for it := NewNodeIterator(trie); it.Next(); { + if it.Hash != (common.Hash{}) { + hashes[it.Hash] = struct{}{} + } + } + // Cross check the hashes and the database itself + for hash, _ := range hashes { + if _, err := db.Get(hash.Bytes()); err != nil { + t.Errorf("failed to retrieve reported node %x: %v", hash, err) + } + } + for _, key := range db.(*ethdb.MemDatabase).Keys() { + if _, ok := hashes[common.BytesToHash(key)]; !ok { + t.Errorf("state entry not reported %x", key) + } + } +} diff --git a/trie/sync_test.go b/trie/sync_test.go index 94d6edd68..ce098d5a0 100644 --- a/trie/sync_test.go +++ b/trie/sync_test.go @@ -96,8 +96,7 @@ func checkTrieConsistency(db Database, root common.Hash) (failure error) { if err != nil { return } - it := NewNodeIterator(trie) - for it.Next() { + for it := NewNodeIterator(trie); it.Next(); { } return nil } |