block.go

package chain

import (
	"context"
	"fmt"
	"math/big"
	"time"

	"github.com/ethereum/go-ethereum"
	"github.com/ethereum/go-ethereum/core/types"
	lru "github.com/hashicorp/golang-lru"
	"github.com/pkg/errors"
	"golang.org/x/sync/errgroup"
)

// HeaderByTime gets the closest block to a given time.
//
// It works by running a binary search against block headers from genesis until now.
// the user can optionally pass in a nullable startBlock *big.Int. If the block is left empty the search is performed from genesis
// the worst case time complexity makes this a cheap operation on any chain, but if done frequently a startBlock should be passed in as a heuristic
//
//nolint:gocognit,cyclop // we ignore complexity warnings here: breaking this up makes it much harder to read.
func (b *baseChain) HeaderByTime(ctx context.Context, startHeight *big.Int, targetTime time.Time) (*types.Header, error) {
	// grab the MeteredEVMClient explicitly to avoid ambiguous references
	client, err := newHeaderCacheClient(b, 4)
	if err != nil {
		return nil, fmt.Errorf("could not create header cache client: %w", err)
	}
	target := uint64(targetTime.Unix())

	// get the start block and end block
	searchRange, err := getSearchRange(ctx, client, startHeight)
	if err != nil {
		return nil, err
	}

	// handle corner cases
	if target <= searchRange.StartTime() {
		return searchRange.startBlock, nil
	}
	if target >= searchRange.EndTime() {
		return searchRange.endBlock, nil
	}

	// run the binary search
	var i, mid, j uint64
	i = searchRange.startBlock.Number.Uint64()
	j = searchRange.endBlock.Number.Uint64()

	for i < j {
		mid = (i + j) / 2

		midBlock, err := client.HeaderByNumber(ctx, big.NewInt(0).SetUint64(mid))
		if err != nil {
			return nil, errors.Wrapf(err, "could not get block %d", mid)
		}

		if midBlock.Time == target {
			return midBlock, nil
		}

		// If target is less than midBlock element
		// then search in left
		//nolint: nestif // we want to keep the logic for the binary search together
		if target < midBlock.Time {
			// If target is greater than previous to mid, return closest of two
			midSubBlock, err := client.HeaderByNumber(ctx, big.NewInt(0).SetUint64(mid-1))
			if err != nil {
				return nil, errors.Wrapf(err, "could not get block %d", mid-1)
			}

			if mid > 0 && target >= midSubBlock.Time {
				return getClosest(midSubBlock, midBlock, target), nil
			}

			j = mid
		} else {
			// If target is greater than mid
			midPlusBlock, err := client.HeaderByNumber(ctx, big.NewInt(0).SetUint64(mid+1))
			if err != nil {
				return nil, errors.Wrapf(err, "could not get block %d", mid+1)
			}

			if mid <= searchRange.Length()-1 && target <= midPlusBlock.Time {
				return getClosest(midBlock, midPlusBlock, target), nil
			}
			i = mid + 1
		}
	}

	// only a single element is left after the search. Fetch the block (from cache) and return it.
	resultingBlock, err := client.HeaderByNumber(ctx, big.NewInt(int64(mid)))
	if err != nil {
		return nil, fmt.Errorf("could not get resultng block")
	}

	return resultingBlock, nil
}

// getClosest gets the closer value to the target of the two blocks
//
// We find the closest by taking the difference between the target and both values
// this method assumes that blockB is greater than blockA and target lies between the two.
func getClosest(lesser *types.Header, greater *types.Header, target uint64) *types.Header {
	if (target - lesser.Time) >= (greater.Time - target) {
		return greater
	}
	return lesser
}

