Merge pull request #14350 from fjl/trie-iterator-skip-2

eth: add debug_storageRangeAt

2 files changed, 178 insertions, 37 deletions

diff --git a/eth/api.go b/eth/api.go
index b386c08b4..61f7bdd92 100644
--- a/eth/api.go
+++ b/eth/api.go
@@ -20,7 +20,6 @@ import (
 	"bytes"
 	"compress/gzip"
 	"context"
-	"errors"
 	"fmt"
 	"io"
 	"io/ioutil"
@@ -41,6 +40,7 @@ import (
 	"github.com/ethereum/go-ethereum/params"
 	"github.com/ethereum/go-ethereum/rlp"
 	"github.com/ethereum/go-ethereum/rpc"
+	"github.com/ethereum/go-ethereum/trie"
 )
 
 const defaultTraceTimeout = 5 * time.Second
@@ -526,59 +526,67 @@ func (api *PrivateDebugAPI) TraceTransaction(ctx context.Context, txHash common.
 	if tx == nil {
 		return nil, fmt.Errorf("transaction %x not found", txHash)
 	}
+	msg, context, statedb, err := api.computeTxEnv(blockHash, int(txIndex))
+	if err != nil {
+		return nil, err
+	}
+
+	// Run the transaction with tracing enabled.
+	vmenv := vm.NewEVM(context, statedb, api.config, vm.Config{Debug: true, Tracer: tracer})
+	ret, gas, err := core.ApplyMessage(vmenv, msg, new(core.GasPool).AddGas(tx.Gas()))
+	if err != nil {
+		return nil, fmt.Errorf("tracing failed: %v", err)
+	}
+	switch tracer := tracer.(type) {
+	case *vm.StructLogger:
+		return &ethapi.ExecutionResult{
+			Gas:         gas,
+			ReturnValue: fmt.Sprintf("%x", ret),
+			StructLogs:  ethapi.FormatLogs(tracer.StructLogs()),
+		}, nil
+	case *ethapi.JavascriptTracer:
+		return tracer.GetResult()
+	default:
+		panic(fmt.Sprintf("bad tracer type %T", tracer))
+	}
+}
+
+// computeTxEnv returns the execution environment of a certain transaction.
+func (api *PrivateDebugAPI) computeTxEnv(blockHash common.Hash, txIndex int) (core.Message, vm.Context, *state.StateDB, error) {
+	// Create the parent state.
 	block := api.eth.BlockChain().GetBlockByHash(blockHash)
 	if block == nil {
-		return nil, fmt.Errorf("block %x not found", blockHash)
+		return nil, vm.Context{}, nil, fmt.Errorf("block %x not found", blockHash)
 	}
-	// Create the state database to mutate and eventually trace
 	parent := api.eth.BlockChain().GetBlock(block.ParentHash(), block.NumberU64()-1)
 	if parent == nil {
-		return nil, fmt.Errorf("block parent %x not found", block.ParentHash())
+		return nil, vm.Context{}, nil, fmt.Errorf("block parent %x not found", block.ParentHash())
 	}
-	stateDb, err := api.eth.BlockChain().StateAt(parent.Root())
+	statedb, err := api.eth.BlockChain().StateAt(parent.Root())
 	if err != nil {
-		return nil, err
+		return nil, vm.Context{}, nil, err
 	}
+	txs := block.Transactions()
 
+	// Recompute transactions up to the target index.
 	signer := types.MakeSigner(api.config, block.Number())
-	// Mutate the state and trace the selected transaction
-	for idx, tx := range block.Transactions() {
+	for idx, tx := range txs {
 		// Assemble the transaction call message
-		msg, err := tx.AsMessage(signer)
-		if err != nil {
-			return nil, fmt.Errorf("sender retrieval failed: %v", err)
-		}
+		msg, _ := tx.AsMessage(signer)
 		context := core.NewEVMContext(msg, block.Header(), api.eth.BlockChain(), nil)
-
-		// Mutate the state if we haven't reached the tracing transaction yet
-		if uint64(idx) < txIndex {
-			vmenv := vm.NewEVM(context, stateDb, api.config, vm.Config{})
-			_, _, err := core.ApplyMessage(vmenv, msg, new(core.GasPool).AddGas(tx.Gas()))
-			if err != nil {
-				return nil, fmt.Errorf("mutation failed: %v", err)
-			}
-			stateDb.DeleteSuicides()
-			continue
+		if idx == txIndex {
+			return msg, context, statedb, nil
 		}
 
-		vmenv := vm.NewEVM(context, stateDb, api.config, vm.Config{Debug: true, Tracer: tracer})
-		ret, gas, err := core.ApplyMessage(vmenv, msg, new(core.GasPool).AddGas(tx.Gas()))
+		vmenv := vm.NewEVM(context, statedb, api.config, vm.Config{})
+		gp := new(core.GasPool).AddGas(tx.Gas())
+		_, _, err := core.ApplyMessage(vmenv, msg, gp)
 		if err != nil {
-			return nil, fmt.Errorf("tracing failed: %v", err)
-		}
-
-		switch tracer := tracer.(type) {
-		case *vm.StructLogger:
-			return &ethapi.ExecutionResult{
-				Gas:         gas,
-				ReturnValue: fmt.Sprintf("%x", ret),
-				StructLogs:  ethapi.FormatLogs(tracer.StructLogs()),
-			}, nil
-		case *ethapi.JavascriptTracer:
-			return tracer.GetResult()
+			return nil, vm.Context{}, nil, fmt.Errorf("tx %x failed: %v", tx.Hash(), err)
 		}
+		statedb.DeleteSuicides()
 	}
-	return nil, errors.New("database inconsistency")
+	return nil, vm.Context{}, nil, fmt.Errorf("tx index %d out of range for block %x", txIndex, blockHash)
 }
 
 // Preimage is a debug API function that returns the preimage for a sha3 hash, if known.
@@ -592,3 +600,48 @@ func (api *PrivateDebugAPI) Preimage(ctx context.Context, hash common.Hash) (hex
 func (api *PrivateDebugAPI) GetBadBlocks(ctx context.Context) ([]core.BadBlockArgs, error) {
 	return api.eth.BlockChain().BadBlocks()
 }
+
+// StorageRangeResult is the result of a debug_storageRangeAt API call.
+type StorageRangeResult struct {
+	Storage storageMap   `json:"storage"`
+	NextKey *common.Hash `json:"nextKey"` // nil if Storage includes the last key in the trie.
+}
+
+type storageMap map[common.Hash]storageEntry
+
+type storageEntry struct {
+	Key   *common.Hash `json:"key"`
+	Value common.Hash  `json:"value"`
+}
+
+// StorageRangeAt returns the storage at the given block height and transaction index.
+func (api *PrivateDebugAPI) StorageRangeAt(ctx context.Context, blockHash common.Hash, txIndex int, contractAddress common.Address, keyStart hexutil.Bytes, maxResult int) (StorageRangeResult, error) {
+	_, _, statedb, err := api.computeTxEnv(blockHash, txIndex)
+	if err != nil {
+		return StorageRangeResult{}, err
+	}
+	st := statedb.StorageTrie(contractAddress)
+	if st == nil {
+		return StorageRangeResult{}, fmt.Errorf("account %x doesn't exist", contractAddress)
+	}
+	return storageRangeAt(st, keyStart, maxResult), nil
+}
+
+func storageRangeAt(st *trie.SecureTrie, start []byte, maxResult int) StorageRangeResult {
+	it := trie.NewIterator(st.NodeIterator(start))
+	result := StorageRangeResult{Storage: storageMap{}}
+	for i := 0; i < maxResult && it.Next(); i++ {
+		e := storageEntry{Value: common.BytesToHash(it.Value)}
+		if preimage := st.GetKey(it.Key); preimage != nil {
+			preimage := common.BytesToHash(preimage)
+			e.Key = &preimage
+		}
+		result.Storage[common.BytesToHash(it.Key)] = e
+	}
+	// Add the 'next key' so clients can continue downloading.
+	if it.Next() {
+		next := common.BytesToHash(it.Key)
+		result.NextKey = &next
+	}
+	return result
+}
diff --git a/eth/api_test.go b/eth/api_test.go
new file mode 100644
index 000000000..f8d2e9c76
--- /dev/null
+++ b/eth/api_test.go
@@ -0,0 +1,88 @@
+// Copyright 2016 The go-ethereum Authors
+// This file is part of the go-ethereum library.
+//
+// The go-ethereum library is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Lesser General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// The go-ethereum library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
+
+package eth
+
+import (
+	"reflect"
+	"testing"
+
+	"github.com/davecgh/go-spew/spew"
+	"github.com/ethereum/go-ethereum/common"
+	"github.com/ethereum/go-ethereum/core/state"
+	"github.com/ethereum/go-ethereum/ethdb"
+)
+
+var dumper = spew.ConfigState{Indent: "    "}
+
+func TestStorageRangeAt(t *testing.T) {
+	// Create a state where account 0x010000... has a few storage entries.
+	var (
+		db, _    = ethdb.NewMemDatabase()
+		state, _ = state.New(common.Hash{}, db)
+		addr     = common.Address{0x01}
+		keys     = []common.Hash{ // hashes of Keys of storage
+			common.HexToHash("340dd630ad21bf010b4e676dbfa9ba9a02175262d1fa356232cfde6cb5b47ef2"),
+			common.HexToHash("426fcb404ab2d5d8e61a3d918108006bbb0a9be65e92235bb10eefbdb6dcd053"),
+			common.HexToHash("48078cfed56339ea54962e72c37c7f588fc4f8e5bc173827ba75cb10a63a96a5"),
+			common.HexToHash("5723d2c3a83af9b735e3b7f21531e5623d183a9095a56604ead41f3582fdfb75"),
+		}
+		storage = storageMap{
+			keys[0]: {Key: &common.Hash{0x02}, Value: common.Hash{0x01}},
+			keys[1]: {Key: &common.Hash{0x04}, Value: common.Hash{0x02}},
+			keys[2]: {Key: &common.Hash{0x01}, Value: common.Hash{0x03}},
+			keys[3]: {Key: &common.Hash{0x03}, Value: common.Hash{0x04}},
+		}
+	)
+	for _, entry := range storage {
+		state.SetState(addr, *entry.Key, entry.Value)
+	}
+
+	// Check a few combinations of limit and start/end.
+	tests := []struct {
+		start []byte
+		limit int
+		want  StorageRangeResult
+	}{
+		{
+			start: []byte{}, limit: 0,
+			want: StorageRangeResult{storageMap{}, &keys[0]},
+		},
+		{
+			start: []byte{}, limit: 100,
+			want: StorageRangeResult{storage, nil},
+		},
+		{
+			start: []byte{}, limit: 2,
+			want: StorageRangeResult{storageMap{keys[0]: storage[keys[0]], keys[1]: storage[keys[1]]}, &keys[2]},
+		},
+		{
+			start: []byte{0x00}, limit: 4,
+			want: StorageRangeResult{storage, nil},
+		},
+		{
+			start: []byte{0x40}, limit: 2,
+			want: StorageRangeResult{storageMap{keys[1]: storage[keys[1]], keys[2]: storage[keys[2]]}, &keys[3]},
+		},
+	}
+	for _, test := range tests {
+		result := storageRangeAt(state.StorageTrie(addr), test.start, test.limit)
+		if !reflect.DeepEqual(result, test.want) {
+			t.Fatalf("wrong result for range 0x%x.., limit %d:\ngot %s\nwant %s",
+				test.start, test.limit, dumper.Sdump(result), dumper.Sdump(&test.want))
+		}
+	}
+}