Contract Address Details

// SPDX-License-Identifier: MIT
pragma solidity 0.8.17;

import "../access/HashRegistry.sol";
import "../utils/ExtendedSelfMulticall.sol";
import "./interfaces/IApi3Market.sol";
import "./AirseekerRegistry.sol";
import "../vendor/@openzeppelin/contracts@4.9.5/utils/math/SafeCast.sol";
import "../vendor/@openzeppelin/contracts@4.9.5/utils/cryptography/MerkleProof.sol";
import "./interfaces/IApi3ServerV1.sol";
import "./proxies/interfaces/IProxyFactory.sol";

/// @title The contract that API3 users interact with using the API3 Market
/// frontend to purchase data feed subscriptions
/// @notice API3 aims to streamline and protocolize its integration processes
/// through the API3 Market (https://market.api3.org), which is a data feed
/// subscription marketplace. The Api3Market contract is the on-chain portion
/// of this system.
/// Api3Market enables API3 to predetermine the decisions related to its data
/// feed services (such as the curation of data feed sources or subscription
/// prices) and publish them on-chain. This streamlines the intergation flow,
/// as it allows the users to initiate subscriptions immediately, without
/// requiring any two-way communication with API3. Furthermore, this removes
/// the need for API3 to have agents operating in the meatspace gathering order
/// details, quoting prices and reviewing payments, and allows all such
/// operations to be cryptographically secured with a multi-party scheme in an
/// end-to-end manner.
/// @dev The user is strongly recommended to use the API3 Market frontend while
/// interacting with this contract, mostly because doing so successfully
/// requires some amount of knowledge of other API3 contracts. Specifically,
/// Api3Market requires the data feed for which the subscription is being
/// purchased to be "readied", the correct Merkle proofs to be provided, and
/// enough payment to be made. The API3 Market frontend will fetch the
/// appropriate Merkle proofs, create a multicall transaction that will ready
/// the data feed before making the call to buy the subscription, and compute
/// the amount to be sent that will barely allow the subscription to be
/// purchased. For most users, building such a transaction themselves would be
/// impractical.
contract Api3Market is HashRegistry, ExtendedSelfMulticall, IApi3Market {
    enum UpdateParametersComparisonResult {
        EqualToQueued,
        BetterThanQueued,
        WorseThanQueued
    }

    // The update parameters for each subscription is kept in a hash map rather
    // than in full form as an optimization. Refer to AirseekerRegistry for a
    // similar scheme.
    // The subscription queues are kept as linked lists, for which each
    // subscription has a next subscription ID field.
    struct Subscription {
        bytes32 updateParametersHash;
        uint32 endTimestamp;
        uint224 dailyPrice;
        bytes32 nextSubscriptionId;
    }

    /// @notice dAPI management Merkle root hash type
    /// @dev "Hash type" is what HashRegistry uses to address hashes used for
    /// different purposes
    bytes32 public constant override DAPI_MANAGEMENT_MERKLE_ROOT_HASH_TYPE =
        keccak256(abi.encodePacked("dAPI management Merkle root"));

    /// @notice dAPI pricing Merkle root hash type
    bytes32 public constant override DAPI_PRICING_MERKLE_ROOT_HASH_TYPE =
        keccak256(abi.encodePacked("dAPI pricing Merkle root"));

    /// @notice Signed API URL Merkle root hash type
    bytes32 public constant override SIGNED_API_URL_MERKLE_ROOT_HASH_TYPE =
        keccak256(abi.encodePacked("Signed API URL Merkle root"));

    /// @notice Maximum dAPI update age. This contract cannot be used to set a
    /// dAPI name to a data feed that has not been updated in the last
    /// `MAXIMUM_DAPI_UPDATE_AGE`.
    uint256 public constant override MAXIMUM_DAPI_UPDATE_AGE = 1 days;

    /// @notice Api3ServerV1 contract address
    address public immutable override api3ServerV1;

    /// @notice ProxyFactory contract address
    address public immutable override proxyFactory;

    /// @notice AirseekerRegistry contract address
    address public immutable override airseekerRegistry;

    /// @notice Maximum subscription queue length for a dAPI
    /// @dev Some functionality in this contract requires to iterate through
    /// the entire subscription queue for a dAPI, and the queue length is
    /// limited to prevent this process from being bloated. Considering that
    /// each item in the subscription queue has unique update parameters, the
    /// length of the subscription queue is also limited by the number of
    /// unique update parameters offered in the dAPI pricing Merkle tree. For
    /// reference, at the time this contract is implemented, the API3 Market
    /// offers 4 update parameter options.
    uint256 public immutable override maximumSubscriptionQueueLength;

    /// @notice Subscriptions indexed by their IDs
    mapping(bytes32 => Subscription) public override subscriptions;

    /// @notice dAPI name to current subscription ID, which denotes the start
    /// of the subscription queue for the dAPI
    mapping(bytes32 => bytes32) public override dapiNameToCurrentSubscriptionId;

    // Update parameters hash map
    mapping(bytes32 => bytes) private updateParametersHashToValue;

    // Length of abi.encode(address, bytes32)
    uint256 private constant DATA_FEED_DETAILS_LENGTH_FOR_SINGLE_BEACON =
        32 + 32;

    // Length of abi.encode(uint256, int224, uint256)
    uint256 private constant UPDATE_PARAMETERS_LENGTH = 32 + 32 + 32;

    bytes32 private constant API3MARKET_SIGNATURE_DELEGATION_HASH_TYPE =
        keccak256(abi.encodePacked("Api3Market signature delegation"));

    /// @dev Api3Market deploys its own AirseekerRegistry deterministically.
    /// This implies that Api3Market-specific Airseekers should be operated by
    /// pointing at this contract.
    /// The maximum subscription queue length should be large enough to not
    /// obstruct subscription purchases under usual conditions, and small
    /// enough to keep the queue at an iterable size. For example, if the
    /// number of unique update parameters in the dAPI pricing Merkle trees
    /// that are being used is around 5, a maximum subscription queue length of
    /// 10 would be acceptable for a typical chain.
    /// @param owner_ Owner address
    /// @param proxyFactory_ ProxyFactory contract address
    /// @param maximumSubscriptionQueueLength_ Maximum subscription queue
    /// length
    constructor(
        address owner_,
        address proxyFactory_,
        uint256 maximumSubscriptionQueueLength_
    ) HashRegistry(owner_) {
        require(
            maximumSubscriptionQueueLength_ != 0,
            "Maximum queue length zero"
        );
        proxyFactory = proxyFactory_;
        address api3ServerV1_ = IProxyFactory(proxyFactory_).api3ServerV1();
        api3ServerV1 = api3ServerV1_;
        airseekerRegistry = address(
            new AirseekerRegistry{salt: bytes32(0)}(
                address(this),
                api3ServerV1_
            )
        );
        maximumSubscriptionQueueLength = maximumSubscriptionQueueLength_;
    }

    /// @notice Returns the owner address
    /// @return Owner address
    function owner()
        public
        view
        override(HashRegistry, IOwnable)
        returns (address)
    {
        return super.owner();
    }

    /// @notice Overriden to be disabled
    function renounceOwnership() public pure override(HashRegistry, IOwnable) {
        revert("Ownership cannot be renounced");
    }

    /// @notice Overriden to be disabled
    function transferOwnership(
        address
    ) public pure override(HashRegistry, IOwnable) {
        revert("Ownership cannot be transferred");
    }

    /// @notice Buys subscription and updates the current subscription ID if
    /// necessary. The user is recommended to interact with this contract over
    /// the API3 Market frontend due to its complexity.
    /// @dev The data feed that the dAPI name will be set to after this
    /// function is called must be readied (see `validateDataFeedReadiness()`)
    /// before calling this function.
    /// Enough funds must be sent to put the sponsor wallet balance over its
    /// expected amount after the subscription is bought. Since sponsor wallets
    /// send data feed update transactions, it is not possible to determine
    /// what their balance will be at the time sent transactions are confirmed.
    /// To avoid transactions being reverted as a result of this, consider
    /// sending some extra.
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    /// @param dapiManagementAndDapiPricingMerkleData ABI-encoded dAPI
    /// management and dAPI pricing Merkle roots and proofs
    /// @return subscriptionId Subscription ID
    function buySubscription(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    ) public payable override returns (bytes32 subscriptionId) {
        require(dataFeedId != bytes32(0), "Data feed ID zero");
        require(sponsorWallet != address(0), "Sponsor wallet address zero");
        verifyDapiManagementAndDapiPricingMerkleProofs(
            dapiName,
            dataFeedId,
            sponsorWallet,
            updateParameters,
            duration,
            price,
            dapiManagementAndDapiPricingMerkleData
        );
        subscriptionId = addSubscriptionToQueue(
            dapiName,
            dataFeedId,
            updateParameters,
            duration,
            price
        );
        require(
            sponsorWallet.balance + msg.value >=
                computeExpectedSponsorWalletBalance(dapiName),
            "Insufficient payment"
        );
        emit BoughtSubscription(
            dapiName,
            subscriptionId,
            dataFeedId,
            sponsorWallet,
            updateParameters,
            duration,
            price,
            msg.value
        );
        if (msg.value > 0) {
            (bool success, ) = sponsorWallet.call{value: msg.value}("");
            require(success, "Transfer unsuccessful");
        }
    }

    /// @notice Called by the owner to cancel all subscriptions for a dAPI
    /// that needs to be decommissioned urgently
    /// @dev The root of a new dAPI pricing Merkle tree that excludes the dAPI
    /// should be registered before canceling the subscriptions. Otherwise,
    /// anyone can immediately buy the subscriptions again.
    /// @param dapiName dAPI name
    function cancelSubscriptions(bytes32 dapiName) external override onlyOwner {
        require(
            dapiNameToCurrentSubscriptionId[dapiName] != bytes32(0),
            "Subscription queue empty"
        );
        dapiNameToCurrentSubscriptionId[dapiName] = bytes32(0);
        AirseekerRegistry(airseekerRegistry).setDapiNameToBeDeactivated(
            dapiName
        );
        emit CanceledSubscriptions(dapiName);
    }

    /// @notice If the current subscription has ended, updates it with the one
    /// that will end next
    /// @dev The fact that there is a current subscription that has ended would
    /// mean that API3 is providing a service that was not paid for. Therefore,
    /// API3 should poll this function for all active dAPI names and call it
    /// whenever it is not going to revert to downgrade the specs.
    /// @param dapiName dAPI name
    function updateCurrentSubscriptionId(bytes32 dapiName) public override {
        bytes32 currentSubscriptionId = dapiNameToCurrentSubscriptionId[
            dapiName
        ];
        require(
            currentSubscriptionId != bytes32(0),
            "Subscription queue empty"
        );
        require(
            subscriptions[currentSubscriptionId].endTimestamp <=
                block.timestamp,
            "Current subscription not ended"
        );
        updateEndedCurrentSubscriptionId(dapiName, currentSubscriptionId);
    }

    /// @notice Updates the dAPI name to match the respective Merkle leaf
    /// @dev Buying a dAPI subscription always updates the dAPI name if
    /// necessary. However, API3 may also publish new Merkle roots between
    /// subscription purchases, in which case API3 should call this function to
    /// bring the chain state up to date. Therefore, API3 should poll this
    /// function for all active dAPI names and call it whenever it will not
    /// revert.
    /// Similar to `buySubscription()`, this function requires the data feed
    /// that the dAPI will be pointed to to be readied.
    /// This function is allowed to be called even when the respective dAPI is
    /// not active, which means that a dAPI name being set does not imply that
    /// the respective data feed is in service. Users should only use dAPIs for
    /// which there is an active subscription with update parameters that
    /// satisfy their needs.
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param dapiManagementMerkleData ABI-encoded dAPI management Merkle root
    /// and proof
    function updateDapiName(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes calldata dapiManagementMerkleData
    ) external override {
        if (dataFeedId != bytes32(0)) {
            require(sponsorWallet != address(0), "Sponsor wallet address zero");
        } else {
            require(
                sponsorWallet == address(0),
                "Sponsor wallet address not zero"
            );
        }
        verifyDapiManagementMerkleProof(
            dapiName,
            dataFeedId,
            sponsorWallet,
            dapiManagementMerkleData
        );
        bytes32 currentDataFeedId = IApi3ServerV1(api3ServerV1)
            .dapiNameHashToDataFeedId(keccak256(abi.encodePacked(dapiName)));
        require(currentDataFeedId != dataFeedId, "Does not update dAPI name");
        if (dataFeedId != bytes32(0)) {
            validateDataFeedReadiness(dataFeedId);
        }
        IApi3ServerV1(api3ServerV1).setDapiName(dapiName, dataFeedId);
    }

    /// @notice Updates the signed API URL of the Airnode to match the
    /// respective Merkle leaf
    /// @dev Unlike the dAPI management and pricing Merkle leaves, the signed
    /// API URL Merkle leaves are not registered by the users as a part of
    /// subscription purchase transactions. API3 should poll this function for
    /// all Airnodes that are used in active dAPIs and call it whenever it will
    /// not revert.
    /// @param airnode Airnode address
    /// @param signedApiUrl Signed API URL
    /// @param signedApiUrlMerkleData ABI-encoded signed API URL Merkle root
    /// and proof
    function updateSignedApiUrl(
        address airnode,
        string calldata signedApiUrl,
        bytes calldata signedApiUrlMerkleData
    ) external override {
        verifySignedApiUrlMerkleProof(
            airnode,
            signedApiUrl,
            signedApiUrlMerkleData
        );
        require(
            keccak256(abi.encodePacked(signedApiUrl)) !=
                keccak256(
                    abi.encodePacked(
                        AirseekerRegistry(airseekerRegistry)
                            .airnodeToSignedApiUrl(airnode)
                    )
                ),
            "Does not update signed API URL"
        );
        AirseekerRegistry(airseekerRegistry).setSignedApiUrl(
            airnode,
            signedApiUrl
        );
    }

    /// @notice Multi-calls this contract, followed by a call with value to buy
    /// the subscription
    /// @dev This function is for the API3 Market frontend to call
    /// `eth_estimateGas` on a single transaction that readies a data feed and
    /// buys the respective subscription
    /// @param multicallData Array of calldata of batched calls
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    /// @param dapiManagementAndDapiPricingMerkleData ABI-encoded dAPI
    /// management and dAPI pricing Merkle roots and proofs
    /// @return returndata Array of returndata of batched calls
    /// @return subscriptionId Subscription ID
    function multicallAndBuySubscription(
        bytes[] calldata multicallData,
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    )
        external
        payable
        override
        returns (bytes[] memory returndata, bytes32 subscriptionId)
    {
        returndata = this.multicall(multicallData);
        subscriptionId = buySubscription(
            dapiName,
            dataFeedId,
            sponsorWallet,
            updateParameters,
            duration,
            price,
            dapiManagementAndDapiPricingMerkleData
        );
    }

    /// @notice Multi-calls this contract in a way that the transaction does
    /// not revert if any of the batched calls reverts, followed by a call with
    /// value to buy the subscription
    /// @dev This function is for the API3 Market frontend to send a single
    /// transaction that readies a data feed and buys the respective
    /// subscription. `tryMulticall()` is preferred in the purchase transaction
    /// because the readying calls may revert due to race conditions.
    /// @param tryMulticallData Array of calldata of batched calls
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    /// @param dapiManagementAndDapiPricingMerkleData ABI-encoded dAPI
    /// management and dAPI pricing Merkle roots and proofs
    /// @return successes Array of success conditions of batched calls
    /// @return returndata Array of returndata of batched calls
    /// @return subscriptionId Subscription ID
    function tryMulticallAndBuySubscription(
        bytes[] calldata tryMulticallData,
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    )
        external
        payable
        override
        returns (
            bool[] memory successes,
            bytes[] memory returndata,
            bytes32 subscriptionId
        )
    {
        (successes, returndata) = this.tryMulticall(tryMulticallData);
        subscriptionId = buySubscription(
            dapiName,
            dataFeedId,
            sponsorWallet,
            updateParameters,
            duration,
            price,
            dapiManagementAndDapiPricingMerkleData
        );
    }

    /// @notice Calls Api3ServerV1 to update the Beacon using data signed by
    /// the Airnode
    /// @dev The user is intended to make a multicall transaction through the
    /// API3 Market frontend to satisfy the required conditions to be able to
    /// buy a subscription and buy the subscription in a single transaction.
    /// The functions to which external calls must be made to to satisfy said
    /// conditions (such as this one) are added to this contract so that they
    /// can be multi-called by the user.
    /// @param airnode Airnode address
    /// @param templateId Template ID
    /// @param timestamp Signature timestamp
    /// @param data Update data (an `int256` encoded in contract ABI)
    /// @param signature Template ID, timestamp and the update data signed by
    /// the Airnode
    /// @return beaconId Updated Beacon ID
    function updateBeaconWithSignedData(
        address airnode,
        bytes32 templateId,
        uint256 timestamp,
        bytes calldata data,
        bytes calldata signature
    ) external override returns (bytes32 beaconId) {
        return
            IApi3ServerV1(api3ServerV1).updateBeaconWithSignedData(
                airnode,
                templateId,
                timestamp,
                data,
                signature
            );
    }

    /// @notice Calls Api3ServerV1 to update the Beacon set using the current
    /// values of its Beacons
    /// @param beaconIds Beacon IDs
    /// @return beaconSetId Updated Beacon set ID
    function updateBeaconSetWithBeacons(
        bytes32[] calldata beaconIds
    ) external override returns (bytes32 beaconSetId) {
        return
            IApi3ServerV1(api3ServerV1).updateBeaconSetWithBeacons(beaconIds);
    }

    /// @notice Calls ProxyFactory to deterministically deploy the dAPI proxy
    /// @dev It is recommended for the users to read data feeds through proxies
    /// deployed by ProxyFactory, rather than calling Api3ServerV1 directly.
    /// Even though proxy deployment is not a condition for purchasing
    /// subscriptions, the interface is implemented here to allow the user to
    /// purchase a dAPI subscription and deploy the respective proxy in the
    /// same transaction with a multicall.
    /// @param dapiName dAPI name
    /// @param metadata Metadata associated with the proxy
    /// @return proxyAddress Proxy address
    function deployDapiProxy(
        bytes32 dapiName,
        bytes calldata metadata
    ) external override returns (address proxyAddress) {
        proxyAddress = IProxyFactory(proxyFactory).deployDapiProxy(
            dapiName,
            metadata
        );
    }

    /// @notice Calls ProxyFactory to deterministically deploy the dAPI proxy
    /// with OEV support
    /// @param dapiName dAPI name
    /// @param oevBeneficiary OEV beneficiary
    /// @param metadata Metadata associated with the proxy
    /// @return proxyAddress Proxy address
    function deployDapiProxyWithOev(
        bytes32 dapiName,
        address oevBeneficiary,
        bytes calldata metadata
    ) external override returns (address proxyAddress) {
        proxyAddress = IProxyFactory(proxyFactory).deployDapiProxyWithOev(
            dapiName,
            oevBeneficiary,
            metadata
        );
    }

    /// @notice Calls AirseekerRegistry to register the data feed
    /// @param dataFeedDetails Data feed details
    /// @return dataFeedId Data feed ID
    function registerDataFeed(
        bytes calldata dataFeedDetails
    ) external override returns (bytes32 dataFeedId) {
        dataFeedId = AirseekerRegistry(airseekerRegistry).registerDataFeed(
            dataFeedDetails
        );
    }

    /// @notice Computes the expected sponsor wallet balance based on the
    /// current subscription queue
    /// @dev API3 estimates the transaction fee cost of subscriptions, and
    /// prices them accordingly. The subscription fees paid for a dAPI are sent
    /// to the respective sponsor wallet, which will send the update
    /// transactions. In the case that a subscription is overpriced, the extra
    /// funds are automatically rolled over as a discount to the next
    /// subscription bought for the same dAPI. In the case that a subscription
    /// is underpriced, there is a risk of the sponsor wallet running out of
    /// funds, resulting in the subscription specs to not be met. To avoid
    /// this, API3 should poll this function for all active dAPI names, check
    /// the respective sponsor wallet balances, and top up the sponsor wallets
    /// as necessary. The conditions that result in the underpricing will most
    /// likely require an updated dAPI pricing Merkle root to be published.
    /// @param dapiName dAPI name
    /// @return expectedSponsorWalletBalance Expected sponsor wallet balance
    function computeExpectedSponsorWalletBalance(
        bytes32 dapiName
    ) public view override returns (uint256 expectedSponsorWalletBalance) {
        uint32 startTimestamp = SafeCast.toUint32(block.timestamp);
        Subscription storage queuedSubscription;
        for (
            bytes32 queuedSubscriptionId = dapiNameToCurrentSubscriptionId[
                dapiName
            ];
            queuedSubscriptionId != bytes32(0);
            queuedSubscriptionId = queuedSubscription.nextSubscriptionId
        ) {
            queuedSubscription = subscriptions[queuedSubscriptionId];
            uint32 endTimestamp = queuedSubscription.endTimestamp;
            if (endTimestamp > block.timestamp) {
                expectedSponsorWalletBalance +=
                    ((endTimestamp - startTimestamp) *
                        queuedSubscription.dailyPrice) /
                    1 days;
                startTimestamp = endTimestamp;
            }
        }
    }

    /// @notice Computes the expected sponsor wallet balance after the
    /// respective subscription is added to the queue
    /// @dev This function is intended to be used by the API3 Market frontend
    /// to calculate how much the user should pay to purchase a specific
    /// subscription. As mentioned in the `buySubscription()` docstring, the
    /// user should aim for the sponsor wallet balance to be slightly more than
    /// the required amount in case it sends a transaction in the meantime,
    /// whose gas cost may decrease the sponsor wallet balance unexpectedly.
    /// Unit prices of the queued subscriptions are recorded on a daily basis
    /// and the expected balance is computed from these, which introduces a
    /// rounding error in the order of Weis. This also applies in practice (in
    /// that one can buy a subscription whose price is 1 ETH at 0.999... ETH).
    /// This behavior is accepted due to its effect being negligible.
    /// @param dapiName dAPI name
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    /// @return expectedSponsorWalletBalance Expected sponsor wallet balance
    function computeExpectedSponsorWalletBalanceAfterSubscriptionIsAdded(
        bytes32 dapiName,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price
    ) external view override returns (uint256 expectedSponsorWalletBalance) {
        require(
            updateParameters.length == UPDATE_PARAMETERS_LENGTH,
            "Update parameters length invalid"
        );
        (
            bytes32 subscriptionId,
            uint32 endTimestamp,
            bytes32 previousSubscriptionId,
            bytes32 nextSubscriptionId
        ) = prospectSubscriptionPositionInQueue(
                dapiName,
                updateParameters,
                duration
            );
        uint256 dailyPrice = (price * 1 days) / duration;
        uint32 startTimestamp = SafeCast.toUint32(block.timestamp);
        bytes32 queuedSubscriptionId = previousSubscriptionId == bytes32(0)
            ? subscriptionId
            : dapiNameToCurrentSubscriptionId[dapiName];
        for (; queuedSubscriptionId != bytes32(0); ) {
            if (queuedSubscriptionId == subscriptionId) {
                expectedSponsorWalletBalance +=
                    ((endTimestamp - startTimestamp) * dailyPrice) /
                    1 days;
                startTimestamp = endTimestamp;
                queuedSubscriptionId = nextSubscriptionId;
            } else {
                Subscription storage queuedSubscription = subscriptions[
                    queuedSubscriptionId
                ];
                uint32 queuedSubscriptionEndTimestamp = queuedSubscription
                    .endTimestamp;
                if (queuedSubscriptionEndTimestamp > block.timestamp) {
                    expectedSponsorWalletBalance +=
                        ((queuedSubscriptionEndTimestamp - startTimestamp) *
                            queuedSubscription.dailyPrice) /
                        1 days;
                    startTimestamp = queuedSubscriptionEndTimestamp;
                }
                if (previousSubscriptionId == queuedSubscriptionId) {
                    queuedSubscriptionId = subscriptionId;
                } else {
                    queuedSubscriptionId = queuedSubscription
                        .nextSubscriptionId;
                }
            }
        }
    }

    /// @notice Gets all data about the dAPI that is available
    /// @dev This function is intended to be used by the API3 Market frontend
    /// to get all data related to a specific dAPI. It returns the entire
    /// subscription queue, including the items whose end timestamps are in the
    /// past.
    /// @param dapiName dAPI name
    /// @return dataFeedDetails Data feed details
    /// @return dapiValue dAPI value read from Api3ServerV1
    /// @return dapiTimestamp dAPI timestamp read from Api3ServerV1
    /// @return beaconValues Beacon values read from Api3ServerV1
    /// @return beaconTimestamps Beacon timestamps read from Api3ServerV1
    /// @return updateParameters Update parameters of the subscriptions in the
    /// queue
    /// @return endTimestamps End timestamps of the subscriptions in the queue
    /// @return dailyPrices Daily prices of the subscriptions in the queue
    function getDapiData(
        bytes32 dapiName
    )
        external
        view
        override
        returns (
            bytes memory dataFeedDetails,
            int224 dapiValue,
            uint32 dapiTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps,
            bytes[] memory updateParameters,
            uint32[] memory endTimestamps,
            uint224[] memory dailyPrices
        )
    {
        bytes32 currentDataFeedId = IApi3ServerV1(api3ServerV1)
            .dapiNameHashToDataFeedId(keccak256(abi.encodePacked(dapiName)));
        (
            dataFeedDetails,
            dapiValue,
            dapiTimestamp,
            beaconValues,
            beaconTimestamps
        ) = getDataFeedData(currentDataFeedId);
        uint256 queueLength = 0;
        for (
            bytes32 queuedSubscriptionId = dapiNameToCurrentSubscriptionId[
                dapiName
            ];
            queuedSubscriptionId != bytes32(0);
            queuedSubscriptionId = subscriptions[queuedSubscriptionId]
                .nextSubscriptionId
        ) {
            queueLength++;
        }
        updateParameters = new bytes[](queueLength);
        endTimestamps = new uint32[](queueLength);
        dailyPrices = new uint224[](queueLength);
        Subscription storage queuedSubscription = subscriptions[
            dapiNameToCurrentSubscriptionId[dapiName]
        ];
        for (uint256 ind = 0; ind < queueLength; ind++) {
            updateParameters[ind] = updateParametersHashToValue[
                queuedSubscription.updateParametersHash
            ];
            endTimestamps[ind] = queuedSubscription.endTimestamp;
            dailyPrices[ind] = queuedSubscription.dailyPrice;
            queuedSubscription = subscriptions[
                queuedSubscription.nextSubscriptionId
            ];
        }
    }

    /// @notice Gets all data about the data feed that is available
    /// @dev This function is intended to be used by the API3 Market frontend
    /// to determine what needs to be done to ready the data feed to purchase
    /// the respective subscription.
    /// In the case that the client wants to use this to fetch the respective
    /// Beacon readings for an unregistered data feed, they can do a static
    /// multicall where the `getDataFeedData()` call is preceded by a
    /// `registerDataFeed()` call.
    /// @param dataFeedId Data feed ID
    /// @return dataFeedDetails Data feed details
    /// @return dataFeedValue Data feed value read from Api3ServerV1
    /// @return dataFeedTimestamp Data feed timestamp read from Api3ServerV1
    /// @return beaconValues Beacon values read from Api3ServerV1
    /// @return beaconTimestamps Beacon timestamps read from Api3ServerV1
    function getDataFeedData(
        bytes32 dataFeedId
    )
        public
        view
        returns (
            bytes memory dataFeedDetails,
            int224 dataFeedValue,
            uint32 dataFeedTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps
        )
    {
        dataFeedDetails = AirseekerRegistry(airseekerRegistry)
            .dataFeedIdToDetails(dataFeedId);
        (dataFeedValue, dataFeedTimestamp) = IApi3ServerV1(api3ServerV1)
            .dataFeeds(dataFeedId);
        if (
            dataFeedDetails.length == DATA_FEED_DETAILS_LENGTH_FOR_SINGLE_BEACON
        ) {
            beaconValues = new int224[](1);
            beaconTimestamps = new uint32[](1);
            (address airnode, bytes32 templateId) = abi.decode(
                dataFeedDetails,
                (address, bytes32)
            );
            (beaconValues[0], beaconTimestamps[0]) = IApi3ServerV1(api3ServerV1)
                .dataFeeds(deriveBeaconId(airnode, templateId));
        } else if (dataFeedDetails.length != 0) {
            (address[] memory airnodes, bytes32[] memory templateIds) = abi
                .decode(dataFeedDetails, (address[], bytes32[]));
            uint256 beaconCount = airnodes.length;
            beaconValues = new int224[](beaconCount);
            beaconTimestamps = new uint32[](beaconCount);
            for (uint256 ind = 0; ind < beaconCount; ind++) {
                (beaconValues[ind], beaconTimestamps[ind]) = IApi3ServerV1(
                    api3ServerV1
                ).dataFeeds(deriveBeaconId(airnodes[ind], templateIds[ind]));
            }
        }
    }

    /// @notice Subscription ID to update parameters
    /// @param subscriptionId Subscription ID
    /// @return updateParameters Update parameters
    function subscriptionIdToUpdateParameters(
        bytes32 subscriptionId
    ) public view override returns (bytes memory updateParameters) {
        updateParameters = updateParametersHashToValue[
            subscriptions[subscriptionId].updateParametersHash
        ];
    }

    /// @notice Returns the signature delegation hash type used in delegation
    /// signatures
    /// @return Signature delegation hash type
    function signatureDelegationHashType()
        public
        view
        virtual
        override(HashRegistry, IHashRegistry)
        returns (bytes32)
    {
        return API3MARKET_SIGNATURE_DELEGATION_HASH_TYPE;
    }

    /// @notice Adds the subscription to the queue if applicable
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    function addSubscriptionToQueue(
        bytes32 dapiName,
        bytes32 dataFeedId,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price
    ) internal returns (bytes32 subscriptionId) {
        uint32 endTimestamp;
        bytes32 previousSubscriptionId;
        bytes32 nextSubscriptionId;
        (
            subscriptionId,
            endTimestamp,
            previousSubscriptionId,
            nextSubscriptionId
        ) = prospectSubscriptionPositionInQueue(
            dapiName,
            updateParameters,
            duration
        );
        bytes32 updateParametersHash = keccak256(updateParameters);
        if (updateParametersHashToValue[updateParametersHash].length == 0) {
            updateParametersHashToValue[
                updateParametersHash
            ] = updateParameters;
        }
        subscriptions[subscriptionId] = Subscription({
            updateParametersHash: updateParametersHash,
            endTimestamp: endTimestamp,
            dailyPrice: SafeCast.toUint224((price * 1 days) / duration),
            nextSubscriptionId: nextSubscriptionId
        });
        if (previousSubscriptionId == bytes32(0)) {
            if (subscriptionId != dapiNameToCurrentSubscriptionId[dapiName]) {
                emit UpdatedCurrentSubscriptionId(dapiName, subscriptionId);
                dapiNameToCurrentSubscriptionId[dapiName] = subscriptionId;
            }
            AirseekerRegistry(airseekerRegistry).setDapiNameUpdateParameters(
                dapiName,
                updateParameters
            );
            AirseekerRegistry(airseekerRegistry).setDapiNameToBeActivated(
                dapiName
            );
        } else {
            subscriptions[previousSubscriptionId]
                .nextSubscriptionId = subscriptionId;
            bytes32 currentSubscriptionId = dapiNameToCurrentSubscriptionId[
                dapiName
            ];
            if (
                subscriptions[currentSubscriptionId].endTimestamp <=
                block.timestamp
            ) {
                updateEndedCurrentSubscriptionId(
                    dapiName,
                    currentSubscriptionId
                );
            }
        }
        validateDataFeedReadiness(dataFeedId);
        if (
            IApi3ServerV1(api3ServerV1).dapiNameHashToDataFeedId(
                keccak256(abi.encodePacked(dapiName))
            ) != dataFeedId
        ) {
            IApi3ServerV1(api3ServerV1).setDapiName(dapiName, dataFeedId);
        }
    }

    /// @notice Updates the current subscription that has ended with the one
    /// that will end next
    /// @param dapiName dAPI name
    /// @param currentSubscriptionId Current subscription ID
    function updateEndedCurrentSubscriptionId(
        bytes32 dapiName,
        bytes32 currentSubscriptionId
    ) private {
        do {
            currentSubscriptionId = subscriptions[currentSubscriptionId]
                .nextSubscriptionId;
        } while (
            currentSubscriptionId != bytes32(0) &&
                subscriptions[currentSubscriptionId].endTimestamp <=
                block.timestamp
        );
        emit UpdatedCurrentSubscriptionId(dapiName, currentSubscriptionId);
        dapiNameToCurrentSubscriptionId[dapiName] = currentSubscriptionId;
        if (currentSubscriptionId == bytes32(0)) {
            AirseekerRegistry(airseekerRegistry).setDapiNameToBeDeactivated(
                dapiName
            );
        } else {
            AirseekerRegistry(airseekerRegistry).setDapiNameUpdateParameters(
                dapiName,
                subscriptionIdToUpdateParameters(currentSubscriptionId)
            );
        }
    }

    /// @notice Prospects the subscription position in the queue. It iterates
    /// through the entire subscription queue, which is implemented as a linked
    /// list, and returns the previous and next nodes of the subscription to be
    /// added.
    /// It reverts if no suitable position can be found, which would be because
    /// the addition of the subscription to the queue does not upgrade its
    /// specs unambiguously or addition of it results in the maximum queue
    /// length to be exceeded.
    /// @param dapiName dAPI name
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @return subscriptionId Subscription ID
    /// @return endTimestamp End timestamp
    /// @return previousSubscriptionId Previous subscription ID
    /// @return nextSubscriptionId Next subscription ID
    function prospectSubscriptionPositionInQueue(
        bytes32 dapiName,
        bytes calldata updateParameters,
        uint256 duration
    )
        private
        view
        returns (
            bytes32 subscriptionId,
            uint32 endTimestamp,
            bytes32 previousSubscriptionId,
            bytes32 nextSubscriptionId
        )
    {
        subscriptionId = keccak256(
            abi.encodePacked(dapiName, keccak256(updateParameters))
        );
        endTimestamp = SafeCast.toUint32(block.timestamp + duration);
        (
            uint256 deviationThresholdInPercentage,
            int224 deviationReference,
            uint256 heartbeatInterval
        ) = abi.decode(updateParameters, (uint256, int224, uint256));
        uint256 newQueueLength = 0;
        Subscription storage queuedSubscription;
        for (
            bytes32 queuedSubscriptionId = dapiNameToCurrentSubscriptionId[
                dapiName
            ];
            queuedSubscriptionId != bytes32(0);
            queuedSubscriptionId = queuedSubscription.nextSubscriptionId
        ) {
            queuedSubscription = subscriptions[queuedSubscriptionId];
            UpdateParametersComparisonResult updateParametersComparisonResult = compareUpdateParametersWithQueued(
                    deviationThresholdInPercentage,
                    deviationReference,
                    heartbeatInterval,
                    queuedSubscription.updateParametersHash
                );
            uint32 queuedSubscriptionEndTimestamp = queuedSubscription
                .endTimestamp;
            require(
                updateParametersComparisonResult ==
                    UpdateParametersComparisonResult.BetterThanQueued ||
                    endTimestamp > queuedSubscriptionEndTimestamp,
                "Subscription does not upgrade"
            );
            if (
                updateParametersComparisonResult ==
                UpdateParametersComparisonResult.WorseThanQueued &&
                queuedSubscriptionEndTimestamp > block.timestamp
            ) {
                previousSubscriptionId = queuedSubscriptionId;
                newQueueLength++;
            }
            if (
                updateParametersComparisonResult ==
                UpdateParametersComparisonResult.BetterThanQueued &&
                endTimestamp < queuedSubscriptionEndTimestamp
            ) {
                nextSubscriptionId = queuedSubscriptionId;
                for (
                    ;
                    queuedSubscriptionId != bytes32(0);
                    queuedSubscriptionId = subscriptions[queuedSubscriptionId]
                        .nextSubscriptionId
                ) {
                    newQueueLength++;
                }
                break;
            }
        }
        require(
            newQueueLength < maximumSubscriptionQueueLength,
            "Subscription queue full"
        );
    }

    /// @notice Compares the update parameters with the ones that belong to a
    /// queued subscription
    /// @param deviationThresholdInPercentage Deviation threshold in percentage
    /// @param deviationReference Deviation reference
    /// @param heartbeatInterval Heartbeat interval
    /// @param queuedUpdateParametersHash Queued update parameters hash
    /// @return Update parameters comparison result
    function compareUpdateParametersWithQueued(
        uint256 deviationThresholdInPercentage,
        int224 deviationReference,
        uint256 heartbeatInterval,
        bytes32 queuedUpdateParametersHash
    ) private view returns (UpdateParametersComparisonResult) {
        // The update parameters that belong to a queued subscription are
        // guaranteed to have been stored in the hash map
        (
            uint256 queuedDeviationThresholdInPercentage,
            int224 queuedDeviationReference,
            uint256 queuedHeartbeatInterval
        ) = abi.decode(
                updateParametersHashToValue[queuedUpdateParametersHash],
                (uint256, int224, uint256)
            );
        require(
            deviationReference == queuedDeviationReference,
            "Deviation references not equal"
        );
        if (
            (deviationThresholdInPercentage ==
                queuedDeviationThresholdInPercentage) &&
            (heartbeatInterval == queuedHeartbeatInterval)
        ) {
            return UpdateParametersComparisonResult.EqualToQueued;
        } else if (
            (deviationThresholdInPercentage <=
                queuedDeviationThresholdInPercentage) &&
            (heartbeatInterval <= queuedHeartbeatInterval)
        ) {
            return UpdateParametersComparisonResult.BetterThanQueued;
        } else if (
            (deviationThresholdInPercentage >=
                queuedDeviationThresholdInPercentage) &&
            (heartbeatInterval >= queuedHeartbeatInterval)
        ) {
            return UpdateParametersComparisonResult.WorseThanQueued;
        } else {
            // This is hit when the set of parameters are superior to each
            // other in different aspects, in which case they should not be
            // allowed to be in the same queue
            revert("Update parameters incomparable");
        }
    }

    /// @notice Validates the readiness of the data feed. The data feed must
    /// have been updated on Api3ServerV1 in the last `MAXIMUM_DAPI_UPDATE_AGE`
    /// and registered on AirseekerRegistry.
    /// @param dataFeedId Data feed ID
    function validateDataFeedReadiness(bytes32 dataFeedId) private view {
        (, uint32 timestamp) = IApi3ServerV1(api3ServerV1).dataFeeds(
            dataFeedId
        );
        require(
            block.timestamp <= timestamp + MAXIMUM_DAPI_UPDATE_AGE,
            "Data feed value stale"
        );
        require(
            AirseekerRegistry(airseekerRegistry).dataFeedIsRegistered(
                dataFeedId
            ),
            "Data feed not registered"
        );
    }

    /// @notice Verifies the dAPI management Merkle proof
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param dapiManagementMerkleData ABI-encoded dAPI management Merkle root
    /// and proof
    function verifyDapiManagementMerkleProof(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes calldata dapiManagementMerkleData
    ) private view {
        require(dapiName != bytes32(0), "dAPI name zero");
        (
            bytes32 dapiManagementMerkleRoot,
            bytes32[] memory dapiManagementMerkleProof
        ) = abi.decode(dapiManagementMerkleData, (bytes32, bytes32[]));
        require(
            hashes[DAPI_MANAGEMENT_MERKLE_ROOT_HASH_TYPE].value ==
                dapiManagementMerkleRoot,
            "Invalid root"
        );
        require(
            MerkleProof.verify(
                dapiManagementMerkleProof,
                dapiManagementMerkleRoot,
                keccak256(
                    bytes.concat(
                        keccak256(
                            abi.encode(dapiName, dataFeedId, sponsorWallet)
                        )
                    )
                )
            ),
            "Invalid proof"
        );
    }

    function verifyDapiManagementAndDapiPricingMerkleProofs(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    ) private view {
        require(dapiName != bytes32(0), "dAPI name zero");
        require(
            updateParameters.length == UPDATE_PARAMETERS_LENGTH,
            "Update parameters length invalid"
        );
        require(duration != 0, "Duration zero");
        require(price != 0, "Price zero");
        (
            bytes32 dapiManagementMerkleRoot,
            bytes32[] memory dapiManagementMerkleProof,
            bytes32 dapiPricingMerkleRoot,
            bytes32[] memory dapiPricingMerkleProof
        ) = abi.decode(
                dapiManagementAndDapiPricingMerkleData,
                (bytes32, bytes32[], bytes32, bytes32[])
            );
        require(
            hashes[DAPI_MANAGEMENT_MERKLE_ROOT_HASH_TYPE].value ==
                dapiManagementMerkleRoot,
            "Invalid root"
        );
        require(
            MerkleProof.verify(
                dapiManagementMerkleProof,
                dapiManagementMerkleRoot,
                keccak256(
                    bytes.concat(
                        keccak256(
                            abi.encode(dapiName, dataFeedId, sponsorWallet)
                        )
                    )
                )
            ),
            "Invalid proof"
        );
        require(
            hashes[DAPI_PRICING_MERKLE_ROOT_HASH_TYPE].value ==
                dapiPricingMerkleRoot,
            "Invalid root"
        );
        require(
            MerkleProof.verify(
                dapiPricingMerkleProof,
                dapiPricingMerkleRoot,
                keccak256(
                    bytes.concat(
                        keccak256(
                            abi.encode(
                                dapiName,
                                block.chainid,
                                updateParameters,
                                duration,
                                price
                            )
                        )
                    )
                )
            ),
            "Invalid proof"
        );
    }

    /// @notice Verifies the signed API URL Merkle proof
    /// @param airnode Airnode address
    /// @param signedApiUrl Signed API URL
    /// @param signedApiUrlMerkleData ABI-encoded signed API URL Merkle root
    /// and proof
    function verifySignedApiUrlMerkleProof(
        address airnode,
        string calldata signedApiUrl,
        bytes calldata signedApiUrlMerkleData
    ) private view {
        (
            bytes32 signedApiUrlMerkleRoot,
            bytes32[] memory signedApiUrlMerkleProof
        ) = abi.decode(signedApiUrlMerkleData, (bytes32, bytes32[]));
        require(
            hashes[SIGNED_API_URL_MERKLE_ROOT_HASH_TYPE].value ==
                signedApiUrlMerkleRoot,
            "Invalid root"
        );
        require(
            MerkleProof.verify(
                signedApiUrlMerkleProof,
                signedApiUrlMerkleRoot,
                keccak256(
                    bytes.concat(keccak256(abi.encode(airnode, signedApiUrl)))
                )
            ),
            "Invalid proof"
        );
    }

    /// @notice Derives the Beacon ID from the Airnode address and template ID
    /// @param airnode Airnode address
    /// @param templateId Template ID
    /// @return beaconId Beacon ID
    function deriveBeaconId(
        address airnode,
        bytes32 templateId
    ) private pure returns (bytes32 beaconId) {
        beaconId = keccak256(abi.encodePacked(airnode, templateId));
    }
}
        

