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

pragma solidity ^0.8.1;

/**
 * @dev Collection of functions related to the address type
 */
library Address {
    /**
     * @dev Returns true if `account` is a contract.
     *
     * [IMPORTANT]
     * ====
     * It is unsafe to assume that an address for which this function returns
     * false is an externally-owned account (EOA) and not a contract.
     *
     * Among others, `isContract` will return false for the following
     * types of addresses:
     *
     *  - an externally-owned account
     *  - a contract in construction
     *  - an address where a contract will be created
     *  - an address where a contract lived, but was destroyed
     *
     * Furthermore, `isContract` will also return true if the target contract within
     * the same transaction is already scheduled for destruction by `SELFDESTRUCT`,
     * which only has an effect at the end of a transaction.
     * ====
     *
     * [IMPORTANT]
     * ====
     * You shouldn't rely on `isContract` to protect against flash loan attacks!
     *
     * Preventing calls from contracts is highly discouraged. It breaks composability, breaks support for smart wallets
     * like Gnosis Safe, and does not provide security since it can be circumvented by calling from a contract
     * constructor.
     * ====
     */
    function isContract(address account) internal view returns (bool) {
        // This method relies on extcodesize/address.code.length, which returns 0
        // for contracts in construction, since the code is only stored at the end
        // of the constructor execution.

        return account.code.length > 0;
    }

    /**
     * @dev Replacement for Solidity's `transfer`: sends `amount` wei to
     * `recipient`, forwarding all available gas and reverting on errors.
     *
     * https://eips.ethereum.org/EIPS/eip-1884[EIP1884] increases the gas cost
     * of certain opcodes, possibly making contracts go over the 2300 gas limit
     * imposed by `transfer`, making them unable to receive funds via
     * `transfer`. {sendValue} removes this limitation.
     *
     * https://consensys.net/diligence/blog/2019/09/stop-using-soliditys-transfer-now/[Learn more].
     *
     * IMPORTANT: because control is transferred to `recipient`, care must be
     * taken to not create reentrancy vulnerabilities. Consider using
     * {ReentrancyGuard} or the
     * https://solidity.readthedocs.io/en/v0.8.0/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
     */
    function sendValue(address payable recipient, uint256 amount) internal {
        require(address(this).balance >= amount, "Address: insufficient balance");

        (bool success, ) = recipient.call{value: amount}("");
        require(success, "Address: unable to send value, recipient may have reverted");
    }

    /**
     * @dev Performs a Solidity function call using a low level `call`. A
     * plain `call` is an unsafe replacement for a function call: use this
     * function instead.
     *
     * If `target` reverts with a revert reason, it is bubbled up by this
     * function (like regular Solidity function calls).
     *
     * Returns the raw returned data. To convert to the expected return value,
     * use https://solidity.readthedocs.io/en/latest/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions[`abi.decode`].
     *
     * Requirements:
     *
     * - `target` must be a contract.
     * - calling `target` with `data` must not revert.
     *
     * _Available since v3.1._
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, "Address: low-level call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`], but with
     * `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but also transferring `value` wei to `target`.
     *
     * Requirements:
     *
     * - the calling contract must have an ETH balance of at least `value`.
     * - the called Solidity function must be `payable`.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory) {
        return functionCallWithValue(target, data, value, "Address: low-level call with value failed");
    }

    /**
     * @dev Same as {xref-Address-functionCallWithValue-address-bytes-uint256-}[`functionCallWithValue`], but
     * with `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(address(this).balance >= value, "Address: insufficient balance for call");
        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
        return functionStaticCall(target, data, "Address: low-level static call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        (bool success, bytes memory returndata) = target.staticcall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionDelegateCall(target, data, "Address: low-level delegate call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        (bool success, bytes memory returndata) = target.delegatecall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Tool to verify that a low level call to smart-contract was successful, and revert (either by bubbling
     * the revert reason or using the provided one) in case of unsuccessful call or if target was not a contract.
     *
     * _Available since v4.8._
     */
    function verifyCallResultFromTarget(
        address target,
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        if (success) {
            if (returndata.length == 0) {
                // only check isContract if the call was successful and the return data is empty
                // otherwise we already know that it was a contract
                require(isContract(target), "Address: call to non-contract");
            }
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }

    /**
     * @dev Tool to verify that a low level call was successful, and revert if it wasn't, either by bubbling the
     * revert reason or using the provided one.
     *
     * _Available since v4.3._
     */
    function verifyCallResult(
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal pure returns (bytes memory) {
        if (success) {
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }

    function _revert(bytes memory returndata, string memory errorMessage) private pure {
        // Look for revert reason and bubble it up if present
        if (returndata.length > 0) {
            // The easiest way to bubble the revert reason is using memory via assembly
            /// @solidity memory-safe-assembly
            assembly {
                let returndata_size := mload(returndata)
                revert(add(32, returndata), returndata_size)
            }
        } else {
            revert(errorMessage);
        }
    }
}

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

// solhint-disable-next-line interface-starts-with-i
interface AggregatorV3Interface {
  function decimals() external view returns (uint8);

  function description() external view returns (string memory);

  function version() external view returns (uint256);

  function getRoundData(
    uint80 _roundId
  ) external view returns (uint80 roundId, int256 answer, uint256 startedAt, uint256 updatedAt, uint80 answeredInRound);

  function latestRoundData()
    external
    view
    returns (uint80 roundId, int256 answer, uint256 startedAt, uint256 updatedAt, uint80 answeredInRound);
}

// Copyright 2021-2022, Offchain Labs, Inc.
// For license information, see https://github.com/OffchainLabs/nitro-contracts/blob/main/LICENSE
// SPDX-License-Identifier: BUSL-1.1

pragma solidity >=0.4.21 <0.9.0;

/// @title Provides insight into the cost of using the chain.
/// @notice These methods have been adjusted to account for Nitro's heavy use of calldata compression.
/// Of note to end-users, we no longer make a distinction between non-zero and zero-valued calldata bytes.
/// Precompiled contract that exists in every Arbitrum chain at 0x000000000000000000000000000000000000006c.
interface ArbGasInfo {
    /// @notice Get gas prices for a provided aggregator
    /// @return return gas prices in wei
    ///        (
    ///            per L2 tx,
    ///            per L1 calldata byte
    ///            per storage allocation,
    ///            per ArbGas base,
    ///            per ArbGas congestion,
    ///            per ArbGas total
    ///        )
    function getPricesInWeiWithAggregator(address aggregator)
    external
    view
    returns (
        uint256,
        uint256,
        uint256,
        uint256,
        uint256,
        uint256
    );

    /// @notice Get gas prices. Uses the caller's preferred aggregator, or the default if the caller doesn't have a preferred one.
    /// @return return gas prices in wei
    ///        (
    ///            per L2 tx,
    ///            per L1 calldata byte
    ///            per storage allocation,
    ///            per ArbGas base,
    ///            per ArbGas congestion,
    ///            per ArbGas total
    ///        )
    function getPricesInWei()
    external
    view
    returns (
        uint256,
        uint256,
        uint256,
        uint256,
        uint256,
        uint256
    );

    /// @notice Get prices in ArbGas for the supplied aggregator
    /// @return (per L2 tx, per L1 calldata byte, per storage allocation)
    function getPricesInArbGasWithAggregator(address aggregator)
    external
    view
    returns (
        uint256,
        uint256,
        uint256
    );

    /// @notice Get prices in ArbGas. Assumes the callers preferred validator, or the default if caller doesn't have a preferred one.
    /// @return (per L2 tx, per L1 calldata byte, per storage allocation)
    function getPricesInArbGas()
    external
    view
    returns (
        uint256,
        uint256,
        uint256
    );

    /// @notice Get the gas accounting parameters. `gasPoolMax` is always zero, as the exponential pricing model has no such notion.
    /// @return (speedLimitPerSecond, gasPoolMax, maxTxGasLimit)
    function getGasAccountingParams()
    external
    view
    returns (
        uint256,
        uint256,
        uint256
    );

    /// @notice Get the minimum gas price needed for a tx to succeed
    function getMinimumGasPrice() external view returns (uint256);

    /// @notice Get ArbOS's estimate of the L1 basefee in wei
    function getL1BaseFeeEstimate() external view returns (uint256);

    /// @notice Get how slowly ArbOS updates its estimate of the L1 basefee
    function getL1BaseFeeEstimateInertia() external view returns (uint64);

    /// @notice Get the L1 pricer reward rate, in wei per unit
    /// Available in ArbOS version 11
    function getL1RewardRate() external view returns (uint64);

    /// @notice Get the L1 pricer reward recipient
    /// Available in ArbOS version 11
    function getL1RewardRecipient() external view returns (address);

    /// @notice Deprecated -- Same as getL1BaseFeeEstimate()
    function getL1GasPriceEstimate() external view returns (uint256);

    /// @notice Get L1 gas fees paid by the current transaction
    function getCurrentTxL1GasFees() external view returns (uint256);

    /// @notice Get the backlogged amount of gas burnt in excess of the speed limit
    function getGasBacklog() external view returns (uint64);

    /// @notice Get how slowly ArbOS updates the L2 basefee in response to backlogged gas
    function getPricingInertia() external view returns (uint64);

    /// @notice Get the forgivable amount of backlogged gas ArbOS will ignore when raising the basefee
    function getGasBacklogTolerance() external view returns (uint64);

    /// @notice Returns the surplus of funds for L1 batch posting payments (may be negative).
    function getL1PricingSurplus() external view returns (int256);

    /// @notice Returns the base charge (in L1 gas) attributed to each data batch in the calldata pricer
    function getPerBatchGasCharge() external view returns (int64);

    /// @notice Returns the cost amortization cap in basis points
    function getAmortizedCostCapBips() external view returns (uint64);

    /// @notice Returns the available funds from L1 fees
    function getL1FeesAvailable() external view returns (uint256);

    /// @notice Returns the equilibration units parameter for L1 price adjustment algorithm
    /// Available in ArbOS version 20
    function getL1PricingEquilibrationUnits() external view returns (uint256);

    /// @notice Returns the last time the L1 calldata pricer was updated.
    /// Available in ArbOS version 20
    function getLastL1PricingUpdateTime() external view returns (uint64);

    /// @notice Returns the amount of L1 calldata payments due for rewards (per the L1 reward rate)
    /// Available in ArbOS version 20
    function getL1PricingFundsDueForRewards() external view returns (uint256);

    /// @notice Returns the amount of L1 calldata posted since the last update.
    /// Available in ArbOS version 20
    function getL1PricingUnitsSinceUpdate() external view returns (uint64);

    /// @notice Returns the L1 pricing surplus as of the last update (may be negative).
    /// Available in ArbOS version 20
    function getLastL1PricingSurplus() external view returns (int256);
}

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

import {SignedMath} from "@openzeppelin/contracts/utils/math/SignedMath.sol";
import {FixedPointMathLib} from "../../../../../@rari-capital/solmate/src/utils/FixedPointMathLib.sol";

/// @title Arithmetic
/// @notice Even more math than before.
library Arithmetic {
  /// @notice Clamps a value between a minimum and maximum.
  /// @param _value The value to clamp.
  /// @param _min   The minimum value.
  /// @param _max   The maximum value.
  /// @return The clamped value.
  function clamp(int256 _value, int256 _min, int256 _max) internal pure returns (int256) {
    return SignedMath.min(SignedMath.max(_value, _min), _max);
  }

  /// @notice (c)oefficient (d)enominator (exp)onentiation function.
  ///         Returns the result of: c * (1 - 1/d)^exp.
  /// @param _coefficient Coefficient of the function.
  /// @param _denominator Fractional denominator.
  /// @param _exponent    Power function exponent.
  /// @return Result of c * (1 - 1/d)^exp.
  function cdexp(int256 _coefficient, int256 _denominator, int256 _exponent) internal pure returns (int256) {
    return (_coefficient * (FixedPointMathLib.powWad(1e18 - (1e18 / _denominator), _exponent * 1e18))) / 1e18;
  }
}

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

/// @title Burn
/// @notice Utilities for burning stuff.
library Burn {
  /// @notice Burns a given amount of ETH.
  /// @param _amount Amount of ETH to burn.
  function eth(uint256 _amount) internal {
    new Burner{value: _amount}();
  }

  /// @notice Burns a given amount of gas.
  /// @param _amount Amount of gas to burn.
  function gas(uint256 _amount) internal view {
    uint256 i = 0;
    uint256 initialGas = gasleft();
    while (initialGas - gasleft() < _amount) {
      ++i;
    }
  }
}

/// @title Burner
/// @notice Burner self-destructs on creation and sends all ETH to itself, removing all ETH given to
///         the contract from the circulating supply. Self-destructing is the only way to remove ETH
///         from the circulating supply.
contract Burner {
  constructor() payable {
    // solhint-disable-next-line avoid-low-level-calls
    selfdestruct(payable(address(this)));
  }
}

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

import {ArbGasInfo} from "../../../../vendor/@arbitrum/nitro-contracts/src/precompiles/ArbGasInfo.sol";
import {GasPriceOracle} from "../../../../vendor/@eth-optimism/contracts-bedrock/v0.17.3/src/L2/GasPriceOracle.sol";

/// @dev A library that abstracts out opcodes that behave differently across chains.
/// @dev The methods below return values that are pertinent to the given chain.
library ChainSpecificUtil {
  // ------------ Start Arbitrum Constants ------------
  /// @dev ARBGAS_ADDR is the address of the ArbGasInfo precompile on Arbitrum.
  /// @dev reference: https://github.com/OffchainLabs/nitro/blob/v2.0.14/contracts/src/precompiles/ArbGasInfo.sol#L10
  address private constant ARBGAS_ADDR = address(0x000000000000000000000000000000000000006C);
  ArbGasInfo private constant ARBGAS = ArbGasInfo(ARBGAS_ADDR);
  /// @dev ARB_DATA_PADDING_SIZE is the max size of the "static" data on Arbitrum for the transaction which refers to the tx data that is not the calldata (signature, etc.)
  /// @dev reference: https://docs.arbitrum.io/build-decentralized-apps/how-to-estimate-gas#where-do-we-get-all-this-information-from
  uint256 private constant ARB_DATA_PADDING_SIZE = 140;

  uint256 private constant ARB_MAINNET_CHAIN_ID = 42161;
  uint256 private constant ARB_GOERLI_TESTNET_CHAIN_ID = 421613;
  uint256 private constant ARB_SEPOLIA_TESTNET_CHAIN_ID = 421614;

  // ------------ End Arbitrum Constants ------------

  // ------------ Start Optimism Constants ------------
  /// @dev GAS_PRICE_ORACLE_ADDR is the address of the GasPriceOracle precompile on Optimism.
  address private constant GAS_PRICE_ORACLE_ADDR = address(0x420000000000000000000000000000000000000F);
  GasPriceOracle private constant GAS_PRICE_ORACLE = GasPriceOracle(GAS_PRICE_ORACLE_ADDR);

  uint256 private constant OP_MAINNET_CHAIN_ID = 10;
  uint256 private constant OP_GOERLI_CHAIN_ID = 420;
  uint256 private constant OP_SEPOLIA_CHAIN_ID = 11155420;

  /// @dev Base is a OP stack based rollup and follows the same L1 pricing logic as Optimism.
  uint256 private constant BASE_MAINNET_CHAIN_ID = 8453;
  uint256 private constant BASE_GOERLI_CHAIN_ID = 84531;
  uint256 private constant BASE_SEPOLIA_CHAIN_ID = 84532;

  // ------------ End Optimism Constants ------------

  /// @notice Returns the upper limit estimate of the L1 fees in wei that will be paid for L2 chains
  /// @notice based on the size of the transaction data and the current gas conditions.
  /// @notice This is an "upper limit" as it assumes the transaction data is uncompressed when posted on L1.
  function _getL1FeeUpperLimit(uint256 calldataSizeBytes) internal view returns (uint256 l1FeeWei) {
    uint256 chainid = block.chainid;
    if (_isArbitrumChainId(chainid)) {
      // https://docs.arbitrum.io/build-decentralized-apps/how-to-estimate-gas#where-do-we-get-all-this-information-from
      (, uint256 l1PricePerByte, , , , ) = ARBGAS.getPricesInWei();
      return l1PricePerByte * (calldataSizeBytes + ARB_DATA_PADDING_SIZE);
    } else if (_isOptimismChainId(chainid)) {
      return GAS_PRICE_ORACLE.getL1FeeUpperBound(calldataSizeBytes);
    }
    return 0;
  }

  /// @notice Return true if and only if the provided chain ID is an Arbitrum chain ID.
  function _isArbitrumChainId(uint256 chainId) internal pure returns (bool) {
    return
      chainId == ARB_MAINNET_CHAIN_ID ||
      chainId == ARB_GOERLI_TESTNET_CHAIN_ID ||
      chainId == ARB_SEPOLIA_TESTNET_CHAIN_ID;
  }

  /// @notice Return true if and only if the provided chain ID is an Optimism (or Base) chain ID.
  /// @notice Note that optimism chain id's are also OP stack chain id's.
  function _isOptimismChainId(uint256 chainId) internal pure returns (bool) {
    return
      chainId == OP_MAINNET_CHAIN_ID ||
      chainId == OP_GOERLI_CHAIN_ID ||
      chainId == OP_SEPOLIA_CHAIN_ID ||
      chainId == BASE_MAINNET_CHAIN_ID ||
      chainId == BASE_GOERLI_CHAIN_ID ||
      chainId == BASE_SEPOLIA_CHAIN_ID;
  }
}

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

import {ConfirmedOwnerWithProposal} from "./ConfirmedOwnerWithProposal.sol";

/// @title The ConfirmedOwner contract
/// @notice A contract with helpers for basic contract ownership.
contract ConfirmedOwner is ConfirmedOwnerWithProposal {
  constructor(address newOwner) ConfirmedOwnerWithProposal(newOwner, address(0)) {}
}

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

import {IOwnable} from "../interfaces/IOwnable.sol";

/// @title The ConfirmedOwner contract
/// @notice A contract with helpers for basic contract ownership.
contract ConfirmedOwnerWithProposal is IOwnable {
  address private s_owner;
  address private s_pendingOwner;

  event OwnershipTransferRequested(address indexed from, address indexed to);
  event OwnershipTransferred(address indexed from, address indexed to);

  constructor(address newOwner, address pendingOwner) {
    // solhint-disable-next-line gas-custom-errors
    require(newOwner != address(0), "Cannot set owner to zero");

    s_owner = newOwner;
    if (pendingOwner != address(0)) {
      _transferOwnership(pendingOwner);
    }
  }

  /// @notice Allows an owner to begin transferring ownership to a new address.
  function transferOwnership(address to) public override onlyOwner {
    _transferOwnership(to);
  }

  /// @notice Allows an ownership transfer to be completed by the recipient.
  function acceptOwnership() external override {
    // solhint-disable-next-line gas-custom-errors
    require(msg.sender == s_pendingOwner, "Must be proposed owner");

    address oldOwner = s_owner;
    s_owner = msg.sender;
    s_pendingOwner = address(0);

    emit OwnershipTransferred(oldOwner, msg.sender);
  }

  /// @notice Get the current owner
  function owner() public view override returns (address) {
    return s_owner;
  }

  /// @notice validate, transfer ownership, and emit relevant events
  function _transferOwnership(address to) private {
    // solhint-disable-next-line gas-custom-errors
    require(to != msg.sender, "Cannot transfer to self");

    s_pendingOwner = to;

    emit OwnershipTransferRequested(s_owner, to);
  }

  /// @notice validate access
  function _validateOwnership() internal view {
    // solhint-disable-next-line gas-custom-errors
    require(msg.sender == s_owner, "Only callable by owner");
  }

  /// @notice Reverts if called by anyone other than the contract owner.
  modifier onlyOwner() {
    _validateOwnership();
    _;
  }
}

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

import {ResourceMetering} from "../L1/ResourceMetering.sol";

/// @title Constants
/// @notice Constants is a library for storing constants. Simple! Don't put everything in here, just
///         the stuff used in multiple contracts. Constants that only apply to a single contract
///         should be defined in that contract instead.
library Constants {
  /// @notice Special address to be used as the tx origin for gas estimation calls in the
  ///         OptimismPortal and CrossDomainMessenger calls. You only need to use this address if
  ///         the minimum gas limit specified by the user is not actually enough to execute the
  ///         given message and you're attempting to estimate the actual necessary gas limit. We
  ///         use address(1) because it's the ecrecover precompile and therefore guaranteed to
  ///         never have any code on any EVM chain.
  address internal constant ESTIMATION_ADDRESS = address(1);

  /// @notice Value used for the L2 sender storage slot in both the OptimismPortal and the
  ///         CrossDomainMessenger contracts before an actual sender is set. This value is
  ///         non-zero to reduce the gas cost of message passing transactions.
  address internal constant DEFAULT_L2_SENDER = 0x000000000000000000000000000000000000dEaD;

  /// @notice The storage slot that holds the address of a proxy implementation.
  /// @dev `bytes32(uint256(keccak256('eip1967.proxy.implementation')) - 1)`
  bytes32 internal constant PROXY_IMPLEMENTATION_ADDRESS =
    0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;

  /// @notice The storage slot that holds the address of the owner.
  /// @dev `bytes32(uint256(keccak256('eip1967.proxy.admin')) - 1)`
  bytes32 internal constant PROXY_OWNER_ADDRESS = 0xb53127684a568b3173ae13b9f8a6016e243e63b6e8ee1178d6a717850b5d6103;

  /// @notice The address that represents ether when dealing with ERC20 token addresses.
  address internal constant ETHER = 0xEeeeeEeeeEeEeeEeEeEeeEEEeeeeEeeeeeeeEEeE;

  /// @notice The address that represents the system caller responsible for L1 attributes
  ///         transactions.
  address internal constant DEPOSITOR_ACCOUNT = 0xDeaDDEaDDeAdDeAdDEAdDEaddeAddEAdDEAd0001;

  /// @notice Returns the default values for the ResourceConfig. These are the recommended values
  ///         for a production network.
  function DEFAULT_RESOURCE_CONFIG() internal pure returns (ResourceMetering.ResourceConfig memory) {
    ResourceMetering.ResourceConfig memory config = ResourceMetering.ResourceConfig({
      maxResourceLimit: 20_000_000,
      elasticityMultiplier: 10,
      baseFeeMaxChangeDenominator: 8,
      minimumBaseFee: 1 gwei,
      systemTxMaxGas: 1_000_000,
      maximumBaseFee: type(uint128).max
    });
    return config;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity >=0.8.0;

/// @notice Arithmetic library with operations for fixed-point numbers.
/// @author Solmate (https://github.com/Rari-Capital/solmate/blob/main/src/utils/FixedPointMathLib.sol)
library FixedPointMathLib {
    /*//////////////////////////////////////////////////////////////
                    SIMPLIFIED FIXED POINT OPERATIONS
    //////////////////////////////////////////////////////////////*/

    uint256 internal constant WAD = 1e18; // The scalar of ETH and most ERC20s.

    function mulWadDown(uint256 x, uint256 y) internal pure returns (uint256) {
        return mulDivDown(x, y, WAD); // Equivalent to (x * y) / WAD rounded down.
    }

    function mulWadUp(uint256 x, uint256 y) internal pure returns (uint256) {
        return mulDivUp(x, y, WAD); // Equivalent to (x * y) / WAD rounded up.
    }

    function divWadDown(uint256 x, uint256 y) internal pure returns (uint256) {
        return mulDivDown(x, WAD, y); // Equivalent to (x * WAD) / y rounded down.
    }

    function divWadUp(uint256 x, uint256 y) internal pure returns (uint256) {
        return mulDivUp(x, WAD, y); // Equivalent to (x * WAD) / y rounded up.
    }

    function powWad(int256 x, int256 y) internal pure returns (int256) {
        // Equivalent to x to the power of y because x ** y = (e ** ln(x)) ** y = e ** (ln(x) * y)
        return expWad((lnWad(x) * y) / int256(WAD)); // Using ln(x) means x must be greater than 0.
    }

    function expWad(int256 x) internal pure returns (int256 r) {
        unchecked {
            // When the result is < 0.5 we return zero. This happens when
            // x <= floor(log(0.5e18) * 1e18) ~ -42e18
            if (x <= -42139678854452767551) return 0;

            // When the result is > (2**255 - 1) / 1e18 we can not represent it as an
            // int. This happens when x >= floor(log((2**255 - 1) / 1e18) * 1e18) ~ 135.
            if (x >= 135305999368893231589) revert("EXP_OVERFLOW");

            // x is now in the range (-42, 136) * 1e18. Convert to (-42, 136) * 2**96
            // for more intermediate precision and a binary basis. This base conversion
            // is a multiplication by 1e18 / 2**96 = 5**18 / 2**78.
            x = (x << 78) / 5**18;

            // Reduce range of x to (-½ ln 2, ½ ln 2) * 2**96 by factoring out powers
            // of two such that exp(x) = exp(x') * 2**k, where k is an integer.
            // Solving this gives k = round(x / log(2)) and x' = x - k * log(2).
            int256 k = ((x << 96) / 54916777467707473351141471128 + 2**95) >> 96;
            x = x - k * 54916777467707473351141471128;

            // k is in the range [-61, 195].

            // Evaluate using a (6, 7)-term rational approximation.
            // p is made monic, we'll multiply by a scale factor later.
            int256 y = x + 1346386616545796478920950773328;
            y = ((y * x) >> 96) + 57155421227552351082224309758442;
            int256 p = y + x - 94201549194550492254356042504812;
            p = ((p * y) >> 96) + 28719021644029726153956944680412240;
            p = p * x + (4385272521454847904659076985693276 << 96);

            // We leave p in 2**192 basis so we don't need to scale it back up for the division.
            int256 q = x - 2855989394907223263936484059900;
            q = ((q * x) >> 96) + 50020603652535783019961831881945;
            q = ((q * x) >> 96) - 533845033583426703283633433725380;
            q = ((q * x) >> 96) + 3604857256930695427073651918091429;
            q = ((q * x) >> 96) - 14423608567350463180887372962807573;
            q = ((q * x) >> 96) + 26449188498355588339934803723976023;

            assembly {
                // Div in assembly because solidity adds a zero check despite the unchecked.
                // The q polynomial won't have zeros in the domain as all its roots are complex.
                // No scaling is necessary because p is already 2**96 too large.
                r := sdiv(p, q)
            }

            // r should be in the range (0.09, 0.25) * 2**96.

            // We now need to multiply r by:
            // * the scale factor s = ~6.031367120.
            // * the 2**k factor from the range reduction.
            // * the 1e18 / 2**96 factor for base conversion.
            // We do this all at once, with an intermediate result in 2**213
            // basis, so the final right shift is always by a positive amount.
            r = int256((uint256(r) * 3822833074963236453042738258902158003155416615667) >> uint256(195 - k));
        }
    }

    function lnWad(int256 x) internal pure returns (int256 r) {
        unchecked {
            require(x > 0, "UNDEFINED");

            // We want to convert x from 10**18 fixed point to 2**96 fixed point.
            // We do this by multiplying by 2**96 / 10**18. But since
            // ln(x * C) = ln(x) + ln(C), we can simply do nothing here
            // and add ln(2**96 / 10**18) at the end.

            // Reduce range of x to (1, 2) * 2**96
            // ln(2^k * x) = k * ln(2) + ln(x)
            int256 k = int256(log2(uint256(x))) - 96;
            x <<= uint256(159 - k);
            x = int256(uint256(x) >> 159);

            // Evaluate using a (8, 8)-term rational approximation.
            // p is made monic, we will multiply by a scale factor later.
            int256 p = x + 3273285459638523848632254066296;
            p = ((p * x) >> 96) + 24828157081833163892658089445524;
            p = ((p * x) >> 96) + 43456485725739037958740375743393;
            p = ((p * x) >> 96) - 11111509109440967052023855526967;
            p = ((p * x) >> 96) - 45023709667254063763336534515857;
            p = ((p * x) >> 96) - 14706773417378608786704636184526;
            p = p * x - (795164235651350426258249787498 << 96);

            // We leave p in 2**192 basis so we don't need to scale it back up for the division.
            // q is monic by convention.
            int256 q = x + 5573035233440673466300451813936;
            q = ((q * x) >> 96) + 71694874799317883764090561454958;
            q = ((q * x) >> 96) + 283447036172924575727196451306956;
            q = ((q * x) >> 96) + 401686690394027663651624208769553;
            q = ((q * x) >> 96) + 204048457590392012362485061816622;
            q = ((q * x) >> 96) + 31853899698501571402653359427138;
            q = ((q * x) >> 96) + 909429971244387300277376558375;
            assembly {
                // Div in assembly because solidity adds a zero check despite the unchecked.
                // The q polynomial is known not to have zeros in the domain.
                // No scaling required because p is already 2**96 too large.
                r := sdiv(p, q)
            }

            // r is in the range (0, 0.125) * 2**96

            // Finalization, we need to:
            // * multiply by the scale factor s = 5.549…
            // * add ln(2**96 / 10**18)
            // * add k * ln(2)
            // * multiply by 10**18 / 2**96 = 5**18 >> 78

            // mul s * 5e18 * 2**96, base is now 5**18 * 2**192
            r *= 1677202110996718588342820967067443963516166;
            // add ln(2) * k * 5e18 * 2**192
            r += 16597577552685614221487285958193947469193820559219878177908093499208371 * k;
            // add ln(2**96 / 10**18) * 5e18 * 2**192
            r += 600920179829731861736702779321621459595472258049074101567377883020018308;
            // base conversion: mul 2**18 / 2**192
            r >>= 174;
        }
    }

    /*//////////////////////////////////////////////////////////////
                    LOW LEVEL FIXED POINT OPERATIONS
    //////////////////////////////////////////////////////////////*/

    function mulDivDown(
        uint256 x,
        uint256 y,
        uint256 denominator
    ) internal pure returns (uint256 z) {
        assembly {
            // Store x * y in z for now.
            z := mul(x, y)

            // Equivalent to require(denominator != 0 && (x == 0 || (x * y) / x == y))
            if iszero(and(iszero(iszero(denominator)), or(iszero(x), eq(div(z, x), y)))) {
                revert(0, 0)
            }

            // Divide z by the denominator.
            z := div(z, denominator)
        }
    }

    function mulDivUp(
        uint256 x,
        uint256 y,
        uint256 denominator
    ) internal pure returns (uint256 z) {
        assembly {
            // Store x * y in z for now.
            z := mul(x, y)

            // Equivalent to require(denominator != 0 && (x == 0 || (x * y) / x == y))
            if iszero(and(iszero(iszero(denominator)), or(iszero(x), eq(div(z, x), y)))) {
                revert(0, 0)
            }

            // First, divide z - 1 by the denominator and add 1.
            // We allow z - 1 to underflow if z is 0, because we multiply the
            // end result by 0 if z is zero, ensuring we return 0 if z is zero.
            z := mul(iszero(iszero(z)), add(div(sub(z, 1), denominator), 1))
        }
    }

    function rpow(
        uint256 x,
        uint256 n,
        uint256 scalar
    ) internal pure returns (uint256 z) {
        assembly {
            switch x
            case 0 {
                switch n
                case 0 {
                    // 0 ** 0 = 1
                    z := scalar
                }
                default {
                    // 0 ** n = 0
                    z := 0
                }
            }
            default {
                switch mod(n, 2)
                case 0 {
                    // If n is even, store scalar in z for now.
                    z := scalar
                }
                default {
                    // If n is odd, store x in z for now.
                    z := x
                }

                // Shifting right by 1 is like dividing by 2.
                let half := shr(1, scalar)

                for {
                    // Shift n right by 1 before looping to halve it.
                    n := shr(1, n)
                } n {
                    // Shift n right by 1 each iteration to halve it.
                    n := shr(1, n)
                } {
                    // Revert immediately if x ** 2 would overflow.
                    // Equivalent to iszero(eq(div(xx, x), x)) here.
                    if shr(128, x) {
                        revert(0, 0)
                    }

                    // Store x squared.
                    let xx := mul(x, x)

                    // Round to the nearest number.
                    let xxRound := add(xx, half)

                    // Revert if xx + half overflowed.
                    if lt(xxRound, xx) {
                        revert(0, 0)
                    }

                    // Set x to scaled xxRound.
                    x := div(xxRound, scalar)

                    // If n is even:
                    if mod(n, 2) {
                        // Compute z * x.
                        let zx := mul(z, x)

                        // If z * x overflowed:
                        if iszero(eq(div(zx, x), z)) {
                            // Revert if x is non-zero.
                            if iszero(iszero(x)) {
                                revert(0, 0)
                            }
                        }

                        // Round to the nearest number.
                        let zxRound := add(zx, half)

                        // Revert if zx + half overflowed.
                        if lt(zxRound, zx) {
                            revert(0, 0)
                        }

                        // Return properly scaled zxRound.
                        z := div(zxRound, scalar)
                    }
                }
            }
        }
    }

    /*//////////////////////////////////////////////////////////////
                        GENERAL NUMBER UTILITIES
    //////////////////////////////////////////////////////////////*/

    function sqrt(uint256 x) internal pure returns (uint256 z) {
        assembly {
            let y := x // We start y at x, which will help us make our initial estimate.

            z := 181 // The "correct" value is 1, but this saves a multiplication later.

            // This segment is to get a reasonable initial estimate for the Babylonian method. With a bad
            // start, the correct # of bits increases ~linearly each iteration instead of ~quadratically.

            // We check y >= 2^(k + 8) but shift right by k bits
            // each branch to ensure that if x >= 256, then y >= 256.
            if iszero(lt(y, 0x10000000000000000000000000000000000)) {
                y := shr(128, y)
                z := shl(64, z)
            }
            if iszero(lt(y, 0x1000000000000000000)) {
                y := shr(64, y)
                z := shl(32, z)
            }
            if iszero(lt(y, 0x10000000000)) {
                y := shr(32, y)
                z := shl(16, z)
            }
            if iszero(lt(y, 0x1000000)) {
                y := shr(16, y)
                z := shl(8, z)
            }

            // Goal was to get z*z*y within a small factor of x. More iterations could
            // get y in a tighter range. Currently, we will have y in [256, 256*2^16).
            // We ensured y >= 256 so that the relative difference between y and y+1 is small.
            // That's not possible if x < 256 but we can just verify those cases exhaustively.

            // Now, z*z*y <= x < z*z*(y+1), and y <= 2^(16+8), and either y >= 256, or x < 256.
            // Correctness can be checked exhaustively for x < 256, so we assume y >= 256.
            // Then z*sqrt(y) is within sqrt(257)/sqrt(256) of sqrt(x), or about 20bps.

            // For s in the range [1/256, 256], the estimate f(s) = (181/1024) * (s+1) is in the range
            // (1/2.84 * sqrt(s), 2.84 * sqrt(s)), with largest error when s = 1 and when s = 256 or 1/256.

            // Since y is in [256, 256*2^16), let a = y/65536, so that a is in [1/256, 256). Then we can estimate
            // sqrt(y) using sqrt(65536) * 181/1024 * (a + 1) = 181/4 * (y + 65536)/65536 = 181 * (y + 65536)/2^18.

            // There is no overflow risk here since y < 2^136 after the first branch above.
            z := shr(18, mul(z, add(y, 65536))) // A mul() is saved from starting z at 181.

            // Given the worst case multiplicative error of 2.84 above, 7 iterations should be enough.
            z := shr(1, add(z, div(x, z)))
            z := shr(1, add(z, div(x, z)))
            z := shr(1, add(z, div(x, z)))
            z := shr(1, add(z, div(x, z)))
            z := shr(1, add(z, div(x, z)))
            z := shr(1, add(z, div(x, z)))
            z := shr(1, add(z, div(x, z)))

            // If x+1 is a perfect square, the Babylonian method cycles between
            // floor(sqrt(x)) and ceil(sqrt(x)). This statement ensures we return floor.
            // See: https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division
            // Since the ceil is rare, we save gas on the assignment and repeat division in the rare case.
            // If you don't care whether the floor or ceil square root is returned, you can remove this statement.
            z := sub(z, lt(div(x, z), z))
        }
    }

    function log2(uint256 x) internal pure returns (uint256 r) {
        require(x > 0, "UNDEFINED");

        assembly {
            r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
            r := or(r, shl(4, lt(0xffff, shr(r, x))))
            r := or(r, shl(3, lt(0xff, shr(r, x))))
            r := or(r, shl(2, lt(0xf, shr(r, x))))
            r := or(r, shl(1, lt(0x3, shr(r, x))))
            r := or(r, lt(0x1, shr(r, x)))
        }
    }
}

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

import {IFunctionsSubscriptions} from "./interfaces/IFunctionsSubscriptions.sol";
import {AggregatorV3Interface} from "../../../shared/interfaces/AggregatorV3Interface.sol";
import {IFunctionsBilling, FunctionsBillingConfig} from "./interfaces/IFunctionsBilling.sol";

import {Routable} from "./Routable.sol";
import {FunctionsResponse} from "./libraries/FunctionsResponse.sol";

import {SafeCast} from "../../../vendor/openzeppelin-solidity/v4.8.3/contracts/utils/math/SafeCast.sol";

import {ChainSpecificUtil} from "./libraries/ChainSpecificUtil.sol";

/// @title Functions Billing contract
/// @notice Contract that calculates payment from users to the nodes of the Decentralized Oracle Network (DON).
abstract contract FunctionsBilling is Routable, IFunctionsBilling {
  using FunctionsResponse for FunctionsResponse.RequestMeta;
  using FunctionsResponse for FunctionsResponse.Commitment;
  using FunctionsResponse for FunctionsResponse.FulfillResult;

  uint256 private constant REASONABLE_GAS_PRICE_CEILING = 1_000_000_000_000_000; // 1 million gwei

  event RequestBilled(
    bytes32 indexed requestId,
    uint96 juelsPerGas,
    uint256 l1FeeShareWei,
    uint96 callbackCostJuels,
    uint72 donFeeJuels,
    uint72 adminFeeJuels,
    uint72 operationFeeJuels
  );

  // ================================================================
  // |                  Request Commitment state                    |
  // ================================================================

  mapping(bytes32 requestId => bytes32 commitmentHash) private s_requestCommitments;

  event CommitmentDeleted(bytes32 requestId);

  FunctionsBillingConfig private s_config;

  event ConfigUpdated(FunctionsBillingConfig config);

  error UnsupportedRequestDataVersion();
  error InsufficientBalance();
  error InvalidSubscription();
  error UnauthorizedSender();
  error MustBeSubOwner(address owner);
  error InvalidLinkWeiPrice(int256 linkWei);
  error InvalidUsdLinkPrice(int256 usdLink);
  error PaymentTooLarge();
  error NoTransmittersSet();
  error InvalidCalldata();

  // ================================================================
  // |                        Balance state                         |
  // ================================================================

  mapping(address transmitter => uint96 balanceJuelsLink) private s_withdrawableTokens;
  // Pool together collected DON fees
  // Disperse them on withdrawal or change in OCR configuration
  uint96 internal s_feePool;

  AggregatorV3Interface private s_linkToNativeFeed;
  AggregatorV3Interface private s_linkToUsdFeed;

  // ================================================================
  // |                       Initialization                         |
  // ================================================================
  constructor(
    address router,
    FunctionsBillingConfig memory config,
    address linkToNativeFeed,
    address linkToUsdFeed
  ) Routable(router) {
    s_linkToNativeFeed = AggregatorV3Interface(linkToNativeFeed);
    s_linkToUsdFeed = AggregatorV3Interface(linkToUsdFeed);

    updateConfig(config);
  }

  // ================================================================
  // |                        Configuration                         |
  // ================================================================

  /// @notice Gets the Chainlink Coordinator's billing configuration
  /// @return config
  function getConfig() external view returns (FunctionsBillingConfig memory) {
    return s_config;
  }

  /// @notice Sets the Chainlink Coordinator's billing configuration
  /// @param config - See the contents of the FunctionsBillingConfig struct in IFunctionsBilling.sol for more information
  function updateConfig(FunctionsBillingConfig memory config) public {
    _onlyOwner();

    s_config = config;
    emit ConfigUpdated(config);
  }

  // ================================================================
  // |                       Fee Calculation                        |
  // ================================================================

  /// @inheritdoc IFunctionsBilling
  function getDONFeeJuels(bytes memory /* requestData */) public view override returns (uint72) {
    // s_config.donFee is in cents of USD. Convert to dollars amount then get amount of Juels.
    return SafeCast.toUint72(_getJuelsFromUsd(s_config.donFeeCentsUsd) / 100);
  }

  /// @inheritdoc IFunctionsBilling
  function getOperationFeeJuels() public view override returns (uint72) {
    // s_config.donFee is in cents of USD. Convert to dollars then get amount of Juels.
    return SafeCast.toUint72(_getJuelsFromUsd(s_config.operationFeeCentsUsd) / 100);
  }

  /// @inheritdoc IFunctionsBilling
  function getAdminFeeJuels() public view override returns (uint72) {
    return _getRouter().getAdminFee();
  }

  /// @inheritdoc IFunctionsBilling
  function getWeiPerUnitLink() public view returns (uint256) {
    (, int256 weiPerUnitLink, , uint256 timestamp, ) = s_linkToNativeFeed.latestRoundData();
    // Only fallback if feedStalenessSeconds is set
    // solhint-disable-next-line not-rely-on-time
    if (s_config.feedStalenessSeconds < block.timestamp - timestamp && s_config.feedStalenessSeconds > 0) {
      return s_config.fallbackNativePerUnitLink;
    }
    if (weiPerUnitLink <= 0) {
      revert InvalidLinkWeiPrice(weiPerUnitLink);
    }
    return uint256(weiPerUnitLink);
  }

  function _getJuelsFromWei(uint256 amountWei) private view returns (uint96) {
    // (1e18 juels/link) * wei / (wei/link) = juels
    // There are only 1e9*1e18 = 1e27 juels in existence, should not exceed uint96 (2^96 ~ 7e28)
    return SafeCast.toUint96((1e18 * amountWei) / getWeiPerUnitLink());
  }

  /// @inheritdoc IFunctionsBilling
  function getUsdPerUnitLink() public view returns (uint256, uint8) {
    (, int256 usdPerUnitLink, , uint256 timestamp, ) = s_linkToUsdFeed.latestRoundData();
    // Only fallback if feedStalenessSeconds is set
    // solhint-disable-next-line not-rely-on-time
    if (s_config.feedStalenessSeconds < block.timestamp - timestamp && s_config.feedStalenessSeconds > 0) {
      return (s_config.fallbackUsdPerUnitLink, s_config.fallbackUsdPerUnitLinkDecimals);
    }
    if (usdPerUnitLink <= 0) {
      revert InvalidUsdLinkPrice(usdPerUnitLink);
    }
    return (uint256(usdPerUnitLink), s_linkToUsdFeed.decimals());
  }

  function _getJuelsFromUsd(uint256 amountUsd) private view returns (uint96) {
    (uint256 usdPerLink, uint8 decimals) = getUsdPerUnitLink();
    // (usd) * (10**18 juels/link) * (10**decimals) / (link / usd) = juels
    // There are only 1e9*1e18 = 1e27 juels in existence, should not exceed uint96 (2^96 ~ 7e28)
    return SafeCast.toUint96((amountUsd * 10 ** (18 + decimals)) / usdPerLink);
  }

  // ================================================================
  // |                       Cost Estimation                        |
  // ================================================================

  /// @inheritdoc IFunctionsBilling
  function estimateCost(
    uint64 subscriptionId,
    bytes calldata data,
    uint32 callbackGasLimit,
    uint256 gasPriceWei
  ) external view override returns (uint96) {
    _getRouter().isValidCallbackGasLimit(subscriptionId, callbackGasLimit);
    // Reasonable ceilings to prevent integer overflows
    if (gasPriceWei > REASONABLE_GAS_PRICE_CEILING) {
      revert InvalidCalldata();
    }
    uint72 adminFee = getAdminFeeJuels();
    uint72 donFee = getDONFeeJuels(data);
    uint72 operationFee = getOperationFeeJuels();
    return _calculateCostEstimate(callbackGasLimit, gasPriceWei, donFee, adminFee, operationFee);
  }

  /// @notice Estimate the cost in Juels of LINK
  // that will be charged to a subscription to fulfill a Functions request
  // Gas Price can be overestimated to account for flucuations between request and response time
  function _calculateCostEstimate(
    uint32 callbackGasLimit,
    uint256 gasPriceWei,
    uint72 donFeeJuels,
    uint72 adminFeeJuels,
    uint72 operationFeeJuels
  ) internal view returns (uint96) {
    // If gas price is less than the minimum fulfillment gas price, override to using the minimum
    if (gasPriceWei < s_config.minimumEstimateGasPriceWei) {
      gasPriceWei = s_config.minimumEstimateGasPriceWei;
    }

    uint256 executionGas = s_config.gasOverheadBeforeCallback + s_config.gasOverheadAfterCallback + callbackGasLimit;
    uint256 l1FeeWei = ChainSpecificUtil._getL1FeeUpperLimit(s_config.transmitTxSizeBytes);
    uint256 totalFeeWei = (gasPriceWei * executionGas) + l1FeeWei;

    // Basis Points are 1/100th of 1%, divide by 10_000 to bring back to original units
    uint256 totalFeeWeiWithOverestimate = totalFeeWei +
      ((totalFeeWei * s_config.fulfillmentGasPriceOverEstimationBP) / 10_000);

    uint96 estimatedGasReimbursementJuels = _getJuelsFromWei(totalFeeWeiWithOverestimate);

    uint96 feesJuels = uint96(donFeeJuels) + uint96(adminFeeJuels) + uint96(operationFeeJuels);

    return estimatedGasReimbursementJuels + feesJuels;
  }

  // ================================================================
  // |                           Billing                            |
  // ================================================================

  /// @notice Initiate the billing process for an Functions request
  /// @dev Only callable by the Functions Router
  /// @param request - Chainlink Functions request data, see FunctionsResponse.RequestMeta for the structure
  /// @return commitment - The parameters of the request that must be held consistent at response time
  function _startBilling(
    FunctionsResponse.RequestMeta memory request
  ) internal returns (FunctionsResponse.Commitment memory commitment, uint72 operationFee) {
    // Nodes should support all past versions of the structure
    if (request.dataVersion > s_config.maxSupportedRequestDataVersion) {
      revert UnsupportedRequestDataVersion();
    }

    uint72 donFee = getDONFeeJuels(request.data);
    operationFee = getOperationFeeJuels();
    uint96 estimatedTotalCostJuels = _calculateCostEstimate(
      request.callbackGasLimit,
      tx.gasprice,
      donFee,
      request.adminFee,
      operationFee
    );

    // Check that subscription can afford the estimated cost
    if ((request.availableBalance) < estimatedTotalCostJuels) {
      revert InsufficientBalance();
    }

    uint32 timeoutTimestamp = uint32(block.timestamp + s_config.requestTimeoutSeconds);
    bytes32 requestId = keccak256(
      abi.encode(
        address(this),
        request.requestingContract,
        request.subscriptionId,
        request.initiatedRequests + 1,
        keccak256(request.data),
        request.dataVersion,
        request.callbackGasLimit,
        estimatedTotalCostJuels,
        timeoutTimestamp,
        // solhint-disable-next-line avoid-tx-origin
        tx.origin
      )
    );

    commitment = FunctionsResponse.Commitment({
      adminFee: request.adminFee,
      coordinator: address(this),
      client: request.requestingContract,
      subscriptionId: request.subscriptionId,
      callbackGasLimit: request.callbackGasLimit,
      estimatedTotalCostJuels: estimatedTotalCostJuels,
      timeoutTimestamp: timeoutTimestamp,
      requestId: requestId,
      donFee: donFee,
      gasOverheadBeforeCallback: s_config.gasOverheadBeforeCallback,
      gasOverheadAfterCallback: s_config.gasOverheadAfterCallback
    });

    s_requestCommitments[requestId] = keccak256(abi.encode(commitment));

    return (commitment, operationFee);
  }

  /// @notice Finalize billing process for an Functions request by sending a callback to the Client contract and then charging the subscription
  /// @param requestId identifier for the request that was generated by the Registry in the beginBilling commitment
  /// @param response response data from DON consensus
  /// @param err error from DON consensus
  /// @param reportBatchSize the number of fulfillments in the transmitter's report
  /// @return result fulfillment result
  /// @dev Only callable by a node that has been approved on the Coordinator
  /// @dev simulated offchain to determine if sufficient balance is present to fulfill the request
  function _fulfillAndBill(
    bytes32 requestId,
    bytes memory response,
    bytes memory err,
    bytes memory onchainMetadata,
    bytes memory /* offchainMetadata TODO: use in getDonFee() for dynamic billing */,
    uint8 reportBatchSize
  ) internal returns (FunctionsResponse.FulfillResult) {
    FunctionsResponse.Commitment memory commitment = abi.decode(onchainMetadata, (FunctionsResponse.Commitment));

    uint256 gasOverheadWei = (commitment.gasOverheadBeforeCallback + commitment.gasOverheadAfterCallback) * tx.gasprice;
    uint256 l1FeeShareWei = ChainSpecificUtil._getL1FeeUpperLimit(msg.data.length) / reportBatchSize;
    // Gas overhead without callback
    uint96 gasOverheadJuels = _getJuelsFromWei(gasOverheadWei + l1FeeShareWei);
    uint96 juelsPerGas = _getJuelsFromWei(tx.gasprice);

    // The Functions Router will perform the callback to the client contract
    (FunctionsResponse.FulfillResult resultCode, uint96 callbackCostJuels) = _getRouter().fulfill(
      response,
      err,
      juelsPerGas,
      // The following line represents: "cost without callback or admin fee, those will be added by the Router"
      // But because the _offchain_ Commitment is using operation fee in the place of the admin fee, this now adds admin fee (actually operation fee)
      // Admin fee is configured to 0 in the Router
      gasOverheadJuels + commitment.donFee + commitment.adminFee,
      msg.sender,
      FunctionsResponse.Commitment({
        adminFee: 0, // The Router should have adminFee set to 0. If it does not this will cause fulfillments to fail with INVALID_COMMITMENT instead of carrying out incorrect bookkeeping.
        coordinator: commitment.coordinator,
        client: commitment.client,
        subscriptionId: commitment.subscriptionId,
        callbackGasLimit: commitment.callbackGasLimit,
        estimatedTotalCostJuels: commitment.estimatedTotalCostJuels,
        timeoutTimestamp: commitment.timeoutTimestamp,
        requestId: commitment.requestId,
        donFee: commitment.donFee,
        gasOverheadBeforeCallback: commitment.gasOverheadBeforeCallback,
        gasOverheadAfterCallback: commitment.gasOverheadAfterCallback
      })
    );

    // The router will only pay the DON on successfully processing the fulfillment
    // In these two fulfillment results the user has been charged
    // Otherwise, the Coordinator should hold on to the request commitment
    if (
      resultCode == FunctionsResponse.FulfillResult.FULFILLED ||
      resultCode == FunctionsResponse.FulfillResult.USER_CALLBACK_ERROR
    ) {
      delete s_requestCommitments[requestId];
      // Reimburse the transmitter for the fulfillment gas cost
      s_withdrawableTokens[msg.sender] += gasOverheadJuels + callbackCostJuels;
      // Put donFee into the pool of fees, to be split later
      // Saves on storage writes that would otherwise be charged to the user
      s_feePool += commitment.donFee;
      // Pay the operation fee to the Coordinator owner
      s_withdrawableTokens[_owner()] += commitment.adminFee; // OperationFee is used in the slot for Admin Fee in the Offchain Commitment. Admin Fee is set to 0 in the Router (enforced by line 316 in FunctionsBilling.sol).
      emit RequestBilled({
        requestId: requestId,
        juelsPerGas: juelsPerGas,
        l1FeeShareWei: l1FeeShareWei,
        callbackCostJuels: callbackCostJuels,
        donFeeJuels: commitment.donFee,
        // The following two lines are because of OperationFee being used in the Offchain Commitment
        adminFeeJuels: 0,
        operationFeeJuels: commitment.adminFee
      });
    }
    return resultCode;
  }

  // ================================================================
  // |                       Request Timeout                        |
  // ================================================================

  /// @inheritdoc IFunctionsBilling
  /// @dev Only callable by the Router
  /// @dev Used by FunctionsRouter.sol during timeout of a request
  function deleteCommitment(bytes32 requestId) external override onlyRouter {
    // Delete commitment
    delete s_requestCommitments[requestId];
    emit CommitmentDeleted(requestId);
  }

  // ================================================================
  // |                    Fund withdrawal                           |
  // ================================================================

  /// @inheritdoc IFunctionsBilling
  function oracleWithdraw(address recipient, uint96 amount) external {
    _disperseFeePool();

    if (amount == 0) {
      amount = s_withdrawableTokens[msg.sender];
    } else if (s_withdrawableTokens[msg.sender] < amount) {
      revert InsufficientBalance();
    }
    s_withdrawableTokens[msg.sender] -= amount;
    IFunctionsSubscriptions(address(_getRouter())).oracleWithdraw(recipient, amount);
  }

  /// @inheritdoc IFunctionsBilling
  /// @dev Only callable by the Coordinator owner
  function oracleWithdrawAll() external {
    _onlyOwner();
    _disperseFeePool();

    address[] memory transmitters = _getTransmitters();

    // Bounded by "maxNumOracles" on OCR2Abstract.sol
    for (uint256 i = 0; i < transmitters.length; ++i) {
      uint96 balance = s_withdrawableTokens[transmitters[i]];
      if (balance > 0) {
        s_withdrawableTokens[transmitters[i]] = 0;
        IFunctionsSubscriptions(address(_getRouter())).oracleWithdraw(transmitters[i], balance);
      }
    }
  }

  // Overriden in FunctionsCoordinator, which has visibility into transmitters
  function _getTransmitters() internal view virtual returns (address[] memory);

  // DON fees are collected into a pool s_feePool
  // When OCR configuration changes, or any oracle withdraws, this must be dispersed
  function _disperseFeePool() internal {
    if (s_feePool == 0) {
      return;
    }
    // All transmitters are assumed to also be observers
    // Pay out the DON fee to all transmitters
    address[] memory transmitters = _getTransmitters();
    uint256 numberOfTransmitters = transmitters.length;
    if (numberOfTransmitters == 0) {
      revert NoTransmittersSet();
    }
    uint96 feePoolShare = s_feePool / uint96(numberOfTransmitters);
    if (feePoolShare == 0) {
      // Dust cannot be evenly distributed to all transmitters
      return;
    }
    // Bounded by "maxNumOracles" on OCR2Abstract.sol
    for (uint256 i = 0; i < numberOfTransmitters; ++i) {
      s_withdrawableTokens[transmitters[i]] += feePoolShare;
    }
    s_feePool -= feePoolShare * uint96(numberOfTransmitters);
  }

  // Overriden in FunctionsCoordinator.sol
  function _onlyOwner() internal view virtual;

  // Used in FunctionsCoordinator.sol
  function _isExistingRequest(bytes32 requestId) internal view returns (bool) {
    return s_requestCommitments[requestId] != bytes32(0);
  }

  // Overriden in FunctionsCoordinator.sol
  function _owner() internal view virtual returns (address owner);
}

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

import {IFunctionsCoordinator} from "./interfaces/IFunctionsCoordinator.sol";
import {ITypeAndVersion} from "../../../shared/interfaces/ITypeAndVersion.sol";

import {FunctionsBilling, FunctionsBillingConfig} from "./FunctionsBilling.sol";
import {OCR2Base} from "./ocr/OCR2Base.sol";
import {FunctionsResponse} from "./libraries/FunctionsResponse.sol";

/// @title Functions Coordinator contract
/// @notice Contract that nodes of a Decentralized Oracle Network (DON) interact with
contract FunctionsCoordinator is OCR2Base, IFunctionsCoordinator, FunctionsBilling {
  using FunctionsResponse for FunctionsResponse.RequestMeta;
  using FunctionsResponse for FunctionsResponse.Commitment;
  using FunctionsResponse for FunctionsResponse.FulfillResult;

  /// @inheritdoc ITypeAndVersion
  string public constant override typeAndVersion = "Functions Coordinator v1.3.1";

  event OracleRequest(
    bytes32 indexed requestId,
    address indexed requestingContract,
    address requestInitiator,
    uint64 subscriptionId,
    address subscriptionOwner,
    bytes data,
    uint16 dataVersion,
    bytes32 flags,
    uint64 callbackGasLimit,
    FunctionsResponse.Commitment commitment
  );
  event OracleResponse(bytes32 indexed requestId, address transmitter);

  error InconsistentReportData();
  error EmptyPublicKey();
  error UnauthorizedPublicKeyChange();

  bytes private s_donPublicKey;
  bytes private s_thresholdPublicKey;

  constructor(
    address router,
    FunctionsBillingConfig memory config,
    address linkToNativeFeed,
    address linkToUsdFeed
  ) OCR2Base() FunctionsBilling(router, config, linkToNativeFeed, linkToUsdFeed) {}

  /// @inheritdoc IFunctionsCoordinator
  function getThresholdPublicKey() external view override returns (bytes memory) {
    if (s_thresholdPublicKey.length == 0) {
      revert EmptyPublicKey();
    }
    return s_thresholdPublicKey;
  }

  /// @inheritdoc IFunctionsCoordinator
  function setThresholdPublicKey(bytes calldata thresholdPublicKey) external override onlyOwner {
    if (thresholdPublicKey.length == 0) {
      revert EmptyPublicKey();
    }
    s_thresholdPublicKey = thresholdPublicKey;
  }

  /// @inheritdoc IFunctionsCoordinator
  function getDONPublicKey() external view override returns (bytes memory) {
    if (s_donPublicKey.length == 0) {
      revert EmptyPublicKey();
    }
    return s_donPublicKey;
  }

  /// @inheritdoc IFunctionsCoordinator
  function setDONPublicKey(bytes calldata donPublicKey) external override onlyOwner {
    if (donPublicKey.length == 0) {
      revert EmptyPublicKey();
    }
    s_donPublicKey = donPublicKey;
  }

  /// @dev check if node is in current transmitter list
  function _isTransmitter(address node) internal view returns (bool) {
    // Bounded by "maxNumOracles" on OCR2Abstract.sol
    for (uint256 i = 0; i < s_transmitters.length; ++i) {
      if (s_transmitters[i] == node) {
        return true;
      }
    }
    return false;
  }

  /// @inheritdoc IFunctionsCoordinator
  function startRequest(
    FunctionsResponse.RequestMeta calldata request
  ) external override onlyRouter returns (FunctionsResponse.Commitment memory commitment) {
    uint72 operationFee;
    (commitment, operationFee) = _startBilling(request);

    emit OracleRequest(
      commitment.requestId,
      request.requestingContract,
      // solhint-disable-next-line avoid-tx-origin
      tx.origin,
      request.subscriptionId,
      request.subscriptionOwner,
      request.data,
      request.dataVersion,
      request.flags,
      request.callbackGasLimit,
      FunctionsResponse.Commitment({
        coordinator: commitment.coordinator,
        client: commitment.client,
        subscriptionId: commitment.subscriptionId,
        callbackGasLimit: commitment.callbackGasLimit,
        estimatedTotalCostJuels: commitment.estimatedTotalCostJuels,
        timeoutTimestamp: commitment.timeoutTimestamp,
        requestId: commitment.requestId,
        donFee: commitment.donFee,
        gasOverheadBeforeCallback: commitment.gasOverheadBeforeCallback,
        gasOverheadAfterCallback: commitment.gasOverheadAfterCallback,
        // The following line is done to use the Coordinator's operationFee in place of the Router's operation fee
        // With this in place the Router.adminFee must be set to 0 in the Router.
        adminFee: operationFee
      })
    );

    return commitment;
  }

  /// @dev DON fees are pooled together. If the OCR configuration is going to change, these need to be distributed.
  function _beforeSetConfig(uint8 /* _f */, bytes memory /* _onchainConfig */) internal override {
    if (_getTransmitters().length > 0) {
      _disperseFeePool();
    }
  }

  /// @dev Used by FunctionsBilling.sol
  function _getTransmitters() internal view override returns (address[] memory) {
    return s_transmitters;
  }

  function _beforeTransmit(
    bytes calldata report
  ) internal view override returns (bool shouldStop, DecodedReport memory decodedReport) {
    (
      bytes32[] memory requestIds,
      bytes[] memory results,
      bytes[] memory errors,
      bytes[] memory onchainMetadata,
      bytes[] memory offchainMetadata
    ) = abi.decode(report, (bytes32[], bytes[], bytes[], bytes[], bytes[]));
    uint256 numberOfFulfillments = uint8(requestIds.length);

    if (
      numberOfFulfillments == 0 ||
      numberOfFulfillments != results.length ||
      numberOfFulfillments != errors.length ||
      numberOfFulfillments != onchainMetadata.length ||
      numberOfFulfillments != offchainMetadata.length
    ) {
      revert ReportInvalid("Fields must be equal length");
    }

    for (uint256 i = 0; i < numberOfFulfillments; ++i) {
      if (_isExistingRequest(requestIds[i])) {
        // If there is an existing request, validate report
        // Leave shouldStop to default, false
        break;
      }
      if (i == numberOfFulfillments - 1) {
        // If the last fulfillment on the report does not exist, then all are duplicates
        // Indicate that it's safe to stop to save on the gas of validating the report
        shouldStop = true;
      }
    }

    return (
      shouldStop,
      DecodedReport({
        requestIds: requestIds,
        results: results,
        errors: errors,
        onchainMetadata: onchainMetadata,
        offchainMetadata: offchainMetadata
      })
    );
  }

  /// @dev Report hook called within OCR2Base.sol
  function _report(DecodedReport memory decodedReport) internal override {
    uint256 numberOfFulfillments = uint8(decodedReport.requestIds.length);

    // Bounded by "MaxRequestBatchSize" on the Job's ReportingPluginConfig
    for (uint256 i = 0; i < numberOfFulfillments; ++i) {
      FunctionsResponse.FulfillResult result = FunctionsResponse.FulfillResult(
        _fulfillAndBill(
          decodedReport.requestIds[i],
          decodedReport.results[i],
          decodedReport.errors[i],
          decodedReport.onchainMetadata[i],
          decodedReport.offchainMetadata[i],
          uint8(numberOfFulfillments) // will not exceed "MaxRequestBatchSize" on the Job's ReportingPluginConfig
        )
      );

      // Emit on successfully processing the fulfillment
      // In these two fulfillment results the user has been charged
      // Otherwise, the DON will re-try
      if (
        result == FunctionsResponse.FulfillResult.FULFILLED ||
        result == FunctionsResponse.FulfillResult.USER_CALLBACK_ERROR
      ) {
        emit OracleResponse(decodedReport.requestIds[i], msg.sender);
      }
    }
  }

  /// @dev Used in FunctionsBilling.sol
  function _onlyOwner() internal view override {
    _validateOwnership();
  }

  /// @dev Used in FunctionsBilling.sol
  function _owner() internal view override returns (address owner) {
    return this.owner();
  }
}

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

/// @title Library of types that are used for fulfillment of a Functions request
library FunctionsResponse {
  // Used to send request information from the Router to the Coordinator
  struct RequestMeta {
    bytes data; // ══════════════════╸ CBOR encoded Chainlink Functions request data, use FunctionsRequest library to encode a request
    bytes32 flags; // ═══════════════╸ Per-subscription flags
    address requestingContract; // ══╗ The client contract that is sending the request
    uint96 availableBalance; // ═════╝ Common LINK balance of the subscription that is controlled by the Router to be used for all consumer requests.
    uint72 adminFee; // ═════════════╗ Flat fee (in Juels of LINK) that will be paid to the Router Owner for operation of the network
    uint64 subscriptionId; //        ║ Identifier of the billing subscription that will be charged for the request
    uint64 initiatedRequests; //     ║ The number of requests that have been started
    uint32 callbackGasLimit; //      ║ The amount of gas that the callback to the consuming contract will be given
    uint16 dataVersion; // ══════════╝ The version of the structure of the CBOR encoded request data
    uint64 completedRequests; // ════╗ The number of requests that have successfully completed or timed out
    address subscriptionOwner; // ═══╝ The owner of the billing subscription
  }

  enum FulfillResult {
    FULFILLED, // 0
    USER_CALLBACK_ERROR, // 1
    INVALID_REQUEST_ID, // 2
    COST_EXCEEDS_COMMITMENT, // 3
    INSUFFICIENT_GAS_PROVIDED, // 4
    SUBSCRIPTION_BALANCE_INVARIANT_VIOLATION, // 5
    INVALID_COMMITMENT // 6
  }

  struct Commitment {
    bytes32 requestId; // ═════════════════╸ A unique identifier for a Chainlink Functions request
    address coordinator; // ═══════════════╗ The Coordinator contract that manages the DON that is servicing a request
    uint96 estimatedTotalCostJuels; // ════╝ The maximum cost in Juels (1e18) of LINK that will be charged to fulfill a request
    address client; // ════════════════════╗ The client contract that sent the request
    uint64 subscriptionId; //              ║ Identifier of the billing subscription that will be charged for the request
    uint32 callbackGasLimit; // ═══════════╝ The amount of gas that the callback to the consuming contract will be given
    uint72 adminFee; // ═══════════════════╗ Flat fee (in Juels of LINK) that will be paid to the Router Owner for operation of the network
    uint72 donFee; //                      ║ Fee (in Juels of LINK) that will be split between Node Operators for servicing a request
    uint40 gasOverheadBeforeCallback; //   ║ Represents the average gas execution cost before the fulfillment callback.
    uint40 gasOverheadAfterCallback; //    ║ Represents the average gas execution cost after the fulfillment callback.
    uint32 timeoutTimestamp; // ═══════════╝ The timestamp at which a request will be eligible to be timed out
  }
}

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

import {Storage} from "./Storage.sol";
import {Constants} from "./Constants.sol";
import {LibString} from "../../../../../solady/src/utils/LibString.sol";

/// @title IGasToken
/// @notice Implemented by contracts that are aware of the custom gas token used
///         by the L2 network.
interface IGasToken {
  /// @notice Getter for the ERC20 token address that is used to pay for gas and its decimals.
  function gasPayingToken() external view returns (address, uint8);
  /// @notice Returns the gas token name.
  function gasPayingTokenName() external view returns (string memory);
  /// @notice Returns the gas token symbol.
  function gasPayingTokenSymbol() external view returns (string memory);
  /// @notice Returns true if the network uses a custom gas token.
  function isCustomGasToken() external view returns (bool);
}

/// @title GasPayingToken
/// @notice Handles reading and writing the custom gas token to storage.
///         To be used in any place where gas token information is read or
///         written to state. If multiple contracts use this library, the
///         values in storage should be kept in sync between them.
library GasPayingToken {
  /// @notice The storage slot that contains the address and decimals of the gas paying token
  bytes32 internal constant GAS_PAYING_TOKEN_SLOT = bytes32(uint256(keccak256("opstack.gaspayingtoken")) - 1);

  /// @notice The storage slot that contains the ERC20 `name()` of the gas paying token
  bytes32 internal constant GAS_PAYING_TOKEN_NAME_SLOT = bytes32(uint256(keccak256("opstack.gaspayingtokenname")) - 1);

  /// @notice the storage slot that contains the ERC20 `symbol()` of the gas paying token
  bytes32 internal constant GAS_PAYING_TOKEN_SYMBOL_SLOT =
    bytes32(uint256(keccak256("opstack.gaspayingtokensymbol")) - 1);

  /// @notice Reads the gas paying token and its decimals from the magic
  ///         storage slot. If nothing is set in storage, then the ether
  ///         address is returned instead.
  function getToken() internal view returns (address addr_, uint8 decimals_) {
    bytes32 slot = Storage.getBytes32(GAS_PAYING_TOKEN_SLOT);
    addr_ = address(uint160(uint256(slot) & uint256(type(uint160).max)));
    if (addr_ == address(0)) {
      addr_ = Constants.ETHER;
      decimals_ = 18;
    } else {
      decimals_ = uint8(uint256(slot) >> 160);
    }
  }

  /// @notice Reads the gas paying token's name from the magic storage slot.
  ///         If nothing is set in storage, then the ether name, 'Ether', is returned instead.
  function getName() internal view returns (string memory name_) {
    (address addr, ) = getToken();
    if (addr == Constants.ETHER) {
      name_ = "Ether";
    } else {
      name_ = LibString.fromSmallString(Storage.getBytes32(GAS_PAYING_TOKEN_NAME_SLOT));
    }
  }

  /// @notice Reads the gas paying token's symbol from the magic storage slot.
  ///         If nothing is set in storage, then the ether symbol, 'ETH', is returned instead.
  function getSymbol() internal view returns (string memory symbol_) {
    (address addr, ) = getToken();
    if (addr == Constants.ETHER) {
      symbol_ = "ETH";
    } else {
      symbol_ = LibString.fromSmallString(Storage.getBytes32(GAS_PAYING_TOKEN_SYMBOL_SLOT));
    }
  }

  /// @notice Writes the gas paying token, its decimals, name and symbol to the magic storage slot.
  function set(address _token, uint8 _decimals, bytes32 _name, bytes32 _symbol) internal {
    Storage.setBytes32(GAS_PAYING_TOKEN_SLOT, bytes32((uint256(_decimals) << 160) | uint256(uint160(_token))));
    Storage.setBytes32(GAS_PAYING_TOKEN_NAME_SLOT, _name);
    Storage.setBytes32(GAS_PAYING_TOKEN_SYMBOL_SLOT, _symbol);
  }

  /// @notice Maps a string to a normalized null-terminated small string.
  function sanitize(string memory _str) internal pure returns (bytes32) {
    require(bytes(_str).length <= 32, "GasPayingToken: string cannot be greater than 32 bytes");

    return LibString.toSmallString(_str);
  }
}

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

import {ISemver} from "../universal/ISemver.sol";
import {Predeploys} from "../libraries/Predeploys.sol";
import {L1Block} from "../L2/L1Block.sol";
import {Constants} from "../libraries/Constants.sol";
import {LibZip} from "../../../../../solady/src/utils/LibZip.sol";

/// @custom:proxied
/// @custom:predeploy 0x420000000000000000000000000000000000000F
/// @title GasPriceOracle
/// @notice This contract maintains the variables responsible for computing the L1 portion of the
///         total fee charged on L2. Before Bedrock, this contract held variables in state that were
///         read during the state transition function to compute the L1 portion of the transaction
///         fee. After Bedrock, this contract now simply proxies the L1Block contract, which has
///         the values used to compute the L1 portion of the fee in its state.
///
///         The contract exposes an API that is useful for knowing how large the L1 portion of the
///         transaction fee will be. The following events were deprecated with Bedrock:
///         - event OverheadUpdated(uint256 overhead);
///         - event ScalarUpdated(uint256 scalar);
///         - event DecimalsUpdated(uint256 decimals);
contract GasPriceOracle is ISemver {
  /// @notice Number of decimals used in the scalar.
  uint256 public constant DECIMALS = 6;

  /// @notice Semantic version.
  /// @custom:semver 1.3.0
  string public constant version = "1.3.0";

  /// @notice This is the intercept value for the linear regression used to estimate the final size of the
  ///         compressed transaction.
  int32 private constant COST_INTERCEPT = -42_585_600;

  /// @notice This is the coefficient value for the linear regression used to estimate the final size of the
  ///         compressed transaction.
  uint32 private constant COST_FASTLZ_COEF = 836_500;

  /// @notice This is the minimum bound for the fastlz to brotli size estimation. Any estimations below this
  ///         are set to this value.
  uint256 private constant MIN_TRANSACTION_SIZE = 100;

  /// @notice Indicates whether the network has gone through the Ecotone upgrade.
  bool public isEcotone;

  /// @notice Indicates whether the network has gone through the Fjord upgrade.
  bool public isFjord;

  /// @notice Computes the L1 portion of the fee based on the size of the rlp encoded input
  ///         transaction, the current L1 base fee, and the various dynamic parameters.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 fee for.
  /// @return L1 fee that should be paid for the tx
  function getL1Fee(bytes memory _data) external view returns (uint256) {
    if (isFjord) {
      return _getL1FeeFjord(_data);
    } else if (isEcotone) {
      return _getL1FeeEcotone(_data);
    }
    return _getL1FeeBedrock(_data);
  }

  /// @notice returns an upper bound for the L1 fee for a given transaction size.
  /// It is provided for callers who wish to estimate L1 transaction costs in the
  /// write path, and is much more gas efficient than `getL1Fee`.
  /// It assumes the worst case of fastlz upper-bound which covers %99.99 txs.
  /// @param _unsignedTxSize Unsigned fully RLP-encoded transaction size to get the L1 fee for.
  /// @return L1 estimated upper-bound fee that should be paid for the tx
  function getL1FeeUpperBound(uint256 _unsignedTxSize) external view returns (uint256) {
    require(isFjord, "GasPriceOracle: getL1FeeUpperBound only supports Fjord");

    // Add 68 to the size to account for unsigned tx:
    uint256 txSize = _unsignedTxSize + 68;
    // txSize / 255 + 16 is the pratical fastlz upper-bound covers %99.99 txs.
    uint256 flzUpperBound = txSize + txSize / 255 + 16;

    return _fjordL1Cost(flzUpperBound);
  }

  /// @notice Set chain to be Ecotone chain (callable by depositor account)
  function setEcotone() external {
    require(
      msg.sender == Constants.DEPOSITOR_ACCOUNT,
      "GasPriceOracle: only the depositor account can set isEcotone flag"
    );
    require(isEcotone == false, "GasPriceOracle: Ecotone already active");
    isEcotone = true;
  }

  /// @notice Set chain to be Fjord chain (callable by depositor account)
  function setFjord() external {
    require(
      msg.sender == Constants.DEPOSITOR_ACCOUNT,
      "GasPriceOracle: only the depositor account can set isFjord flag"
    );
    require(isEcotone, "GasPriceOracle: Fjord can only be activated after Ecotone");
    require(isFjord == false, "GasPriceOracle: Fjord already active");
    isFjord = true;
  }

  /// @notice Retrieves the current gas price (base fee).
  /// @return Current L2 gas price (base fee).
  function gasPrice() public view returns (uint256) {
    return block.basefee;
  }

  /// @notice Retrieves the current base fee.
  /// @return Current L2 base fee.
  function baseFee() public view returns (uint256) {
    return block.basefee;
  }

  /// @custom:legacy
  /// @notice Retrieves the current fee overhead.
  /// @return Current fee overhead.
  function overhead() public view returns (uint256) {
    require(!isEcotone, "GasPriceOracle: overhead() is deprecated");
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeOverhead();
  }

  /// @custom:legacy
  /// @notice Retrieves the current fee scalar.
  /// @return Current fee scalar.
  function scalar() public view returns (uint256) {
    require(!isEcotone, "GasPriceOracle: scalar() is deprecated");
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeScalar();
  }

  /// @notice Retrieves the latest known L1 base fee.
  /// @return Latest known L1 base fee.
  function l1BaseFee() public view returns (uint256) {
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).basefee();
  }

  /// @notice Retrieves the current blob base fee.
  /// @return Current blob base fee.
  function blobBaseFee() public view returns (uint256) {
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).blobBaseFee();
  }

  /// @notice Retrieves the current base fee scalar.
  /// @return Current base fee scalar.
  function baseFeeScalar() public view returns (uint32) {
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).baseFeeScalar();
  }

  /// @notice Retrieves the current blob base fee scalar.
  /// @return Current blob base fee scalar.
  function blobBaseFeeScalar() public view returns (uint32) {
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).blobBaseFeeScalar();
  }

  /// @custom:legacy
  /// @notice Retrieves the number of decimals used in the scalar.
  /// @return Number of decimals used in the scalar.
  function decimals() public pure returns (uint256) {
    return DECIMALS;
  }

  /// @notice Computes the amount of L1 gas used for a transaction. Adds 68 bytes
  ///         of padding to account for the fact that the input does not have a signature.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 gas for.
  /// @return Amount of L1 gas used to publish the transaction.
  /// @custom:deprecated This method does not accurately estimate the gas used for a transaction.
  ///                    If you are calculating fees use getL1Fee or getL1FeeUpperBound.
  function getL1GasUsed(bytes memory _data) public view returns (uint256) {
    if (isFjord) {
      // Add 68 to the size to account for unsigned tx
      // Assume the compressed data is mostly non-zero, and would pay 16 gas per calldata byte
      // Divide by 1e6 due to the scaling factor of the linear regression
      return (_fjordLinearRegression(LibZip.flzCompress(_data).length + 68) * 16) / 1e6;
    }
    uint256 l1GasUsed = _getCalldataGas(_data);
    if (isEcotone) {
      return l1GasUsed;
    }
    return l1GasUsed + L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeOverhead();
  }

  /// @notice Computation of the L1 portion of the fee for Bedrock.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 fee for.
  /// @return L1 fee that should be paid for the tx
  function _getL1FeeBedrock(bytes memory _data) internal view returns (uint256) {
    uint256 l1GasUsed = _getCalldataGas(_data);
    uint256 fee = (l1GasUsed + L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeOverhead()) *
      l1BaseFee() *
      L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeScalar();
    return fee / (10 ** DECIMALS);
  }

  /// @notice L1 portion of the fee after Ecotone.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 fee for.
  /// @return L1 fee that should be paid for the tx
  function _getL1FeeEcotone(bytes memory _data) internal view returns (uint256) {
    uint256 l1GasUsed = _getCalldataGas(_data);
    uint256 scaledBaseFee = baseFeeScalar() * 16 * l1BaseFee();
    uint256 scaledBlobBaseFee = blobBaseFeeScalar() * blobBaseFee();
    uint256 fee = l1GasUsed * (scaledBaseFee + scaledBlobBaseFee);
    return fee / (16 * 10 ** DECIMALS);
  }

  /// @notice L1 portion of the fee after Fjord.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 fee for.
  /// @return L1 fee that should be paid for the tx
  function _getL1FeeFjord(bytes memory _data) internal view returns (uint256) {
    return _fjordL1Cost(LibZip.flzCompress(_data).length + 68);
  }

  /// @notice L1 gas estimation calculation.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 gas for.
  /// @return Amount of L1 gas used to publish the transaction.
  function _getCalldataGas(bytes memory _data) internal pure returns (uint256) {
    uint256 total = 0;
    uint256 length = _data.length;
    for (uint256 i = 0; i < length; i++) {
      if (_data[i] == 0) {
        total += 4;
      } else {
        total += 16;
      }
    }
    return total + (68 * 16);
  }

  /// @notice Fjord L1 cost based on the compressed and original tx size.
  /// @param _fastLzSize estimated compressed tx size.
  /// @return Fjord L1 fee that should be paid for the tx
  function _fjordL1Cost(uint256 _fastLzSize) internal view returns (uint256) {
    // Apply the linear regression to estimate the Brotli 10 size
    uint256 estimatedSize = _fjordLinearRegression(_fastLzSize);
    uint256 feeScaled = baseFeeScalar() * 16 * l1BaseFee() + blobBaseFeeScalar() * blobBaseFee();
    return (estimatedSize * feeScaled) / (10 ** (DECIMALS * 2));
  }

  /// @notice Takes the fastLz size compression and returns the estimated Brotli
  /// @param _fastLzSize fastlz compressed tx size.
  /// @return Number of bytes in the compressed transaction
  function _fjordLinearRegression(uint256 _fastLzSize) internal pure returns (uint256) {
    int256 estimatedSize = COST_INTERCEPT + int256(COST_FASTLZ_COEF * _fastLzSize);
    if (estimatedSize < int256(MIN_TRANSACTION_SIZE) * 1e6) {
      estimatedSize = int256(MIN_TRANSACTION_SIZE) * 1e6;
    }
    return uint256(estimatedSize);
  }
}

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

/// @title Chainlink Functions DON billing interface.
interface IFunctionsBilling {
  /// @notice Return the current conversion from WEI of ETH to LINK from the configured Chainlink data feed
  /// @return weiPerUnitLink - The amount of WEI in one LINK
  function getWeiPerUnitLink() external view returns (uint256);

  /// @notice Return the current conversion from LINK to USD from the configured Chainlink data feed
  /// @return weiPerUnitLink - The amount of USD that one LINK is worth
  /// @return decimals - The number of decimals that should be represented in the price feed's response
  function getUsdPerUnitLink() external view returns (uint256, uint8);

  /// @notice Determine the fee that will be split between Node Operators for servicing a request
  /// @param requestCBOR - CBOR encoded Chainlink Functions request data, use FunctionsRequest library to encode a request
  /// @return fee - Cost in Juels (1e18) of LINK
  function getDONFeeJuels(bytes memory requestCBOR) external view returns (uint72);

  /// @notice Determine the fee that will be paid to the Coordinator owner for operating the network
  /// @return fee - Cost in Juels (1e18) of LINK
  function getOperationFeeJuels() external view returns (uint72);

  /// @notice Determine the fee that will be paid to the Router owner for operating the network
  /// @return fee - Cost in Juels (1e18) of LINK
  function getAdminFeeJuels() external view returns (uint72);

  /// @notice Estimate the total cost that will be charged to a subscription to make a request: transmitter gas re-reimbursement, plus DON fee, plus Registry fee
  /// @param - subscriptionId An identifier of the billing account
  /// @param - data Encoded Chainlink Functions request data, use FunctionsClient API to encode a request
  /// @param - callbackGasLimit Gas limit for the fulfillment callback
  /// @param - gasPriceWei The blockchain's gas price to estimate with
  /// @return - billedCost Cost in Juels (1e18) of LINK
  function estimateCost(
    uint64 subscriptionId,
    bytes calldata data,
    uint32 callbackGasLimit,
    uint256 gasPriceWei
  ) external view returns (uint96);

  /// @notice Remove a request commitment that the Router has determined to be stale
  /// @param requestId - The request ID to remove
  function deleteCommitment(bytes32 requestId) external;

  /// @notice Oracle withdraw LINK earned through fulfilling requests
  /// @notice If amount is 0 the full balance will be withdrawn
  /// @param recipient where to send the funds
  /// @param amount amount to withdraw
  function oracleWithdraw(address recipient, uint96 amount) external;

  /// @notice Withdraw all LINK earned by Oracles through fulfilling requests
  /// @dev transmitter addresses must support LINK tokens to avoid tokens from getting stuck as oracleWithdrawAll() calls will forward tokens directly to transmitters
  function oracleWithdrawAll() external;
}

// ================================================================
// |                     Configuration state                      |
// ================================================================

struct FunctionsBillingConfig {
  uint32 fulfillmentGasPriceOverEstimationBP; // ══╗ Percentage of gas price overestimation to account for changes in gas price between request and response. Held as basis points (one hundredth of 1 percentage point)
  uint32 feedStalenessSeconds; //                  ║ How long before we consider the feed price to be stale and fallback to fallbackNativePerUnitLink. Default of 0 means no fallback.
  uint32 gasOverheadBeforeCallback; //             ║ Represents the average gas execution cost before the fulfillment callback. This amount is always billed for every request.
  uint32 gasOverheadAfterCallback; //              ║ Represents the average gas execution cost after the fulfillment callback. This amount is always billed for every request.
  uint40 minimumEstimateGasPriceWei; //            ║ The lowest amount of wei that will be used as the tx.gasprice when estimating the cost to fulfill the request
  uint16 maxSupportedRequestDataVersion; //        ║ The highest support request data version supported by the node. All lower versions should also be supported.
  uint64 fallbackUsdPerUnitLink; //                ║ Fallback LINK / USD conversion rate if the data feed is stale
  uint8 fallbackUsdPerUnitLinkDecimals; // ════════╝ Fallback LINK / USD conversion rate decimal places if the data feed is stale
  uint224 fallbackNativePerUnitLink; // ═══════════╗ Fallback NATIVE CURRENCY / LINK conversion rate if the data feed is stale
  uint32 requestTimeoutSeconds; // ════════════════╝ How many seconds it takes before we consider a request to be timed out
  uint16 donFeeCentsUsd; // ═══════════════════════════════╗ Additional flat fee (denominated in cents of USD, paid as LINK) that will be split between Node Operators.
  uint16 operationFeeCentsUsd; //                          ║ Additional flat fee (denominated in cents of USD, paid as LINK) that will be paid to the owner of the Coordinator contract.
  uint16 transmitTxSizeBytes; // ══════════════════════════╝ The size of the calldata for the transmit transaction in bytes assuming a single 256 byte response payload. Used to estimate L1 cost for fulfillments on L2 chains.
}

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

import {FunctionsResponse} from "../libraries/FunctionsResponse.sol";

/// @title Chainlink Functions DON Coordinator interface.
interface IFunctionsCoordinator {
  /// @notice Returns the DON's threshold encryption public key used to encrypt secrets
  /// @dev All nodes on the DON have separate key shares of the threshold decryption key
  /// and nodes must participate in a threshold decryption OCR round to decrypt secrets
  /// @return thresholdPublicKey the DON's threshold encryption public key
  function getThresholdPublicKey() external view returns (bytes memory);

  /// @notice Sets the DON's threshold encryption public key used to encrypt secrets
  /// @dev Used to rotate the key
  /// @param thresholdPublicKey The new public key
  function setThresholdPublicKey(bytes calldata thresholdPublicKey) external;

  /// @notice Returns the DON's secp256k1 public key that is used to encrypt secrets
  /// @dev All nodes on the DON have the corresponding private key
  /// needed to decrypt the secrets encrypted with the public key
  /// @return publicKey the DON's public key
  function getDONPublicKey() external view returns (bytes memory);

  /// @notice Sets DON's secp256k1 public key used to encrypt secrets
  /// @dev Used to rotate the key
  /// @param donPublicKey The new public key
  function setDONPublicKey(bytes calldata donPublicKey) external;

  /// @notice Receives a request to be emitted to the DON for processing
  /// @param request The request metadata
  /// @dev see the struct for field descriptions
  /// @return commitment - The parameters of the request that must be held consistent at response time
  function startRequest(
    FunctionsResponse.RequestMeta calldata request
  ) external returns (FunctionsResponse.Commitment memory commitment);
}

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

import {FunctionsResponse} from "../libraries/FunctionsResponse.sol";

/// @title Chainlink Functions Router interface.
interface IFunctionsRouter {
  /// @notice The identifier of the route to retrieve the address of the access control contract
  /// The access control contract controls which accounts can manage subscriptions
  /// @return id - bytes32 id that can be passed to the "getContractById" of the Router
  function getAllowListId() external view returns (bytes32);

  /// @notice Set the identifier of the route to retrieve the address of the access control contract
  /// The access control contract controls which accounts can manage subscriptions
  function setAllowListId(bytes32 allowListId) external;

  /// @notice Get the flat fee (in Juels of LINK) that will be paid to the Router owner for operation of the network
  /// @return adminFee
  function getAdminFee() external view returns (uint72 adminFee);

  /// @notice Sends a request using the provided subscriptionId
  /// @param subscriptionId - A unique subscription ID allocated by billing system,
  /// a client can make requests from different contracts referencing the same subscription
  /// @param data - CBOR encoded Chainlink Functions request data, use FunctionsClient API to encode a request
  /// @param dataVersion - Gas limit for the fulfillment callback
  /// @param callbackGasLimit - Gas limit for the fulfillment callback
  /// @param donId - An identifier used to determine which route to send the request along
  /// @return requestId - A unique request identifier
  function sendRequest(
    uint64 subscriptionId,
    bytes calldata data,
    uint16 dataVersion,
    uint32 callbackGasLimit,
    bytes32 donId
  ) external returns (bytes32);

  /// @notice Sends a request to the proposed contracts
  /// @param subscriptionId - A unique subscription ID allocated by billing system,
  /// a client can make requests from different contracts referencing the same subscription
  /// @param data - CBOR encoded Chainlink Functions request data, use FunctionsClient API to encode a request
  /// @param dataVersion - Gas limit for the fulfillment callback
  /// @param callbackGasLimit - Gas limit for the fulfillment callback
  /// @param donId - An identifier used to determine which route to send the request along
  /// @return requestId - A unique request identifier
  function sendRequestToProposed(
    uint64 subscriptionId,
    bytes calldata data,
    uint16 dataVersion,
    uint32 callbackGasLimit,
    bytes32 donId
  ) external returns (bytes32);

  /// @notice Fulfill the request by:
  /// - calling back the data that the Oracle returned to the client contract
  /// - pay the DON for processing the request
  /// @dev Only callable by the Coordinator contract that is saved in the commitment
  /// @param response response data from DON consensus
  /// @param err error from DON consensus
  /// @param juelsPerGas - current rate of juels/gas
  /// @param costWithoutFulfillment - The cost of processing the request (in Juels of LINK ), without fulfillment
  /// @param transmitter - The Node that transmitted the OCR report
  /// @param commitment - The parameters of the request that must be held consistent between request and response time
  /// @return fulfillResult -
  /// @return callbackGasCostJuels -
  function fulfill(
    bytes memory response,
    bytes memory err,
    uint96 juelsPerGas,
    uint96 costWithoutFulfillment,
    address transmitter,
    FunctionsResponse.Commitment memory commitment
  ) external returns (FunctionsResponse.FulfillResult, uint96);

  /// @notice Validate requested gas limit is below the subscription max.
  /// @param subscriptionId subscription ID
  /// @param callbackGasLimit desired callback gas limit
  function isValidCallbackGasLimit(uint64 subscriptionId, uint32 callbackGasLimit) external view;

  /// @notice Get the current contract given an ID
  /// @param id A bytes32 identifier for the route
  /// @return contract The current contract address
  function getContractById(bytes32 id) external view returns (address);

  /// @notice Get the proposed next contract given an ID
  /// @param id A bytes32 identifier for the route
  /// @return contract The current or proposed contract address
  function getProposedContractById(bytes32 id) external view returns (address);

  /// @notice Return the latest proprosal set
  /// @return ids The identifiers of the contracts to update
  /// @return to The addresses of the contracts that will be updated to
  function getProposedContractSet() external view returns (bytes32[] memory, address[] memory);

  /// @notice Proposes one or more updates to the contract routes
  /// @dev Only callable by owner
  function proposeContractsUpdate(bytes32[] memory proposalSetIds, address[] memory proposalSetAddresses) external;

  /// @notice Updates the current contract routes to the proposed contracts
  /// @dev Only callable by owner
  function updateContracts() external;

  /// @dev Puts the system into an emergency stopped state.
  /// @dev Only callable by owner
  function pause() external;

  /// @dev Takes the system out of an emergency stopped state.
  /// @dev Only callable by owner
  function unpause() external;
}

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

import {FunctionsResponse} from "../libraries/FunctionsResponse.sol";

/// @title Chainlink Functions Subscription interface.
interface IFunctionsSubscriptions {
  struct Subscription {
    uint96 balance; // ═════════╗ Common LINK balance that is controlled by the Router to be used for all consumer requests.
    address owner; // ══════════╝ The owner can fund/withdraw/cancel the subscription.
    uint96 blockedBalance; // ══╗ LINK balance that is reserved to pay for pending consumer requests.
    address proposedOwner; // ══╝ For safely transferring sub ownership.
    address[] consumers; // ════╸ Client contracts that can use the subscription
    bytes32 flags; // ══════════╸ Per-subscription flags
  }

  struct Consumer {
    bool allowed; // ══════════════╗ Owner can fund/withdraw/cancel the sub.
    uint64 initiatedRequests; //   ║ The number of requests that have been started
    uint64 completedRequests; // ══╝ The number of requests that have successfully completed or timed out
  }

  /// @notice Get details about a subscription.
  /// @param subscriptionId - the ID of the subscription
  /// @return subscription - see IFunctionsSubscriptions.Subscription for more information on the structure
  function getSubscription(uint64 subscriptionId) external view returns (Subscription memory);

  /// @notice Retrieve details about multiple subscriptions using an inclusive range
  /// @param subscriptionIdStart - the ID of the subscription to start the range at
  /// @param subscriptionIdEnd - the ID of the subscription to end the range at
  /// @return subscriptions - see IFunctionsSubscriptions.Subscription for more information on the structure
  function getSubscriptionsInRange(
    uint64 subscriptionIdStart,
    uint64 subscriptionIdEnd
  ) external view returns (Subscription[] memory);

  /// @notice Get details about a consumer of a subscription.
  /// @param client - the consumer contract address
  /// @param subscriptionId - the ID of the subscription
  /// @return consumer - see IFunctionsSubscriptions.Consumer for more information on the structure
  function getConsumer(address client, uint64 subscriptionId) external view returns (Consumer memory);

  /// @notice Get details about the total amount of LINK within the system
  /// @return totalBalance - total Juels of LINK held by the contract
  function getTotalBalance() external view returns (uint96);

  /// @notice Get details about the total number of subscription accounts
  /// @return count - total number of subscriptions in the system
  function getSubscriptionCount() external view returns (uint64);

  /// @notice Time out all expired requests: unlocks funds and removes the ability for the request to be fulfilled
  /// @param requestsToTimeoutByCommitment - A list of request commitments to time out
  /// @dev The commitment can be found on the "OracleRequest" event created when sending the request.
  function timeoutRequests(FunctionsResponse.Commitment[] calldata requestsToTimeoutByCommitment) external;

  /// @notice Oracle withdraw LINK earned through fulfilling requests
  /// @notice If amount is 0 the full balance will be withdrawn
  /// @notice Both signing and transmitting wallets will have a balance to withdraw
  /// @param recipient where to send the funds
  /// @param amount amount to withdraw
  function oracleWithdraw(address recipient, uint96 amount) external;

  /// @notice Owner cancel subscription, sends remaining link directly to the subscription owner.
  /// @dev Only callable by the Router Owner
  /// @param subscriptionId subscription id
  /// @dev notably can be called even if there are pending requests, outstanding ones may fail onchain
  function ownerCancelSubscription(uint64 subscriptionId) external;

  /// @notice Recover link sent with transfer instead of transferAndCall.
  /// @dev Only callable by the Router Owner
  /// @param to address to send link to
  function recoverFunds(address to) external;

  /// @notice Create a new subscription.
  /// @return subscriptionId - A unique subscription id.
  /// @dev You can manage the consumer set dynamically with addConsumer/removeConsumer.
  /// @dev Note to fund the subscription, use transferAndCall. For example
  /// @dev  LINKTOKEN.transferAndCall(
  /// @dev    address(ROUTER),
  /// @dev    amount,
  /// @dev    abi.encode(subscriptionId));
  function createSubscription() external returns (uint64);

  /// @notice Create a new subscription and add a consumer.
  /// @return subscriptionId - A unique subscription id.
  /// @dev You can manage the consumer set dynamically with addConsumer/removeConsumer.
  /// @dev Note to fund the subscription, use transferAndCall. For example
  /// @dev  LINKTOKEN.transferAndCall(
  /// @dev    address(ROUTER),
  /// @dev    amount,
  /// @dev    abi.encode(subscriptionId));
  function createSubscriptionWithConsumer(address consumer) external returns (uint64 subscriptionId);

  /// @notice Propose a new owner for a subscription.
  /// @dev Only callable by the Subscription's owner
  /// @param subscriptionId - ID of the subscription
  /// @param newOwner - proposed new owner of the subscription
  function proposeSubscriptionOwnerTransfer(uint64 subscriptionId, address newOwner) external;

  /// @notice Accept an ownership transfer.
  /// @param subscriptionId - ID of the subscription
  /// @dev will revert if original owner of subscriptionId has not requested that msg.sender become the new owner.
  function acceptSubscriptionOwnerTransfer(uint64 subscriptionId) external;

  /// @notice Remove a consumer from a Chainlink Functions subscription.
  /// @dev Only callable by the Subscription's owner
  /// @param subscriptionId - ID of the subscription
  /// @param consumer - Consumer to remove from the subscription
  function removeConsumer(uint64 subscriptionId, address consumer) external;

  /// @notice Add a consumer to a Chainlink Functions subscription.
  /// @dev Only callable by the Subscription's owner
  /// @param subscriptionId - ID of the subscription
  /// @param consumer - New consumer which can use the subscription
  function addConsumer(uint64 subscriptionId, address consumer) external;

  /// @notice Cancel a subscription
  /// @dev Only callable by the Subscription's owner
  /// @param subscriptionId - ID of the subscription
  /// @param to - Where to send the remaining LINK to
  function cancelSubscription(uint64 subscriptionId, address to) external;

  /// @notice Check to see if there exists a request commitment for all consumers for a given sub.
  /// @param subscriptionId - ID of the subscription
  /// @return true if there exists at least one unfulfilled request for the subscription, false otherwise.
  /// @dev Looping is bounded to MAX_CONSUMERS*(number of DONs).
  /// @dev Used to disable subscription canceling while outstanding request are present.
  function pendingRequestExists(uint64 subscriptionId) external view returns (bool);

  /// @notice Set subscription specific flags for a subscription.
  /// Each byte of the flag is used to represent a resource tier that the subscription can utilize.
  /// @param subscriptionId - ID of the subscription
  /// @param flags - desired flag values
  function setFlags(uint64 subscriptionId, bytes32 flags) external;

  /// @notice Get flags for a given subscription.
  /// @param subscriptionId - ID of the subscription
  /// @return flags - current flag values
  function getFlags(uint64 subscriptionId) external view returns (bytes32);
}

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

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

  function transferOwnership(address recipient) external;

  function acceptOwnership() external;
}

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

