eth: add debug_accountRange (#17438)

This adds the debug_accountRange method which returns all accounts in
the state for a given block and transaction index.

2 files changed, 223 insertions, 0 deletions

diff --git a/eth/api.go b/eth/api.go
index 8afa21a38..98c2f5874 100644
--- a/eth/api.go
+++ b/eth/api.go
@@ -334,6 +334,72 @@ func (api *PrivateDebugAPI) GetBadBlocks(ctx context.Context) ([]*BadBlockArgs,
 	return results, nil
 }
 
+// AccountRangeResult returns a mapping from the hash of an account addresses
+// to its preimage. It will return the JSON null if no preimage is found.
+// Since a query can return a limited amount of results, a "next" field is
+// also present for paging.
+type AccountRangeResult struct {
+	Accounts map[common.Hash]*common.Address `json:"accounts"`
+	Next     common.Hash                     `json:"next"`
+}
+
+func accountRange(st state.Trie, start *common.Hash, maxResults int) (AccountRangeResult, error) {
+	if start == nil {
+		start = &common.Hash{0}
+	}
+	it := trie.NewIterator(st.NodeIterator(start.Bytes()))
+	result := AccountRangeResult{Accounts: make(map[common.Hash]*common.Address), Next: common.Hash{}}
+
+	if maxResults > AccountRangeMaxResults {
+		maxResults = AccountRangeMaxResults
+	}
+
+	for i := 0; i < maxResults && it.Next(); i++ {
+		if preimage := st.GetKey(it.Key); preimage != nil {
+			addr := &common.Address{}
+			addr.SetBytes(preimage)
+			result.Accounts[common.BytesToHash(it.Key)] = addr
+		} else {
+			result.Accounts[common.BytesToHash(it.Key)] = nil
+		}
+	}
+
+	if it.Next() {
+		result.Next = common.BytesToHash(it.Key)
+	}
+
+	return result, nil
+}
+
+// AccountRangeMaxResults is the maximum number of results to be returned per call
+const AccountRangeMaxResults = 256
+
+// AccountRange enumerates all accounts in the latest state
+func (api *PrivateDebugAPI) AccountRange(ctx context.Context, start *common.Hash, maxResults int) (AccountRangeResult, error) {
+	var statedb *state.StateDB
+	var err error
+	block := api.eth.blockchain.CurrentBlock()
+
+	if len(block.Transactions()) == 0 {
+		statedb, err = api.computeStateDB(block, defaultTraceReexec)
+		if err != nil {
+			return AccountRangeResult{}, err
+		}
+	} else {
+		_, _, statedb, err = api.computeTxEnv(block.Hash(), len(block.Transactions())-1, 0)
+		if err != nil {
+			return AccountRangeResult{}, err
+		}
+	}
+
+	trie, err := statedb.Database().OpenTrie(block.Header().Root)
+	if err != nil {
+		return AccountRangeResult{}, err
+	}
+
+	return accountRange(trie, start, maxResults)
+}
+
 // StorageRangeResult is the result of a debug_storageRangeAt API call.
 type StorageRangeResult struct {
 	Storage storageMap   `json:"storage"`
diff --git a/eth/api_test.go b/eth/api_test.go
index cdd5bb8e3..1e7c489c3 100644
--- a/eth/api_test.go
+++ b/eth/api_test.go
@@ -17,17 +17,174 @@
 package eth
 
 import (
+	"bytes"
+	"fmt"
+	"math/big"
 	"reflect"
+	"sort"
 	"testing"
 
 	"github.com/davecgh/go-spew/spew"
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/core/rawdb"
 	"github.com/ethereum/go-ethereum/core/state"
+	"github.com/ethereum/go-ethereum/crypto"
 )
 
 var dumper = spew.ConfigState{Indent: "    "}
 
+func accountRangeTest(t *testing.T, trie *state.Trie, statedb *state.StateDB, start *common.Hash, requestedNum int, expectedNum int) AccountRangeResult {
+	result, err := accountRange(*trie, start, requestedNum)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if len(result.Accounts) != expectedNum {
+		t.Fatalf("expected %d results.  Got %d", expectedNum, len(result.Accounts))
+	}
+
+	for _, address := range result.Accounts {
+		if address == nil {
+			t.Fatalf("null address returned")
+		}
+		if !statedb.Exist(*address) {
+			t.Fatalf("account not found in state %s", address.Hex())
+		}
+	}
+
+	return result
+}
+
+type resultHash []*common.Hash
+
+func (h resultHash) Len() int           { return len(h) }
+func (h resultHash) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
+func (h resultHash) Less(i, j int) bool { return bytes.Compare(h[i].Bytes(), h[j].Bytes()) < 0 }
+
+func TestAccountRange(t *testing.T) {
+	var (
+		statedb  = state.NewDatabase(rawdb.NewMemoryDatabase())
+		state, _ = state.New(common.Hash{}, statedb)
+		addrs    = [AccountRangeMaxResults * 2]common.Address{}
+		m        = map[common.Address]bool{}
+	)
+
+	for i := range addrs {
+		hash := common.HexToHash(fmt.Sprintf("%x", i))
+		addr := common.BytesToAddress(crypto.Keccak256Hash(hash.Bytes()).Bytes())
+		addrs[i] = addr
+		state.SetBalance(addrs[i], big.NewInt(1))
+		if _, ok := m[addr]; ok {
+			t.Fatalf("bad")
+		} else {
+			m[addr] = true
+		}
+	}
+
+	state.Commit(true)
+	root := state.IntermediateRoot(true)
+
+	trie, err := statedb.OpenTrie(root)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	t.Logf("test getting number of results less than max")
+	accountRangeTest(t, &trie, state, &common.Hash{0x0}, AccountRangeMaxResults/2, AccountRangeMaxResults/2)
+
+	t.Logf("test getting number of results greater than max %d", AccountRangeMaxResults)
+	accountRangeTest(t, &trie, state, &common.Hash{0x0}, AccountRangeMaxResults*2, AccountRangeMaxResults)
+
+	t.Logf("test with empty 'start' hash")
+	accountRangeTest(t, &trie, state, nil, AccountRangeMaxResults, AccountRangeMaxResults)
+
+	t.Logf("test pagination")
+
+	// test pagination
+	firstResult := accountRangeTest(t, &trie, state, &common.Hash{0x0}, AccountRangeMaxResults, AccountRangeMaxResults)
+
+	t.Logf("test pagination 2")
+	secondResult := accountRangeTest(t, &trie, state, &firstResult.Next, AccountRangeMaxResults, AccountRangeMaxResults)
+
+	hList := make(resultHash, 0)
+	for h1, addr1 := range firstResult.Accounts {
+		h := &common.Hash{}
+		h.SetBytes(h1.Bytes())
+		hList = append(hList, h)
+		for h2, addr2 := range secondResult.Accounts {
+			// Make sure that the hashes aren't the same
+			if bytes.Equal(h1.Bytes(), h2.Bytes()) {
+				t.Fatalf("pagination test failed:  results should not overlap")
+			}
+
+			// If either address is nil, then it makes no sense to compare
+			// them as they might be two different accounts.
+			if addr1 == nil || addr2 == nil {
+				continue
+			}
+
+			// Since the two hashes are different, they should not have
+			// the same preimage, but let's check anyway in case there
+			// is a bug in the (hash, addr) map generation code.
+			if bytes.Equal(addr1.Bytes(), addr2.Bytes()) {
+				t.Fatalf("pagination test failed: addresses should not repeat")
+			}
+		}
+	}
+
+	// Test to see if it's possible to recover from the middle of the previous
+	// set and get an even split between the first and second sets.
+	t.Logf("test random access pagination")
+	sort.Sort(hList)
+	middleH := hList[AccountRangeMaxResults/2]
+	middleResult := accountRangeTest(t, &trie, state, middleH, AccountRangeMaxResults, AccountRangeMaxResults)
+	innone, infirst, insecond := 0, 0, 0
+	for h := range middleResult.Accounts {
+		if _, ok := firstResult.Accounts[h]; ok {
+			infirst++
+		} else if _, ok := secondResult.Accounts[h]; ok {
+			insecond++
+		} else {
+			innone++
+		}
+	}
+	if innone != 0 {
+		t.Fatalf("%d hashes in the 'middle' set were neither in the first not the second set", innone)
+	}
+	if infirst != AccountRangeMaxResults/2 {
+		t.Fatalf("Imbalance in the number of first-test results: %d != %d", infirst, AccountRangeMaxResults/2)
+	}
+	if insecond != AccountRangeMaxResults/2 {
+		t.Fatalf("Imbalance in the number of second-test results: %d != %d", insecond, AccountRangeMaxResults/2)
+	}
+}
+
+func TestEmptyAccountRange(t *testing.T) {
+	var (
+		statedb  = state.NewDatabase(rawdb.NewMemoryDatabase())
+		state, _ = state.New(common.Hash{}, statedb)
+	)
+
+	state.Commit(true)
+	root := state.IntermediateRoot(true)
+
+	trie, err := statedb.OpenTrie(root)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	results, err := accountRange(trie, &common.Hash{0x0}, AccountRangeMaxResults)
+	if err != nil {
+		t.Fatalf("Empty results should not trigger an error: %v", err)
+	}
+	if results.Next != common.HexToHash("0") {
+		t.Fatalf("Empty results should not return a second page")
+	}
+	if len(results.Accounts) != 0 {
+		t.Fatalf("Empty state should not return addresses: %v", results.Accounts)
+	}
+}
+
 func TestStorageRangeAt(t *testing.T) {
 	// Create a state where account 0x010000... has a few storage entries.
 	var (