// SPDX-License-Identifier: MIT
pragma solidity 0.8.17;

import "../vendor/@openzeppelin/contracts@4.9.5/access/Ownable.sol";
import "./interfaces/IHashRegistry.sol";
import "../vendor/@openzeppelin/contracts@4.9.5/utils/cryptography/ECDSA.sol";

/// @title A contract where a value for each hash type can be registered using
/// the signatures of the respective signers that are set by the contract owner
/// @notice Hashes are identified by a unique "hash type", which is a `bytes32`
/// type that can be determined based on any arbitrary convention. The contract
/// owner can set a list of signers for each hash type. For a hash value to be
/// registered, its signers must be set by the contract owner, and valid
/// signatures by each signer must be provided. The hash values are bundled
/// with timestamps that act as nonces, meaning that each registration must
/// be with a larger timestamp than the previous. The contract owner can
/// override previously registered hashes.
/// A signer can sign a delegation message that allows the delegate to sign
/// hashes on their behalf across all instances of this contract until the
/// specified time. This delegation is irrevocable by design (as revoking across
/// all instances would be error-prone). To undo an unwanted delegation, the
/// signer must be swapped out by the contract owner until the delegation runs
/// out.
/// @dev This contract can be used in standalone form to be referred to through
/// external calls, or inherited by the contract that will access the
/// registered hashes internally.
/// HashRegistry is intended for use-cases where signatures and delegations
/// need to apply universally across domains, which is why it is blind to the
/// domain (unlike ERC-712). However, the inheriting contract can implement the
/// type hashes to be domain-specific.
contract HashRegistry is Ownable, IHashRegistry {
    struct Hash {
        bytes32 value;
        uint256 timestamp;
    }

    /// @notice Hash type to the last registered value and timestamp
    mapping(bytes32 => Hash) public override hashes;

    /// @notice Hash type to the hash of the array of signer addresses
    mapping(bytes32 => bytes32) public override hashTypeToSignersHash;

    uint256 private constant ECDSA_SIGNATURE_LENGTH = 65;

    // Length of abi.encode(uint256, bytes, bytes), where the bytes types are
    // ECDSA signatures padded to the next largest multiple of 32 bytes, which
    // is 96
    uint256 private constant DELEGATED_SIGNATURE_LENGTH =
        32 + 32 + 32 + (32 + 96) + (32 + 96);

    /// @param owner_ Owner address
    constructor(address owner_) {
        require(owner_ != address(0), "Owner address zero");
        _transferOwnership(owner_);
    }

    /// @notice Returns the owner address
    /// @return Owner address
    function owner()
        public
        view
        virtual
        override(Ownable, IOwnable)
        returns (address)
    {
        return super.owner();
    }

    /// @notice Called by the owner to renounce the ownership of the contract
    function renounceOwnership() public virtual override(Ownable, IOwnable) {
        return super.renounceOwnership();
    }

    /// @notice Called by the owner to transfer the ownership of the contract
    /// @param newOwner New owner address
    function transferOwnership(
        address newOwner
    ) public virtual override(Ownable, IOwnable) {
        return super.transferOwnership(newOwner);
    }

    /// @notice Called by the contract owner to set signers for a hash type.
    /// The signer addresses must be in ascending order.
    /// @param hashType Hash type
    /// @param signers Signer addresses
    function setSigners(
        bytes32 hashType,
        address[] calldata signers
    ) external override onlyOwner {
        require(hashType != bytes32(0), "Hash type zero");
        uint256 signersCount = signers.length;
        require(signersCount != 0, "Signers empty");
        require(signers[0] != address(0), "First signer address zero");
        for (uint256 ind = 1; ind < signersCount; ind++) {
            require(
                signers[ind] > signers[ind - 1],
                "Signers not in ascending order"
            );
        }
        hashTypeToSignersHash[hashType] = keccak256(abi.encodePacked(signers));
        emit SetSigners(hashType, signers);
    }

    /// @notice Called by the owner to set a hash. Overrides previous
    /// registrations and is allowed to set the value to `bytes32(0)`.
    /// @param hashType Hash type
    /// @param hashValue Hash value
    function setHash(
        bytes32 hashType,
        bytes32 hashValue
    ) external override onlyOwner {
        hashes[hashType] = Hash({value: hashValue, timestamp: block.timestamp});
        emit SetHash(hashType, hashValue, block.timestamp);
    }

    /// @notice Registers the hash value and timestamp for the respective type.
    /// The hash value cannot be zero.
    /// The timestamp must not exceed the block timestamp, yet be larger than
    /// the timestamp of the previous registration.
    /// The signers must have been set for the hash type, and the signatures
    /// must be sorted for the respective signer addresses to be in ascending
    /// order.
    /// Each signature can either be a standalone signature by the respective
    /// signer, or a signature by the signer's delegate, encoded along with
    /// the delegation end timestamp and delegation signature.
    /// @param hashType Hash type
    /// @param hashValue Hash value
    /// @param hashTimestamp Hash timestamp
    /// @param signatures Signatures
    function registerHash(
        bytes32 hashType,
        bytes32 hashValue,
        uint256 hashTimestamp,
        bytes[] calldata signatures
    ) external override {
        require(hashValue != bytes32(0), "Hash value zero");
        require(hashTimestamp <= block.timestamp, "Hash timestamp from future");
        require(
            hashTimestamp > hashes[hashType].timestamp,
            "Hash timestamp not more recent"
        );
        bytes32 signersHash = hashTypeToSignersHash[hashType];
        require(signersHash != bytes32(0), "Signers not set");
        uint256 signaturesCount = signatures.length;
        address[] memory signers = new address[](signaturesCount);
        bytes32 ethSignedMessageHash = ECDSA.toEthSignedMessageHash(
            keccak256(abi.encodePacked(hashType, hashValue, hashTimestamp))
        );
        for (uint256 ind = 0; ind < signaturesCount; ind++) {
            uint256 signatureLength = signatures[ind].length;
            if (signatureLength == ECDSA_SIGNATURE_LENGTH) {
                signers[ind] = ECDSA.recover(
                    ethSignedMessageHash,
                    signatures[ind]
                );
            } else if (signatureLength == DELEGATED_SIGNATURE_LENGTH) {
                (
                    uint256 delegationEndTimestamp,
                    bytes memory delegationSignature,
                    bytes memory hashSignature
                ) = abi.decode(signatures[ind], (uint256, bytes, bytes));
                require(
                    block.timestamp < delegationEndTimestamp,
                    "Delegation ended"
                );
                signers[ind] = ECDSA.recover(
                    ECDSA.toEthSignedMessageHash(
                        keccak256(
                            abi.encodePacked(
                                signatureDelegationHashType(),
                                ECDSA.recover(
                                    ethSignedMessageHash,
                                    hashSignature
                                ),
                                delegationEndTimestamp
                            )
                        )
                    ),
                    delegationSignature
                );
            } else {
                revert("Invalid signature length");
            }
        }
        require(
            signersHash == keccak256(abi.encodePacked(signers)),
            "Signature mismatch"
        );
        hashes[hashType] = Hash({value: hashValue, timestamp: hashTimestamp});
        emit RegisteredHash(hashType, hashValue, hashTimestamp);
    }

    /// @notice Returns the signature delegation hash type used in delegation
    /// signatures
    /// @dev Delegation signatures signed with a signature delegation hash type
    /// will apply universally across all HashRegistry instances that use that
    /// same signature delegation hash type. The inheriting contract can
    /// specify a special signature delegation hash type by overriding this
    /// function.
    /// @return Signature delegation hash type
    function signatureDelegationHashType()
        public
        view
        virtual
        override
        returns (bytes32)
    {
        return keccak256(abi.encodePacked("HashRegistry signature delegation"));
    }

    /// @notice Returns get the hash value for the type
    /// @param hashType Hash type
    /// @return hashValue Hash value
    function getHashValue(
        bytes32 hashType
    ) external view override returns (bytes32 hashValue) {
        hashValue = hashes[hashType].value;
    }
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "../../utils/interfaces/ISelfMulticall.sol";

interface IAccessControlRegistryAdminned is ISelfMulticall {
    function accessControlRegistry() external view returns (address);

    function adminRoleDescription() external view returns (string memory);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./IAccessControlRegistryAdminned.sol";

interface IAccessControlRegistryAdminnedWithManager is
    IAccessControlRegistryAdminned
{
    function manager() external view returns (address);

    function adminRole() external view returns (bytes32);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./IOwnable.sol";

interface IHashRegistry is IOwnable {
    event SetSigners(bytes32 indexed hashType, address[] signers);

    event SetHash(
        bytes32 indexed hashType,
        bytes32 hashValue,
        uint256 hashTimestamp
    );

    event RegisteredHash(
        bytes32 indexed hashType,
        bytes32 hashValue,
        uint256 hashTimestamp
    );

    function setSigners(bytes32 hashType, address[] calldata signers) external;

    function setHash(bytes32 hashType, bytes32 hashValue) external;

    function registerHash(
        bytes32 hashType,
        bytes32 hashValue,
        uint256 hashTimestamp,
        bytes[] calldata signatures
    ) external;

    function signatureDelegationHashType() external view returns (bytes32);

    function getHashValue(
        bytes32 hashType
    ) external view returns (bytes32 hashValue);

    function hashes(
        bytes32 hashType
    ) external view returns (bytes32 hashValue, uint256 hashTimestamp);

    function hashTypeToSignersHash(
        bytes32 hashType
    ) external view returns (bytes32 signersHash);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

interface IOwnable {
    function owner() external view returns (address);

    function renounceOwnership() external;

    function transferOwnership(address newOwner) external;
}
          

// SPDX-License-Identifier: MIT
pragma solidity 0.8.17;

import "../vendor/@openzeppelin/contracts@4.9.5/access/Ownable.sol";
import "../utils/ExtendedSelfMulticall.sol";
import "./interfaces/IAirseekerRegistry.sol";
import "../vendor/@openzeppelin/contracts@4.9.5/utils/structs/EnumerableSet.sol";
import "./interfaces/IApi3ServerV1.sol";

/// @title A contract where active data feeds and their specs are registered by
/// the contract owner for the Airseeker that serves them to refer to
/// @notice Airseeker is an application that pushes API provider-signed data to
/// chain when certain conditions are met so that the data feeds served on the
/// Api3ServerV1 contract are updated according to the respective specs. In
/// other words, this contract is an on-chain configuration file for an
/// Airseeker (or multiple Airseekers in a setup with redundancy).
/// The Airseeker must know which data feeds are active (and thus need to be
/// updated), the constituting Airnode (the oracle node that API providers
/// operate to sign data) addresses and request template IDs, what the
/// respective on-chain data feed values are, what the update parameters are,
/// and the URL of the signed APIs (from which Airseeker can fetch signed data)
/// that are hosted by the respective API providers.
/// The contract owner is responsible with leaving the state of this contract
/// in a way that Airseeker expects. For example, if a dAPI name is activated
/// without registering the respective data feed, the Airseeker will not have
/// access to the data that it needs to execute updates.
contract AirseekerRegistry is
    Ownable,
    ExtendedSelfMulticall,
    IAirseekerRegistry
{
    using EnumerableSet for EnumerableSet.Bytes32Set;

    /// @notice Maximum number of Beacons in a Beacon set that can be
    /// registered
    /// @dev Api3ServerV1 introduces the concept of a Beacon, which is a
    /// single-source data feed. Api3ServerV1 allows Beacons to be read
    /// individually, or arbitrary combinations of them to be aggregated
    /// on-chain to form multiple-source data feeds, which are called Beacon
    /// sets. This contract does not support Beacon sets that consist of more
    /// than `MAXIMUM_BEACON_COUNT_IN_SET` Beacons to be registered.
    uint256 public constant override MAXIMUM_BEACON_COUNT_IN_SET = 21;

    /// @notice Maximum encoded update parameters length
    uint256 public constant override MAXIMUM_UPDATE_PARAMETERS_LENGTH = 1024;

    /// @notice Maximum signed API URL length
    uint256 public constant override MAXIMUM_SIGNED_API_URL_LENGTH = 256;

    /// @notice Api3ServerV1 contract address
    address public immutable override api3ServerV1;

    /// @notice Airnode address to signed API URL
    /// @dev An Airseeker can be configured to refer to additional signed APIs
    /// than the ones whose URLs are stored in this contract for redundancy
    mapping(address => string) public override airnodeToSignedApiUrl;

    /// @notice Data feed ID to encoded details
    mapping(bytes32 => bytes) public override dataFeedIdToDetails;

    // Api3ServerV1 uses Beacon IDs (see the `deriveBeaconId()` implementation)
    // and Beacon set IDs (see the `deriveBeaconSetId()` implementation) to
    // address data feeds. We use data feed ID as a general term to refer to a
    // Beacon ID/Beacon set ID.
    // A data feed ID is immutable (i.e., it always points to the same Beacon
    // or Beacon set). Api3ServerV1 allows a dAPI name to be pointed to a data
    // feed ID by privileged accounts to implement a mutable data feed
    // addressing scheme.
    // If the data feed ID or dAPI name should be used to read a data feed
    // depends on the use case. To support both schemes, AirseekerRegistry
    // allows data feeds specs to be defined with either the data feed ID or
    // the dAPI name.
    EnumerableSet.Bytes32Set private activeDataFeedIds;

    EnumerableSet.Bytes32Set private activeDapiNames;

    // Considering that the update parameters are typically reused between data
    // feeds, a hash map is used to avoid storing the same update parameters
    // redundantly
    mapping(bytes32 => bytes32) private dataFeedIdToUpdateParametersHash;

    mapping(bytes32 => bytes32) private dapiNameToUpdateParametersHash;

    mapping(bytes32 => bytes) private updateParametersHashToValue;

    // Length of abi.encode(address, bytes32)
    uint256 private constant DATA_FEED_DETAILS_LENGTH_FOR_SINGLE_BEACON =
        32 + 32;

    // Length of abi.encode(address[2], bytes32[2])
    uint256
        private constant DATA_FEED_DETAILS_LENGTH_FOR_BEACON_SET_WITH_TWO_BEACONS =
        32 + 32 + (32 + 2 * 32) + (32 + 2 * 32);

    // Length of
    // abi.encode(address[MAXIMUM_BEACON_COUNT_IN_SET], bytes32[MAXIMUM_BEACON_COUNT_IN_SET])
    uint256 private constant MAXIMUM_DATA_FEED_DETAILS_LENGTH =
        32 +
            32 +
            (32 + MAXIMUM_BEACON_COUNT_IN_SET * 32) +
            (32 + MAXIMUM_BEACON_COUNT_IN_SET * 32);

    /// @dev Reverts if the data feed ID is zero
    /// @param dataFeedId Data feed ID
    modifier onlyNonZeroDataFeedId(bytes32 dataFeedId) {
        require(dataFeedId != bytes32(0), "Data feed ID zero");
        _;
    }

    /// @dev Reverts if the dAPI name is zero
    /// @param dapiName dAPI name
    modifier onlyNonZeroDapiName(bytes32 dapiName) {
        require(dapiName != bytes32(0), "dAPI name zero");
        _;
    }

    /// @dev Reverts if the update parameters are too long
    /// @param updateParameters Update parameters
    modifier onlyValidUpdateParameters(bytes calldata updateParameters) {
        require(
            updateParameters.length <= MAXIMUM_UPDATE_PARAMETERS_LENGTH,
            "Update parameters too long"
        );
        _;
    }

    /// @param owner_ Owner address
    /// @param api3ServerV1_ Api3ServerV1 contract address
    constructor(address owner_, address api3ServerV1_) {
        require(owner_ != address(0), "Owner address zero");
        require(api3ServerV1_ != address(0), "Api3ServerV1 address zero");
        _transferOwnership(owner_);
        api3ServerV1 = api3ServerV1_;
    }

    /// @notice Returns the owner address
    /// @return Owner address
    function owner() public view override(Ownable, IOwnable) returns (address) {
        return super.owner();
    }

    /// @notice Overriden to be disabled
    function renounceOwnership() public pure override(Ownable, IOwnable) {
        revert("Ownership cannot be renounced");
    }

    /// @notice Overriden to be disabled
    function transferOwnership(
        address
    ) public pure override(Ownable, IOwnable) {
        revert("Ownership cannot be transferred");
    }

    /// @notice Called by the owner to set the data feed ID to be activated
    /// @param dataFeedId Data feed ID
    function setDataFeedIdToBeActivated(
        bytes32 dataFeedId
    ) external override onlyOwner onlyNonZeroDataFeedId(dataFeedId) {
        if (activeDataFeedIds.add(dataFeedId)) {
            emit ActivatedDataFeedId(dataFeedId);
        }
    }

    /// @notice Called by the owner to set the dAPI name to be activated
    /// @param dapiName dAPI name
    function setDapiNameToBeActivated(
        bytes32 dapiName
    ) external override onlyOwner onlyNonZeroDapiName(dapiName) {
        if (activeDapiNames.add(dapiName)) {
            emit ActivatedDapiName(dapiName);
        }
    }

    /// @notice Called by the owner to set the data feed ID to be deactivated
    /// @param dataFeedId Data feed ID
    function setDataFeedIdToBeDeactivated(
        bytes32 dataFeedId
    ) external override onlyOwner onlyNonZeroDataFeedId(dataFeedId) {
        if (activeDataFeedIds.remove(dataFeedId)) {
            emit DeactivatedDataFeedId(dataFeedId);
        }
    }

    /// @notice Called by the owner to set the dAPI name to be deactivated
    /// @param dapiName dAPI name
    function setDapiNameToBeDeactivated(
        bytes32 dapiName
    ) external override onlyOwner onlyNonZeroDapiName(dapiName) {
        if (activeDapiNames.remove(dapiName)) {
            emit DeactivatedDapiName(dapiName);
        }
    }

    /// @notice Called by the owner to set the data feed ID update parameters.
    /// The update parameters must be encoded in a format that Airseeker
    /// expects.
    /// @param dataFeedId Data feed ID
    /// @param updateParameters Update parameters
    function setDataFeedIdUpdateParameters(
        bytes32 dataFeedId,
        bytes calldata updateParameters
    )
        external
        override
        onlyOwner
        onlyNonZeroDataFeedId(dataFeedId)
        onlyValidUpdateParameters(updateParameters)
    {
        bytes32 updateParametersHash = keccak256(updateParameters);
        if (
            dataFeedIdToUpdateParametersHash[dataFeedId] != updateParametersHash
        ) {
            dataFeedIdToUpdateParametersHash[dataFeedId] = updateParametersHash;
            if (
                updateParametersHashToValue[updateParametersHash].length !=
                updateParameters.length
            ) {
                updateParametersHashToValue[
                    updateParametersHash
                ] = updateParameters;
            }
            emit UpdatedDataFeedIdUpdateParameters(
                dataFeedId,
                updateParameters
            );
        }
    }

    /// @notice Called by the owner to set the dAPI name update parameters.
    /// The update parameters must be encoded in a format that Airseeker
    /// expects.
    /// @param dapiName dAPI name
    /// @param updateParameters Update parameters
    function setDapiNameUpdateParameters(
        bytes32 dapiName,
        bytes calldata updateParameters
    )
        external
        override
        onlyOwner
        onlyNonZeroDapiName(dapiName)
        onlyValidUpdateParameters(updateParameters)
    {
        bytes32 updateParametersHash = keccak256(updateParameters);
        if (dapiNameToUpdateParametersHash[dapiName] != updateParametersHash) {
            dapiNameToUpdateParametersHash[dapiName] = updateParametersHash;
            if (
                updateParametersHashToValue[updateParametersHash].length !=
                updateParameters.length
            ) {
                updateParametersHashToValue[
                    updateParametersHash
                ] = updateParameters;
            }
            emit UpdatedDapiNameUpdateParameters(dapiName, updateParameters);
        }
    }

    /// @notice Called by the owner to set the signed API URL for the Airnode.
    /// The signed API must implement the specific interface that Airseeker
    /// expects.
    /// @param airnode Airnode address
    /// @param signedApiUrl Signed API URL
    function setSignedApiUrl(
        address airnode,
        string calldata signedApiUrl
    ) external override onlyOwner {
        require(airnode != address(0), "Airnode address zero");
        require(
            abi.encodePacked(signedApiUrl).length <=
                MAXIMUM_SIGNED_API_URL_LENGTH,
            "Signed API URL too long"
        );
        if (
            keccak256(abi.encodePacked(airnodeToSignedApiUrl[airnode])) !=
            keccak256(abi.encodePacked(signedApiUrl))
        ) {
            airnodeToSignedApiUrl[airnode] = signedApiUrl;
            emit UpdatedSignedApiUrl(airnode, signedApiUrl);
        }
    }

    /// @notice Registers the data feed. In the case that the data feed is a
    /// Beacon, the details should be the ABI-encoded Airnode address and
    /// template ID. In the case that the data feed is a Beacon set, the
    /// details should be the ABI-encoded Airnode addresses array and template
    /// IDs array.
    /// @param dataFeedDetails Data feed details
    /// @return dataFeedId Data feed ID
    function registerDataFeed(
        bytes calldata dataFeedDetails
    ) external override returns (bytes32 dataFeedId) {
        uint256 dataFeedDetailsLength = dataFeedDetails.length;
        if (
            dataFeedDetailsLength == DATA_FEED_DETAILS_LENGTH_FOR_SINGLE_BEACON
        ) {
            // dataFeedId maps to a Beacon
            (address airnode, bytes32 templateId) = abi.decode(
                dataFeedDetails,
                (address, bytes32)
            );
            require(airnode != address(0), "Airnode address zero");
            dataFeedId = deriveBeaconId(airnode, templateId);
        } else if (
            dataFeedDetailsLength >=
            DATA_FEED_DETAILS_LENGTH_FOR_BEACON_SET_WITH_TWO_BEACONS
        ) {
            require(
                dataFeedDetailsLength <= MAXIMUM_DATA_FEED_DETAILS_LENGTH,
                "Data feed details too long"
            );
            (address[] memory airnodes, bytes32[] memory templateIds) = abi
                .decode(dataFeedDetails, (address[], bytes32[]));
            require(
                abi.encode(airnodes, templateIds).length ==
                    dataFeedDetailsLength,
                "Data feed details trail"
            );
            uint256 beaconCount = airnodes.length;
            require(
                beaconCount == templateIds.length,
                "Parameter length mismatch"
            );
            bytes32[] memory beaconIds = new bytes32[](beaconCount);
            for (uint256 ind = 0; ind < beaconCount; ind++) {
                require(airnodes[ind] != address(0), "Airnode address zero");
                beaconIds[ind] = deriveBeaconId(
                    airnodes[ind],
                    templateIds[ind]
                );
            }
            dataFeedId = deriveBeaconSetId(beaconIds);
        } else {
            revert("Data feed details too short");
        }
        if (dataFeedIdToDetails[dataFeedId].length != dataFeedDetailsLength) {
            dataFeedIdToDetails[dataFeedId] = dataFeedDetails;
            emit RegisteredDataFeed(dataFeedId, dataFeedDetails);
        }
    }

    /// @notice In an imaginary array consisting of the the active data feed
    /// IDs and active dAPI names, picks the index-th identifier, and returns
    /// all data about the respective data feed that is available. Whenever
    /// data is not available (including the case where index does not
    /// correspond to an active data feed), returns empty values.
    /// @dev Airseeker uses this function to get all the data it needs about an
    /// active data feed with a single RPC call
    /// @param index Index
    /// @return dataFeedId Data feed ID
    /// @return dapiName dAPI name (`bytes32(0)` if the active data feed is
    /// identified by a data feed ID)
    /// @return dataFeedDetails Data feed details
    /// @return dataFeedValue Data feed value read from Api3ServerV1
    /// @return dataFeedTimestamp Data feed timestamp read from Api3ServerV1
    /// @return beaconValues Beacon values read from Api3ServerV1
    /// @return beaconTimestamps Beacon timestamps read from Api3ServerV1
    /// @return updateParameters Update parameters
    /// @return signedApiUrls Signed API URLs of the Beacon Airnodes
    function activeDataFeed(
        uint256 index
    )
        external
        view
        override
        returns (
            bytes32 dataFeedId,
            bytes32 dapiName,
            bytes memory dataFeedDetails,
            int224 dataFeedValue,
            uint32 dataFeedTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps,
            bytes memory updateParameters,
            string[] memory signedApiUrls
        )
    {
        uint256 activeDataFeedIdsLength = activeDataFeedIdCount();
        if (index < activeDataFeedIdsLength) {
            dataFeedId = activeDataFeedIds.at(index);
            updateParameters = dataFeedIdToUpdateParameters(dataFeedId);
        } else if (index < activeDataFeedIdsLength + activeDapiNames.length()) {
            dapiName = activeDapiNames.at(index - activeDataFeedIdsLength);
            dataFeedId = IApi3ServerV1(api3ServerV1).dapiNameHashToDataFeedId(
                keccak256(abi.encodePacked(dapiName))
            );
            updateParameters = dapiNameToUpdateParameters(dapiName);
        }
        if (dataFeedId != bytes32(0)) {
            dataFeedDetails = dataFeedIdToDetails[dataFeedId];
            (dataFeedValue, dataFeedTimestamp) = IApi3ServerV1(api3ServerV1)
                .dataFeeds(dataFeedId);
        }
        if (dataFeedDetails.length != 0) {
            if (
                dataFeedDetails.length ==
                DATA_FEED_DETAILS_LENGTH_FOR_SINGLE_BEACON
            ) {
                beaconValues = new int224[](1);
                beaconTimestamps = new uint32[](1);
                signedApiUrls = new string[](1);
                (address airnode, bytes32 templateId) = abi.decode(
                    dataFeedDetails,
                    (address, bytes32)
                );
                (beaconValues[0], beaconTimestamps[0]) = IApi3ServerV1(
                    api3ServerV1
                ).dataFeeds(deriveBeaconId(airnode, templateId));
                signedApiUrls[0] = airnodeToSignedApiUrl[airnode];
            } else {
                (address[] memory airnodes, bytes32[] memory templateIds) = abi
                    .decode(dataFeedDetails, (address[], bytes32[]));
                uint256 beaconCount = airnodes.length;
                beaconValues = new int224[](beaconCount);
                beaconTimestamps = new uint32[](beaconCount);
                signedApiUrls = new string[](beaconCount);
                for (uint256 ind = 0; ind < beaconCount; ind++) {
                    (beaconValues[ind], beaconTimestamps[ind]) = IApi3ServerV1(
                        api3ServerV1
                    ).dataFeeds(
                            deriveBeaconId(airnodes[ind], templateIds[ind])
                        );
                    signedApiUrls[ind] = airnodeToSignedApiUrl[airnodes[ind]];
                }
            }
        }
    }

    /// @notice Returns the number of active data feeds identified by a data
    /// feed ID or dAPI name
    /// @return Active data feed count
    function activeDataFeedCount() external view override returns (uint256) {
        return activeDataFeedIdCount() + activeDapiNameCount();
    }

    /// @notice Returns the number of active data feeds identified by a data
    /// feed ID
    /// @return Active data feed ID count
    function activeDataFeedIdCount() public view override returns (uint256) {
        return activeDataFeedIds.length();
    }

    /// @notice Returns the number of active data feeds identified by a dAPI
    /// name
    /// @return Active dAPI name count
    function activeDapiNameCount() public view override returns (uint256) {
        return activeDapiNames.length();
    }

    /// @notice Data feed ID to update parameters
    /// @param dataFeedId Data feed ID
    /// @return updateParameters Update parameters
    function dataFeedIdToUpdateParameters(
        bytes32 dataFeedId
    ) public view override returns (bytes memory updateParameters) {
        updateParameters = updateParametersHashToValue[
            dataFeedIdToUpdateParametersHash[dataFeedId]
        ];
    }

    /// @notice dAPI name to update parameters
    /// @param dapiName dAPI name
    /// @return updateParameters Update parameters
    function dapiNameToUpdateParameters(
        bytes32 dapiName
    ) public view override returns (bytes memory updateParameters) {
        updateParameters = updateParametersHashToValue[
            dapiNameToUpdateParametersHash[dapiName]
        ];
    }

    /// @notice Returns if the data feed with ID is registered
    /// @param dataFeedId Data feed ID
    /// @return If the data feed with ID is registered
    function dataFeedIsRegistered(
        bytes32 dataFeedId
    ) external view override returns (bool) {
        return dataFeedIdToDetails[dataFeedId].length != 0;
    }

    /// @notice Derives the Beacon ID from the Airnode address and template ID
    /// @param airnode Airnode address
    /// @param templateId Template ID
    /// @return beaconId Beacon ID
    function deriveBeaconId(
        address airnode,
        bytes32 templateId
    ) private pure returns (bytes32 beaconId) {
        beaconId = keccak256(abi.encodePacked(airnode, templateId));
    }

    /// @notice Derives the Beacon set ID from the Beacon IDs
    /// @param beaconIds Beacon IDs
    /// @return beaconSetId Beacon set ID
    function deriveBeaconSetId(
        bytes32[] memory beaconIds
    ) private pure returns (bytes32 beaconSetId) {
        beaconSetId = keccak256(abi.encode(beaconIds));
    }
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "../../access/interfaces/IOwnable.sol";
import "../../utils/interfaces/IExtendedSelfMulticall.sol";

interface IAirseekerRegistry is IOwnable, IExtendedSelfMulticall {
    event ActivatedDataFeedId(bytes32 indexed dataFeedId);

    event ActivatedDapiName(bytes32 indexed dapiName);

    event DeactivatedDataFeedId(bytes32 indexed dataFeedId);

    event DeactivatedDapiName(bytes32 indexed dapiName);

    event UpdatedDataFeedIdUpdateParameters(
        bytes32 indexed dataFeedId,
        bytes updateParameters
    );

    event UpdatedDapiNameUpdateParameters(
        bytes32 indexed dapiName,
        bytes updateParameters
    );

    event UpdatedSignedApiUrl(address indexed airnode, string signedApiUrl);

    event RegisteredDataFeed(bytes32 indexed dataFeedId, bytes dataFeedDetails);

    function setDataFeedIdToBeActivated(bytes32 dataFeedId) external;

    function setDapiNameToBeActivated(bytes32 dapiName) external;

    function setDataFeedIdToBeDeactivated(bytes32 dataFeedId) external;

    function setDapiNameToBeDeactivated(bytes32 dapiName) external;

    function setDataFeedIdUpdateParameters(
        bytes32 dataFeedId,
        bytes calldata updateParameters
    ) external;

    function setDapiNameUpdateParameters(
        bytes32 dapiName,
        bytes calldata updateParameters
    ) external;

    function setSignedApiUrl(
        address airnode,
        string calldata signedApiUrl
    ) external;

    function registerDataFeed(
        bytes calldata dataFeedDetails
    ) external returns (bytes32 dataFeedId);

    function activeDataFeed(
        uint256 index
    )
        external
        view
        returns (
            bytes32 dataFeedId,
            bytes32 dapiName,
            bytes memory dataFeedDetails,
            int224 dataFeedValue,
            uint32 dataFeedTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps,
            bytes memory updateParameters,
            string[] memory signedApiUrls
        );

    function activeDataFeedCount() external view returns (uint256);

    function activeDataFeedIdCount() external view returns (uint256);

    function activeDapiNameCount() external view returns (uint256);

    function dataFeedIdToUpdateParameters(
        bytes32 dataFeedId
    ) external view returns (bytes memory updateParameters);

    function dapiNameToUpdateParameters(
        bytes32 dapiName
    ) external view returns (bytes memory updateParameters);

    function dataFeedIsRegistered(
        bytes32 dataFeedId
    ) external view returns (bool);

    function MAXIMUM_BEACON_COUNT_IN_SET() external view returns (uint256);

    function MAXIMUM_UPDATE_PARAMETERS_LENGTH() external view returns (uint256);

    function MAXIMUM_SIGNED_API_URL_LENGTH() external view returns (uint256);

    function api3ServerV1() external view returns (address);

    function airnodeToSignedApiUrl(
        address airnode
    ) external view returns (string memory signedApiUrl);

    function dataFeedIdToDetails(
        bytes32 dataFeedId
    ) external view returns (bytes memory dataFeedDetails);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "../../access/interfaces/IHashRegistry.sol";
import "../../utils/interfaces/IExtendedSelfMulticall.sol";

interface IApi3Market is IHashRegistry, IExtendedSelfMulticall {
    event BoughtSubscription(
        bytes32 indexed dapiName,
        bytes32 indexed subscriptionId,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes updateParameters,
        uint256 duration,
        uint256 price,
        uint256 paymentAmount
    );

    event CanceledSubscriptions(bytes32 indexed dapiName);

    event UpdatedCurrentSubscriptionId(
        bytes32 indexed dapiName,
        bytes32 indexed subscriptionId
    );

    function buySubscription(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    ) external payable returns (bytes32 subscriptionId);

    function cancelSubscriptions(bytes32 dapiName) external;

    function updateCurrentSubscriptionId(bytes32 dapiName) external;

    function updateDapiName(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes calldata dapiManagementMerkleData
    ) external;

    function updateSignedApiUrl(
        address airnode,
        string calldata signedApiUrl,
        bytes calldata signedApiUrlMerkleData
    ) external;

    function multicallAndBuySubscription(
        bytes[] calldata multicallData,
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    )
        external
        payable
        returns (bytes[] memory returndata, bytes32 subscriptionId);

    function tryMulticallAndBuySubscription(
        bytes[] calldata tryMulticallData,
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    )
        external
        payable
        returns (
            bool[] memory successes,
            bytes[] memory returndata,
            bytes32 subscriptionId
        );

    function updateBeaconWithSignedData(
        address airnode,
        bytes32 templateId,
        uint256 timestamp,
        bytes calldata data,
        bytes calldata signature
    ) external returns (bytes32 beaconId);

    function updateBeaconSetWithBeacons(
        bytes32[] calldata beaconIds
    ) external returns (bytes32 beaconSetId);

    function deployDapiProxy(
        bytes32 dapiName,
        bytes calldata metadata
    ) external returns (address proxyAddress);

    function deployDapiProxyWithOev(
        bytes32 dapiName,
        address oevBeneficiary,
        bytes calldata metadata
    ) external returns (address proxyAddress);

    function registerDataFeed(
        bytes calldata dataFeedDetails
    ) external returns (bytes32 dataFeedId);

    function computeExpectedSponsorWalletBalance(
        bytes32 dapiName
    ) external view returns (uint256 expectedSponsorWalletBalance);

    function computeExpectedSponsorWalletBalanceAfterSubscriptionIsAdded(
        bytes32 dapiName,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price
    ) external view returns (uint256 expectedSponsorWalletBalance);

    function getDapiData(
        bytes32 dapiName
    )
        external
        view
        returns (
            bytes memory dataFeedDetails,
            int224 dapiValue,
            uint32 dapiTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps,
            bytes[] memory updateParameters,
            uint32[] memory endTimestamps,
            uint224[] memory dailyPrices
        );

    function getDataFeedData(
        bytes32 dataFeedId
    )
        external
        view
        returns (
            bytes memory dataFeedDetails,
            int224 dataFeedValue,
            uint32 dataFeedTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps
        );

    function subscriptionIdToUpdateParameters(
        bytes32 subscriptionId
    ) external view returns (bytes memory updateParameters);

    function DAPI_MANAGEMENT_MERKLE_ROOT_HASH_TYPE()
        external
        view
        returns (bytes32);

    function DAPI_PRICING_MERKLE_ROOT_HASH_TYPE()
        external
        view
        returns (bytes32);

    function SIGNED_API_URL_MERKLE_ROOT_HASH_TYPE()
        external
        view
        returns (bytes32);

    function MAXIMUM_DAPI_UPDATE_AGE() external view returns (uint256);

    function api3ServerV1() external view returns (address);

    function proxyFactory() external view returns (address);

    function airseekerRegistry() external view returns (address);

    function maximumSubscriptionQueueLength() external view returns (uint256);

    function subscriptions(
        bytes32 subscriptionId
    )
        external
        view
        returns (
            bytes32 updateParametersHash,
            uint32 endTimestamp,
            uint224 dailyPrice,
            bytes32 nextSubscriptionId
        );

    function dapiNameToCurrentSubscriptionId(
        bytes32 dapiName
    ) external view returns (bytes32 currentSubscriptionId);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./IOevDapiServer.sol";
import "./IBeaconUpdatesWithSignedData.sol";

interface IApi3ServerV1 is IOevDapiServer, IBeaconUpdatesWithSignedData {
    function readDataFeedWithId(
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);

    function readDataFeedWithDapiNameHash(
        bytes32 dapiNameHash
    ) external view returns (int224 value, uint32 timestamp);

    function readDataFeedWithIdAsOevProxy(
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);

    function readDataFeedWithDapiNameHashAsOevProxy(
        bytes32 dapiNameHash
    ) external view returns (int224 value, uint32 timestamp);

    function dataFeeds(
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);

    function oevProxyToIdToDataFeed(
        address proxy,
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./IDataFeedServer.sol";

interface IBeaconUpdatesWithSignedData is IDataFeedServer {
    function updateBeaconWithSignedData(
        address airnode,
        bytes32 templateId,
        uint256 timestamp,
        bytes calldata data,
        bytes calldata signature
    ) external returns (bytes32 beaconId);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "../../access/interfaces/IAccessControlRegistryAdminnedWithManager.sol";
import "./IDataFeedServer.sol";

interface IDapiServer is
    IAccessControlRegistryAdminnedWithManager,
    IDataFeedServer
{
    event SetDapiName(
        bytes32 indexed dataFeedId,
        bytes32 indexed dapiName,
        address sender
    );

    function setDapiName(bytes32 dapiName, bytes32 dataFeedId) external;

    function dapiNameToDataFeedId(
        bytes32 dapiName
    ) external view returns (bytes32);

    // solhint-disable-next-line func-name-mixedcase
    function DAPI_NAME_SETTER_ROLE_DESCRIPTION()
        external
        view
        returns (string memory);

    function dapiNameSetterRole() external view returns (bytes32);

    function dapiNameHashToDataFeedId(
        bytes32 dapiNameHash
    ) external view returns (bytes32 dataFeedId);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "../../utils/interfaces/IExtendedSelfMulticall.sol";

interface IDataFeedServer is IExtendedSelfMulticall {
    event UpdatedBeaconWithSignedData(
        bytes32 indexed beaconId,
        int224 value,
        uint32 timestamp
    );

    event UpdatedBeaconSetWithBeacons(
        bytes32 indexed beaconSetId,
        int224 value,
        uint32 timestamp
    );

    function updateBeaconSetWithBeacons(
        bytes32[] memory beaconIds
    ) external returns (bytes32 beaconSetId);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./IOevDataFeedServer.sol";
import "./IDapiServer.sol";

interface IOevDapiServer is IOevDataFeedServer, IDapiServer {}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./IDataFeedServer.sol";

interface IOevDataFeedServer is IDataFeedServer {
    event UpdatedOevProxyBeaconWithSignedData(
        bytes32 indexed beaconId,
        address indexed proxy,
        bytes32 indexed updateId,
        int224 value,
        uint32 timestamp
    );

    event UpdatedOevProxyBeaconSetWithSignedData(
        bytes32 indexed beaconSetId,
        address indexed proxy,
        bytes32 indexed updateId,
        int224 value,
        uint32 timestamp
    );

    event Withdrew(
        address indexed oevProxy,
        address oevBeneficiary,
        uint256 amount
    );

    function updateOevProxyDataFeedWithSignedData(
        address oevProxy,
        bytes32 dataFeedId,
        bytes32 updateId,
        uint256 timestamp,
        bytes calldata data,
        bytes[] calldata packedOevUpdateSignatures
    ) external payable;

    function withdraw(address oevProxy) external;

    function oevProxyToBalance(
        address oevProxy
    ) external view returns (uint256 balance);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

interface IProxyFactory {
    event DeployedDataFeedProxy(
        address indexed proxyAddress,
        bytes32 indexed dataFeedId,
        bytes metadata
    );

    event DeployedDapiProxy(
        address indexed proxyAddress,
        bytes32 indexed dapiName,
        bytes metadata
    );

    event DeployedDataFeedProxyWithOev(
        address indexed proxyAddress,
        bytes32 indexed dataFeedId,
        address oevBeneficiary,
        bytes metadata
    );

    event DeployedDapiProxyWithOev(
        address indexed proxyAddress,
        bytes32 indexed dapiName,
        address oevBeneficiary,
        bytes metadata
    );

    function deployDataFeedProxy(
        bytes32 dataFeedId,
        bytes calldata metadata
    ) external returns (address proxyAddress);

    function deployDapiProxy(
        bytes32 dapiName,
        bytes calldata metadata
    ) external returns (address proxyAddress);

    function deployDataFeedProxyWithOev(
        bytes32 dataFeedId,
        address oevBeneficiary,
        bytes calldata metadata
    ) external returns (address proxyAddress);

    function deployDapiProxyWithOev(
        bytes32 dapiName,
        address oevBeneficiary,
        bytes calldata metadata
    ) external returns (address proxyAddress);

    function computeDataFeedProxyAddress(
        bytes32 dataFeedId,
        bytes calldata metadata
    ) external view returns (address proxyAddress);

    function computeDapiProxyAddress(
        bytes32 dapiName,
        bytes calldata metadata
    ) external view returns (address proxyAddress);

    function computeDataFeedProxyWithOevAddress(
        bytes32 dataFeedId,
        address oevBeneficiary,
        bytes calldata metadata
    ) external view returns (address proxyAddress);

    function computeDapiProxyWithOevAddress(
        bytes32 dapiName,
        address oevBeneficiary,
        bytes calldata metadata
    ) external view returns (address proxyAddress);

    function api3ServerV1() external view returns (address);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.7;

import "./SelfMulticall.sol";
import "./interfaces/IExtendedSelfMulticall.sol";

/// @title Contract that extends SelfMulticall to fetch some of the global
/// variables
/// @notice Available global variables are limited to the ones that Airnode
/// tends to need
contract ExtendedSelfMulticall is SelfMulticall, IExtendedSelfMulticall {
    /// @notice Returns the chain ID
    /// @return Chain ID
    function getChainId() external view override returns (uint256) {
        return block.chainid;
    }

    /// @notice Returns the account balance
    /// @param account Account address
    /// @return Account balance
    function getBalance(
        address account
    ) external view override returns (uint256) {
        return account.balance;
    }

    /// @notice Returns if the account contains bytecode
    /// @dev An account not containing any bytecode does not indicate that it
    /// is an EOA or it will not contain any bytecode in the future.
    /// Contract construction and `SELFDESTRUCT` updates the bytecode at the
    /// end of the transaction.
    /// @return If the account contains bytecode
    function containsBytecode(
        address account
    ) external view override returns (bool) {
        return account.code.length > 0;
    }

    /// @notice Returns the current block number
    /// @return Current block number
    function getBlockNumber() external view override returns (uint256) {
        return block.number;
    }

    /// @notice Returns the current block timestamp
    /// @return Current block timestamp
    function getBlockTimestamp() external view override returns (uint256) {
        return block.timestamp;
    }

    /// @notice Returns the current block basefee
    /// @return Current block basefee
    function getBlockBasefee() external view override returns (uint256) {
        return block.basefee;
    }
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./interfaces/ISelfMulticall.sol";

/// @title Contract that enables calls to the inheriting contract to be batched
/// @notice Implements two ways of batching, one requires none of the calls to
/// revert and the other tolerates individual calls reverting
/// @dev This implementation uses delegatecall for individual function calls.
/// Since delegatecall is a message call, it can only be made to functions that
/// are externally visible. This means that a contract cannot multicall its own
/// functions that use internal/private visibility modifiers.
/// Refer to OpenZeppelin's Multicall.sol for a similar implementation.
contract SelfMulticall is ISelfMulticall {
    /// @notice Batches calls to the inheriting contract and reverts as soon as
    /// one of the batched calls reverts
    /// @param data Array of calldata of batched calls
    /// @return returndata Array of returndata of batched calls
    function multicall(
        bytes[] calldata data
    ) external override returns (bytes[] memory returndata) {
        uint256 callCount = data.length;
        returndata = new bytes[](callCount);
        for (uint256 ind = 0; ind < callCount; ) {
            bool success;
            // solhint-disable-next-line avoid-low-level-calls
            (success, returndata[ind]) = address(this).delegatecall(data[ind]);
            if (!success) {
                bytes memory returndataWithRevertData = returndata[ind];
                if (returndataWithRevertData.length > 0) {
                    // Adapted from OpenZeppelin's Address.sol
                    // solhint-disable-next-line no-inline-assembly
                    assembly {
                        let returndata_size := mload(returndataWithRevertData)
                        revert(
                            add(32, returndataWithRevertData),
                            returndata_size
                        )
                    }
                } else {
                    revert("Multicall: No revert string");
                }
            }
            unchecked {
                ind++;
            }
        }
    }

    /// @notice Batches calls to the inheriting contract but does not revert if
    /// any of the batched calls reverts
    /// @param data Array of calldata of batched calls
    /// @return successes Array of success conditions of batched calls
    /// @return returndata Array of returndata of batched calls
    function tryMulticall(
        bytes[] calldata data
    )
        external
        override
        returns (bool[] memory successes, bytes[] memory returndata)
    {
        uint256 callCount = data.length;
        successes = new bool[](callCount);
        returndata = new bytes[](callCount);
        for (uint256 ind = 0; ind < callCount; ) {
            // solhint-disable-next-line avoid-low-level-calls
            (successes[ind], returndata[ind]) = address(this).delegatecall(
                data[ind]
            );
            unchecked {
                ind++;
            }
        }
    }
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./ISelfMulticall.sol";

interface IExtendedSelfMulticall is ISelfMulticall {
    function getChainId() external view returns (uint256);

    function getBalance(address account) external view returns (uint256);

    function containsBytecode(address account) external view returns (bool);

    function getBlockNumber() external view returns (uint256);

    function getBlockTimestamp() external view returns (uint256);

    function getBlockBasefee() external view returns (uint256);
}
          

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

interface ISelfMulticall {
    function multicall(
        bytes[] calldata data
    ) external returns (bytes[] memory returndata);

    function tryMulticall(
        bytes[] calldata data
    ) external returns (bool[] memory successes, bytes[] memory returndata);
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (access/Ownable.sol)

pragma solidity ^0.8.0;

import "../utils/Context.sol";

/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;

    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);

    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _transferOwnership(_msgSender());
    }

    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        _checkOwner();
        _;
    }

    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }

    /**
     * @dev Throws if the sender is not the owner.
     */
    function _checkOwner() internal view virtual {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
    }

    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby disabling any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _transferOwnership(address(0));
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _transferOwnership(newOwner);
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Internal function without access restriction.
     */
    function _transferOwnership(address newOwner) internal virtual {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.4) (utils/Context.sol)

pragma solidity ^0.8.0;

/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }

    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }

    function _contextSuffixLength() internal view virtual returns (uint256) {
        return 0;
    }
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/Strings.sol)

pragma solidity ^0.8.0;

import "./math/Math.sol";
import "./math/SignedMath.sol";

/**
 * @dev String operations.
 */
library Strings {
    bytes16 private constant _SYMBOLS = "0123456789abcdef";
    uint8 private constant _ADDRESS_LENGTH = 20;

    /**
     * @dev Converts a `uint256` to its ASCII `string` decimal representation.
     */
    function toString(uint256 value) internal pure returns (string memory) {
        unchecked {
            uint256 length = Math.log10(value) + 1;
            string memory buffer = new string(length);
            uint256 ptr;
            /// @solidity memory-safe-assembly
            assembly {
                ptr := add(buffer, add(32, length))
            }
            while (true) {
                ptr--;
                /// @solidity memory-safe-assembly
                assembly {
                    mstore8(ptr, byte(mod(value, 10), _SYMBOLS))
                }
                value /= 10;
                if (value == 0) break;
            }
            return buffer;
        }
    }

    /**
     * @dev Converts a `int256` to its ASCII `string` decimal representation.
     */
    function toString(int256 value) internal pure returns (string memory) {
        return string(abi.encodePacked(value < 0 ? "-" : "", toString(SignedMath.abs(value))));
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation.
     */
    function toHexString(uint256 value) internal pure returns (string memory) {
        unchecked {
            return toHexString(value, Math.log256(value) + 1);
        }
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation with fixed length.
     */
    function toHexString(uint256 value, uint256 length) internal pure returns (string memory) {
        bytes memory buffer = new bytes(2 * length + 2);
        buffer[0] = "0";
        buffer[1] = "x";
        for (uint256 i = 2 * length + 1; i > 1; --i) {
            buffer[i] = _SYMBOLS[value & 0xf];
            value >>= 4;
        }
        require(value == 0, "Strings: hex length insufficient");
        return string(buffer);
    }

    /**
     * @dev Converts an `address` with fixed length of 20 bytes to its not checksummed ASCII `string` hexadecimal representation.
     */
    function toHexString(address addr) internal pure returns (string memory) {
        return toHexString(uint256(uint160(addr)), _ADDRESS_LENGTH);
    }

    /**
     * @dev Returns true if the two strings are equal.
     */
    function equal(string memory a, string memory b) internal pure returns (bool) {
        return keccak256(bytes(a)) == keccak256(bytes(b));
    }
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/cryptography/ECDSA.sol)

pragma solidity ^0.8.0;

import "../Strings.sol";

/**
 * @dev Elliptic Curve Digital Signature Algorithm (ECDSA) operations.
 *
 * These functions can be used to verify that a message was signed by the holder
 * of the private keys of a given address.
 */
library ECDSA {
    enum RecoverError {
        NoError,
        InvalidSignature,
        InvalidSignatureLength,
        InvalidSignatureS,
        InvalidSignatureV // Deprecated in v4.8
    }

    function _throwError(RecoverError error) private pure {
        if (error == RecoverError.NoError) {
            return; // no error: do nothing
        } else if (error == RecoverError.InvalidSignature) {
            revert("ECDSA: invalid signature");
        } else if (error == RecoverError.InvalidSignatureLength) {
            revert("ECDSA: invalid signature length");
        } else if (error == RecoverError.InvalidSignatureS) {
            revert("ECDSA: invalid signature 's' value");
        }
    }

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with
     * `signature` or error string. This address can then be used for verification purposes.
     *
     * The `ecrecover` EVM opcode allows for malleable (non-unique) signatures:
     * this function rejects them by requiring the `s` value to be in the lower
     * half order, and the `v` value to be either 27 or 28.
     *
     * IMPORTANT: `hash` _must_ be the result of a hash operation for the
     * verification to be secure: it is possible to craft signatures that
     * recover to arbitrary addresses for non-hashed data. A safe way to ensure
     * this is by receiving a hash of the original message (which may otherwise
     * be too long), and then calling {toEthSignedMessageHash} on it.
     *
     * Documentation for signature generation:
     * - with https://web3js.readthedocs.io/en/v1.3.4/web3-eth-accounts.html#sign[Web3.js]
     * - with https://docs.ethers.io/v5/api/signer/#Signer-signMessage[ethers]
     *
     * _Available since v4.3._
     */
    function tryRecover(bytes32 hash, bytes memory signature) internal pure returns (address, RecoverError) {
        if (signature.length == 65) {
            bytes32 r;
            bytes32 s;
            uint8 v;
            // ecrecover takes the signature parameters, and the only way to get them
            // currently is to use assembly.
            /// @solidity memory-safe-assembly
            assembly {
                r := mload(add(signature, 0x20))
                s := mload(add(signature, 0x40))
                v := byte(0, mload(add(signature, 0x60)))
            }
            return tryRecover(hash, v, r, s);
        } else {
            return (address(0), RecoverError.InvalidSignatureLength);
        }
    }

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with
     * `signature`. This address can then be used for verification purposes.
     *
     * The `ecrecover` EVM opcode allows for malleable (non-unique) signatures:
     * this function rejects them by requiring the `s` value to be in the lower
     * half order, and the `v` value to be either 27 or 28.
     *
     * IMPORTANT: `hash` _must_ be the result of a hash operation for the
     * verification to be secure: it is possible to craft signatures that
     * recover to arbitrary addresses for non-hashed data. A safe way to ensure
     * this is by receiving a hash of the original message (which may otherwise
     * be too long), and then calling {toEthSignedMessageHash} on it.
     */
    function recover(bytes32 hash, bytes memory signature) internal pure returns (address) {
        (address recovered, RecoverError error) = tryRecover(hash, signature);
        _throwError(error);
        return recovered;
    }

    /**
     * @dev Overload of {ECDSA-tryRecover} that receives the `r` and `vs` short-signature fields separately.
     *
     * See https://eips.ethereum.org/EIPS/eip-2098[EIP-2098 short signatures]
     *
     * _Available since v4.3._
     */
    function tryRecover(bytes32 hash, bytes32 r, bytes32 vs) internal pure returns (address, RecoverError) {
        bytes32 s = vs & bytes32(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff);
        uint8 v = uint8((uint256(vs) >> 255) + 27);
        return tryRecover(hash, v, r, s);
    }

    /**
     * @dev Overload of {ECDSA-recover} that receives the `r and `vs` short-signature fields separately.
     *
     * _Available since v4.2._
     */
    function recover(bytes32 hash, bytes32 r, bytes32 vs) internal pure returns (address) {
        (address recovered, RecoverError error) = tryRecover(hash, r, vs);
        _throwError(error);
        return recovered;
    }

    /**
     * @dev Overload of {ECDSA-tryRecover} that receives the `v`,
     * `r` and `s` signature fields separately.
     *
     * _Available since v4.3._
     */
    function tryRecover(bytes32 hash, uint8 v, bytes32 r, bytes32 s) internal pure returns (address, RecoverError) {
        // EIP-2 still allows signature malleability for ecrecover(). Remove this possibility and make the signature
        // unique. Appendix F in the Ethereum Yellow paper (https://ethereum.github.io/yellowpaper/paper.pdf), defines
        // the valid range for s in (301): 0 < s < secp256k1n ÷ 2 + 1, and for v in (302): v ∈ {27, 28}. Most
        // signatures from current libraries generate a unique signature with an s-value in the lower half order.
        //
        // If your library generates malleable signatures, such as s-values in the upper range, calculate a new s-value
        // with 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 - s1 and flip v from 27 to 28 or
        // vice versa. If your library also generates signatures with 0/1 for v instead 27/28, add 27 to v to accept
        // these malleable signatures as well.
        if (uint256(s) > 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0) {
            return (address(0), RecoverError.InvalidSignatureS);
        }

        // If the signature is valid (and not malleable), return the signer address
        address signer = ecrecover(hash, v, r, s);
        if (signer == address(0)) {
            return (address(0), RecoverError.InvalidSignature);
        }

        return (signer, RecoverError.NoError);
    }

    /**
     * @dev Overload of {ECDSA-recover} that receives the `v`,
     * `r` and `s` signature fields separately.
     */
    function recover(bytes32 hash, uint8 v, bytes32 r, bytes32 s) internal pure returns (address) {
        (address recovered, RecoverError error) = tryRecover(hash, v, r, s);
        _throwError(error);
        return recovered;
    }

    /**
     * @dev Returns an Ethereum Signed Message, created from a `hash`. This
     * produces hash corresponding to the one signed with the
     * https://eth.wiki/json-rpc/API#eth_sign[`eth_sign`]
     * JSON-RPC method as part of EIP-191.
     *
     * See {recover}.
     */
    function toEthSignedMessageHash(bytes32 hash) internal pure returns (bytes32 message) {
        // 32 is the length in bytes of hash,
        // enforced by the type signature above
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x00, "\x19Ethereum Signed Message:\n32")
            mstore(0x1c, hash)
            message := keccak256(0x00, 0x3c)
        }
    }

    /**
     * @dev Returns an Ethereum Signed Message, created from `s`. This
     * produces hash corresponding to the one signed with the
     * https://eth.wiki/json-rpc/API#eth_sign[`eth_sign`]
     * JSON-RPC method as part of EIP-191.
     *
     * See {recover}.
     */
    function toEthSignedMessageHash(bytes memory s) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked("\x19Ethereum Signed Message:\n", Strings.toString(s.length), s));
    }

    /**
     * @dev Returns an Ethereum Signed Typed Data, created from a
     * `domainSeparator` and a `structHash`. This produces hash corresponding
     * to the one signed with the
     * https://eips.ethereum.org/EIPS/eip-712[`eth_signTypedData`]
     * JSON-RPC method as part of EIP-712.
     *
     * See {recover}.
     */
    function toTypedDataHash(bytes32 domainSeparator, bytes32 structHash) internal pure returns (bytes32 data) {
        /// @solidity memory-safe-assembly
        assembly {
            let ptr := mload(0x40)
            mstore(ptr, "\x19\x01")
            mstore(add(ptr, 0x02), domainSeparator)
            mstore(add(ptr, 0x22), structHash)
            data := keccak256(ptr, 0x42)
        }
    }

    /**
     * @dev Returns an Ethereum Signed Data with intended validator, created from a
     * `validator` and `data` according to the version 0 of EIP-191.
     *
     * See {recover}.
     */
    function toDataWithIntendedValidatorHash(address validator, bytes memory data) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked("\x19\x00", validator, data));
    }
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.2) (utils/cryptography/MerkleProof.sol)

pragma solidity ^0.8.0;

/**
 * @dev These functions deal with verification of Merkle Tree proofs.
 *
 * The tree and the proofs can be generated using our
 * https://github.com/OpenZeppelin/merkle-tree[JavaScript library].
 * You will find a quickstart guide in the readme.
 *
 * WARNING: You should avoid using leaf values that are 64 bytes long prior to
 * hashing, or use a hash function other than keccak256 for hashing leaves.
 * This is because the concatenation of a sorted pair of internal nodes in
 * the merkle tree could be reinterpreted as a leaf value.
 * OpenZeppelin's JavaScript library generates merkle trees that are safe
 * against this attack out of the box.
 */
library MerkleProof {
    /**
     * @dev Returns true if a `leaf` can be proved to be a part of a Merkle tree
     * defined by `root`. For this, a `proof` must be provided, containing
     * sibling hashes on the branch from the leaf to the root of the tree. Each
     * pair of leaves and each pair of pre-images are assumed to be sorted.
     */
    function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {
        return processProof(proof, leaf) == root;
    }

    /**
     * @dev Calldata version of {verify}
     *
     * _Available since v4.7._
     */
    function verifyCalldata(bytes32[] calldata proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {
        return processProofCalldata(proof, leaf) == root;
    }

    /**
     * @dev Returns the rebuilt hash obtained by traversing a Merkle tree up
     * from `leaf` using `proof`. A `proof` is valid if and only if the rebuilt
     * hash matches the root of the tree. When processing the proof, the pairs
     * of leafs & pre-images are assumed to be sorted.
     *
     * _Available since v4.4._
     */
    function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
        bytes32 computedHash = leaf;
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }
        return computedHash;
    }

    /**
     * @dev Calldata version of {processProof}
     *
     * _Available since v4.7._
     */
    function processProofCalldata(bytes32[] calldata proof, bytes32 leaf) internal pure returns (bytes32) {
        bytes32 computedHash = leaf;
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }
        return computedHash;
    }

    /**
     * @dev Returns true if the `leaves` can be simultaneously proven to be a part of a merkle tree defined by
     * `root`, according to `proof` and `proofFlags` as described in {processMultiProof}.
     *
     * CAUTION: Not all merkle trees admit multiproofs. See {processMultiProof} for details.
     *
     * _Available since v4.7._
     */
    function multiProofVerify(
        bytes32[] memory proof,
        bool[] memory proofFlags,
        bytes32 root,
        bytes32[] memory leaves
    ) internal pure returns (bool) {
        return processMultiProof(proof, proofFlags, leaves) == root;
    }

    /**
     * @dev Calldata version of {multiProofVerify}
     *
     * CAUTION: Not all merkle trees admit multiproofs. See {processMultiProof} for details.
     *
     * _Available since v4.7._
     */
    function multiProofVerifyCalldata(
        bytes32[] calldata proof,
        bool[] calldata proofFlags,
        bytes32 root,
        bytes32[] memory leaves
    ) internal pure returns (bool) {
        return processMultiProofCalldata(proof, proofFlags, leaves) == root;
    }

    /**
     * @dev Returns the root of a tree reconstructed from `leaves` and sibling nodes in `proof`. The reconstruction
     * proceeds by incrementally reconstructing all inner nodes by combining a leaf/inner node with either another
     * leaf/inner node or a proof sibling node, depending on whether each `proofFlags` item is true or false
     * respectively.
     *
     * CAUTION: Not all merkle trees admit multiproofs. To use multiproofs, it is sufficient to ensure that: 1) the tree
     * is complete (but not necessarily perfect), 2) the leaves to be proven are in the opposite order they are in the
     * tree (i.e., as seen from right to left starting at the deepest layer and continuing at the next layer).
     *
     * _Available since v4.7._
     */
    function processMultiProof(
        bytes32[] memory proof,
        bool[] memory proofFlags,
        bytes32[] memory leaves
    ) internal pure returns (bytes32 merkleRoot) {
        // This function rebuilds the root hash by traversing the tree up from the leaves. The root is rebuilt by
        // consuming and producing values on a queue. The queue starts with the `leaves` array, then goes onto the
        // `hashes` array. At the end of the process, the last hash in the `hashes` array should contain the root of
        // the merkle tree.
        uint256 leavesLen = leaves.length;
        uint256 proofLen = proof.length;
        uint256 totalHashes = proofFlags.length;

        // Check proof validity.
        require(leavesLen + proofLen - 1 == totalHashes, "MerkleProof: invalid multiproof");

        // The xxxPos values are "pointers" to the next value to consume in each array. All accesses are done using
        // `xxx[xxxPos++]`, which return the current value and increment the pointer, thus mimicking a queue's "pop".
        bytes32[] memory hashes = new bytes32[](totalHashes);
        uint256 leafPos = 0;
        uint256 hashPos = 0;
        uint256 proofPos = 0;
        // At each step, we compute the next hash using two values:
        // - a value from the "main queue". If not all leaves have been consumed, we get the next leaf, otherwise we
        //   get the next hash.
        // - depending on the flag, either another value from the "main queue" (merging branches) or an element from the
        //   `proof` array.
        for (uint256 i = 0; i < totalHashes; i++) {
            bytes32 a = leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++];
            bytes32 b = proofFlags[i]
                ? (leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++])
                : proof[proofPos++];
            hashes[i] = _hashPair(a, b);
        }

        if (totalHashes > 0) {
            require(proofPos == proofLen, "MerkleProof: invalid multiproof");
            unchecked {
                return hashes[totalHashes - 1];
            }
        } else if (leavesLen > 0) {
            return leaves[0];
        } else {
            return proof[0];
        }
    }

    /**
     * @dev Calldata version of {processMultiProof}.
     *
     * CAUTION: Not all merkle trees admit multiproofs. See {processMultiProof} for details.
     *
     * _Available since v4.7._
     */
    function processMultiProofCalldata(
        bytes32[] calldata proof,
        bool[] calldata proofFlags,
        bytes32[] memory leaves
    ) internal pure returns (bytes32 merkleRoot) {
        // This function rebuilds the root hash by traversing the tree up from the leaves. The root is rebuilt by
        // consuming and producing values on a queue. The queue starts with the `leaves` array, then goes onto the
        // `hashes` array. At the end of the process, the last hash in the `hashes` array should contain the root of
        // the merkle tree.
        uint256 leavesLen = leaves.length;
        uint256 proofLen = proof.length;
        uint256 totalHashes = proofFlags.length;

        // Check proof validity.
        require(leavesLen + proofLen - 1 == totalHashes, "MerkleProof: invalid multiproof");

        // The xxxPos values are "pointers" to the next value to consume in each array. All accesses are done using
        // `xxx[xxxPos++]`, which return the current value and increment the pointer, thus mimicking a queue's "pop".
        bytes32[] memory hashes = new bytes32[](totalHashes);
        uint256 leafPos = 0;
        uint256 hashPos = 0;
        uint256 proofPos = 0;
        // At each step, we compute the next hash using two values:
        // - a value from the "main queue". If not all leaves have been consumed, we get the next leaf, otherwise we
        //   get the next hash.
        // - depending on the flag, either another value from the "main queue" (merging branches) or an element from the
        //   `proof` array.
        for (uint256 i = 0; i < totalHashes; i++) {
            bytes32 a = leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++];
            bytes32 b = proofFlags[i]
                ? (leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++])
                : proof[proofPos++];
            hashes[i] = _hashPair(a, b);
        }

        if (totalHashes > 0) {
            require(proofPos == proofLen, "MerkleProof: invalid multiproof");
            unchecked {
                return hashes[totalHashes - 1];
            }
        } else if (leavesLen > 0) {
            return leaves[0];
        } else {
            return proof[0];
        }
    }

    function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
        return a < b ? _efficientHash(a, b) : _efficientHash(b, a);
    }

    function _efficientHash(bytes32 a, bytes32 b) private pure returns (bytes32 value) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x00, a)
            mstore(0x20, b)
            value := keccak256(0x00, 0x40)
        }
    }
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/math/Math.sol)