import {IFunctionsRouter} from "./IFunctionsRouter.sol";
import {IOwnable} from "../../../../shared/interfaces/IOwnable.sol";

/// @title Chainlink Functions Router interface with Ownability.
interface IOwnableFunctionsRouter is IOwnable, IFunctionsRouter {}

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

/// @title ISemver
/// @notice ISemver is a simple contract for ensuring that contracts are
///         versioned using semantic versioning.
interface ISemver {
  /// @notice Getter for the semantic version of the contract. This is not
  ///         meant to be used onchain but instead meant to be used by offchain
  ///         tooling.
  /// @return Semver contract version as a string.
  function version() external view returns (string memory);
}

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

interface ITypeAndVersion {
  function typeAndVersion() external pure returns (string memory);
}

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

pragma solidity ^0.8.2;

import "../../utils/Address.sol";

/**
 * @dev This is a base contract to aid in writing upgradeable contracts, or any kind of contract that will be deployed
 * behind a proxy. Since proxied contracts do not make use of a constructor, it's common to move constructor logic to an
 * external initializer function, usually called `initialize`. It then becomes necessary to protect this initializer
 * function so it can only be called once. The {initializer} modifier provided by this contract will have this effect.
 *
 * The initialization functions use a version number. Once a version number is used, it is consumed and cannot be
 * reused. This mechanism prevents re-execution of each "step" but allows the creation of new initialization steps in
 * case an upgrade adds a module that needs to be initialized.
 *
 * For example:
 *
 * [.hljs-theme-light.nopadding]
 * ```solidity
 * contract MyToken is ERC20Upgradeable {
 *     function initialize() initializer public {
 *         __ERC20_init("MyToken", "MTK");
 *     }
 * }
 *
 * contract MyTokenV2 is MyToken, ERC20PermitUpgradeable {
 *     function initializeV2() reinitializer(2) public {
 *         __ERC20Permit_init("MyToken");
 *     }
 * }
 * ```
 *
 * TIP: To avoid leaving the proxy in an uninitialized state, the initializer function should be called as early as
 * possible by providing the encoded function call as the `_data` argument to {ERC1967Proxy-constructor}.
 *
 * CAUTION: When used with inheritance, manual care must be taken to not invoke a parent initializer twice, or to ensure
 * that all initializers are idempotent. This is not verified automatically as constructors are by Solidity.
 *
 * [CAUTION]
 * ====
 * Avoid leaving a contract uninitialized.
 *
 * An uninitialized contract can be taken over by an attacker. This applies to both a proxy and its implementation
 * contract, which may impact the proxy. To prevent the implementation contract from being used, you should invoke
 * the {_disableInitializers} function in the constructor to automatically lock it when it is deployed:
 *
 * [.hljs-theme-light.nopadding]
 * ```
 * /// @custom:oz-upgrades-unsafe-allow constructor
 * constructor() {
 *     _disableInitializers();
 * }
 * ```
 * ====
 */
