trie: more node iterator improvements (#14615)

* ethdb: remove Set

Set deadlocks immediately and isn't part of the Database interface.

* trie: add Err to Iterator

This is useful for testing because the underlying NodeIterator doesn't
need to be kept in a separate variable just to get the error.

* trie: add LeafKey to iterator, panic when not at leaf

LeafKey is useful for callers that can't interpret Path.

* trie: retry failed seek/peek in iterator Next

Instead of failing iteration irrecoverably, make it so Next retries the
pending seek or peek every time.

Smaller changes in this commit make this easier to test:

* The iterator previously returned from Next on encountering a hash
  node. This caused it to visit the same path twice.
* Path returned nibbles with terminator symbol for valueNode attached
  to fullNode, but removed it for valueNode attached to shortNode. Now
  the terminator is always present. This makes Path unique to each node
  and simplifies Leaf.

* trie: add Path to MissingNodeError

The light client trie iterator needs to know the path of the node that's
missing so it can retrieve a proof for it. NodeIterator.Path is not
sufficient because it is updated when the node is resolved and actually
visited by the iterator.

Also remove unused fields. They were added a long time ago before we
knew which fields would be needed for the light client.

1 files changed, 136 insertions, 107 deletions

diff --git a/trie/iterator.go b/trie/iterator.go
index 26ae1d5ad..76146c0d6 100644
--- a/trie/iterator.go
+++ b/trie/iterator.go
@@ -24,14 +24,13 @@ import (
 	"github.com/ethereum/go-ethereum/common"
 )
 
-var iteratorEnd = errors.New("end of iteration")
-
 // Iterator is a key-value trie iterator that traverses a Trie.
 type Iterator struct {
 	nodeIt NodeIterator
 
 	Key   []byte // Current data key on which the iterator is positioned on
 	Value []byte // Current data value on which the iterator is positioned on
+	Err   error
 }
 
 // NewIterator creates a new key-value iterator from a node iterator
@@ -45,35 +44,42 @@ func NewIterator(it NodeIterator) *Iterator {
 func (it *Iterator) Next() bool {
 	for it.nodeIt.Next(true) {
 		if it.nodeIt.Leaf() {
-			it.Key = hexToKeybytes(it.nodeIt.Path())
+			it.Key = it.nodeIt.LeafKey()
 			it.Value = it.nodeIt.LeafBlob()
 			return true
 		}
 	}
 	it.Key = nil
 	it.Value = nil
+	it.Err = it.nodeIt.Error()
 	return false
 }
 
 // NodeIterator is an iterator to traverse the trie pre-order.
 type NodeIterator interface {
-	// Hash returns the hash of the current node
-	Hash() common.Hash
-	// Parent returns the hash of the parent of the current node
-	Parent() common.Hash
-	// Leaf returns true iff the current node is a leaf node.
-	Leaf() bool
-	// LeafBlob returns the contents of the node, if it is a leaf.
-	// Callers must not retain references to the return value after calling Next()
-	LeafBlob() []byte
-	// Path returns the hex-encoded path to the current node.
-	// Callers must not retain references to the return value after calling Next()
-	Path() []byte
 	// Next moves the iterator to the next node. If the parameter is false, any child
 	// nodes will be skipped.
 	Next(bool) bool
 	// Error returns the error status of the iterator.
 	Error() error
+
+	// Hash returns the hash of the current node.
+	Hash() common.Hash
+	// Parent returns the hash of the parent of the current node. The hash may be the one
+	// grandparent if the immediate parent is an internal node with no hash.
+	Parent() common.Hash
+	// Path returns the hex-encoded path to the current node.
+	// Callers must not retain references to the return value after calling Next.
+	// For leaf nodes, the last element of the path is the 'terminator symbol' 0x10.
+	Path() []byte
+
+	// Leaf returns true iff the current node is a leaf node.
+	// LeafBlob, LeafKey return the contents and key of the leaf node. These
+	// method panic if the iterator is not positioned at a leaf.
+	// Callers must not retain references to their return value after calling Next
+	Leaf() bool
+	LeafBlob() []byte
+	LeafKey() []byte
 }
 
 // nodeIteratorState represents the iteration state at one particular node of the
@@ -89,8 +95,21 @@ type nodeIteratorState struct {
 type nodeIterator struct {
 	trie  *Trie                // Trie being iterated
 	stack []*nodeIteratorState // Hierarchy of trie nodes persisting the iteration state
-	err   error                // Failure set in case of an internal error in the iterator
 	path  []byte               // Path to the current node
+	err   error                // Failure set in case of an internal error in the iterator
+}
+
+// iteratorEnd is stored in nodeIterator.err when iteration is done.
+var iteratorEnd = errors.New("end of iteration")
+
+// seekError is stored in nodeIterator.err if the initial seek has failed.
+type seekError struct {
+	key []byte
+	err error
+}
+
+func (e seekError) Error() string {
+	return "seek error: " + e.err.Error()
 }
 
 func newNodeIterator(trie *Trie, start []byte) NodeIterator {
@@ -98,60 +117,57 @@ func newNodeIterator(trie *Trie, start []byte) NodeIterator {
 		return new(nodeIterator)
 	}
 	it := &nodeIterator{trie: trie}
-	it.seek(start)
+	it.err = it.seek(start)
 	return it
 }
 
-// Hash returns the hash of the current node
 func (it *nodeIterator) Hash() common.Hash {
 	if len(it.stack) == 0 {
 		return common.Hash{}
 	}
-
 	return it.stack[len(it.stack)-1].hash
 }
 
-// Parent returns the hash of the parent node
 func (it *nodeIterator) Parent() common.Hash {
 	if len(it.stack) == 0 {
 		return common.Hash{}
 	}
-
 	return it.stack[len(it.stack)-1].parent
 }
 
-// Leaf returns true if the current node is a leaf
 func (it *nodeIterator) Leaf() bool {
-	if len(it.stack) == 0 {
-		return false
-	}
-
-	_, ok := it.stack[len(it.stack)-1].node.(valueNode)
-	return ok
+	return hasTerm(it.path)
 }
 
-// LeafBlob returns the data for the current node, if it is a leaf
 func (it *nodeIterator) LeafBlob() []byte {
-	if len(it.stack) == 0 {
-		return nil
+	if len(it.stack) > 0 {
+		if node, ok := it.stack[len(it.stack)-1].node.(valueNode); ok {
+			return []byte(node)
+		}
 	}
+	panic("not at leaf")
+}
 
-	if node, ok := it.stack[len(it.stack)-1].node.(valueNode); ok {
-		return []byte(node)
+func (it *nodeIterator) LeafKey() []byte {
+	if len(it.stack) > 0 {
+		if _, ok := it.stack[len(it.stack)-1].node.(valueNode); ok {
+			return hexToKeybytes(it.path)
+		}
 	}
-	return nil
+	panic("not at leaf")
 }
 
-// Path returns the hex-encoded path to the current node
 func (it *nodeIterator) Path() []byte {
 	return it.path
 }
 
-// Error returns the error set in case of an internal error in the iterator
 func (it *nodeIterator) Error() error {
 	if it.err == iteratorEnd {
 		return nil
 	}
+	if seek, ok := it.err.(seekError); ok {
+		return seek.err
+	}
 	return it.err
 }
 
@@ -160,29 +176,37 @@ func (it *nodeIterator) Error() error {
 // sets the Error field to the encountered failure. If `descend` is false,
 // skips iterating over any subnodes of the current node.
 func (it *nodeIterator) Next(descend bool) bool {
-	if it.err != nil {
+	if it.err == iteratorEnd {
 		return false
 	}
-	// Otherwise step forward with the iterator and report any errors
+	if seek, ok := it.err.(seekError); ok {
+		if it.err = it.seek(seek.key); it.err != nil {
+			return false
+		}
+	}
+	// Otherwise step forward with the iterator and report any errors.
 	state, parentIndex, path, err := it.peek(descend)
-	if err != nil {
-		it.err = err
+	it.err = err
+	if it.err != nil {
 		return false
 	}
 	it.push(state, parentIndex, path)
 	return true
 }
 
-func (it *nodeIterator) seek(prefix []byte) {
+func (it *nodeIterator) seek(prefix []byte) error {
 	// The path we're looking for is the hex encoded key without terminator.
 	key := keybytesToHex(prefix)
 	key = key[:len(key)-1]
 	// Move forward until we're just before the closest match to key.
 	for {
 		state, parentIndex, path, err := it.peek(bytes.HasPrefix(key, it.path))
-		if err != nil || bytes.Compare(path, key) >= 0 {
-			it.err = err
-			return
+		if err == iteratorEnd {
+			return iteratorEnd
+		} else if err != nil {
+			return seekError{prefix, err}
+		} else if bytes.Compare(path, key) >= 0 {
+			return nil
 		}
 		it.push(state, parentIndex, path)
 	}
@@ -197,7 +221,8 @@ func (it *nodeIterator) peek(descend bool) (*nodeIteratorState, *int, []byte, er
 		if root != emptyRoot {
 			state.hash = root
 		}
-		return state, nil, nil, nil
+		err := state.resolve(it.trie, nil)
+		return state, nil, nil, err
 	}
 	if !descend {
 		// If we're skipping children, pop the current node first
@@ -205,72 +230,73 @@ func (it *nodeIterator) peek(descend bool) (*nodeIteratorState, *int, []byte, er
 	}
 
 	// Continue iteration to the next child
-	for {
-		if len(it.stack) == 0 {
-			return nil, nil, nil, iteratorEnd
-		}
+	for len(it.stack) > 0 {
 		parent := it.stack[len(it.stack)-1]
 		ancestor := parent.hash
 		if (ancestor == common.Hash{}) {
 			ancestor = parent.parent
 		}
-		if node, ok := parent.node.(*fullNode); ok {
-			// Full node, move to the first non-nil child.
-			for i := parent.index + 1; i < len(node.Children); i++ {
-				child := node.Children[i]
-				if child != nil {
-					hash, _ := child.cache()
-					state := &nodeIteratorState{
-						hash:    common.BytesToHash(hash),
-						node:    child,
-						parent:  ancestor,
-						index:   -1,
-						pathlen: len(it.path),
-					}
-					path := append(it.path, byte(i))
-					parent.index = i - 1
-					return state, &parent.index, path, nil
-				}
+		state, path, ok := it.nextChild(parent, ancestor)
+		if ok {
+			if err := state.resolve(it.trie, path); err != nil {
+				return parent, &parent.index, path, err
 			}
-		} else if node, ok := parent.node.(*shortNode); ok {
-			// Short node, return the pointer singleton child
-			if parent.index < 0 {
-				hash, _ := node.Val.cache()
+			return state, &parent.index, path, nil
+		}
+		// No more child nodes, move back up.
+		it.pop()
+	}
+	return nil, nil, nil, iteratorEnd
+}
+
+func (st *nodeIteratorState) resolve(tr *Trie, path []byte) error {
+	if hash, ok := st.node.(hashNode); ok {
+		resolved, err := tr.resolveHash(hash, path)
+		if err != nil {
+			return err
+		}
+		st.node = resolved
+		st.hash = common.BytesToHash(hash)
+	}
+	return nil
+}
+
+func (it *nodeIterator) nextChild(parent *nodeIteratorState, ancestor common.Hash) (*nodeIteratorState, []byte, bool) {
+	switch node := parent.node.(type) {
+	case *fullNode:
+		// Full node, move to the first non-nil child.
+		for i := parent.index + 1; i < len(node.Children); i++ {
+			child := node.Children[i]
+			if child != nil {
+				hash, _ := child.cache()
 				state := &nodeIteratorState{
 					hash:    common.BytesToHash(hash),
-					node:    node.Val,
+					node:    child,
 					parent:  ancestor,
 					index:   -1,
 					pathlen: len(it.path),
 				}
-				var path []byte
-				if hasTerm(node.Key) {
-					path = append(it.path, node.Key[:len(node.Key)-1]...)
-				} else {
-					path = append(it.path, node.Key...)
-				}
-				return state, &parent.index, path, nil
+				path := append(it.path, byte(i))
+				parent.index = i - 1
+				return state, path, true
 			}
-		} else if hash, ok := parent.node.(hashNode); ok {
-			// Hash node, resolve the hash child from the database
-			if parent.index < 0 {
-				node, err := it.trie.resolveHash(hash, nil, nil)
-				if err != nil {
-					return it.stack[len(it.stack)-1], &parent.index, it.path, err
-				}
-				state := &nodeIteratorState{
-					hash:    common.BytesToHash(hash),
-					node:    node,
-					parent:  ancestor,
-					index:   -1,
-					pathlen: len(it.path),
-				}
-				return state, &parent.index, it.path, nil
+		}
+	case *shortNode:
+		// Short node, return the pointer singleton child
+		if parent.index < 0 {
+			hash, _ := node.Val.cache()
+			state := &nodeIteratorState{
+				hash:    common.BytesToHash(hash),
+				node:    node.Val,
+				parent:  ancestor,
+				index:   -1,
+				pathlen: len(it.path),
 			}
+			path := append(it.path, node.Key...)
+			return state, path, true
 		}
-		// No more child nodes, move back up.
-		it.pop()
 	}
+	return parent, it.path, false
 }
 
 func (it *nodeIterator) push(state *nodeIteratorState, parentIndex *int, path []byte) {
@@ -288,23 +314,21 @@ func (it *nodeIterator) pop() {
 }
 
 func compareNodes(a, b NodeIterator) int {
-	cmp := bytes.Compare(a.Path(), b.Path())
-	if cmp != 0 {
+	if cmp := bytes.Compare(a.Path(), b.Path()); cmp != 0 {
 		return cmp
 	}
-
 	if a.Leaf() && !b.Leaf() {
 		return -1
 	} else if b.Leaf() && !a.Leaf() {
 		return 1
 	}
-
-	cmp = bytes.Compare(a.Hash().Bytes(), b.Hash().Bytes())
-	if cmp != 0 {
+	if cmp := bytes.Compare(a.Hash().Bytes(), b.Hash().Bytes()); cmp != 0 {
 		return cmp
 	}
-
-	return bytes.Compare(a.LeafBlob(), b.LeafBlob())
+	if a.Leaf() && b.Leaf() {
+		return bytes.Compare(a.LeafBlob(), b.LeafBlob())
+	}
+	return 0
 }
 
 type differenceIterator struct {
@@ -341,6 +365,10 @@ func (it *differenceIterator) LeafBlob() []byte {
 	return it.b.LeafBlob()
 }
 
+func (it *differenceIterator) LeafKey() []byte {
+	return it.b.LeafKey()
+}
+
 func (it *differenceIterator) Path() []byte {
 	return it.b.Path()
 }
@@ -410,7 +438,6 @@ func (h *nodeIteratorHeap) Pop() interface{} {
 type unionIterator struct {
 	items *nodeIteratorHeap // Nodes returned are the union of the ones in these iterators
 	count int               // Number of nodes scanned across all tries
-	err   error             // The error, if one has been encountered
 }
 
 // NewUnionIterator constructs a NodeIterator that iterates over elements in the union
@@ -421,9 +448,7 @@ func NewUnionIterator(iters []NodeIterator) (NodeIterator, *int) {
 	copy(h, iters)
 	heap.Init(&h)
 
-	ui := &unionIterator{
-		items: &h,
-	}
+	ui := &unionIterator{items: &h}
 	return ui, &ui.count
 }
 
@@ -443,6 +468,10 @@ func (it *unionIterator) LeafBlob() []byte {
 	return (*it.items)[0].LeafBlob()
 }
 
+func (it *unionIterator) LeafKey() []byte {
+	return (*it.items)[0].LeafKey()
+}
+
 func (it *unionIterator) Path() []byte {
 	return (*it.items)[0].Path()
 }