// getSearchRange gets the block range used for performing a binary search.
// an error is returned if either startBlock or endBlock is null. Uses 1 if startBlock is nil.
func getSearchRange(ctx context.Context, client ethereum.ChainReader, startHeight *big.Int) (_ *blockRange, err error) {
	var output blockRange
	if startHeight == nil || startHeight.Cmp(big.NewInt(0)) == 0 {
		startHeight = big.NewInt(1)
	}

	g, ctx := errgroup.WithContext(ctx)
	g.Go(func() error {
		output.startBlock, err = client.HeaderByNumber(ctx, startHeight)
		if err != nil {
			return fmt.Errorf("could not get start block: %w", err)
		}
		return nil
	})

	g.Go(func() error {
		output.endBlock, err = client.HeaderByNumber(ctx, nil)
		if err != nil {
			return fmt.Errorf("could not get start block: %w", err)
		}
		return nil
	})

	err = g.Wait()
	if err != nil {
		return nil, fmt.Errorf("unable to get search range: %w", err)
	}
	return &output, nil
}

// blockRange contains data about a range of block
// accessor methods are exposed for performing a binary search.
type blockRange struct {
	// startBlock of the range. This should not be nil
	startBlock *types.Header

	// endBlock of the range. Will always be greater than start block
	endBlock *types.Header
}

// Length gets the length of the block range as a uint64.
func (b *blockRange) Length() uint64 {
	return big.NewInt(0).Sub(b.endBlock.Number, b.startBlock.Number).Uint64() + 1
}

// StartTime gets the start time of the range as a unix timestamp.
func (b *blockRange) StartTime() uint64 {
	return b.startBlock.Time
}

// EndTime gets the end time of the range as a unix timestamp.
func (b *blockRange) EndTime() uint64 {
	return b.endBlock.Time
}

// headerCacheClient is a client that caches the last count headers
// we use this here so we don't have to store midBlock/handle instances of cached vs uncached blocks differently.
type headerCacheClient struct {
	ethereum.ChainReader
	// headerCache holds the headers
	headerCache *lru.Cache
}

// newHeaderCacheClient creates a client that contains a header cache
// the cache checks if the header exists and if not fetches it. If the cache size
// exceeds maxSize the oldest item is removed.
//
// this cache is intended for use with HeaderByTime to prevent refetching blocks when iterating
// but can be used generally. This will also not handle reorgs since doing so would require a refetch.
func newHeaderCacheClient(ethClient ethereum.ChainReader, count int) (*headerCacheClient, error) {
	cache, err := lru.New(count)
	if err != nil {
		return nil, fmt.Errorf("could not create header cache: %w", err)
	}
	return &headerCacheClient{
		ChainReader: ethClient,
		headerCache: cache,
	}, nil
}

// HeaderByNumber wraps header cache client and introduces caching.
func (c *headerCacheClient) HeaderByNumber(ctx context.Context, number *big.Int) (header *types.Header, err error) {
	// handle latest block query. We cache this by number after the fetch
	if number == nil {
		return c.fetchAndStoreHeader(ctx, number)
	}

	rawHeader, hasKey := c.headerCache.Get(number.Uint64())
	if hasKey {
		var ok bool
		header, ok = rawHeader.(*types.Header)
		// we should always be able to cast here, but if we can't fetch and store the header
		if !ok {
			logger.Warnf("couldn't cast header of type %T to %T. cache may be corrupted", rawHeader, &types.Header{})
			return c.fetchAndStoreHeader(ctx, number)
		}
		return header, nil
	}

	return c.fetchAndStoreHeader(ctx, number)
}

// fetchAndStoreHeader fetches and stores the header bypassing the cache.
func (c *headerCacheClient) fetchAndStoreHeader(ctx context.Context, number *big.Int) (header *types.Header, err error) {
	fetchedBlock, err := c.ChainReader.HeaderByNumber(ctx, number)
	if err != nil {
		return nil, fmt.Errorf("could not fetch latest block: %w", err)
	}
	// add the header to the cache
	c.headerCache.Add(fetchedBlock.Number.Uint64(), fetchedBlock)
	return fetchedBlock, nil
}