// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;

/// @title RingBufferStorage
/// @author The Warp Team <contact@warp.inc>
/// @notice This contract manages a eip1967 stored ring buffer of messages.
/// @dev This contract is intended to be inherited by the Outbox. It stores
///      messages in a ring buffer, and allows for reading messages from the
///      buffer until it is overwritten. Messages may also be proven in state
///      while they are in the ring buffer via `eth_getProof`. This contract
///      functions as a simple accumulator in the EVM merkle-patricia trie. By
///      re-using state slots, we can reduce gas costs for sending messages.
abstract contract RingBufferStorage {
    /// @notice Size of the ring buffer, in messages. Gas savings kick in once
    ///         the ring buffer is full.
    /// @dev This value is set at construction time and cannot be changed.
    uint64 public immutable RING_BUFFER_SIZE;

    /// @notice Stores the next index within the message vector.
    /// @dev The index is a count of all past messages. It is also the value
    ///      used to calculate the storage slot when storing a message in the
    ///      ring buffer.
    /// @dev 0x9c4ac79203be492bdf9cdcb9cf6c26723bb061bc7c89edaf285249fd105e6fa0
    bytes32 public constant INDEX_SLOT = bytes32(uint256(keccak256("eip1967.proxy.accumulate.index")) - 1);

    /// @notice The slot at which the first element of the ring buffer is
    ///         stored.
    /// @dev This is the first slot in the ring buffer. It stores the message
    ///      at index 0, later to be overwritten by the message at index
    ///      RING_BUFFER_SIZE.
    /// @dev Individual message slots are computed as follows:
    ///      MESSAGES_SLOT + (INDEX % RING_BUFFER_SIZE)
    /// @dev 0x0f6ff53b226acb501abb7521a3041f9642de1094e1d74e547a4dbd4bbe9693d3
    bytes32 public constant MESSAGES_SLOT = bytes32(uint256(keccak256("eip1967.proxy.accumulate.messages")) - 1);

    /// @notice Thrown when attempting to instantiate RING_BUFFER_SIZE to zero.
    ///         (This would make messageAt(0) unusable due to arithmetic underflow).
    /// @dev selector 0xc345df04.
    error ZeroRingBufferSize();

    /// @notice Thrown when attempting to read a message that is not in the
    ///         ring buffer.
    /// @param minRead - The smallest index still present in the ring buffer.
    /// @param maxRead - The largest index present in the ring buffer.
    /// @dev selector 0xc5a6beed.
    error OutOfBoundsRead(uint256 minRead, uint256 maxRead);

    /// @notice Construct a new RingBufferStorage contract.
    /// @dev Sets the ring buffer size.
    /// @param _ringBufferSize - The size of the ring buffer, in messages.
    constructor(uint64 _ringBufferSize) {
        if (_ringBufferSize == 0) revert ZeroRingBufferSize();
        RING_BUFFER_SIZE = _ringBufferSize;
    }

    /// @notice Get the number of messages in the vector.
    /// @dev This is an alias for nextIndex(). It allows clearer code when
    ///      reading from the contract.
    /// @return _count The number of messages in the vector.
    function count() public view returns (uint256 _count) {
        return nextIndex();
    }

    /// @notice Get the next message index.
    /// @return _index The next message index.
    function nextIndex() public view returns (uint64 _index) {
        uint256 slot = uint256(INDEX_SLOT);
        assembly ("memory-safe") {
            _index := sload(slot)
        }
    }

    /// @notice Get the message hash at the given index, if still present in
    ///         the ring buffer. Reverts if the message is no longer present.
    /// @dev Reads are checked, and the readable range is included in the
    ///      revert data. This is intended for off-chain access. It aids clients
    ///      in determining whether a given state contains the message they are
    ///      looking for.
    /// @custom:reverts OutOfBoundsRead(minRead, maxRead) if the message hash
    ///                 is no longer stored in the ring buffer.
    /// @param _index The index of the message in the history of all messages.
    /// @return h The message hash.
    function messageAt(uint64 _index) public view returns (bytes32 h) {
        uint256 _count = count();
        if (_count == 0) revert OutOfBoundsRead(0, 0);

        uint256 maxRead = _count - 1;
        uint256 minRead = maxRead >= RING_BUFFER_SIZE ? maxRead - (RING_BUFFER_SIZE - 1) : 0;

        if (_index < minRead || _index > maxRead) {
            revert OutOfBoundsRead(minRead, maxRead);
        }

        uint256 slot = messageSlot(_index);
        assembly ("memory-safe") {
            h := sload(slot)
        }
    }

    /// @notice Get the next message index, then increment it
    /// @dev This function is used when storing a message in the ring buffer to
    ///      reserve the spot.
    /// @return _index The next message index.
    function incrIndex() internal returns (uint64 _index) {
        _index = nextIndex();
        uint256 slot = uint256(INDEX_SLOT);
        assembly ("memory-safe") {
            sstore(slot, add(_index, 1))
        }
    }

    /// @notice Append a message hash to the vector.
    /// @dev The vector is backed by a ring buffer, so new messages overwrite
    ///      old ones in a FIFO fashion. The returned index is the index of the
    ///      message in the history of all messages sent from this Outbox. The
    ///      slot at which it is stored is calculated using messageSlot(_index).
    /// @param h The message hash to append.
    /// @return _index The index of the message in the history of all messages
    function pushMessage(bytes32 h) internal returns (uint64 _index) {
        _index = incrIndex();
        uint256 slot = messageSlot(_index);
        assembly ("memory-safe") {
            sstore(slot, h)
        }
    }

    /// @notice Get the slot storing the message hash at the given index.
    /// @dev This is calculated from the index and the ring buffer size.
    /// @dev This is intended for off-chain use. When proving a specific
    ///      message in the state trie, the output of this function can be
    ///      passed to eth_getProof directly as a storage key.
    /// @param _index The index of the message in the history of all messages
    ///        sent from this Outbox.
    /// @return slotNum The slot number of the message hash.
    function messageSlot(uint64 _index) internal view returns (uint256 slotNum) {
        slotNum = uint256(MESSAGES_SLOT) + (_index % RING_BUFFER_SIZE);
    }
}