1// Copyright 2021 The go-ethereum Authors
2// This file is part of the go-ethereum library.
3//
4// The go-ethereum library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU Lesser General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// The go-ethereum library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU Lesser General Public License for more details.
13//
14// You should have received a copy of the GNU Lesser General Public License
15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
16
17package logger
18
19import (
20	"math/big"
21	"time"
22
23	"github.com/ethereum/go-ethereum/common"
24	"github.com/ethereum/go-ethereum/core/types"
25	"github.com/ethereum/go-ethereum/core/vm"
26)
27
28// accessList is an accumulator for the set of accounts and storage slots an EVM
29// contract execution touches.
30type accessList map[common.Address]accessListSlots
31
32// accessListSlots is an accumulator for the set of storage slots within a single
33// contract that an EVM contract execution touches.
34type accessListSlots map[common.Hash]struct{}
35
36// newAccessList creates a new accessList.
37func newAccessList() accessList {
38	return make(map[common.Address]accessListSlots)
39}
40
41// addAddress adds an address to the accesslist.
42func (al accessList) addAddress(address common.Address) {
43	// Set address if not previously present
44	if _, present := al[address]; !present {
45		al[address] = make(map[common.Hash]struct{})
46	}
47}
48
49// addSlot adds a storage slot to the accesslist.
50func (al accessList) addSlot(address common.Address, slot common.Hash) {
51	// Set address if not previously present
52	al.addAddress(address)
53
54	// Set the slot on the surely existent storage set
55	al[address][slot] = struct{}{}
56}
57
58// equal checks if the content of the current access list is the same as the
59// content of the other one.
60func (al accessList) equal(other accessList) bool {
61	// Cross reference the accounts first
62	if len(al) != len(other) {
63		return false
64	}
65	for addr := range al {
66		if _, ok := other[addr]; !ok {
67			return false
68		}
69	}
70	for addr := range other {
71		if _, ok := al[addr]; !ok {
72			return false
73		}
74	}
75	// Accounts match, cross reference the storage slots too
76	for addr, slots := range al {
77		otherslots := other[addr]
78
79		if len(slots) != len(otherslots) {
80			return false
81		}
82		for hash := range slots {
83			if _, ok := otherslots[hash]; !ok {
84				return false
85			}
86		}
87		for hash := range otherslots {
88			if _, ok := slots[hash]; !ok {
89				return false
90			}
91		}
92	}
93	return true
94}
95
96// accesslist converts the accesslist to a types.AccessList.
97func (al accessList) accessList() types.AccessList {
98	acl := make(types.AccessList, 0, len(al))
99	for addr, slots := range al {
100		tuple := types.AccessTuple{Address: addr, StorageKeys: []common.Hash{}}
101		for slot := range slots {
102			tuple.StorageKeys = append(tuple.StorageKeys, slot)
103		}
104		acl = append(acl, tuple)
105	}
106	return acl
107}
108
109// AccessListTracer is a tracer that accumulates touched accounts and storage
110// slots into an internal set.
111type AccessListTracer struct {
112	excl map[common.Address]struct{} // Set of account to exclude from the list
113	list accessList                  // Set of accounts and storage slots touched
114}
115
116// NewAccessListTracer creates a new tracer that can generate AccessLists.
117// An optional AccessList can be specified to occupy slots and addresses in
118// the resulting accesslist.
119func NewAccessListTracer(acl types.AccessList, from, to common.Address, precompiles []common.Address) *AccessListTracer {
120	excl := map[common.Address]struct{}{
121		from: {}, to: {},
122	}
123	for _, addr := range precompiles {
124		excl[addr] = struct{}{}
125	}
126	list := newAccessList()
127	for _, al := range acl {
128		if _, ok := excl[al.Address]; !ok {
129			list.addAddress(al.Address)
130		}
131		for _, slot := range al.StorageKeys {
132			list.addSlot(al.Address, slot)
133		}
134	}
135	return &AccessListTracer{
136		excl: excl,
137		list: list,
138	}
139}
140
141func (a *AccessListTracer) CaptureStart(env *vm.EVM, from common.Address, to common.Address, create bool, input []byte, gas uint64, value *big.Int) {
142}
143
144// CaptureState captures all opcodes that touch storage or addresses and adds them to the accesslist.
145func (a *AccessListTracer) CaptureState(pc uint64, op vm.OpCode, gas, cost uint64, scope *vm.ScopeContext, rData []byte, depth int, err error) {
146	stack := scope.Stack
147	stackData := stack.Data()
148	stackLen := len(stackData)
149	if (op == vm.SLOAD || op == vm.SSTORE) && stackLen >= 1 {
150		slot := common.Hash(stackData[stackLen-1].Bytes32())
151		a.list.addSlot(scope.Contract.Address(), slot)
152	}
153	if (op == vm.EXTCODECOPY || op == vm.EXTCODEHASH || op == vm.EXTCODESIZE || op == vm.BALANCE || op == vm.SELFDESTRUCT) && stackLen >= 1 {
154		addr := common.Address(stackData[stackLen-1].Bytes20())
155		if _, ok := a.excl[addr]; !ok {
156			a.list.addAddress(addr)
157		}
158	}
159	if (op == vm.DELEGATECALL || op == vm.CALL || op == vm.STATICCALL || op == vm.CALLCODE) && stackLen >= 5 {
160		addr := common.Address(stackData[stackLen-2].Bytes20())
161		if _, ok := a.excl[addr]; !ok {
162			a.list.addAddress(addr)
163		}
164	}
165}
166
167func (*AccessListTracer) CaptureFault(pc uint64, op vm.OpCode, gas, cost uint64, scope *vm.ScopeContext, depth int, err error) {
168}
169
170func (*AccessListTracer) CaptureEnd(output []byte, gasUsed uint64, t time.Duration, err error) {}
171
172func (*AccessListTracer) CaptureEnter(typ vm.OpCode, from common.Address, to common.Address, input []byte, gas uint64, value *big.Int) {
173}
174
175func (*AccessListTracer) CaptureExit(output []byte, gasUsed uint64, err error) {}
176
177// AccessList returns the current accesslist maintained by the tracer.
178func (a *AccessListTracer) AccessList() types.AccessList {
179	return a.list.accessList()
180}
181
182// Equal returns if the content of two access list traces are equal.
183func (a *AccessListTracer) Equal(other *AccessListTracer) bool {
184	return a.list.equal(other.list)
185}
186