abstract contract Initializable {
    /**
     * @dev Indicates that the contract has been initialized.
     * @custom:oz-retyped-from bool
     */
    uint8 private _initialized;

    /**
     * @dev Indicates that the contract is in the process of being initialized.
     */
    bool private _initializing;

    /**
     * @dev Triggered when the contract has been initialized or reinitialized.
     */
    event Initialized(uint8 version);

    /**
     * @dev A modifier that defines a protected initializer function that can be invoked at most once. In its scope,
     * `onlyInitializing` functions can be used to initialize parent contracts.
     *
     * Similar to `reinitializer(1)`, except that functions marked with `initializer` can be nested in the context of a
     * constructor.
     *
     * Emits an {Initialized} event.
     */
    modifier initializer() {
        bool isTopLevelCall = !_initializing;
        require(
            (isTopLevelCall && _initialized < 1) || (!Address.isContract(address(this)) && _initialized == 1),
            "Initializable: contract is already initialized"
        );
        _initialized = 1;
        if (isTopLevelCall) {
            _initializing = true;
        }
        _;
        if (isTopLevelCall) {
            _initializing = false;
            emit Initialized(1);
        }
    }

    /**
     * @dev A modifier that defines a protected reinitializer function that can be invoked at most once, and only if the
     * contract hasn't been initialized to a greater version before. In its scope, `onlyInitializing` functions can be
     * used to initialize parent contracts.
     *
     * A reinitializer may be used after the original initialization step. This is essential to configure modules that
     * are added through upgrades and that require initialization.
     *
     * When `version` is 1, this modifier is similar to `initializer`, except that functions marked with `reinitializer`
     * cannot be nested. If one is invoked in the context of another, execution will revert.
     *
     * Note that versions can jump in increments greater than 1; this implies that if multiple reinitializers coexist in
     * a contract, executing them in the right order is up to the developer or operator.
     *
     * WARNING: setting the version to 255 will prevent any future reinitialization.
     *
     * Emits an {Initialized} event.
     */
    modifier reinitializer(uint8 version) {
        require(!_initializing && _initialized < version, "Initializable: contract is already initialized");
        _initialized = version;
        _initializing = true;
        _;
        _initializing = false;
        emit Initialized(version);
    }

    /**
     * @dev Modifier to protect an initialization function so that it can only be invoked by functions with the
     * {initializer} and {reinitializer} modifiers, directly or indirectly.
     */
    modifier onlyInitializing() {
        require(_initializing, "Initializable: contract is not initializing");
        _;
    }

    /**
     * @dev Locks the contract, preventing any future reinitialization. This cannot be part of an initializer call.
     * Calling this in the constructor of a contract will prevent that contract from being initialized or reinitialized
     * to any version. It is recommended to use this to lock implementation contracts that are designed to be called
     * through proxies.
     *
     * Emits an {Initialized} event the first time it is successfully executed.
     */
    function _disableInitializers() internal virtual {
        require(!_initializing, "Initializable: contract is initializing");
        if (_initialized != type(uint8).max) {
            _initialized = type(uint8).max;
            emit Initialized(type(uint8).max);
        }
    }

    /**
     * @dev Returns the highest version that has been initialized. See {reinitializer}.
     */
    function _getInitializedVersion() internal view returns (uint8) {
        return _initialized;
    }

    /**
     * @dev Returns `true` if the contract is currently initializing. See {onlyInitializing}.
     */
    function _isInitializing() internal view returns (bool) {
        return _initializing;
    }
}

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