pragma solidity ^0.8.0;

/**
 * @dev Standard math utilities missing in the Solidity language.
 */
library Math {
    enum Rounding {
        Down, // Toward negative infinity
        Up, // Toward infinity
        Zero // Toward zero
    }

    /**
     * @dev Returns the largest of two numbers.
     */
    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        return a > b ? a : b;
    }

    /**
     * @dev Returns the smallest of two numbers.
     */
    function min(uint256 a, uint256 b) internal pure returns (uint256) {
        return a < b ? a : b;
    }

    /**
     * @dev Returns the average of two numbers. The result is rounded towards
     * zero.
     */
    function average(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b) / 2 can overflow.
        return (a & b) + (a ^ b) / 2;
    }

    /**
     * @dev Returns the ceiling of the division of two numbers.
     *
     * This differs from standard division with `/` in that it rounds up instead
     * of rounding down.
     */
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b - 1) / b can overflow on addition, so we distribute.
        return a == 0 ? 0 : (a - 1) / b + 1;
    }

    /**
     * @notice Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
     * @dev Original credit to Remco Bloemen under MIT license (https://xn--2-umb.com/21/muldiv)
     * with further edits by Uniswap Labs also under MIT license.
     */
    function mulDiv(uint256 x, uint256 y, uint256 denominator) internal pure returns (uint256 result) {
        unchecked {
            // 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
            // use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
            // variables such that product = prod1 * 2^256 + prod0.
            uint256 prod0; // Least significant 256 bits of the product
            uint256 prod1; // Most significant 256 bits of the product
            assembly {
                let mm := mulmod(x, y, not(0))
                prod0 := mul(x, y)
                prod1 := sub(sub(mm, prod0), lt(mm, prod0))
            }

            // Handle non-overflow cases, 256 by 256 division.
            if (prod1 == 0) {
                // Solidity will revert if denominator == 0, unlike the div opcode on its own.
                // The surrounding unchecked block does not change this fact.
                // See https://docs.soliditylang.org/en/latest/control-structures.html#checked-or-unchecked-arithmetic.
                return prod0 / denominator;
            }

            // Make sure the result is less than 2^256. Also prevents denominator == 0.
            require(denominator > prod1, "Math: mulDiv overflow");

            ///////////////////////////////////////////////
            // 512 by 256 division.
            ///////////////////////////////////////////////

            // Make division exact by subtracting the remainder from [prod1 prod0].
            uint256 remainder;
            assembly {
                // Compute remainder using mulmod.
                remainder := mulmod(x, y, denominator)

                // Subtract 256 bit number from 512 bit number.
                prod1 := sub(prod1, gt(remainder, prod0))
                prod0 := sub(prod0, remainder)
            }

            // Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
            // See https://cs.stackexchange.com/q/138556/92363.

            // Does not overflow because the denominator cannot be zero at this stage in the function.
            uint256 twos = denominator & (~denominator + 1);
            assembly {
                // Divide denominator by twos.
                denominator := div(denominator, twos)

                // Divide [prod1 prod0] by twos.
                prod0 := div(prod0, twos)

                // Flip twos such that it is 2^256 / twos. If twos is zero, then it becomes one.
                twos := add(div(sub(0, twos), twos), 1)
            }

            // Shift in bits from prod1 into prod0.
            prod0 |= prod1 * twos;

            // Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
            // that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
            // four bits. That is, denominator * inv = 1 mod 2^4.
            uint256 inverse = (3 * denominator) ^ 2;

            // Use the Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also works
            // in modular arithmetic, doubling the correct bits in each step.
            inverse *= 2 - denominator * inverse; // inverse mod 2^8
            inverse *= 2 - denominator * inverse; // inverse mod 2^16
            inverse *= 2 - denominator * inverse; // inverse mod 2^32
            inverse *= 2 - denominator * inverse; // inverse mod 2^64
            inverse *= 2 - denominator * inverse; // inverse mod 2^128
            inverse *= 2 - denominator * inverse; // inverse mod 2^256

            // Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
            // This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
            // less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
            // is no longer required.
            result = prod0 * inverse;
            return result;
        }
    }

    /**
     * @notice Calculates x * y / denominator with full precision, following the selected rounding direction.
     */
    function mulDiv(uint256 x, uint256 y, uint256 denominator, Rounding rounding) internal pure returns (uint256) {
        uint256 result = mulDiv(x, y, denominator);
        if (rounding == Rounding.Up && mulmod(x, y, denominator) > 0) {
            result += 1;
        }
        return result;
    }

    /**
     * @dev Returns the square root of a number. If the number is not a perfect square, the value is rounded down.
     *
     * Inspired by Henry S. Warren, Jr.'s "Hacker's Delight" (Chapter 11).
     */
    function sqrt(uint256 a) internal pure returns (uint256) {
        if (a == 0) {
            return 0;
        }

        // For our first guess, we get the biggest power of 2 which is smaller than the square root of the target.
        //
        // We know that the "msb" (most significant bit) of our target number `a` is a power of 2 such that we have
        // `msb(a) <= a < 2*msb(a)`. This value can be written `msb(a)=2**k` with `k=log2(a)`.
        //
        // This can be rewritten `2**log2(a) <= a < 2**(log2(a) + 1)`
        // → `sqrt(2**k) <= sqrt(a) < sqrt(2**(k+1))`
        // → `2**(k/2) <= sqrt(a) < 2**((k+1)/2) <= 2**(k/2 + 1)`
        //
        // Consequently, `2**(log2(a) / 2)` is a good first approximation of `sqrt(a)` with at least 1 correct bit.
        uint256 result = 1 << (log2(a) >> 1);

        // At this point `result` is an estimation with one bit of precision. We know the true value is a uint128,
        // since it is the square root of a uint256. Newton's method converges quadratically (precision doubles at
        // every iteration). We thus need at most 7 iteration to turn our partial result with one bit of precision
        // into the expected uint128 result.
        unchecked {
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            return min(result, a / result);
        }
    }

    /**
     * @notice Calculates sqrt(a), following the selected rounding direction.
     */
    function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = sqrt(a);
            return result + (rounding == Rounding.Up && result * result < a ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 2, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 128;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 64;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 32;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 16;
            }
            if (value >> 8 > 0) {
                value >>= 8;
                result += 8;
            }
            if (value >> 4 > 0) {
                value >>= 4;
                result += 4;
            }
            if (value >> 2 > 0) {
                value >>= 2;
                result += 2;
            }
            if (value >> 1 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 2, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log2(value);
            return result + (rounding == Rounding.Up && 1 << result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 10, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >= 10 ** 64) {
                value /= 10 ** 64;
                result += 64;
            }
            if (value >= 10 ** 32) {
                value /= 10 ** 32;
                result += 32;
            }
            if (value >= 10 ** 16) {
                value /= 10 ** 16;
                result += 16;
            }
            if (value >= 10 ** 8) {
                value /= 10 ** 8;
                result += 8;
            }
            if (value >= 10 ** 4) {
                value /= 10 ** 4;
                result += 4;
            }
            if (value >= 10 ** 2) {
                value /= 10 ** 2;
                result += 2;
            }
            if (value >= 10 ** 1) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 10, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log10(value);
            return result + (rounding == Rounding.Up && 10 ** result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 256, rounded down, of a positive value.
     * Returns 0 if given 0.
     *
     * Adding one to the result gives the number of pairs of hex symbols needed to represent `value` as a hex string.
     */
    function log256(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 16;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 8;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 4;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 2;
            }
            if (value >> 8 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 256, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log256(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log256(value);
            return result + (rounding == Rounding.Up && 1 << (result << 3) < value ? 1 : 0);
        }
    }
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (utils/math/SafeCast.sol)
// This file was procedurally generated from scripts/generate/templates/SafeCast.js.

pragma solidity ^0.8.0;

/**
 * @dev Wrappers over Solidity's uintXX/intXX casting operators with added overflow
 * checks.
 *
 * Downcasting from uint256/int256 in Solidity does not revert on overflow. This can
 * easily result in undesired exploitation or bugs, since developers usually
 * assume that overflows raise errors. `SafeCast` restores this intuition by
 * reverting the transaction when such an operation overflows.
 *
 * Using this library instead of the unchecked operations eliminates an entire
 * class of bugs, so it's recommended to use it always.
 *
 * Can be combined with {SafeMath} and {SignedSafeMath} to extend it to smaller types, by performing
 * all math on `uint256` and `int256` and then downcasting.
 */
library SafeCast {
    /**
     * @dev Returns the downcasted uint248 from uint256, reverting on
     * overflow (when the input is greater than largest uint248).
     *
     * Counterpart to Solidity's `uint248` operator.
     *
     * Requirements:
     *
     * - input must fit into 248 bits
     *
     * _Available since v4.7._
     */
    function toUint248(uint256 value) internal pure returns (uint248) {
        require(value <= type(uint248).max, "SafeCast: value doesn't fit in 248 bits");
        return uint248(value);
    }

    /**
     * @dev Returns the downcasted uint240 from uint256, reverting on
     * overflow (when the input is greater than largest uint240).
     *
     * Counterpart to Solidity's `uint240` operator.
     *
     * Requirements:
     *
     * - input must fit into 240 bits
     *
     * _Available since v4.7._
     */
    function toUint240(uint256 value) internal pure returns (uint240) {
        require(value <= type(uint240).max, "SafeCast: value doesn't fit in 240 bits");
        return uint240(value);
    }

    /**
     * @dev Returns the downcasted uint232 from uint256, reverting on
     * overflow (when the input is greater than largest uint232).
     *
     * Counterpart to Solidity's `uint232` operator.
     *
     * Requirements:
     *
     * - input must fit into 232 bits
     *
     * _Available since v4.7._
     */
    function toUint232(uint256 value) internal pure returns (uint232) {
        require(value <= type(uint232).max, "SafeCast: value doesn't fit in 232 bits");
        return uint232(value);
    }

    /**
     * @dev Returns the downcasted uint224 from uint256, reverting on
     * overflow (when the input is greater than largest uint224).
     *
     * Counterpart to Solidity's `uint224` operator.
     *
     * Requirements:
     *
     * - input must fit into 224 bits
     *
     * _Available since v4.2._
     */
    function toUint224(uint256 value) internal pure returns (uint224) {
        require(value <= type(uint224).max, "SafeCast: value doesn't fit in 224 bits");
        return uint224(value);
    }

    /**
     * @dev Returns the downcasted uint216 from uint256, reverting on
     * overflow (when the input is greater than largest uint216).
     *
     * Counterpart to Solidity's `uint216` operator.
     *
     * Requirements:
     *
     * - input must fit into 216 bits
     *
     * _Available since v4.7._
     */
    function toUint216(uint256 value) internal pure returns (uint216) {
        require(value <= type(uint216).max, "SafeCast: value doesn't fit in 216 bits");
        return uint216(value);
    }

    /**
     * @dev Returns the downcasted uint208 from uint256, reverting on
     * overflow (when the input is greater than largest uint208).
     *
     * Counterpart to Solidity's `uint208` operator.
     *
     * Requirements:
     *
     * - input must fit into 208 bits
     *
     * _Available since v4.7._
     */
    function toUint208(uint256 value) internal pure returns (uint208) {
        require(value <= type(uint208).max, "SafeCast: value doesn't fit in 208 bits");
        return uint208(value);
    }

    /**
     * @dev Returns the downcasted uint200 from uint256, reverting on
     * overflow (when the input is greater than largest uint200).
     *
     * Counterpart to Solidity's `uint200` operator.
     *
     * Requirements:
     *
     * - input must fit into 200 bits
     *
     * _Available since v4.7._
     */
    function toUint200(uint256 value) internal pure returns (uint200) {
        require(value <= type(uint200).max, "SafeCast: value doesn't fit in 200 bits");
        return uint200(value);
    }

    /**
     * @dev Returns the downcasted uint192 from uint256, reverting on
     * overflow (when the input is greater than largest uint192).
     *
     * Counterpart to Solidity's `uint192` operator.
     *
     * Requirements:
     *
     * - input must fit into 192 bits
     *
     * _Available since v4.7._
     */
    function toUint192(uint256 value) internal pure returns (uint192) {
        require(value <= type(uint192).max, "SafeCast: value doesn't fit in 192 bits");
        return uint192(value);
    }

    /**
     * @dev Returns the downcasted uint184 from uint256, reverting on
     * overflow (when the input is greater than largest uint184).
     *
     * Counterpart to Solidity's `uint184` operator.
     *
     * Requirements:
     *
     * - input must fit into 184 bits
     *
     * _Available since v4.7._
     */
    function toUint184(uint256 value) internal pure returns (uint184) {
        require(value <= type(uint184).max, "SafeCast: value doesn't fit in 184 bits");
        return uint184(value);
    }

    /**
     * @dev Returns the downcasted uint176 from uint256, reverting on
     * overflow (when the input is greater than largest uint176).
     *
     * Counterpart to Solidity's `uint176` operator.
     *
     * Requirements:
     *
     * - input must fit into 176 bits
     *
     * _Available since v4.7._
     */
    function toUint176(uint256 value) internal pure returns (uint176) {
        require(value <= type(uint176).max, "SafeCast: value doesn't fit in 176 bits");
        return uint176(value);
    }

    /**
     * @dev Returns the downcasted uint168 from uint256, reverting on
     * overflow (when the input is greater than largest uint168).
     *
     * Counterpart to Solidity's `uint168` operator.
     *
     * Requirements:
     *
     * - input must fit into 168 bits
     *
     * _Available since v4.7._
     */
    function toUint168(uint256 value) internal pure returns (uint168) {
        require(value <= type(uint168).max, "SafeCast: value doesn't fit in 168 bits");
        return uint168(value);
    }

    /**
     * @dev Returns the downcasted uint160 from uint256, reverting on
     * overflow (when the input is greater than largest uint160).
     *
     * Counterpart to Solidity's `uint160` operator.
     *
     * Requirements:
     *
     * - input must fit into 160 bits
     *
     * _Available since v4.7._
     */
    function toUint160(uint256 value) internal pure returns (uint160) {
        require(value <= type(uint160).max, "SafeCast: value doesn't fit in 160 bits");
        return uint160(value);
    }

    /**
     * @dev Returns the downcasted uint152 from uint256, reverting on
     * overflow (when the input is greater than largest uint152).
     *
     * Counterpart to Solidity's `uint152` operator.
     *
     * Requirements:
     *
     * - input must fit into 152 bits
     *
     * _Available since v4.7._
     */
    function toUint152(uint256 value) internal pure returns (uint152) {
        require(value <= type(uint152).max, "SafeCast: value doesn't fit in 152 bits");
        return uint152(value);
    }

    /**
     * @dev Returns the downcasted uint144 from uint256, reverting on
     * overflow (when the input is greater than largest uint144).
     *
     * Counterpart to Solidity's `uint144` operator.
     *
     * Requirements:
     *
     * - input must fit into 144 bits
     *
     * _Available since v4.7._
     */
    function toUint144(uint256 value) internal pure returns (uint144) {
        require(value <= type(uint144).max, "SafeCast: value doesn't fit in 144 bits");
        return uint144(value);
    }

    /**
     * @dev Returns the downcasted uint136 from uint256, reverting on
     * overflow (when the input is greater than largest uint136).
     *
     * Counterpart to Solidity's `uint136` operator.
     *
     * Requirements:
     *
     * - input must fit into 136 bits
     *
     * _Available since v4.7._
     */
    function toUint136(uint256 value) internal pure returns (uint136) {
        require(value <= type(uint136).max, "SafeCast: value doesn't fit in 136 bits");
        return uint136(value);
    }

    /**
     * @dev Returns the downcasted uint128 from uint256, reverting on
     * overflow (when the input is greater than largest uint128).
     *
     * Counterpart to Solidity's `uint128` operator.
     *
     * Requirements:
     *
     * - input must fit into 128 bits
     *
     * _Available since v2.5._
     */
    function toUint128(uint256 value) internal pure returns (uint128) {
        require(value <= type(uint128).max, "SafeCast: value doesn't fit in 128 bits");
        return uint128(value);
    }

    /**
     * @dev Returns the downcasted uint120 from uint256, reverting on
     * overflow (when the input is greater than largest uint120).
     *
     * Counterpart to Solidity's `uint120` operator.
     *
     * Requirements:
     *
     * - input must fit into 120 bits
     *
     * _Available since v4.7._
     */
    function toUint120(uint256 value) internal pure returns (uint120) {
        require(value <= type(uint120).max, "SafeCast: value doesn't fit in 120 bits");
        return uint120(value);
    }

    /**
     * @dev Returns the downcasted uint112 from uint256, reverting on
     * overflow (when the input is greater than largest uint112).
     *
     * Counterpart to Solidity's `uint112` operator.
     *
     * Requirements:
     *
     * - input must fit into 112 bits
     *
     * _Available since v4.7._
     */
    function toUint112(uint256 value) internal pure returns (uint112) {
        require(value <= type(uint112).max, "SafeCast: value doesn't fit in 112 bits");
        return uint112(value);
    }

    /**
     * @dev Returns the downcasted uint104 from uint256, reverting on
     * overflow (when the input is greater than largest uint104).
     *
     * Counterpart to Solidity's `uint104` operator.
     *
     * Requirements:
     *
     * - input must fit into 104 bits
     *
     * _Available since v4.7._
     */
    function toUint104(uint256 value) internal pure returns (uint104) {
        require(value <= type(uint104).max, "SafeCast: value doesn't fit in 104 bits");
        return uint104(value);
    }

    /**
     * @dev Returns the downcasted uint96 from uint256, reverting on
     * overflow (when the input is greater than largest uint96).
     *
     * Counterpart to Solidity's `uint96` operator.
     *
     * Requirements:
     *
     * - input must fit into 96 bits
     *
     * _Available since v4.2._
     */
    function toUint96(uint256 value) internal pure returns (uint96) {
        require(value <= type(uint96).max, "SafeCast: value doesn't fit in 96 bits");
        return uint96(value);
    }

    /**
     * @dev Returns the downcasted uint88 from uint256, reverting on
     * overflow (when the input is greater than largest uint88).
     *
     * Counterpart to Solidity's `uint88` operator.
     *
     * Requirements:
     *
     * - input must fit into 88 bits
     *
     * _Available since v4.7._
     */
    function toUint88(uint256 value) internal pure returns (uint88) {
        require(value <= type(uint88).max, "SafeCast: value doesn't fit in 88 bits");
        return uint88(value);
    }

    /**
     * @dev Returns the downcasted uint80 from uint256, reverting on
     * overflow (when the input is greater than largest uint80).
     *
     * Counterpart to Solidity's `uint80` operator.
     *
     * Requirements:
     *
     * - input must fit into 80 bits
     *
     * _Available since v4.7._
     */
    function toUint80(uint256 value) internal pure returns (uint80) {
        require(value <= type(uint80).max, "SafeCast: value doesn't fit in 80 bits");
        return uint80(value);
    }

    /**
     * @dev Returns the downcasted uint72 from uint256, reverting on
     * overflow (when the input is greater than largest uint72).
     *
     * Counterpart to Solidity's `uint72` operator.
     *
     * Requirements:
     *
     * - input must fit into 72 bits
     *
     * _Available since v4.7._
     */
    function toUint72(uint256 value) internal pure returns (uint72) {
        require(value <= type(uint72).max, "SafeCast: value doesn't fit in 72 bits");
        return uint72(value);
    }

    /**
     * @dev Returns the downcasted uint64 from uint256, reverting on
     * overflow (when the input is greater than largest uint64).
     *
     * Counterpart to Solidity's `uint64` operator.
     *
     * Requirements:
     *
     * - input must fit into 64 bits
     *
     * _Available since v2.5._
     */
    function toUint64(uint256 value) internal pure returns (uint64) {
        require(value <= type(uint64).max, "SafeCast: value doesn't fit in 64 bits");
        return uint64(value);
    }

    /**
     * @dev Returns the downcasted uint56 from uint256, reverting on
     * overflow (when the input is greater than largest uint56).
     *
     * Counterpart to Solidity's `uint56` operator.
     *
     * Requirements:
     *
     * - input must fit into 56 bits
     *
     * _Available since v4.7._
     */
    function toUint56(uint256 value) internal pure returns (uint56) {
        require(value <= type(uint56).max, "SafeCast: value doesn't fit in 56 bits");
        return uint56(value);
    }

    /**
     * @dev Returns the downcasted uint48 from uint256, reverting on
     * overflow (when the input is greater than largest uint48).
     *
     * Counterpart to Solidity's `uint48` operator.
     *
     * Requirements:
     *
     * - input must fit into 48 bits
     *
     * _Available since v4.7._
     */
    function toUint48(uint256 value) internal pure returns (uint48) {
        require(value <= type(uint48).max, "SafeCast: value doesn't fit in 48 bits");
        return uint48(value);
    }

    /**
     * @dev Returns the downcasted uint40 from uint256, reverting on
     * overflow (when the input is greater than largest uint40).
     *
     * Counterpart to Solidity's `uint40` operator.
     *
     * Requirements:
     *
     * - input must fit into 40 bits
     *
     * _Available since v4.7._
     */
    function toUint40(uint256 value) internal pure returns (uint40) {
        require(value <= type(uint40).max, "SafeCast: value doesn't fit in 40 bits");
        return uint40(value);
    }

    /**
     * @dev Returns the downcasted uint32 from uint256, reverting on
     * overflow (when the input is greater than largest uint32).
     *
     * Counterpart to Solidity's `uint32` operator.
     *
     * Requirements:
     *
     * - input must fit into 32 bits
     *
     * _Available since v2.5._
     */
    function toUint32(uint256 value) internal pure returns (uint32) {
        require(value <= type(uint32).max, "SafeCast: value doesn't fit in 32 bits");
        return uint32(value);
    }

    /**
     * @dev Returns the downcasted uint24 from uint256, reverting on
     * overflow (when the input is greater than largest uint24).
     *
     * Counterpart to Solidity's `uint24` operator.
     *
     * Requirements:
     *
     * - input must fit into 24 bits
     *
     * _Available since v4.7._
     */
    function toUint24(uint256 value) internal pure returns (uint24) {
        require(value <= type(uint24).max, "SafeCast: value doesn't fit in 24 bits");
        return uint24(value);
    }

    /**
     * @dev Returns the downcasted uint16 from uint256, reverting on
     * overflow (when the input is greater than largest uint16).
     *
     * Counterpart to Solidity's `uint16` operator.
     *
     * Requirements:
     *
     * - input must fit into 16 bits
     *
     * _Available since v2.5._
     */
    function toUint16(uint256 value) internal pure returns (uint16) {
        require(value <= type(uint16).max, "SafeCast: value doesn't fit in 16 bits");
        return uint16(value);
    }

    /**
     * @dev Returns the downcasted uint8 from uint256, reverting on
     * overflow (when the input is greater than largest uint8).
     *
     * Counterpart to Solidity's `uint8` operator.
     *
     * Requirements:
     *
     * - input must fit into 8 bits
     *
     * _Available since v2.5._
     */
    function toUint8(uint256 value) internal pure returns (uint8) {
        require(value <= type(uint8).max, "SafeCast: value doesn't fit in 8 bits");
        return uint8(value);
    }

    /**
     * @dev Converts a signed int256 into an unsigned uint256.
     *
     * Requirements:
     *
     * - input must be greater than or equal to 0.
     *
     * _Available since v3.0._
     */
    function toUint256(int256 value) internal pure returns (uint256) {
        require(value >= 0, "SafeCast: value must be positive");
        return uint256(value);
    }

    /**
     * @dev Returns the downcasted int248 from int256, reverting on
     * overflow (when the input is less than smallest int248 or
     * greater than largest int248).
     *
     * Counterpart to Solidity's `int248` operator.
     *
     * Requirements:
     *
     * - input must fit into 248 bits
     *
     * _Available since v4.7._
     */
    function toInt248(int256 value) internal pure returns (int248 downcasted) {
        downcasted = int248(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 248 bits");
    }

    /**
     * @dev Returns the downcasted int240 from int256, reverting on
     * overflow (when the input is less than smallest int240 or
     * greater than largest int240).
     *
     * Counterpart to Solidity's `int240` operator.
     *
     * Requirements:
     *
     * - input must fit into 240 bits
     *
     * _Available since v4.7._
     */
    function toInt240(int256 value) internal pure returns (int240 downcasted) {
        downcasted = int240(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 240 bits");
    }

    /**
     * @dev Returns the downcasted int232 from int256, reverting on
     * overflow (when the input is less than smallest int232 or
     * greater than largest int232).
     *
     * Counterpart to Solidity's `int232` operator.
     *
     * Requirements:
     *
     * - input must fit into 232 bits
     *
     * _Available since v4.7._
     */
    function toInt232(int256 value) internal pure returns (int232 downcasted) {
        downcasted = int232(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 232 bits");
    }

    /**
     * @dev Returns the downcasted int224 from int256, reverting on
     * overflow (when the input is less than smallest int224 or
     * greater than largest int224).
     *
     * Counterpart to Solidity's `int224` operator.
     *
     * Requirements:
     *
     * - input must fit into 224 bits
     *
     * _Available since v4.7._
     */
    function toInt224(int256 value) internal pure returns (int224 downcasted) {
        downcasted = int224(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 224 bits");
    }

    /**
     * @dev Returns the downcasted int216 from int256, reverting on
     * overflow (when the input is less than smallest int216 or
     * greater than largest int216).
     *
     * Counterpart to Solidity's `int216` operator.
     *
     * Requirements:
     *
     * - input must fit into 216 bits
     *
     * _Available since v4.7._
     */
    function toInt216(int256 value) internal pure returns (int216 downcasted) {
        downcasted = int216(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 216 bits");
    }

    /**
     * @dev Returns the downcasted int208 from int256, reverting on
     * overflow (when the input is less than smallest int208 or
     * greater than largest int208).
     *
     * Counterpart to Solidity's `int208` operator.
     *
     * Requirements:
     *
     * - input must fit into 208 bits
     *
     * _Available since v4.7._
     */
    function toInt208(int256 value) internal pure returns (int208 downcasted) {
        downcasted = int208(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 208 bits");
    }

    /**
     * @dev Returns the downcasted int200 from int256, reverting on
     * overflow (when the input is less than smallest int200 or
     * greater than largest int200).
     *
     * Counterpart to Solidity's `int200` operator.
     *
     * Requirements:
     *
     * - input must fit into 200 bits
     *
     * _Available since v4.7._
     */
    function toInt200(int256 value) internal pure returns (int200 downcasted) {
        downcasted = int200(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 200 bits");
    }

    /**
     * @dev Returns the downcasted int192 from int256, reverting on
     * overflow (when the input is less than smallest int192 or
     * greater than largest int192).
     *
     * Counterpart to Solidity's `int192` operator.
     *
     * Requirements:
     *
     * - input must fit into 192 bits
     *
     * _Available since v4.7._
     */
    function toInt192(int256 value) internal pure returns (int192 downcasted) {
        downcasted = int192(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 192 bits");
    }

    /**
     * @dev Returns the downcasted int184 from int256, reverting on
     * overflow (when the input is less than smallest int184 or
     * greater than largest int184).
     *
     * Counterpart to Solidity's `int184` operator.
     *
     * Requirements:
     *
     * - input must fit into 184 bits
     *
     * _Available since v4.7._
     */
    function toInt184(int256 value) internal pure returns (int184 downcasted) {
        downcasted = int184(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 184 bits");
    }

    /**
     * @dev Returns the downcasted int176 from int256, reverting on
     * overflow (when the input is less than smallest int176 or
     * greater than largest int176).
     *
     * Counterpart to Solidity's `int176` operator.
     *
     * Requirements:
     *
     * - input must fit into 176 bits
     *
     * _Available since v4.7._
     */
    function toInt176(int256 value) internal pure returns (int176 downcasted) {
        downcasted = int176(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 176 bits");
    }

    /**
     * @dev Returns the downcasted int168 from int256, reverting on
     * overflow (when the input is less than smallest int168 or
     * greater than largest int168).
     *
     * Counterpart to Solidity's `int168` operator.
     *
     * Requirements:
     *
     * - input must fit into 168 bits
     *
     * _Available since v4.7._
     */
    function toInt168(int256 value) internal pure returns (int168 downcasted) {
        downcasted = int168(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 168 bits");
    }

    /**
     * @dev Returns the downcasted int160 from int256, reverting on
     * overflow (when the input is less than smallest int160 or
     * greater than largest int160).
     *
     * Counterpart to Solidity's `int160` operator.
     *
     * Requirements:
     *
     * - input must fit into 160 bits
     *
     * _Available since v4.7._
     */
    function toInt160(int256 value) internal pure returns (int160 downcasted) {
        downcasted = int160(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 160 bits");
    }

    /**
     * @dev Returns the downcasted int152 from int256, reverting on
     * overflow (when the input is less than smallest int152 or
     * greater than largest int152).
     *
     * Counterpart to Solidity's `int152` operator.
     *
     * Requirements:
     *
     * - input must fit into 152 bits
     *
     * _Available since v4.7._
     */
    function toInt152(int256 value) internal pure returns (int152 downcasted) {
        downcasted = int152(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 152 bits");
    }

    /**
     * @dev Returns the downcasted int144 from int256, reverting on
     * overflow (when the input is less than smallest int144 or
     * greater than largest int144).
     *
     * Counterpart to Solidity's `int144` operator.
     *
     * Requirements:
     *
     * - input must fit into 144 bits
     *
     * _Available since v4.7._
     */
    function toInt144(int256 value) internal pure returns (int144 downcasted) {
        downcasted = int144(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 144 bits");
    }

    /**
     * @dev Returns the downcasted int136 from int256, reverting on
     * overflow (when the input is less than smallest int136 or
     * greater than largest int136).
     *
     * Counterpart to Solidity's `int136` operator.
     *
     * Requirements:
     *
     * - input must fit into 136 bits
     *
     * _Available since v4.7._
     */
    function toInt136(int256 value) internal pure returns (int136 downcasted) {
        downcasted = int136(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 136 bits");
    }

    /**
     * @dev Returns the downcasted int128 from int256, reverting on
     * overflow (when the input is less than smallest int128 or
     * greater than largest int128).
     *
     * Counterpart to Solidity's `int128` operator.
     *
     * Requirements:
     *
     * - input must fit into 128 bits
     *
     * _Available since v3.1._
     */
    function toInt128(int256 value) internal pure returns (int128 downcasted) {
        downcasted = int128(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 128 bits");
    }

    /**
     * @dev Returns the downcasted int120 from int256, reverting on
     * overflow (when the input is less than smallest int120 or
     * greater than largest int120).
     *
     * Counterpart to Solidity's `int120` operator.
     *
     * Requirements:
     *
     * - input must fit into 120 bits
     *
     * _Available since v4.7._
     */
    function toInt120(int256 value) internal pure returns (int120 downcasted) {
        downcasted = int120(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 120 bits");
    }

    /**
     * @dev Returns the downcasted int112 from int256, reverting on
     * overflow (when the input is less than smallest int112 or
     * greater than largest int112).
     *
     * Counterpart to Solidity's `int112` operator.
     *
     * Requirements:
     *
     * - input must fit into 112 bits
     *
     * _Available since v4.7._
     */
    function toInt112(int256 value) internal pure returns (int112 downcasted) {
        downcasted = int112(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 112 bits");
    }

    /**
     * @dev Returns the downcasted int104 from int256, reverting on
     * overflow (when the input is less than smallest int104 or
     * greater than largest int104).
     *
     * Counterpart to Solidity's `int104` operator.
     *
     * Requirements:
     *
     * - input must fit into 104 bits
     *
     * _Available since v4.7._
     */
    function toInt104(int256 value) internal pure returns (int104 downcasted) {
        downcasted = int104(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 104 bits");
    }

    /**
     * @dev Returns the downcasted int96 from int256, reverting on
     * overflow (when the input is less than smallest int96 or
     * greater than largest int96).
     *
     * Counterpart to Solidity's `int96` operator.
     *
     * Requirements:
     *
     * - input must fit into 96 bits
     *
     * _Available since v4.7._
     */
    function toInt96(int256 value) internal pure returns (int96 downcasted) {
        downcasted = int96(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 96 bits");
    }

    /**
     * @dev Returns the downcasted int88 from int256, reverting on
     * overflow (when the input is less than smallest int88 or
     * greater than largest int88).
     *
     * Counterpart to Solidity's `int88` operator.
     *
     * Requirements:
     *
     * - input must fit into 88 bits
     *
     * _Available since v4.7._
     */
    function toInt88(int256 value) internal pure returns (int88 downcasted) {
        downcasted = int88(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 88 bits");
    }

    /**
     * @dev Returns the downcasted int80 from int256, reverting on
     * overflow (when the input is less than smallest int80 or
     * greater than largest int80).
     *
     * Counterpart to Solidity's `int80` operator.
     *
     * Requirements:
     *
     * - input must fit into 80 bits
     *
     * _Available since v4.7._
     */
    function toInt80(int256 value) internal pure returns (int80 downcasted) {
        downcasted = int80(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 80 bits");
    }

    /**
     * @dev Returns the downcasted int72 from int256, reverting on
     * overflow (when the input is less than smallest int72 or
     * greater than largest int72).
     *
     * Counterpart to Solidity's `int72` operator.
     *
     * Requirements:
     *
     * - input must fit into 72 bits
     *
     * _Available since v4.7._
     */
    function toInt72(int256 value) internal pure returns (int72 downcasted) {
        downcasted = int72(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 72 bits");
    }

    /**
     * @dev Returns the downcasted int64 from int256, reverting on
     * overflow (when the input is less than smallest int64 or
     * greater than largest int64).
     *
     * Counterpart to Solidity's `int64` operator.
     *
     * Requirements:
     *
     * - input must fit into 64 bits
     *
     * _Available since v3.1._
     */
    function toInt64(int256 value) internal pure returns (int64 downcasted) {
        downcasted = int64(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 64 bits");
    }

    /**
     * @dev Returns the downcasted int56 from int256, reverting on
     * overflow (when the input is less than smallest int56 or
     * greater than largest int56).
     *
     * Counterpart to Solidity's `int56` operator.
     *
     * Requirements:
     *
     * - input must fit into 56 bits
     *
     * _Available since v4.7._
     */
    function toInt56(int256 value) internal pure returns (int56 downcasted) {
        downcasted = int56(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 56 bits");
    }

    /**
     * @dev Returns the downcasted int48 from int256, reverting on
     * overflow (when the input is less than smallest int48 or
     * greater than largest int48).
     *
     * Counterpart to Solidity's `int48` operator.
     *
     * Requirements:
     *
     * - input must fit into 48 bits
     *
     * _Available since v4.7._
     */
    function toInt48(int256 value) internal pure returns (int48 downcasted) {
        downcasted = int48(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 48 bits");
    }

    /**
     * @dev Returns the downcasted int40 from int256, reverting on
     * overflow (when the input is less than smallest int40 or
     * greater than largest int40).
     *
     * Counterpart to Solidity's `int40` operator.
     *
     * Requirements:
     *
     * - input must fit into 40 bits
     *
     * _Available since v4.7._
     */
    function toInt40(int256 value) internal pure returns (int40 downcasted) {
        downcasted = int40(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 40 bits");
    }

    /**
     * @dev Returns the downcasted int32 from int256, reverting on
     * overflow (when the input is less than smallest int32 or
     * greater than largest int32).
     *
     * Counterpart to Solidity's `int32` operator.
     *
     * Requirements:
     *
     * - input must fit into 32 bits
     *
     * _Available since v3.1._
     */
    function toInt32(int256 value) internal pure returns (int32 downcasted) {
        downcasted = int32(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 32 bits");
    }

    /**
     * @dev Returns the downcasted int24 from int256, reverting on
     * overflow (when the input is less than smallest int24 or
     * greater than largest int24).
     *
     * Counterpart to Solidity's `int24` operator.
     *
     * Requirements:
     *
     * - input must fit into 24 bits
     *
     * _Available since v4.7._
     */
    function toInt24(int256 value) internal pure returns (int24 downcasted) {
        downcasted = int24(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 24 bits");
    }

    /**
     * @dev Returns the downcasted int16 from int256, reverting on
     * overflow (when the input is less than smallest int16 or
     * greater than largest int16).
     *
     * Counterpart to Solidity's `int16` operator.
     *
     * Requirements:
     *
     * - input must fit into 16 bits
     *
     * _Available since v3.1._
     */
    function toInt16(int256 value) internal pure returns (int16 downcasted) {
        downcasted = int16(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 16 bits");
    }

    /**
     * @dev Returns the downcasted int8 from int256, reverting on
     * overflow (when the input is less than smallest int8 or
     * greater than largest int8).
     *
     * Counterpart to Solidity's `int8` operator.
     *
     * Requirements:
     *
     * - input must fit into 8 bits
     *
     * _Available since v3.1._
     */
    function toInt8(int256 value) internal pure returns (int8 downcasted) {
        downcasted = int8(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 8 bits");
    }

    /**
     * @dev Converts an unsigned uint256 into a signed int256.
     *
     * Requirements:
     *
     * - input must be less than or equal to maxInt256.
     *
     * _Available since v3.0._
     */
    function toInt256(uint256 value) internal pure returns (int256) {
        // Note: Unsafe cast below is okay because `type(int256).max` is guaranteed to be positive
        require(value <= uint256(type(int256).max), "SafeCast: value doesn't fit in an int256");
        return int256(value);
    }
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (utils/math/SignedMath.sol)

pragma solidity ^0.8.0;

/**
 * @dev Standard signed math utilities missing in the Solidity language.
 */
library SignedMath {
    /**
     * @dev Returns the largest of two signed numbers.
     */
    function max(int256 a, int256 b) internal pure returns (int256) {
        return a > b ? a : b;
    }

    /**
     * @dev Returns the smallest of two signed numbers.
     */
    function min(int256 a, int256 b) internal pure returns (int256) {
        return a < b ? a : b;
    }

    /**
     * @dev Returns the average of two signed numbers without overflow.
     * The result is rounded towards zero.
     */
    function average(int256 a, int256 b) internal pure returns (int256) {
        // Formula from the book "Hacker's Delight"
        int256 x = (a & b) + ((a ^ b) >> 1);
        return x + (int256(uint256(x) >> 255) & (a ^ b));
    }

    /**
     * @dev Returns the absolute unsigned value of a signed value.
     */
    function abs(int256 n) internal pure returns (uint256) {
        unchecked {
            // must be unchecked in order to support `n = type(int256).min`
            return uint256(n >= 0 ? n : -n);
        }
    }
}
          

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/structs/EnumerableSet.sol)
// This file was procedurally generated from scripts/generate/templates/EnumerableSet.js.

pragma solidity ^0.8.0;

/**
 * @dev Library for managing
 * https://en.wikipedia.org/wiki/Set_(abstract_data_type)[sets] of primitive
 * types.
 *
 * Sets have the following properties:
 *
 * - Elements are added, removed, and checked for existence in constant time
 * (O(1)).
 * - Elements are enumerated in O(n). No guarantees are made on the ordering.
 *
 * ```solidity
 * contract Example {
 *     // Add the library methods
 *     using EnumerableSet for EnumerableSet.AddressSet;
 *
 *     // Declare a set state variable
 *     EnumerableSet.AddressSet private mySet;
 * }
 * ```
 *
 * As of v3.3.0, sets of type `bytes32` (`Bytes32Set`), `address` (`AddressSet`)
 * and `uint256` (`UintSet`) are supported.
 *
 * [WARNING]
 * ====
 * Trying to delete such a structure from storage will likely result in data corruption, rendering the structure
 * unusable.
 * See https://github.com/ethereum/solidity/pull/11843[ethereum/solidity#11843] for more info.
 *
 * In order to clean an EnumerableSet, you can either remove all elements one by one or create a fresh instance using an
 * array of EnumerableSet.
 * ====
 */
library EnumerableSet {
    // To implement this library for multiple types with as little code
    // repetition as possible, we write it in terms of a generic Set type with
    // bytes32 values.
    // The Set implementation uses private functions, and user-facing
    // implementations (such as AddressSet) are just wrappers around the
    // underlying Set.
    // This means that we can only create new EnumerableSets for types that fit
    // in bytes32.

    struct Set {
        // Storage of set values
        bytes32[] _values;
        // Position of the value in the `values` array, plus 1 because index 0
        // means a value is not in the set.
        mapping(bytes32 => uint256) _indexes;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function _add(Set storage set, bytes32 value) private returns (bool) {
        if (!_contains(set, value)) {
            set._values.push(value);
            // The value is stored at length-1, but we add 1 to all indexes
            // and use 0 as a sentinel value
            set._indexes[value] = set._values.length;
            return true;
        } else {
            return false;
        }
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function _remove(Set storage set, bytes32 value) private returns (bool) {
        // We read and store the value's index to prevent multiple reads from the same storage slot
        uint256 valueIndex = set._indexes[value];

        if (valueIndex != 0) {
            // Equivalent to contains(set, value)
            // To delete an element from the _values array in O(1), we swap the element to delete with the last one in
            // the array, and then remove the last element (sometimes called as 'swap and pop').
            // This modifies the order of the array, as noted in {at}.

            uint256 toDeleteIndex = valueIndex - 1;
            uint256 lastIndex = set._values.length - 1;

            if (lastIndex != toDeleteIndex) {
                bytes32 lastValue = set._values[lastIndex];

                // Move the last value to the index where the value to delete is
                set._values[toDeleteIndex] = lastValue;
                // Update the index for the moved value
                set._indexes[lastValue] = valueIndex; // Replace lastValue's index to valueIndex
            }

            // Delete the slot where the moved value was stored
            set._values.pop();

            // Delete the index for the deleted slot
            delete set._indexes[value];

            return true;
        } else {
            return false;
        }
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function _contains(Set storage set, bytes32 value) private view returns (bool) {
        return set._indexes[value] != 0;
    }

    /**
     * @dev Returns the number of values on the set. O(1).
     */
    function _length(Set storage set) private view returns (uint256) {
        return set._values.length;
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function _at(Set storage set, uint256 index) private view returns (bytes32) {
        return set._values[index];
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function _values(Set storage set) private view returns (bytes32[] memory) {
        return set._values;
    }

    // Bytes32Set

    struct Bytes32Set {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _add(set._inner, value);
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _remove(set._inner, value);
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(Bytes32Set storage set, bytes32 value) internal view returns (bool) {
        return _contains(set._inner, value);
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(Bytes32Set storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(Bytes32Set storage set, uint256 index) internal view returns (bytes32) {
        return _at(set._inner, index);
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(Bytes32Set storage set) internal view returns (bytes32[] memory) {
        bytes32[] memory store = _values(set._inner);
        bytes32[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // AddressSet

    struct AddressSet {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(AddressSet storage set, address value) internal returns (bool) {
        return _add(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(AddressSet storage set, address value) internal returns (bool) {
        return _remove(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(AddressSet storage set, address value) internal view returns (bool) {
        return _contains(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(AddressSet storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(AddressSet storage set, uint256 index) internal view returns (address) {
        return address(uint160(uint256(_at(set._inner, index))));
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(AddressSet storage set) internal view returns (address[] memory) {
        bytes32[] memory store = _values(set._inner);
        address[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // UintSet

    struct UintSet {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(UintSet storage set, uint256 value) internal returns (bool) {
        return _add(set._inner, bytes32(value));
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(UintSet storage set, uint256 value) internal returns (bool) {
        return _remove(set._inner, bytes32(value));
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(UintSet storage set, uint256 value) internal view returns (bool) {
        return _contains(set._inner, bytes32(value));
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(UintSet storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(UintSet storage set, uint256 index) internal view returns (uint256) {
        return uint256(_at(set._inner, index));
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(UintSet storage set) internal view returns (uint256[] memory) {
        bytes32[] memory store = _values(set._inner);
        uint256[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }
}