import {ISemver} from "../universal/ISemver.sol";
import {Constants} from "../libraries/Constants.sol";
import {GasPayingToken, IGasToken} from "../libraries/GasPayingToken.sol";
import "../libraries/L1BlockErrors.sol";

/// @custom:proxied
/// @custom:predeploy 0x4200000000000000000000000000000000000015
/// @title L1Block
/// @notice The L1Block predeploy gives users access to information about the last known L1 block.
///         Values within this contract are updated once per epoch (every L1 block) and can only be
///         set by the "depositor" account, a special system address. Depositor account transactions
///         are created by the protocol whenever we move to a new epoch.
contract L1Block is ISemver, IGasToken {
  /// @notice Event emitted when the gas paying token is set.
  event GasPayingTokenSet(address indexed token, uint8 indexed decimals, bytes32 name, bytes32 symbol);

  /// @notice Address of the special depositor account.
  function DEPOSITOR_ACCOUNT() public pure returns (address addr_) {
    addr_ = Constants.DEPOSITOR_ACCOUNT;
  }

  /// @notice The latest L1 block number known by the L2 system.
  uint64 public number;

  /// @notice The latest L1 timestamp known by the L2 system.
  uint64 public timestamp;

  /// @notice The latest L1 base fee.
  uint256 public basefee;

  /// @notice The latest L1 blockhash.
  bytes32 public hash;

  /// @notice The number of L2 blocks in the same epoch.
  uint64 public sequenceNumber;

  /// @notice The scalar value applied to the L1 blob base fee portion of the blob-capable L1 cost func.
  uint32 public blobBaseFeeScalar;

  /// @notice The scalar value applied to the L1 base fee portion of the blob-capable L1 cost func.
  uint32 public baseFeeScalar;

  /// @notice The versioned hash to authenticate the batcher by.
  bytes32 public batcherHash;

  /// @notice The overhead value applied to the L1 portion of the transaction fee.
  /// @custom:legacy
  uint256 public l1FeeOverhead;

  /// @notice The scalar value applied to the L1 portion of the transaction fee.
  /// @custom:legacy
  uint256 public l1FeeScalar;

  /// @notice The latest L1 blob base fee.
  uint256 public blobBaseFee;

  /// @custom:semver 1.4.1-beta.1
  function version() public pure virtual returns (string memory) {
    return "1.4.1-beta.1";
  }

  /// @notice Returns the gas paying token, its decimals, name and symbol.
  ///         If nothing is set in state, then it means ether is used.
  function gasPayingToken() public view returns (address addr_, uint8 decimals_) {
    (addr_, decimals_) = GasPayingToken.getToken();
  }

  /// @notice Returns the gas paying token name.
  ///         If nothing is set in state, then it means ether is used.
  function gasPayingTokenName() public view returns (string memory name_) {
    name_ = GasPayingToken.getName();
  }

  /// @notice Returns the gas paying token symbol.
  ///         If nothing is set in state, then it means ether is used.
  function gasPayingTokenSymbol() public view returns (string memory symbol_) {
    symbol_ = GasPayingToken.getSymbol();
  }

  /// @notice Getter for custom gas token paying networks. Returns true if the
  ///         network uses a custom gas token.
  function isCustomGasToken() public view returns (bool) {
    (address token, ) = gasPayingToken();
    return token != Constants.ETHER;
  }

  /// @custom:legacy
  /// @notice Updates the L1 block values.
  /// @param _number         L1 blocknumber.
  /// @param _timestamp      L1 timestamp.
  /// @param _basefee        L1 basefee.
  /// @param _hash           L1 blockhash.
  /// @param _sequenceNumber Number of L2 blocks since epoch start.
  /// @param _batcherHash    Versioned hash to authenticate batcher by.
  /// @param _l1FeeOverhead  L1 fee overhead.
  /// @param _l1FeeScalar    L1 fee scalar.
  function setL1BlockValues(
    uint64 _number,
    uint64 _timestamp,
    uint256 _basefee,
    bytes32 _hash,
    uint64 _sequenceNumber,
    bytes32 _batcherHash,
    uint256 _l1FeeOverhead,
    uint256 _l1FeeScalar
  ) external {
    require(msg.sender == DEPOSITOR_ACCOUNT(), "L1Block: only the depositor account can set L1 block values");

    number = _number;
    timestamp = _timestamp;
    basefee = _basefee;
    hash = _hash;
    sequenceNumber = _sequenceNumber;
    batcherHash = _batcherHash;
    l1FeeOverhead = _l1FeeOverhead;
    l1FeeScalar = _l1FeeScalar;
  }

  /// @notice Updates the L1 block values for an Ecotone upgraded chain.
  /// Params are packed and passed in as raw msg.data instead of ABI to reduce calldata size.
  /// Params are expected to be in the following order:
  ///   1. _baseFeeScalar      L1 base fee scalar
  ///   2. _blobBaseFeeScalar  L1 blob base fee scalar
  ///   3. _sequenceNumber     Number of L2 blocks since epoch start.
  ///   4. _timestamp          L1 timestamp.
  ///   5. _number             L1 blocknumber.
  ///   6. _basefee            L1 base fee.
  ///   7. _blobBaseFee        L1 blob base fee.
  ///   8. _hash               L1 blockhash.
  ///   9. _batcherHash        Versioned hash to authenticate batcher by.
  function setL1BlockValuesEcotone() external {
    address depositor = DEPOSITOR_ACCOUNT();
    assembly {
      // Revert if the caller is not the depositor account.
      if xor(caller(), depositor) {
        mstore(0x00, 0x3cc50b45) // 0x3cc50b45 is the 4-byte selector of "NotDepositor()"
        revert(0x1C, 0x04) // returns the stored 4-byte selector from above
      }
      // sequencenum (uint64), blobBaseFeeScalar (uint32), baseFeeScalar (uint32)
      sstore(sequenceNumber.slot, shr(128, calldataload(4)))
      // number (uint64) and timestamp (uint64)
      sstore(number.slot, shr(128, calldataload(20)))
      sstore(basefee.slot, calldataload(36)) // uint256
      sstore(blobBaseFee.slot, calldataload(68)) // uint256
      sstore(hash.slot, calldataload(100)) // bytes32
      sstore(batcherHash.slot, calldataload(132)) // bytes32
    }
  }

  /// @notice Sets the gas paying token for the L2 system. Can only be called by the special
  ///         depositor account. This function is not called on every L2 block but instead
  ///         only called by specially crafted L1 deposit transactions.
  function setGasPayingToken(address _token, uint8 _decimals, bytes32 _name, bytes32 _symbol) external {
    if (msg.sender != DEPOSITOR_ACCOUNT()) revert NotDepositor();

    GasPayingToken.set({_token: _token, _decimals: _decimals, _name: _name, _symbol: _symbol});

    emit GasPayingTokenSet({token: _token, decimals: _decimals, name: _name, symbol: _symbol});
  }
}

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

/// @notice Error returns when a non-depositor account tries to set L1 block values.
error NotDepositor();

/// @notice Error when a chain ID is not in the interop dependency set.
error NotDependency();

/// @notice Error when the interop dependency set size is too large.
error DependencySetSizeTooLarge();

/// @notice Error when a chain ID already in the interop dependency set is attempted to be added.
error AlreadyDependency();

/// @notice Error when the chain's chain ID is attempted to be removed from the interop dependency set.
error CantRemovedDependency();

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

/// @notice Library for converting numbers into strings and other string operations.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibString.sol)
/// @author Modified from Solmate (https://github.com/transmissions11/solmate/blob/main/src/utils/LibString.sol)
///
/// Note:
/// For performance and bytecode compactness, most of the string operations are restricted to
/// byte strings (7-bit ASCII), except where otherwise specified.
/// Usage of byte string operations on charsets with runes spanning two or more bytes
/// can lead to undefined behavior.
library LibString {
  /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
  /*                        CUSTOM ERRORS                       */
  /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

  /// @dev The length of the output is too small to contain all the hex digits.
  error HexLengthInsufficient();

  /// @dev The length of the string is more than 32 bytes.
  error TooBigForSmallString();

  /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
  /*                         CONSTANTS                          */
  /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

  /// @dev The constant returned when the `search` is not found in the string.
  uint256 internal constant NOT_FOUND = type(uint256).max;

  /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
  /*                     DECIMAL OPERATIONS                     */
  /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

  /// @dev Returns the base 10 decimal representation of `value`.
  function toString(uint256 value) internal pure returns (string memory str) {
    /// @solidity memory-safe-assembly
    assembly {
      // The maximum value of a uint256 contains 78 digits (1 byte per digit), but
      // we allocate 0xa0 bytes to keep the free memory pointer 32-byte word aligned.
      // We will need 1 word for the trailing zeros padding, 1 word for the length,
      // and 3 words for a maximum of 78 digits.
      str := add(mload(0x40), 0x80)
      // Update the free memory pointer to allocate.
      mstore(0x40, add(str, 0x20))
      // Zeroize the slot after the string.
      mstore(str, 0)

      // Cache the end of the memory to calculate the length later.
      let end := str

      let w := not(0) // Tsk.
      // We write the string from rightmost digit to leftmost digit.
      // The following is essentially a do-while loop that also handles the zero case.
      for {
        let temp := value
      } 1 {

      } {
        str := add(str, w) // `sub(str, 1)`.
        // Write the character to the pointer.
        // The ASCII index of the '0' character is 48.
        mstore8(str, add(48, mod(temp, 10)))
        // Keep dividing `temp` until zero.
        temp := div(temp, 10)
        if iszero(temp) {
          break
        }
      }

      let length := sub(end, str)
      // Move the pointer 32 bytes leftwards to make room for the length.
      str := sub(str, 0x20)
      // Store the length.
      mstore(str, length)
    }
  }

  /// @dev Returns the base 10 decimal representation of `value`.
  function toString(int256 value) internal pure returns (string memory str) {
    if (value >= 0) {
      return toString(uint256(value));
    }
    unchecked {
      str = toString(uint256(-value));
    }
    /// @solidity memory-safe-assembly
    assembly {
      // We still have some spare memory space on the left,
      // as we have allocated 3 words (96 bytes) for up to 78 digits.
      let length := mload(str) // Load the string length.
      mstore(str, 0x2d) // Store the '-' character.
      str := sub(str, 1) // Move back the string pointer by a byte.
      mstore(str, add(length, 1)) // Update the string length.
    }
  }

  /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
  /*                   HEXADECIMAL OPERATIONS                   */
  /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

  /// @dev Returns the hexadecimal representation of `value`,
  /// left-padded to an input length of `length` bytes.
  /// The output is prefixed with "0x" encoded using 2 hexadecimal digits per byte,
  /// giving a total length of `length * 2 + 2` bytes.
  /// Reverts if `length` is too small for the output to contain all the digits.
  function toHexString(uint256 value, uint256 length) internal pure returns (string memory str) {
    str = toHexStringNoPrefix(value, length);
    /// @solidity memory-safe-assembly
    assembly {
      let strLength := add(mload(str), 2) // Compute the length.
      mstore(str, 0x3078) // Write the "0x" prefix.
      str := sub(str, 2) // Move the pointer.
      mstore(str, strLength) // Write the length.
    }
  }

  /// @dev Returns the hexadecimal representation of `value`,
  /// left-padded to an input length of `length` bytes.
  /// The output is prefixed with "0x" encoded using 2 hexadecimal digits per byte,
  /// giving a total length of `length * 2` bytes.
  /// Reverts if `length` is too small for the output to contain all the digits.
  function toHexStringNoPrefix(uint256 value, uint256 length) internal pure returns (string memory str) {
    /// @solidity memory-safe-assembly
    assembly {
      // We need 0x20 bytes for the trailing zeros padding, `length * 2` bytes
      // for the digits, 0x02 bytes for the prefix, and 0x20 bytes for the length.
      // We add 0x20 to the total and round down to a multiple of 0x20.
      // (0x20 + 0x20 + 0x02 + 0x20) = 0x62.
      str := add(mload(0x40), and(add(shl(1, length), 0x42), not(0x1f)))
      // Allocate the memory.
      mstore(0x40, add(str, 0x20))
      // Zeroize the slot after the string.
      mstore(str, 0)

      // Cache the end to calculate the length later.
      let end := str
      // Store "0123456789abcdef" in scratch space.
      mstore(0x0f, 0x30313233343536373839616263646566)

      let start := sub(str, add(length, length))
      let w := not(1) // Tsk.
      let temp := value
      // We write the string from rightmost digit to leftmost digit.
      // The following is essentially a do-while loop that also handles the zero case.
      for {

      } 1 {

      } {
        str := add(str, w) // `sub(str, 2)`.
        mstore8(add(str, 1), mload(and(temp, 15)))
        mstore8(str, mload(and(shr(4, temp), 15)))
        temp := shr(8, temp)
        if iszero(xor(str, start)) {
          break
        }
      }

      if temp {
        mstore(0x00, 0x2194895a) // `HexLengthInsufficient()`.
        revert(0x1c, 0x04)
      }

      // Compute the string's length.
      let strLength := sub(end, str)
      // Move the pointer and write the length.
      str := sub(str, 0x20)
      mstore(str, strLength)
    }
  }

  /// @dev Returns the hexadecimal representation of `value`.
  /// The output is prefixed with "0x" and encoded using 2 hexadecimal digits per byte.
  /// As address are 20 bytes long, the output will left-padded to have
  /// a length of `20 * 2 + 2` bytes.
  function toHexString(uint256 value) internal pure returns (string memory str) {
    str = toHexStringNoPrefix(value);
    /// @solidity memory-safe-assembly
    assembly {
      let strLength := add(mload(str), 2) // Compute the length.
      mstore(str, 0x3078) // Write the "0x" prefix.
      str := sub(str, 2) // Move the pointer.
      mstore(str, strLength) // Write the length.
    }
  }

  /// @dev Returns the hexadecimal representation of `value`.
  /// The output is prefixed with "0x".
  /// The output excludes leading "0" from the `toHexString` output.
  /// `0x00: "0x0", 0x01: "0x1", 0x12: "0x12", 0x123: "0x123"`.
  function toMinimalHexString(uint256 value) internal pure returns (string memory str) {
    str = toHexStringNoPrefix(value);
    /// @solidity memory-safe-assembly
    assembly {
      let o := eq(byte(0, mload(add(str, 0x20))), 0x30) // Whether leading zero is present.
      let strLength := add(mload(str), 2) // Compute the length.
      mstore(add(str, o), 0x3078) // Write the "0x" prefix, accounting for leading zero.
      str := sub(add(str, o), 2) // Move the pointer, accounting for leading zero.
      mstore(str, sub(strLength, o)) // Write the length, accounting for leading zero.
    }
  }

  /// @dev Returns the hexadecimal representation of `value`.
  /// The output excludes leading "0" from the `toHexStringNoPrefix` output.
  /// `0x00: "0", 0x01: "1", 0x12: "12", 0x123: "123"`.
  function toMinimalHexStringNoPrefix(uint256 value) internal pure returns (string memory str) {
    str = toHexStringNoPrefix(value);
    /// @solidity memory-safe-assembly
    assembly {
      let o := eq(byte(0, mload(add(str, 0x20))), 0x30) // Whether leading zero is present.
      let strLength := mload(str) // Get the length.
      str := add(str, o) // Move the pointer, accounting for leading zero.
      mstore(str, sub(strLength, o)) // Write the length, accounting for leading zero.
    }
  }

  /// @dev Returns the hexadecimal representation of `value`.
  /// The output is encoded using 2 hexadecimal digits per byte.
  /// As address are 20 bytes long, the output will left-padded to have
  /// a length of `20 * 2` bytes.
  function toHexStringNoPrefix(uint256 value) internal pure returns (string memory str) {
    /// @solidity memory-safe-assembly
    assembly {
      // We need 0x20 bytes for the trailing zeros padding, 0x20 bytes for the length,
      // 0x02 bytes for the prefix, and 0x40 bytes for the digits.
      // The next multiple of 0x20 above (0x20 + 0x20 + 0x02 + 0x40) is 0xa0.
      str := add(mload(0x40), 0x80)
      // Allocate the memory.
      mstore(0x40, add(str, 0x20))
      // Zeroize the slot after the string.
      mstore(str, 0)

      // Cache the end to calculate the length later.
      let end := str
      // Store "0123456789abcdef" in scratch space.
      mstore(0x0f, 0x30313233343536373839616263646566)

      let w := not(1) // Tsk.
      // We write the string from rightmost digit to leftmost digit.
      // The following is essentially a do-while loop that also handles the zero case.
      for {
        let temp := value
      } 1 {

      } {
        str := add(str, w) // `sub(str, 2)`.
        mstore8(add(str, 1), mload(and(temp, 15)))
        mstore8(str, mload(and(shr(4, temp), 15)))
        temp := shr(8, temp)
        if iszero(temp) {
          break
        }
      }

      // Compute the string's length.
      let strLength := sub(end, str)
      // Move the pointer and write the length.
      str := sub(str, 0x20)
      mstore(str, strLength)
    }
  }

  /// @dev Returns the hexadecimal representation of `value`.
  /// The output is prefixed with "0x", encoded using 2 hexadecimal digits per byte,
  /// and the alphabets are capitalized conditionally according to
  /// https://eips.ethereum.org/EIPS/eip-55
  function toHexStringChecksummed(address value) internal pure returns (string memory str) {
    str = toHexString(value);
    /// @solidity memory-safe-assembly
    assembly {
      let mask := shl(6, div(not(0), 255)) // `0b010000000100000000 ...`
      let o := add(str, 0x22)
      let hashed := and(keccak256(o, 40), mul(34, mask)) // `0b10001000 ... `
      let t := shl(240, 136) // `0b10001000 << 240`
      for {
        let i := 0
      } 1 {

      } {
        mstore(add(i, i), mul(t, byte(i, hashed)))
        i := add(i, 1)
        if eq(i, 20) {
          break
        }
      }
      mstore(o, xor(mload(o), shr(1, and(mload(0x00), and(mload(o), mask)))))
      o := add(o, 0x20)
      mstore(o, xor(mload(o), shr(1, and(mload(0x20), and(mload(o), mask)))))
    }
  }

  /// @dev Returns the hexadecimal representation of `value`.
  /// The output is prefixed with "0x" and encoded using 2 hexadecimal digits per byte.
  function toHexString(address value) internal pure returns (string memory str) {
    str = toHexStringNoPrefix(value);
    /// @solidity memory-safe-assembly
    assembly {
      let strLength := add(mload(str), 2) // Compute the length.
      mstore(str, 0x3078) // Write the "0x" prefix.
      str := sub(str, 2) // Move the pointer.
      mstore(str, strLength) // Write the length.
    }
  }

  /// @dev Returns the hexadecimal representation of `value`.
  /// The output is encoded using 2 hexadecimal digits per byte.
  function toHexStringNoPrefix(address value) internal pure returns (string memory str) {
    /// @solidity memory-safe-assembly
    assembly {
      str := mload(0x40)

      // Allocate the memory.
      // We need 0x20 bytes for the trailing zeros padding, 0x20 bytes for the length,
      // 0x02 bytes for the prefix, and 0x28 bytes for the digits.
      // The next multiple of 0x20 above (0x20 + 0x20 + 0x02 + 0x28) is 0x80.
      mstore(0x40, add(str, 0x80))

      // Store "0123456789abcdef" in scratch space.
      mstore(0x0f, 0x30313233343536373839616263646566)

      str := add(str, 2)
      mstore(str, 40)

      let o := add(str, 0x20)
      mstore(add(o, 40), 0)

      value := shl(96, value)

      // We write the string from rightmost digit to leftmost digit.
      // The following is essentially a do-while loop that also handles the zero case.
      for {
        let i := 0
      } 1 {

      } {
        let p := add(o, add(i, i))
        let temp := byte(i, value)
        mstore8(add(p, 1), mload(and(temp, 15)))
        mstore8(p, mload(shr(4, temp)))
        i := add(i, 1)
        if eq(i, 20) {
          break
        }
      }
    }
  }

  /// @dev Returns the hex encoded string from the raw bytes.
  /// The output is encoded using 2 hexadecimal digits per byte.
  function toHexString(bytes memory raw) internal pure returns (string memory str) {
    str = toHexStringNoPrefix(raw);
    /// @solidity memory-safe-assembly
    assembly {
      let strLength := add(mload(str), 2) // Compute the length.
      mstore(str, 0x3078) // Write the "0x" prefix.
      str := sub(str, 2) // Move the pointer.
      mstore(str, strLength) // Write the length.
    }
  }

  /// @dev Returns the hex encoded string from the raw bytes.
  /// The output is encoded using 2 hexadecimal digits per byte.
  function toHexStringNoPrefix(bytes memory raw) internal pure returns (string memory str) {
    /// @solidity memory-safe-assembly
    assembly {
      let length := mload(raw)
      str := add(mload(0x40), 2) // Skip 2 bytes for the optional prefix.
      mstore(str, add(length, length)) // Store the length of the output.

      // Store "0123456789abcdef" in scratch space.
      mstore(0x0f, 0x30313233343536373839616263646566)

      let o := add(str, 0x20)
      let end := add(raw, length)

      for {

      } iszero(eq(raw, end)) {

      } {
        raw := add(raw, 1)
        mstore8(add(o, 1), mload(and(mload(raw), 15)))
        mstore8(o, mload(and(shr(4, mload(raw)), 15)))
        o := add(o, 2)
      }
      mstore(o, 0) // Zeroize the slot after the string.
      mstore(0x40, add(o, 0x20)) // Allocate the memory.
    }
  }

  /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
  /*                   RUNE STRING OPERATIONS                   */
  /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

  /// @dev Returns the number of UTF characters in the string.
  function runeCount(string memory s) internal pure returns (uint256 result) {
    /// @solidity memory-safe-assembly
    assembly {
      if mload(s) {
        mstore(0x00, div(not(0), 255))
        mstore(0x20, 0x0202020202020202020202020202020202020202020202020303030304040506)
        let o := add(s, 0x20)
        let end := add(o, mload(s))
        for {
          result := 1
        } 1 {
          result := add(result, 1)
        } {
          o := add(o, byte(0, mload(shr(250, mload(o)))))
          if iszero(lt(o, end)) {
            break
          }
        }
      }
    }
  }

  /// @dev Returns if this string is a 7-bit ASCII string.
  /// (i.e. all characters codes are in [0..127])
  function is7BitASCII(string memory s) internal pure returns (bool result) {
    /// @solidity memory-safe-assembly
    assembly {
      let mask := shl(7, div(not(0), 255))
      result := 1
      let n := mload(s)
      if n {
        let o := add(s, 0x20)
        let end := add(o, n)
        let last := mload(end)
        mstore(end, 0)
        for {

        } 1 {

        } {
          if and(mask, mload(o)) {
            result := 0
            break
          }
          o := add(o, 0x20)
          if iszero(lt(o, end)) {
            break
          }
        }
        mstore(end, last)
      }
    }
  }

  /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
  /*                   BYTE STRING OPERATIONS                   */
  /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

  // For performance and bytecode compactness, byte string operations are restricted
  // to 7-bit ASCII strings. All offsets are byte offsets, not UTF character offsets.
  // Usage of byte string operations on charsets with runes spanning two or more bytes
  // can lead to undefined behavior.

  /// @dev Returns `subject` all occurrences of `search` replaced with `replacement`.
  function replace(
    string memory subject,
    string memory search,
    string memory replacement
  ) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      let subjectLength := mload(subject)
      let searchLength := mload(search)
      let replacementLength := mload(replacement)

      subject := add(subject, 0x20)
      search := add(search, 0x20)
      replacement := add(replacement, 0x20)
      result := add(mload(0x40), 0x20)

      let subjectEnd := add(subject, subjectLength)
      if iszero(gt(searchLength, subjectLength)) {
        let subjectSearchEnd := add(sub(subjectEnd, searchLength), 1)
        let h := 0
        if iszero(lt(searchLength, 0x20)) {
          h := keccak256(search, searchLength)
        }
        let m := shl(3, sub(0x20, and(searchLength, 0x1f)))
        let s := mload(search)
        for {

        } 1 {

        } {
          let t := mload(subject)
          // Whether the first `searchLength % 32` bytes of
          // `subject` and `search` matches.
          if iszero(shr(m, xor(t, s))) {
            if h {
              if iszero(eq(keccak256(subject, searchLength), h)) {
                mstore(result, t)
                result := add(result, 1)
                subject := add(subject, 1)
                if iszero(lt(subject, subjectSearchEnd)) {
                  break
                }
                continue
              }
            }
            // Copy the `replacement` one word at a time.
            for {
              let o := 0
            } 1 {

            } {
              mstore(add(result, o), mload(add(replacement, o)))
              o := add(o, 0x20)
              if iszero(lt(o, replacementLength)) {
                break
              }
            }
            result := add(result, replacementLength)
            subject := add(subject, searchLength)
            if searchLength {
              if iszero(lt(subject, subjectSearchEnd)) {
                break
              }
              continue
            }
          }
          mstore(result, t)
          result := add(result, 1)
          subject := add(subject, 1)
          if iszero(lt(subject, subjectSearchEnd)) {
            break
          }
        }
      }

      let resultRemainder := result
      result := add(mload(0x40), 0x20)
      let k := add(sub(resultRemainder, result), sub(subjectEnd, subject))
      // Copy the rest of the string one word at a time.
      for {

      } lt(subject, subjectEnd) {

      } {
        mstore(resultRemainder, mload(subject))
        resultRemainder := add(resultRemainder, 0x20)
        subject := add(subject, 0x20)
      }
      result := sub(result, 0x20)
      let last := add(add(result, 0x20), k) // Zeroize the slot after the string.
      mstore(last, 0)
      mstore(0x40, add(last, 0x20)) // Allocate the memory.
      mstore(result, k) // Store the length.
    }
  }

  /// @dev Returns the byte index of the first location of `search` in `subject`,
  /// searching from left to right, starting from `from`.
  /// Returns `NOT_FOUND` (i.e. `type(uint256).max`) if the `search` is not found.
  function indexOf(string memory subject, string memory search, uint256 from) internal pure returns (uint256 result) {
    /// @solidity memory-safe-assembly
    assembly {
      for {
        let subjectLength := mload(subject)
      } 1 {

      } {
        if iszero(mload(search)) {
          if iszero(gt(from, subjectLength)) {
            result := from
            break
          }
          result := subjectLength
          break
        }
        let searchLength := mload(search)
        let subjectStart := add(subject, 0x20)

        result := not(0) // Initialize to `NOT_FOUND`.

        subject := add(subjectStart, from)
        let end := add(sub(add(subjectStart, subjectLength), searchLength), 1)

        let m := shl(3, sub(0x20, and(searchLength, 0x1f)))
        let s := mload(add(search, 0x20))

        if iszero(and(lt(subject, end), lt(from, subjectLength))) {
          break
        }

        if iszero(lt(searchLength, 0x20)) {
          for {
            let h := keccak256(add(search, 0x20), searchLength)
          } 1 {

          } {
            if iszero(shr(m, xor(mload(subject), s))) {
              if eq(keccak256(subject, searchLength), h) {
                result := sub(subject, subjectStart)
                break
              }
            }
            subject := add(subject, 1)
            if iszero(lt(subject, end)) {
              break
            }
          }
          break
        }
        for {

        } 1 {

        } {
          if iszero(shr(m, xor(mload(subject), s))) {
            result := sub(subject, subjectStart)
            break
          }
          subject := add(subject, 1)
          if iszero(lt(subject, end)) {
            break
          }
        }
        break
      }
    }
  }

  /// @dev Returns the byte index of the first location of `search` in `subject`,
  /// searching from left to right.
  /// Returns `NOT_FOUND` (i.e. `type(uint256).max`) if the `search` is not found.
  function indexOf(string memory subject, string memory search) internal pure returns (uint256 result) {
    result = indexOf(subject, search, 0);
  }

  /// @dev Returns the byte index of the first location of `search` in `subject`,
  /// searching from right to left, starting from `from`.
  /// Returns `NOT_FOUND` (i.e. `type(uint256).max`) if the `search` is not found.
  function lastIndexOf(
    string memory subject,
    string memory search,
    uint256 from
  ) internal pure returns (uint256 result) {
    /// @solidity memory-safe-assembly
    assembly {
      for {

      } 1 {

      } {
        result := not(0) // Initialize to `NOT_FOUND`.
        let searchLength := mload(search)
        if gt(searchLength, mload(subject)) {
          break
        }
        let w := result

        let fromMax := sub(mload(subject), searchLength)
        if iszero(gt(fromMax, from)) {
          from := fromMax
        }

        let end := add(add(subject, 0x20), w)
        subject := add(add(subject, 0x20), from)
        if iszero(gt(subject, end)) {
          break
        }
        // As this function is not too often used,
        // we shall simply use keccak256 for smaller bytecode size.
        for {
          let h := keccak256(add(search, 0x20), searchLength)
        } 1 {

        } {
          if eq(keccak256(subject, searchLength), h) {
            result := sub(subject, add(end, 1))
            break
          }
          subject := add(subject, w) // `sub(subject, 1)`.
          if iszero(gt(subject, end)) {
            break
          }
        }
        break
      }
    }
  }

  /// @dev Returns the byte index of the first location of `search` in `subject`,
  /// searching from right to left.
  /// Returns `NOT_FOUND` (i.e. `type(uint256).max`) if the `search` is not found.
  function lastIndexOf(string memory subject, string memory search) internal pure returns (uint256 result) {
    result = lastIndexOf(subject, search, uint256(int256(-1)));
  }

  /// @dev Returns true if `search` is found in `subject`, false otherwise.
  function contains(string memory subject, string memory search) internal pure returns (bool) {
    return indexOf(subject, search) != NOT_FOUND;
  }

  /// @dev Returns whether `subject` starts with `search`.
  function startsWith(string memory subject, string memory search) internal pure returns (bool result) {
    /// @solidity memory-safe-assembly
    assembly {
      let searchLength := mload(search)
      // Just using keccak256 directly is actually cheaper.
      // forgefmt: disable-next-item
      result := and(
        iszero(gt(searchLength, mload(subject))),
        eq(keccak256(add(subject, 0x20), searchLength), keccak256(add(search, 0x20), searchLength))
      )
    }
  }

  /// @dev Returns whether `subject` ends with `search`.
  function endsWith(string memory subject, string memory search) internal pure returns (bool result) {
    /// @solidity memory-safe-assembly
    assembly {
      let searchLength := mload(search)
      let subjectLength := mload(subject)
      // Whether `search` is not longer than `subject`.
      let withinRange := iszero(gt(searchLength, subjectLength))
      // Just using keccak256 directly is actually cheaper.
      // forgefmt: disable-next-item
      result := and(
        withinRange,
        eq(
          keccak256(
            // `subject + 0x20 + max(subjectLength - searchLength, 0)`.
            add(add(subject, 0x20), mul(withinRange, sub(subjectLength, searchLength))),
            searchLength
          ),
          keccak256(add(search, 0x20), searchLength)
        )
      )
    }
  }

  /// @dev Returns `subject` repeated `times`.
  function repeat(string memory subject, uint256 times) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      let subjectLength := mload(subject)
      if iszero(or(iszero(times), iszero(subjectLength))) {
        subject := add(subject, 0x20)
        result := mload(0x40)
        let output := add(result, 0x20)
        for {

        } 1 {

        } {
          // Copy the `subject` one word at a time.
          for {
            let o := 0
          } 1 {

          } {
            mstore(add(output, o), mload(add(subject, o)))
            o := add(o, 0x20)
            if iszero(lt(o, subjectLength)) {
              break
            }
          }
          output := add(output, subjectLength)
          times := sub(times, 1)
          if iszero(times) {
            break
          }
        }
        mstore(output, 0) // Zeroize the slot after the string.
        let resultLength := sub(output, add(result, 0x20))
        mstore(result, resultLength) // Store the length.
        // Allocate the memory.
        mstore(0x40, add(result, add(resultLength, 0x20)))
      }
    }
  }

  /// @dev Returns a copy of `subject` sliced from `start` to `end` (exclusive).
  /// `start` and `end` are byte offsets.
  function slice(string memory subject, uint256 start, uint256 end) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      let subjectLength := mload(subject)
      if iszero(gt(subjectLength, end)) {
        end := subjectLength
      }
      if iszero(gt(subjectLength, start)) {
        start := subjectLength
      }
      if lt(start, end) {
        result := mload(0x40)
        let resultLength := sub(end, start)
        mstore(result, resultLength)
        subject := add(subject, start)
        let w := not(0x1f)
        // Copy the `subject` one word at a time, backwards.
        for {
          let o := and(add(resultLength, 0x1f), w)
        } 1 {

        } {
          mstore(add(result, o), mload(add(subject, o)))
          o := add(o, w) // `sub(o, 0x20)`.
          if iszero(o) {
            break
          }
        }
        // Zeroize the slot after the string.
        mstore(add(add(result, 0x20), resultLength), 0)
        // Allocate memory for the length and the bytes,
        // rounded up to a multiple of 32.
        mstore(0x40, add(result, and(add(resultLength, 0x3f), w)))
      }
    }
  }

  /// @dev Returns a copy of `subject` sliced from `start` to the end of the string.
  /// `start` is a byte offset.
  function slice(string memory subject, uint256 start) internal pure returns (string memory result) {
    result = slice(subject, start, uint256(int256(-1)));
  }

  /// @dev Returns all the indices of `search` in `subject`.
  /// The indices are byte offsets.
  function indicesOf(string memory subject, string memory search) internal pure returns (uint256[] memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      let subjectLength := mload(subject)
      let searchLength := mload(search)

      if iszero(gt(searchLength, subjectLength)) {
        subject := add(subject, 0x20)
        search := add(search, 0x20)
        result := add(mload(0x40), 0x20)

        let subjectStart := subject
        let subjectSearchEnd := add(sub(add(subject, subjectLength), searchLength), 1)
        let h := 0
        if iszero(lt(searchLength, 0x20)) {
          h := keccak256(search, searchLength)
        }
        let m := shl(3, sub(0x20, and(searchLength, 0x1f)))
        let s := mload(search)
        for {

        } 1 {

        } {
          let t := mload(subject)
          // Whether the first `searchLength % 32` bytes of
          // `subject` and `search` matches.
          if iszero(shr(m, xor(t, s))) {
            if h {
              if iszero(eq(keccak256(subject, searchLength), h)) {
                subject := add(subject, 1)
                if iszero(lt(subject, subjectSearchEnd)) {
                  break
                }
                continue
              }
            }
            // Append to `result`.
            mstore(result, sub(subject, subjectStart))
            result := add(result, 0x20)
            // Advance `subject` by `searchLength`.
            subject := add(subject, searchLength)
            if searchLength {
              if iszero(lt(subject, subjectSearchEnd)) {
                break
              }
              continue
            }
          }
          subject := add(subject, 1)
          if iszero(lt(subject, subjectSearchEnd)) {
            break
          }
        }
        let resultEnd := result
        // Assign `result` to the free memory pointer.
        result := mload(0x40)
        // Store the length of `result`.
        mstore(result, shr(5, sub(resultEnd, add(result, 0x20))))
        // Allocate memory for result.
        // We allocate one more word, so this array can be recycled for {split}.
        mstore(0x40, add(resultEnd, 0x20))
      }
    }
  }

  /// @dev Returns a arrays of strings based on the `delimiter` inside of the `subject` string.
  function split(string memory subject, string memory delimiter) internal pure returns (string[] memory result) {
    uint256[] memory indices = indicesOf(subject, delimiter);
    /// @solidity memory-safe-assembly
    assembly {
      let w := not(0x1f)
      let indexPtr := add(indices, 0x20)
      let indicesEnd := add(indexPtr, shl(5, add(mload(indices), 1)))
      mstore(add(indicesEnd, w), mload(subject))
      mstore(indices, add(mload(indices), 1))
      let prevIndex := 0
      for {

      } 1 {

      } {
        let index := mload(indexPtr)
        mstore(indexPtr, 0x60)
        if iszero(eq(index, prevIndex)) {
          let element := mload(0x40)
          let elementLength := sub(index, prevIndex)
          mstore(element, elementLength)
          // Copy the `subject` one word at a time, backwards.
          for {
            let o := and(add(elementLength, 0x1f), w)
          } 1 {

          } {
            mstore(add(element, o), mload(add(add(subject, prevIndex), o)))
            o := add(o, w) // `sub(o, 0x20)`.
            if iszero(o) {
              break
            }
          }
          // Zeroize the slot after the string.
          mstore(add(add(element, 0x20), elementLength), 0)
          // Allocate memory for the length and the bytes,
          // rounded up to a multiple of 32.
          mstore(0x40, add(element, and(add(elementLength, 0x3f), w)))
          // Store the `element` into the array.
          mstore(indexPtr, element)
        }
        prevIndex := add(index, mload(delimiter))
        indexPtr := add(indexPtr, 0x20)
        if iszero(lt(indexPtr, indicesEnd)) {
          break
        }
      }
      result := indices
      if iszero(mload(delimiter)) {
        result := add(indices, 0x20)
        mstore(result, sub(mload(indices), 2))
      }
    }
  }

  /// @dev Returns a concatenated string of `a` and `b`.
  /// Cheaper than `string.concat()` and does not de-align the free memory pointer.
  function concat(string memory a, string memory b) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      let w := not(0x1f)
      result := mload(0x40)
      let aLength := mload(a)
      // Copy `a` one word at a time, backwards.
      for {
        let o := and(add(aLength, 0x20), w)
      } 1 {

      } {
        mstore(add(result, o), mload(add(a, o)))
        o := add(o, w) // `sub(o, 0x20)`.
        if iszero(o) {
          break
        }
      }
      let bLength := mload(b)
      let output := add(result, aLength)
      // Copy `b` one word at a time, backwards.
      for {
        let o := and(add(bLength, 0x20), w)
      } 1 {

      } {
        mstore(add(output, o), mload(add(b, o)))
        o := add(o, w) // `sub(o, 0x20)`.
        if iszero(o) {
          break
        }
      }
      let totalLength := add(aLength, bLength)
      let last := add(add(result, 0x20), totalLength)
      // Zeroize the slot after the string.
      mstore(last, 0)
      // Stores the length.
      mstore(result, totalLength)
      // Allocate memory for the length and the bytes,
      // rounded up to a multiple of 32.
      mstore(0x40, and(add(last, 0x1f), w))
    }
  }

  /// @dev Returns a copy of the string in either lowercase or UPPERCASE.
  /// WARNING! This function is only compatible with 7-bit ASCII strings.
  function toCase(string memory subject, bool toUpper) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      let length := mload(subject)
      if length {
        result := add(mload(0x40), 0x20)
        subject := add(subject, 1)
        let flags := shl(add(70, shl(5, toUpper)), 0x3ffffff)
        let w := not(0)
        for {
          let o := length
        } 1 {

        } {
          o := add(o, w)
          let b := and(0xff, mload(add(subject, o)))
          mstore8(add(result, o), xor(b, and(shr(b, flags), 0x20)))
          if iszero(o) {
            break
          }
        }
        result := mload(0x40)
        mstore(result, length) // Store the length.
        let last := add(add(result, 0x20), length)
        mstore(last, 0) // Zeroize the slot after the string.
        mstore(0x40, add(last, 0x20)) // Allocate the memory.
      }
    }
  }

  /// @dev Returns a string from a small bytes32 string.
  /// `s` must be null-terminated, or behavior will be undefined.
  function fromSmallString(bytes32 s) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      result := mload(0x40)
      let n := 0
      for {

      } byte(n, s) {
        n := add(n, 1)
      } {

      } // Scan for '\0'.
      mstore(result, n)
      let o := add(result, 0x20)
      mstore(o, s)
      mstore(add(o, n), 0)
      mstore(0x40, add(result, 0x40))
    }
  }

  /// @dev Returns the small string, with all bytes after the first null byte zeroized.
  function normalizeSmallString(bytes32 s) internal pure returns (bytes32 result) {
    /// @solidity memory-safe-assembly
    assembly {
      for {

      } byte(result, s) {
        result := add(result, 1)
      } {

      } // Scan for '\0'.
      mstore(0x00, s)
      mstore(result, 0x00)
      result := mload(0x00)
    }
  }

  /// @dev Returns the string as a normalized null-terminated small string.
  function toSmallString(string memory s) internal pure returns (bytes32 result) {
    /// @solidity memory-safe-assembly
    assembly {
      result := mload(s)
      if iszero(lt(result, 33)) {
        mstore(0x00, 0xec92f9a3) // `TooBigForSmallString()`.
        revert(0x1c, 0x04)
      }
      result := shl(shl(3, sub(32, result)), mload(add(s, result)))
    }
  }

  /// @dev Returns a lowercased copy of the string.
  /// WARNING! This function is only compatible with 7-bit ASCII strings.
  function lower(string memory subject) internal pure returns (string memory result) {
    result = toCase(subject, false);
  }

  /// @dev Returns an UPPERCASED copy of the string.
  /// WARNING! This function is only compatible with 7-bit ASCII strings.
  function upper(string memory subject) internal pure returns (string memory result) {
    result = toCase(subject, true);
  }

  /// @dev Escapes the string to be used within HTML tags.
  function escapeHTML(string memory s) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      let end := add(s, mload(s))
      result := add(mload(0x40), 0x20)
      // Store the bytes of the packed offsets and strides into the scratch space.
      // `packed = (stride << 5) | offset`. Max offset is 20. Max stride is 6.
      mstore(0x1f, 0x900094)
      mstore(0x08, 0xc0000000a6ab)
      // Store "&quot;&amp;&#39;&lt;&gt;" into the scratch space.
      mstore(0x00, shl(64, 0x2671756f743b26616d703b262333393b266c743b2667743b))
      for {

      } iszero(eq(s, end)) {

      } {
        s := add(s, 1)
        let c := and(mload(s), 0xff)
        // Not in `["\"","'","&","<",">"]`.
        if iszero(and(shl(c, 1), 0x500000c400000000)) {
          mstore8(result, c)
          result := add(result, 1)
          continue
        }
        let t := shr(248, mload(c))
        mstore(result, mload(and(t, 0x1f)))
        result := add(result, shr(5, t))
      }
      let last := result
      mstore(last, 0) // Zeroize the slot after the string.
      result := mload(0x40)
      mstore(result, sub(last, add(result, 0x20))) // Store the length.
      mstore(0x40, add(last, 0x20)) // Allocate the memory.
    }
  }

  /// @dev Escapes the string to be used within double-quotes in a JSON.
  /// If `addDoubleQuotes` is true, the result will be enclosed in double-quotes.
  function escapeJSON(string memory s, bool addDoubleQuotes) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      let end := add(s, mload(s))
      result := add(mload(0x40), 0x20)
      if addDoubleQuotes {
        mstore8(result, 34)
        result := add(1, result)
      }
      // Store "\\u0000" in scratch space.
      // Store "0123456789abcdef" in scratch space.
      // Also, store `{0x08:"b", 0x09:"t", 0x0a:"n", 0x0c:"f", 0x0d:"r"}`.
      // into the scratch space.
      mstore(0x15, 0x5c75303030303031323334353637383961626364656662746e006672)
      // Bitmask for detecting `["\"","\\"]`.
      let e := or(shl(0x22, 1), shl(0x5c, 1))
      for {

      } iszero(eq(s, end)) {

      } {
        s := add(s, 1)
        let c := and(mload(s), 0xff)
        if iszero(lt(c, 0x20)) {
          if iszero(and(shl(c, 1), e)) {
            // Not in `["\"","\\"]`.
            mstore8(result, c)
            result := add(result, 1)
            continue
          }
          mstore8(result, 0x5c) // "\\".
          mstore8(add(result, 1), c)
          result := add(result, 2)
          continue
        }
        if iszero(and(shl(c, 1), 0x3700)) {
          // Not in `["\b","\t","\n","\f","\d"]`.
          mstore8(0x1d, mload(shr(4, c))) // Hex value.
          mstore8(0x1e, mload(and(c, 15))) // Hex value.
          mstore(result, mload(0x19)) // "\\u00XX".
          result := add(result, 6)
          continue
        }
        mstore8(result, 0x5c) // "\\".
        mstore8(add(result, 1), mload(add(c, 8)))
        result := add(result, 2)
      }
      if addDoubleQuotes {
        mstore8(result, 34)
        result := add(1, result)
      }
      let last := result
      mstore(last, 0) // Zeroize the slot after the string.
      result := mload(0x40)
      mstore(result, sub(last, add(result, 0x20))) // Store the length.
      mstore(0x40, add(last, 0x20)) // Allocate the memory.
    }
  }

  /// @dev Escapes the string to be used within double-quotes in a JSON.
  function escapeJSON(string memory s) internal pure returns (string memory result) {
    result = escapeJSON(s, false);
  }

  /// @dev Returns whether `a` equals `b`.
  function eq(string memory a, string memory b) internal pure returns (bool result) {
    /// @solidity memory-safe-assembly
    assembly {
      result := eq(keccak256(add(a, 0x20), mload(a)), keccak256(add(b, 0x20), mload(b)))
    }
  }

  /// @dev Returns whether `a` equals `b`, where `b` is a null-terminated small string.
  function eqs(string memory a, bytes32 b) internal pure returns (bool result) {
    /// @solidity memory-safe-assembly
    assembly {
      // These should be evaluated on compile time, as far as possible.
      let m := not(shl(7, div(not(iszero(b)), 255))) // `0x7f7f ...`.
      let x := not(or(m, or(b, add(m, and(b, m)))))
      let r := shl(7, iszero(iszero(shr(128, x))))
      r := or(r, shl(6, iszero(iszero(shr(64, shr(r, x))))))
      r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
      r := or(r, shl(4, lt(0xffff, shr(r, x))))
      r := or(r, shl(3, lt(0xff, shr(r, x))))
      // forgefmt: disable-next-item
      result := gt(
        eq(mload(a), add(iszero(x), xor(31, shr(3, r)))),
        xor(shr(add(8, r), b), shr(add(8, r), mload(add(a, 0x20))))
      )
    }
  }

  /// @dev Packs a single string with its length into a single word.
  /// Returns `bytes32(0)` if the length is zero or greater than 31.
  function packOne(string memory a) internal pure returns (bytes32 result) {
    /// @solidity memory-safe-assembly
    assembly {
      // We don't need to zero right pad the string,
      // since this is our own custom non-standard packing scheme.
      result := mul(
        // Load the length and the bytes.
        mload(add(a, 0x1f)),
        // `length != 0 && length < 32`. Abuses underflow.
        // Assumes that the length is valid and within the block gas limit.
        lt(sub(mload(a), 1), 0x1f)
      )
    }
  }

  /// @dev Unpacks a string packed using {packOne}.
  /// Returns the empty string if `packed` is `bytes32(0)`.
  /// If `packed` is not an output of {packOne}, the output behavior is undefined.
  function unpackOne(bytes32 packed) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      // Grab the free memory pointer.
      result := mload(0x40)
      // Allocate 2 words (1 for the length, 1 for the bytes).
      mstore(0x40, add(result, 0x40))
      // Zeroize the length slot.
      mstore(result, 0)
      // Store the length and bytes.
      mstore(add(result, 0x1f), packed)
      // Right pad with zeroes.
      mstore(add(add(result, 0x20), mload(result)), 0)
    }
  }

  /// @dev Packs two strings with their lengths into a single word.
  /// Returns `bytes32(0)` if combined length is zero or greater than 30.
  function packTwo(string memory a, string memory b) internal pure returns (bytes32 result) {
    /// @solidity memory-safe-assembly
    assembly {
      let aLength := mload(a)
      // We don't need to zero right pad the strings,
      // since this is our own custom non-standard packing scheme.
      result := mul(
        // Load the length and the bytes of `a` and `b`.
        or(shl(shl(3, sub(0x1f, aLength)), mload(add(a, aLength))), mload(sub(add(b, 0x1e), aLength))),
        // `totalLength != 0 && totalLength < 31`. Abuses underflow.
        // Assumes that the lengths are valid and within the block gas limit.
        lt(sub(add(aLength, mload(b)), 1), 0x1e)
      )
    }
  }

  /// @dev Unpacks strings packed using {packTwo}.
  /// Returns the empty strings if `packed` is `bytes32(0)`.
  /// If `packed` is not an output of {packTwo}, the output behavior is undefined.
  function unpackTwo(bytes32 packed) internal pure returns (string memory resultA, string memory resultB) {
    /// @solidity memory-safe-assembly
    assembly {
      // Grab the free memory pointer.
      resultA := mload(0x40)
      resultB := add(resultA, 0x40)
      // Allocate 2 words for each string (1 for the length, 1 for the byte). Total 4 words.
      mstore(0x40, add(resultB, 0x40))
      // Zeroize the length slots.
      mstore(resultA, 0)
      mstore(resultB, 0)
      // Store the lengths and bytes.
      mstore(add(resultA, 0x1f), packed)
      mstore(add(resultB, 0x1f), mload(add(add(resultA, 0x20), mload(resultA))))
      // Right pad with zeroes.
      mstore(add(add(resultA, 0x20), mload(resultA)), 0)
      mstore(add(add(resultB, 0x20), mload(resultB)), 0)
    }
  }

  /// @dev Directly returns `a` without copying.
  function directReturn(string memory a) internal pure {
    assembly {
      // Assumes that the string does not start from the scratch space.
      let retStart := sub(a, 0x20)
      let retSize := add(mload(a), 0x40)
      // Right pad with zeroes. Just in case the string is produced
      // by a method that doesn't zero right pad.
      mstore(add(retStart, retSize), 0)
      // Store the return offset.
      mstore(retStart, 0x20)
      // End the transaction, returning the string.
      return(retStart, retSize)
    }
  }
}