// File: src/accounts/LlamaAccount.sol



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

import {Initializable} from "@openzeppelin/proxy/utils/Initializable.sol";
import {IERC20} from "@openzeppelin/token/ERC20/IERC20.sol";
import {SafeERC20} from "@openzeppelin/token/ERC20/utils/SafeERC20.sol";
import {IERC721} from "@openzeppelin/token/ERC721/IERC721.sol";
import {ERC721Holder} from "@openzeppelin/token/ERC721/utils/ERC721Holder.sol";
import {IERC1155} from "@openzeppelin/token/ERC1155/IERC1155.sol";
import {ERC1155Holder} from "@openzeppelin/token/ERC1155/utils/ERC1155Holder.sol";
import {Address} from "@openzeppelin/utils/Address.sol";

import {ILlamaAccount} from "src/interfaces/ILlamaAccount.sol";
import {LlamaUtils} from "src/lib/LlamaUtils.sol";
import {LlamaCore} from "src/LlamaCore.sol";

/// @title Llama Account
/// @author Llama (devsdosomething@llama.xyz)
/// @notice This contract can be used to hold assets for a Llama instance.
contract LlamaAccount is ILlamaAccount, ERC721Holder, ERC1155Holder, Initializable {
  using SafeERC20 for IERC20;
  using Address for address payable;

  // =========================
  // ======== Structs ========
  // =========================

  /// @dev Llama account initialization configuration.
  struct Config {
    string name; // Name of the Llama account.
  }

  /// @dev Data for sending native tokens to recipients.
  struct NativeTokenData {
    address payable recipient; // Recipient of the native tokens.
    uint256 amount; // Amount of native tokens to send.
  }

  /// @dev Data for sending ERC20 tokens to recipients.
  struct ERC20Data {
    IERC20 token; // The ERC20 token to transfer.
    address recipient; // The address to transfer the token to.
    uint256 amount; // The amount of tokens to transfer.
  }

  /// @dev Data for sending ERC721 tokens to recipients.
  struct ERC721Data {
    IERC721 token; // The ERC721 token to transfer.
    address recipient; // The address to transfer the token to.
    uint256 tokenId; // The tokenId of the token to transfer.
  }

  /// @dev Data for operator allowance for ERC721 transfers.
  struct ERC721OperatorData {
    IERC721 token; // The ERC721 token to transfer.
    address recipient; // The address to transfer the token to.
    bool approved; // Whether to approve or revoke allowance.
  }

  /// @dev Data for sending ERC1155 tokens to recipients.
  struct ERC1155Data {
    IERC1155 token; // The ERC1155 token to transfer.
    address recipient; // The address to transfer the token to.
    uint256 tokenId; // The tokenId of the token to transfer.
    uint256 amount; // The amount of tokens to transfer.
    bytes data; // The data to pass to the ERC1155 token.
  }

  /// @dev Data for batch sending ERC1155 tokens to recipients.
  struct ERC1155BatchData {
    IERC1155 token; // The ERC1155 token to transfer.
    address recipient; // The address to transfer the token to.
    uint256[] tokenIds; // The tokenId of the token to transfer.
    uint256[] amounts; // The amount of tokens to transfer.
    bytes data; // The data to pass to the ERC1155 token.
  }

  /// @dev Data for operator allowance for ERC1155 transfers.
  struct ERC1155OperatorData {
    IERC1155 token; // The ERC1155 token to transfer.
    address recipient; // The address to transfer the token to.
    bool approved; // Whether to approve or revoke allowance.
  }

  // ======================================
  // ======== Errors and Modifiers ========
  // ======================================

  /// @dev Only callable by a Llama instance's executor.
  error OnlyLlama();

  /// @dev Recipient cannot be the 0 address.
  error ZeroAddressNotAllowed();

  /// @dev External call failed.
  /// @param result Data returned by the called function.
  error FailedExecution(bytes result);

  /// @dev Slot 0 cannot be changed as a result of delegatecalls.
  error Slot0Changed();

  /// @dev Value cannot be sent with delegatecalls.
  error CannotDelegatecallWithValue();

  /// @dev Checks that the caller is the Llama executor and reverts if not.
  modifier onlyLlama() {
    if (msg.sender != llamaExecutor) revert OnlyLlama();
    _;
  }

  // ===================================
  // ======== Storage Variables ========
  // ===================================

  /// @notice The Llama instance's executor.
  /// @dev We intentionally put this before the `name` so it's packed with the `Initializable`
  /// storage variables, that way we can only check one slot before and after a delegatecall.
  address public llamaExecutor;

  /// @notice Name of the Llama account.
  string public name;

  // ======================================================
  // ======== Contract Creation and Initialization ========
  // ======================================================

  /// @dev This contract is deployed as a minimal proxy from the core's `_deployAccounts` function. The
  /// `_disableInitializers` locks the implementation (logic) contract, preventing any future initialization of it.
  constructor() {
    _disableInitializers();
  }

  /// @inheritdoc ILlamaAccount
  function initialize(bytes memory config) external initializer returns (bool) {
    llamaExecutor = address(LlamaCore(msg.sender).executor());
    Config memory accountConfig = abi.decode(config, (Config));
    name = accountConfig.name;

    return true;
  }

  // ===========================================
  // ======== External and Public Logic ========
  // ===========================================

  // -------- Native Token --------

  /// @notice Enables the Llama account to receive native tokens.
  receive() external payable {}

  /// @notice Transfer native tokens to a recipient.
  /// @param nativeTokenData The `amount` and `recipient` of the native token transfer.
  function transferNativeToken(NativeTokenData calldata nativeTokenData) public onlyLlama {
    if (nativeTokenData.recipient == address(0)) revert ZeroAddressNotAllowed();
    nativeTokenData.recipient.sendValue(nativeTokenData.amount);
  }

  /// @notice Batch transfer native tokens to a recipient.
  /// @param nativeTokenData The `amounts` and `recipients` for the native token transfers.
  function batchTransferNativeToken(NativeTokenData[] calldata nativeTokenData) external onlyLlama {
    uint256 length = nativeTokenData.length;
    for (uint256 i = 0; i < length; i = LlamaUtils.uncheckedIncrement(i)) {
      transferNativeToken(nativeTokenData[i]);
    }
  }

  // -------- ERC20 Token --------

  /// @notice Transfer ERC20 tokens to a recipient.
  /// @param erc20Data The `token`, `recipient`, and `amount` for the ERC20 transfer.
  function transferERC20(ERC20Data calldata erc20Data) public onlyLlama {
    if (erc20Data.recipient == address(0)) revert ZeroAddressNotAllowed();
    erc20Data.token.safeTransfer(erc20Data.recipient, erc20Data.amount);
  }

  /// @notice Batch transfer ERC20 tokens to recipients.
  /// @param erc20Data The `token`, `recipient`, and `amount` for the ERC20 transfers.
  function batchTransferERC20(ERC20Data[] calldata erc20Data) external onlyLlama {
    uint256 length = erc20Data.length;
    for (uint256 i = 0; i < length; i = LlamaUtils.uncheckedIncrement(i)) {
      transferERC20(erc20Data[i]);
    }
  }

  /// @notice Approve an ERC20 allowance for a recipient.
  /// @param erc20Data The `token`, `recipient`, and `amount` for the ERC20 approval.
  function approveERC20(ERC20Data calldata erc20Data) public onlyLlama {
    erc20Data.token.safeApprove(erc20Data.recipient, erc20Data.amount);
  }

  /// @notice Batch approve ERC20 allowances for recipients.
  /// @param erc20Data The `token`, `recipient`, and `amount` for the ERC20 approvals.
  function batchApproveERC20(ERC20Data[] calldata erc20Data) external onlyLlama {
    uint256 length = erc20Data.length;
    for (uint256 i = 0; i < length; i = LlamaUtils.uncheckedIncrement(i)) {
      approveERC20(erc20Data[i]);
    }
  }

  // -------- ERC721 Token --------

  /// @notice Transfer an ERC721 token to a recipient.
  /// @param erc721Data The `token`, `recipient`, and `tokenId` of the ERC721 transfer.
  function transferERC721(ERC721Data calldata erc721Data) public onlyLlama {
    if (erc721Data.recipient == address(0)) revert ZeroAddressNotAllowed();
    erc721Data.token.transferFrom(address(this), erc721Data.recipient, erc721Data.tokenId);
  }

  /// @notice Batch transfer ERC721 tokens to recipients.
  /// @param erc721Data The `token`, `recipient`, and `tokenId` of the ERC721 transfers.
  function batchTransferERC721(ERC721Data[] calldata erc721Data) external onlyLlama {
    uint256 length = erc721Data.length;
    for (uint256 i = 0; i < length; i = LlamaUtils.uncheckedIncrement(i)) {
      transferERC721(erc721Data[i]);
    }
  }

  /// @notice Approve a recipient to transfer an ERC721.
  /// @param erc721Data The `token`, `recipient`, and `tokenId` of the ERC721 approval.
  function approveERC721(ERC721Data calldata erc721Data) public onlyLlama {
    erc721Data.token.approve(erc721Data.recipient, erc721Data.tokenId);
  }

  /// @notice Batch approve recipients to transfer ERC721s.
  /// @param erc721Data The `token`, `recipient`, and `tokenId` for the ERC721 approvals.
  function batchApproveERC721(ERC721Data[] calldata erc721Data) external onlyLlama {
    uint256 length = erc721Data.length;
    for (uint256 i = 0; i < length; i = LlamaUtils.uncheckedIncrement(i)) {
      approveERC721(erc721Data[i]);
    }
  }

  /// @notice Approve an operator for ERC721 transfers.
  /// @param erc721OperatorData The `token`, `recipient`, and `approved` boolean for the ERC721 operator approval.
  function approveOperatorERC721(ERC721OperatorData calldata erc721OperatorData) public onlyLlama {
    erc721OperatorData.token.setApprovalForAll(erc721OperatorData.recipient, erc721OperatorData.approved);
  }

  /// @notice Batch approve operators for ERC721 transfers.
  /// @param erc721OperatorData The `token`, `recipient`, and `approved` booleans for the ERC721 operator approvals.
  function batchApproveOperatorERC721(ERC721OperatorData[] calldata erc721OperatorData) external onlyLlama {
    uint256 length = erc721OperatorData.length;
    for (uint256 i = 0; i < length; i = LlamaUtils.uncheckedIncrement(i)) {
      approveOperatorERC721(erc721OperatorData[i]);
    }
  }

  // -------- ERC1155 Token --------

  /// @notice Transfer ERC1155 tokens to a recipient.
  /// @param erc1155Data The data of the ERC1155 transfer.
  function transferERC1155(ERC1155Data calldata erc1155Data) external onlyLlama {
    if (erc1155Data.recipient == address(0)) revert ZeroAddressNotAllowed();
    erc1155Data.token.safeTransferFrom(
      address(this), erc1155Data.recipient, erc1155Data.tokenId, erc1155Data.amount, erc1155Data.data
    );
  }

  /// @notice Batch transfer ERC1155 tokens of a single ERC1155 collection to recipients.
  /// @param erc1155BatchData The data of the ERC1155 batch transfer.
  function batchTransferSingleERC1155(ERC1155BatchData calldata erc1155BatchData) public onlyLlama {
    if (erc1155BatchData.recipient == address(0)) revert ZeroAddressNotAllowed();
    erc1155BatchData.token.safeBatchTransferFrom(
      address(this),
      erc1155BatchData.recipient,
      erc1155BatchData.tokenIds,
      erc1155BatchData.amounts,
      erc1155BatchData.data
    );
  }

  /// @notice Batch transfer ERC1155 tokens of multiple ERC1155 collections to recipients.
  /// @param erc1155BatchData The data of the ERC1155 batch transfers.
  function batchTransferMultipleERC1155(ERC1155BatchData[] calldata erc1155BatchData) external onlyLlama {
    uint256 length = erc1155BatchData.length;
    for (uint256 i = 0; i < length; i = LlamaUtils.uncheckedIncrement(i)) {
      batchTransferSingleERC1155(erc1155BatchData[i]);
    }
  }

  /// @notice Grant an ERC1155 operator allowance to recipients.
  /// @param erc1155OperatorData The data of the ERC1155 operator allowance.
  function approveOperatorERC1155(ERC1155OperatorData calldata erc1155OperatorData) public onlyLlama {
    erc1155OperatorData.token.setApprovalForAll(erc1155OperatorData.recipient, erc1155OperatorData.approved);
  }

  /// @notice Batch approve ERC1155 operator allowances to recipients.
  /// @param erc1155OperatorData The data of the ERC1155 operator allowances.
  function batchApproveOperatorERC1155(ERC1155OperatorData[] calldata erc1155OperatorData) external onlyLlama {
    uint256 length = erc1155OperatorData.length;
    for (uint256 i = 0; i < length; i = LlamaUtils.uncheckedIncrement(i)) {
      approveOperatorERC1155(erc1155OperatorData[i]);
    }
  }

  // -------- Generic Execution --------

  /// @notice Execute arbitrary calls from the Llama Account.
  /// @dev Be careful and intentional while assigning permissions to a policyholder that can create an action to call
  /// this function, especially while using the delegatecall functionality as it can lead to arbitrary code execution in
  /// the context of this Llama account.
  /// @param target The address of the contract to call.
  /// @param withDelegatecall Whether to use delegatecall or call.
  /// @param value The amount of ETH to send with the call, taken from the Llama Account.
  /// @param callData The calldata to pass to the contract.
  /// @return The result of the call.
  function execute(address target, bool withDelegatecall, uint256 value, bytes calldata callData)
    external
    onlyLlama
    returns (bytes memory)
  {
    bool success;
    bytes memory result;

    if (withDelegatecall) {
      if (value > 0) revert CannotDelegatecallWithValue();

      // Whenever we're executing arbitrary code in the context of this account, we want to ensure
      // that none of the storage in this contract changes, as this could let someone who sneaks in
      // a malicious (or buggy) target to take ownership of this contract. Slot 0 contains all
      // relevant storage variables for security, so we check the value before and after execution
      // to make sure it's unchanged. The contract name starts in slot 1, but it's not as important
      // if that's changed (and it can be changed back), so to save gas we don't check the name.
      // The storage layout of this contract is below:
      //
      // | Variable Name | Type    | Slot | Offset | Bytes |
      // |---------------|---------|------|--------|-------|
      // | _initialized  | uint8   | 0    | 0      | 1     |
      // | _initializing | bool    | 0    | 1      | 1     |
      // | llamaExecutor | address | 0    | 2      | 20    |
      // | name          | string  | 1    | 0      | 32    |

      bytes32 originalStorage = _readSlot0();
      (success, result) = target.delegatecall(callData);
      if (originalStorage != _readSlot0()) revert Slot0Changed();
    } else {
      (success, result) = target.call{value: value}(callData);
    }

    if (!success) revert FailedExecution(result);
    return result;
  }

  // ================================
  // ======== Internal Logic ========
  // ================================

  /// @dev Reads slot 0 from storage, used to check that storage hasn't changed after delegatecall.
  function _readSlot0() internal view returns (bytes32 slot0) {
    assembly {
      slot0 := sload(0)
    }
  }
}

// File: lib/openzeppelin-contracts/contracts/proxy/utils/Initializable.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.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]
 * ```
 * 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 Internal function that returns the initialized version. Returns `_initialized`
     */
    function _getInitializedVersion() internal view returns (uint8) {
        return _initialized;
    }

    /**
     * @dev Internal function that returns the initialized version. Returns `_initializing`
     */
    function _isInitializing() internal view returns (bool) {
        return _initializing;
    }
}

// File: lib/openzeppelin-contracts/contracts/token/ERC20/IERC20.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.6.0) (token/ERC20/IERC20.sol)

pragma solidity ^0.8.0;

/**
 * @dev Interface of the ERC20 standard as defined in the EIP.
 */
interface IERC20 {
    /**
     * @dev Emitted when `value` tokens are moved from one account (`from`) to
     * another (`to`).
     *
     * Note that `value` may be zero.
     */
    event Transfer(address indexed from, address indexed to, uint256 value);

    /**
     * @dev Emitted when the allowance of a `spender` for an `owner` is set by
     * a call to {approve}. `value` is the new allowance.
     */
    event Approval(address indexed owner, address indexed spender, uint256 value);

    /**
     * @dev Returns the amount of tokens in existence.
     */
    function totalSupply() external view returns (uint256);

    /**
     * @dev Returns the amount of tokens owned by `account`.
     */
    function balanceOf(address account) external view returns (uint256);

    /**
     * @dev Moves `amount` tokens from the caller's account to `to`.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transfer(address to, uint256 amount) external returns (bool);

    /**
     * @dev Returns the remaining number of tokens that `spender` will be
     * allowed to spend on behalf of `owner` through {transferFrom}. This is
     * zero by default.
     *
     * This value changes when {approve} or {transferFrom} are called.
     */
    function allowance(address owner, address spender) external view returns (uint256);

    /**
     * @dev Sets `amount` as the allowance of `spender` over the caller's tokens.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * IMPORTANT: Beware that changing an allowance with this method brings the risk
     * that someone may use both the old and the new allowance by unfortunate
     * transaction ordering. One possible solution to mitigate this race
     * condition is to first reduce the spender's allowance to 0 and set the
     * desired value afterwards:
     * https://github.com/ethereum/EIPs/issues/20#issuecomment-263524729
     *
     * Emits an {Approval} event.
     */
    function approve(address spender, uint256 amount) external returns (bool);

    /**
     * @dev Moves `amount` tokens from `from` to `to` using the
     * allowance mechanism. `amount` is then deducted from the caller's
     * allowance.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(
        address from,
        address to,
        uint256 amount
    ) external returns (bool);
}

// File: lib/openzeppelin-contracts/contracts/token/ERC20/utils/SafeERC20.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (token/ERC20/utils/SafeERC20.sol)

pragma solidity ^0.8.0;

import "../IERC20.sol";
import "../extensions/draft-IERC20Permit.sol";
import "../../../utils/Address.sol";

/**
 * @title SafeERC20
 * @dev Wrappers around ERC20 operations that throw on failure (when the token
 * contract returns false). Tokens that return no value (and instead revert or
 * throw on failure) are also supported, non-reverting calls are assumed to be
 * successful.
 * To use this library you can add a `using SafeERC20 for IERC20;` statement to your contract,
 * which allows you to call the safe operations as `token.safeTransfer(...)`, etc.
 */
library SafeERC20 {
    using Address for address;

    function safeTransfer(
        IERC20 token,
        address to,
        uint256 value
    ) internal {
        _callOptionalReturn(token, abi.encodeWithSelector(token.transfer.selector, to, value));
    }

    function safeTransferFrom(
        IERC20 token,
        address from,
        address to,
        uint256 value
    ) internal {
        _callOptionalReturn(token, abi.encodeWithSelector(token.transferFrom.selector, from, to, value));
    }

    /**
     * @dev Deprecated. This function has issues similar to the ones found in
     * {IERC20-approve}, and its usage is discouraged.
     *
     * Whenever possible, use {safeIncreaseAllowance} and
     * {safeDecreaseAllowance} instead.
     */
    function safeApprove(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        // safeApprove should only be called when setting an initial allowance,
        // or when resetting it to zero. To increase and decrease it, use
        // 'safeIncreaseAllowance' and 'safeDecreaseAllowance'
        require(
            (value == 0) || (token.allowance(address(this), spender) == 0),
            "SafeERC20: approve from non-zero to non-zero allowance"
        );
        _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, value));
    }

    function safeIncreaseAllowance(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        uint256 newAllowance = token.allowance(address(this), spender) + value;
        _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, newAllowance));
    }

    function safeDecreaseAllowance(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        unchecked {
            uint256 oldAllowance = token.allowance(address(this), spender);
            require(oldAllowance >= value, "SafeERC20: decreased allowance below zero");
            uint256 newAllowance = oldAllowance - value;
            _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, newAllowance));
        }
    }

    function safePermit(
        IERC20Permit token,
        address owner,
        address spender,
        uint256 value,
        uint256 deadline,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) internal {
        uint256 nonceBefore = token.nonces(owner);
        token.permit(owner, spender, value, deadline, v, r, s);
        uint256 nonceAfter = token.nonces(owner);
        require(nonceAfter == nonceBefore + 1, "SafeERC20: permit did not succeed");
    }

    /**
     * @dev Imitates a Solidity high-level call (i.e. a regular function call to a contract), relaxing the requirement
     * on the return value: the return value is optional (but if data is returned, it must not be false).
     * @param token The token targeted by the call.
     * @param data The call data (encoded using abi.encode or one of its variants).
     */
    function _callOptionalReturn(IERC20 token, bytes memory data) private {
        // We need to perform a low level call here, to bypass Solidity's return data size checking mechanism, since
        // we're implementing it ourselves. We use {Address-functionCall} to perform this call, which verifies that
        // the target address contains contract code and also asserts for success in the low-level call.

        bytes memory returndata = address(token).functionCall(data, "SafeERC20: low-level call failed");
        if (returndata.length > 0) {
            // Return data is optional
            require(abi.decode(returndata, (bool)), "SafeERC20: ERC20 operation did not succeed");
        }
    }
}

// File: lib/openzeppelin-contracts/contracts/token/ERC721/IERC721.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (token/ERC721/IERC721.sol)

pragma solidity ^0.8.0;

import "../../utils/introspection/IERC165.sol";

/**
 * @dev Required interface of an ERC721 compliant contract.
 */
interface IERC721 is IERC165 {
    /**
     * @dev Emitted when `tokenId` token is transferred from `from` to `to`.
     */
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables `approved` to manage the `tokenId` token.
     */
    event Approval(address indexed owner, address indexed approved, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables or disables (`approved`) `operator` to manage all of its assets.
     */
    event ApprovalForAll(address indexed owner, address indexed operator, bool approved);

    /**
     * @dev Returns the number of tokens in ``owner``'s account.
     */
    function balanceOf(address owner) external view returns (uint256 balance);

    /**
     * @dev Returns the owner of the `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function ownerOf(uint256 tokenId) external view returns (address owner);

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token by either {approve} or {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes calldata data
    ) external;

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`, checking first that contract recipients
     * are aware of the ERC721 protocol to prevent tokens from being forever locked.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must have been allowed to move this token by either {approve} or {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external;

    /**
     * @dev Transfers `tokenId` token from `from` to `to`.
     *
     * WARNING: Note that the caller is responsible to confirm that the recipient is capable of receiving ERC721
     * or else they may be permanently lost. Usage of {safeTransferFrom} prevents loss, though the caller must
     * understand this adds an external call which potentially creates a reentrancy vulnerability.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token by either {approve} or {setApprovalForAll}.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external;

    /**
     * @dev Gives permission to `to` to transfer `tokenId` token to another account.
     * The approval is cleared when the token is transferred.
     *
     * Only a single account can be approved at a time, so approving the zero address clears previous approvals.
     *
     * Requirements:
     *
     * - The caller must own the token or be an approved operator.
     * - `tokenId` must exist.
     *
     * Emits an {Approval} event.
     */
    function approve(address to, uint256 tokenId) external;

    /**
     * @dev Approve or remove `operator` as an operator for the caller.
     * Operators can call {transferFrom} or {safeTransferFrom} for any token owned by the caller.
     *
     * Requirements:
     *
     * - The `operator` cannot be the caller.
     *
     * Emits an {ApprovalForAll} event.
     */
    function setApprovalForAll(address operator, bool _approved) external;

    /**
     * @dev Returns the account approved for `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function getApproved(uint256 tokenId) external view returns (address operator);

    /**
     * @dev Returns if the `operator` is allowed to manage all of the assets of `owner`.
     *
     * See {setApprovalForAll}
     */
    function isApprovedForAll(address owner, address operator) external view returns (bool);
}

// File: lib/openzeppelin-contracts/contracts/token/ERC721/utils/ERC721Holder.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (token/ERC721/utils/ERC721Holder.sol)

pragma solidity ^0.8.0;

import "../IERC721Receiver.sol";

/**
 * @dev Implementation of the {IERC721Receiver} interface.
 *
 * Accepts all token transfers.
 * Make sure the contract is able to use its token with {IERC721-safeTransferFrom}, {IERC721-approve} or {IERC721-setApprovalForAll}.
 */
contract ERC721Holder is IERC721Receiver {
    /**
     * @dev See {IERC721Receiver-onERC721Received}.
     *
     * Always returns `IERC721Receiver.onERC721Received.selector`.
     */
    function onERC721Received(
        address,
        address,
        uint256,
        bytes memory
    ) public virtual override returns (bytes4) {
        return this.onERC721Received.selector;
    }
}

// File: lib/openzeppelin-contracts/contracts/token/ERC1155/IERC1155.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (token/ERC1155/IERC1155.sol)

pragma solidity ^0.8.0;

import "../../utils/introspection/IERC165.sol";

/**
 * @dev Required interface of an ERC1155 compliant contract, as defined in the
 * https://eips.ethereum.org/EIPS/eip-1155[EIP].
 *
 * _Available since v3.1._
 */
interface IERC1155 is IERC165 {
    /**
     * @dev Emitted when `value` tokens of token type `id` are transferred from `from` to `to` by `operator`.
     */
    event TransferSingle(address indexed operator, address indexed from, address indexed to, uint256 id, uint256 value);

    /**
     * @dev Equivalent to multiple {TransferSingle} events, where `operator`, `from` and `to` are the same for all
     * transfers.
     */
    event TransferBatch(
        address indexed operator,
        address indexed from,
        address indexed to,
        uint256[] ids,
        uint256[] values
    );

    /**
     * @dev Emitted when `account` grants or revokes permission to `operator` to transfer their tokens, according to
     * `approved`.
     */
    event ApprovalForAll(address indexed account, address indexed operator, bool approved);

    /**
     * @dev Emitted when the URI for token type `id` changes to `value`, if it is a non-programmatic URI.
     *
     * If an {URI} event was emitted for `id`, the standard
     * https://eips.ethereum.org/EIPS/eip-1155#metadata-extensions[guarantees] that `value` will equal the value
     * returned by {IERC1155MetadataURI-uri}.
     */
    event URI(string value, uint256 indexed id);

    /**
     * @dev Returns the amount of tokens of token type `id` owned by `account`.
     *
     * Requirements:
     *
     * - `account` cannot be the zero address.
     */
    function balanceOf(address account, uint256 id) external view returns (uint256);

    /**
     * @dev xref:ROOT:erc1155.adoc#batch-operations[Batched] version of {balanceOf}.
     *
     * Requirements:
     *
     * - `accounts` and `ids` must have the same length.
     */
    function balanceOfBatch(address[] calldata accounts, uint256[] calldata ids)
        external
        view
        returns (uint256[] memory);

    /**
     * @dev Grants or revokes permission to `operator` to transfer the caller's tokens, according to `approved`,
     *
     * Emits an {ApprovalForAll} event.
     *
     * Requirements:
     *
     * - `operator` cannot be the caller.
     */
    function setApprovalForAll(address operator, bool approved) external;

    /**
     * @dev Returns true if `operator` is approved to transfer ``account``'s tokens.
     *
     * See {setApprovalForAll}.
     */
    function isApprovedForAll(address account, address operator) external view returns (bool);

    /**
     * @dev Transfers `amount` tokens of token type `id` from `from` to `to`.
     *
     * Emits a {TransferSingle} event.
     *
     * Requirements:
     *
     * - `to` cannot be the zero address.
     * - If the caller is not `from`, it must have been approved to spend ``from``'s tokens via {setApprovalForAll}.
     * - `from` must have a balance of tokens of type `id` of at least `amount`.
     * - If `to` refers to a smart contract, it must implement {IERC1155Receiver-onERC1155Received} and return the
     * acceptance magic value.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 id,
        uint256 amount,
        bytes calldata data
    ) external;

    /**
     * @dev xref:ROOT:erc1155.adoc#batch-operations[Batched] version of {safeTransferFrom}.
     *
     * Emits a {TransferBatch} event.
     *
     * Requirements:
     *
     * - `ids` and `amounts` must have the same length.
     * - If `to` refers to a smart contract, it must implement {IERC1155Receiver-onERC1155BatchReceived} and return the
     * acceptance magic value.
     */
    function safeBatchTransferFrom(
        address from,
        address to,
        uint256[] calldata ids,
        uint256[] calldata amounts,
        bytes calldata data
    ) external;
}

// File: lib/openzeppelin-contracts/contracts/token/ERC1155/utils/ERC1155Holder.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.5.0) (token/ERC1155/utils/ERC1155Holder.sol)

pragma solidity ^0.8.0;

import "./ERC1155Receiver.sol";

/**
 * Simple implementation of `ERC1155Receiver` that will allow a contract to hold ERC1155 tokens.
 *
 * IMPORTANT: When inheriting this contract, you must include a way to use the received tokens, otherwise they will be
 * stuck.
 *
 * @dev _Available since v3.1._
 */
contract ERC1155Holder is ERC1155Receiver {
    function onERC1155Received(
        address,
        address,
        uint256,
        uint256,
        bytes memory
    ) public virtual override returns (bytes4) {
        return this.onERC1155Received.selector;
    }

    function onERC1155BatchReceived(
        address,
        address,
        uint256[] memory,
        uint256[] memory,
        bytes memory
    ) public virtual override returns (bytes4) {
        return this.onERC1155BatchReceived.selector;
    }
}

// File: lib/openzeppelin-contracts/contracts/utils/Address.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.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
     * ====
     *
     * [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://diligence.consensys.net/posts/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.5.11/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);
        }
    }
}

// File: src/interfaces/ILlamaAccount.sol



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

/// @title Llama Account Logic Interface
/// @author Llama (devsdosomething@llama.xyz)
/// @notice This is the interface for Llama accounts which can be used to hold assets for a Llama instance.
interface ILlamaAccount {
  // -------- For Inspection --------

  /// @notice Returns the address of the Llama instance's executor.
  function llamaExecutor() external view returns (address);

  // -------- At Account Creation --------

  /// @notice Initializes a new clone of the account.
  /// @dev This function is called by the `_deployAccounts` function in the `LlamaCore` contract. The `initializer`
  /// modifier ensures that this function can be invoked at most once.
  /// @param config The account configuration, encoded as bytes to support differing constructor arguments in
  /// different account logic contracts.
  /// @return This return statement must be hardcoded to `true` to ensure that initializing an EOA
  /// (like the zero address) will revert.
  function initialize(bytes memory config) external returns (bool);
}

// File: src/lib/LlamaUtils.sol



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

import {PermissionData} from "src/lib/Structs.sol";

/// @dev Shared helper methods for Llama's contracts.
library LlamaUtils {
  /// @dev Thrown when a value cannot be safely casted to a smaller type.
  error UnsafeCast(uint256 n);

  /// @dev Reverts if `n` does not fit in a `uint64`.
  function toUint64(uint256 n) internal pure returns (uint64) {
    if (n > type(uint64).max) revert UnsafeCast(n);
    return uint64(n);
  }

  /// @dev Reverts if `n` does not fit in a `uint96`.
  function toUint96(uint256 n) internal pure returns (uint96) {
    if (n > type(uint96).max) revert UnsafeCast(n);
    return uint96(n);
  }

  /// @dev Increments a `uint256` without checking for overflow.
  function uncheckedIncrement(uint256 i) internal pure returns (uint256) {
    unchecked {
      return i + 1;
    }
  }

  /// @dev Hashes a permission to return the corresponding permission ID.
  function computePermissionId(PermissionData memory permission) internal pure returns (bytes32) {
    return keccak256(abi.encode(permission));
  }
}

// File: src/LlamaCore.sol



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

import {Clones} from "@openzeppelin/proxy/Clones.sol";
import {Initializable} from "@openzeppelin/proxy/utils/Initializable.sol";

import {ILlamaAccount} from "src/interfaces/ILlamaAccount.sol";
import {ILlamaActionGuard} from "src/interfaces/ILlamaActionGuard.sol";
import {ILlamaPolicyMetadata} from "src/interfaces/ILlamaPolicyMetadata.sol";
import {ILlamaStrategy} from "src/interfaces/ILlamaStrategy.sol";
import {ActionState} from "src/lib/Enums.sol";
import {LlamaUtils} from "src/lib/LlamaUtils.sol";
import {
  Action,
  ActionInfo,
  LlamaInstanceConfig,
  LlamaPolicyConfig,
  PermissionData,
  RoleHolderData,
  RolePermissionData
} from "src/lib/Structs.sol";
import {LlamaExecutor} from "src/LlamaExecutor.sol";
import {LlamaPolicy} from "src/LlamaPolicy.sol";

/// @title Llama Core
/// @author Llama (devsdosomething@llama.xyz)
/// @notice Manages the action process from creation to execution.
contract LlamaCore is Initializable {
  // =========================
  // ======== Structs ========
  // =========================

  /// @dev Stores the two different status values for a strategy.
  struct StrategyStatus {
    bool deployed; // Whether or not the strategy has been deployed from this `LlamaCore`.
    bool authorized; // Whether or not the strategy has been authorized for action creations in this `LlamaCore`.
  }

  // ======================================
  // ======== Errors and Modifiers ========
  // ======================================

  /// @dev Bootstrap strategy must be deployed and authorized during initialization.
  /// @dev This should never be thrown in production.
  error BootstrapStrategyNotAuthorized();

  /// @dev Policyholder cannot cast if it has 0 quantity of role.
  /// @param policyholder Address of policyholder.
  /// @param role The role being used in the cast.
  error CannotCastWithZeroQuantity(address policyholder, uint8 role);

  /// @dev Policyholder cannot cast after the minimum execution time.
  error CannotDisapproveAfterMinExecutionTime();

  /// @dev An action's target contract cannot be the executor.
  error CannotSetExecutorAsTarget();

  /// @dev Address cannot be used.
  error RestrictedAddress();

  /// @dev Policyholders can only cast once.
  error DuplicateCast();

  /// @dev Action execution failed.
  /// @param reason Data returned by the function called by the action.
  error FailedActionExecution(bytes reason);

  /// @dev `ActionInfo` does not hash to the correct value.
  error InfoHashMismatch();

  /// @dev `msg.value` does not equal the action's value.
  error IncorrectMsgValue();

  /// @dev The action is not in the expected state.
  /// @param current The current state of the action.
  error InvalidActionState(ActionState current);

  /// @dev The policyholder does not have the role at action creation time.
  error InvalidPolicyholder();

  /// @dev The recovered signer does not match the expected policyholder.
  error InvalidSignature();

  /// @dev An action cannot queue successfully if it's `minExecutionTime` is less than `block.timestamp`.
  error MinExecutionTimeCannotBeInThePast();

  /// @dev The provided strategy address does not map to a deployed strategy.
  error NonExistentStrategy();

  /// @dev Only callable by a Llama instance's executor.
  error OnlyLlama();

  /// @dev Policyholder does not have the permission ID to create the action.
  error PolicyholderDoesNotHavePermission();

  /// @dev If `block.timestamp` is less than `minExecutionTime`, the action cannot be executed.
  error MinExecutionTimeNotReached();

  /// @dev Actions can only be created with authorized strategies.
  error UnauthorizedStrategy();

  /// @dev Strategies can only be created with valid logic contracts.
  error UnauthorizedStrategyLogic();

  /// @dev Accounts can only be created with valid logic contracts.
  error UnauthorizedAccountLogic();

  /// @dev Checks that the caller is the Llama Executor and reverts if not.
  modifier onlyLlama() {
    if (msg.sender != address(executor)) revert OnlyLlama();
    _;
  }

  // ========================
  // ======== Events ========
  // ========================

  /// @dev Emitted when an account is created.
  event AccountCreated(ILlamaAccount account, ILlamaAccount indexed accountLogic, bytes initializationData);

  /// @dev Emitted when a new account implementation (logic) contract is authorized or unauthorized.
  event AccountLogicAuthorizationSet(ILlamaAccount indexed accountLogic, bool authorized);

  /// @dev Emitted when an action is created.
  event ActionCreated(
    uint256 id,
    address indexed creator,
    uint8 role,
    ILlamaStrategy indexed strategy,
    address indexed target,
    uint256 value,
    bytes data,
    string description
  );

  /// @dev Emitted when an action is canceled.
  event ActionCanceled(uint256 id, address indexed caller);

  /// @dev Emitted when an action guard is set.
  event ActionGuardSet(address indexed target, bytes4 indexed selector, ILlamaActionGuard actionGuard);

  /// @dev Emitted when an action is queued.
  event ActionQueued(
    uint256 id,
    address indexed caller,
    ILlamaStrategy indexed strategy,
    address indexed creator,
    uint256 minExecutionTime
  );

  /// @dev Emitted when an action is executed.
  event ActionExecuted(
    uint256 id, address indexed caller, ILlamaStrategy indexed strategy, address indexed creator, bytes result
  );

  /// @dev Emitted when an approval is cast.
  event ApprovalCast(uint256 id, address indexed policyholder, uint8 indexed role, uint256 quantity, string reason);

  /// @dev Emitted when a disapproval is cast.
  event DisapprovalCast(uint256 id, address indexed policyholder, uint8 indexed role, uint256 quantity, string reason);

  /// @dev Emitted when a deployed strategy is authorized or unauthorized.
  event StrategyAuthorizationSet(ILlamaStrategy indexed strategy, bool authorized);

  /// @dev Emitted when a strategy is created.
  event StrategyCreated(ILlamaStrategy strategy, ILlamaStrategy indexed strategyLogic, bytes initializationData);

  /// @dev Emitted when a new strategy implementation (logic) contract is authorized or unauthorized.
  event StrategyLogicAuthorizationSet(ILlamaStrategy indexed strategyLogic, bool authorized);

  /// @dev Emitted when a script is authorized or unauthorized.
  event ScriptAuthorizationSet(address indexed script, bool authorized);

  // =================================================
  // ======== Constants and Storage Variables ========
  // =================================================

  /// @dev EIP-712 base typehash.
  bytes32 internal constant EIP712_DOMAIN_TYPEHASH =
    keccak256("EIP712Domain(string name,string version,uint256 chainId,address verifyingContract)");

  /// @dev EIP-712 createAction typehash.
  bytes32 internal constant CREATE_ACTION_TYPEHASH = keccak256(
    "CreateAction(address policyholder,uint8 role,address strategy,address target,uint256 value,bytes data,string description,uint256 nonce)"
  );

  /// @dev EIP-712 cancelAction typehash.
  bytes32 internal constant CANCEL_ACTION_TYPEHASH = keccak256(
    "CancelAction(address policyholder,ActionInfo actionInfo,uint256 nonce)ActionInfo(uint256 id,address creator,uint8 creatorRole,address strategy,address target,uint256 value,bytes data)"
  );

  /// @dev EIP-712 castApproval typehash.
  bytes32 internal constant CAST_APPROVAL_TYPEHASH = keccak256(
    "CastApproval(address policyholder,uint8 role,ActionInfo actionInfo,string reason,uint256 nonce)ActionInfo(uint256 id,address creator,uint8 creatorRole,address strategy,address target,uint256 value,bytes data)"
  );

  /// @dev EIP-712 castDisapproval typehash.
  bytes32 internal constant CAST_DISAPPROVAL_TYPEHASH = keccak256(
    "CastDisapproval(address policyholder,uint8 role,ActionInfo actionInfo,string reason,uint256 nonce)ActionInfo(uint256 id,address creator,uint8 creatorRole,address strategy,address target,uint256 value,bytes data)"
  );

  /// @dev EIP-712 actionInfo typehash.
  bytes32 internal constant ACTION_INFO_TYPEHASH = keccak256(
    "ActionInfo(uint256 id,address creator,uint8 creatorRole,address strategy,address target,uint256 value,bytes data)"
  );

  /// @dev Mapping of actionIds to Actions. This data can be accessed through the `getAction` function.
  mapping(uint256 actionId => Action) internal actions;

  /// @notice The contract that executes actions for this Llama instance.
  LlamaExecutor public executor;

  /// @notice The ERC721 contract that defines the policies for this Llama instance.
  LlamaPolicy public policy;

  /// @notice Name of this Llama instance.
  string public name;

  /// @notice The current number of actions created.
  uint256 public actionsCount;

  /// @notice Mapping of actionIds to policyholders to approvals.
  mapping(uint256 actionId => mapping(address policyholder => bool hasApproved)) public approvals;

  /// @notice Mapping of actionIds to policyholders to disapprovals.
  mapping(uint256 actionId => mapping(address policyholder => bool hasDisapproved)) public disapprovals;

  /// @notice Mapping of all deployed strategies and their current authorization status.
  mapping(ILlamaStrategy strategy => StrategyStatus authorizationStatus) public strategies;

  /// @notice Mapping of all authorized scripts.
  mapping(address script => bool isAuthorized) public authorizedScripts;

  /// @notice Mapping of policyholders to function selectors to current nonces for EIP-712 signatures.
  /// @dev This is used to prevent replay attacks by incrementing the nonce for each operation (`createAction`,
  /// `cancelAction`, `castApproval` and `castDisapproval`) signed by the policyholder.
  mapping(address policyholder => mapping(bytes4 selector => uint256 currentNonce)) public nonces;

  /// @notice Mapping of target to selector to actionGuard address.
  mapping(address target => mapping(bytes4 selector => ILlamaActionGuard guard)) public actionGuard;

  /// @notice Mapping of all authorized Llama account implementation (logic) contracts.
  mapping(ILlamaAccount accountLogic => bool isAuthorized) public authorizedAccountLogics;

  /// @notice Mapping of all authorized Llama strategy implementation (logic) contracts.
  mapping(ILlamaStrategy strategyLogic => bool isAuthorized) public authorizedStrategyLogics;

  // ======================================================
  // ======== Contract Creation and Initialization ========
  // ======================================================

  /// @dev This contract is deployed as a minimal proxy from the factory's `deploy` function. The `_disableInitializers`
  /// locks the implementation (logic) contract, preventing any future initialization of it.
  constructor() {
    _disableInitializers();
  }

  /// @notice Initializes a new `LlamaCore` clone.
  /// @dev This function is called by the `deploy` function in the `LlamaFactory` contract. The `initializer` modifier
  /// ensures that this function can be invoked at most once.
  /// @param config The struct that contains the configuration for this Llama instance. See `Structs.sol` for details on
  /// the parameters
  /// @param policyLogic The `LlamaPolicy` implementation (logic) contract
  /// @param policyMetadataLogic The `LlamaPolicyMetadata` implementation (logic) contract
  function initialize(
    LlamaInstanceConfig calldata config,
    LlamaPolicy policyLogic,
    ILlamaPolicyMetadata policyMetadataLogic
  ) external initializer {
    name = config.name;
    // Deploy the executor.
    executor = new LlamaExecutor();

    // Since the `LlamaCore` salt is dependent on the name and deployer, we can use a constant salt of 0 here.
    // The policy address will still be deterministic and dependent on the name and deployer because with CREATE2
    // the resulting address is a function of the deployer address (the core address).
    policy = LlamaPolicy(Clones.cloneDeterministic(address(policyLogic), 0));

    // Calculated from the first strategy configuration passed in.
    ILlamaStrategy bootstrapStrategy = ILlamaStrategy(
      Clones.predictDeterministicAddress(
        address(config.strategyLogic), keccak256(config.initialStrategies[0]), address(this)
      )
    );
    PermissionData memory bootstrapPermissionData =
      PermissionData(address(policy), LlamaPolicy.setRolePermission.selector, bootstrapStrategy);

    // Initialize `LlamaPolicy` with holders of role ID 1 (Bootstrap Role) given permission to change role
    // permissions. This is required to reduce the chance that an instance is deployed with an invalid configuration
    // that results in the instance being unusable.
    policy.initialize(config.name, config.policyConfig, policyMetadataLogic, address(executor), bootstrapPermissionData);

    // Authorize strategy logic contract and deploy strategies.
    _setStrategyLogicAuthorization(config.strategyLogic, true);
    _deployStrategies(config.strategyLogic, config.initialStrategies);

    // Check that the bootstrap strategy was deployed and authorized to the pre-calculated address.
    // This should never be thrown in production and is just here as an extra safety check.
    if (!strategies[bootstrapStrategy].authorized) revert BootstrapStrategyNotAuthorized();

    // Authorize account logic contract and deploy accounts.
    _setAccountLogicAuthorization(config.accountLogic, true);
    _deployAccounts(config.accountLogic, config.initialAccounts);
  }

  // ===========================================
  // ======== External and Public Logic ========
  // ===========================================

  // -------- Action Lifecycle Management --------

  /// @notice Creates an action. The creator needs to hold a policy with the permission ID of the provided
  /// `(target, selector, strategy)`.
  /// @dev Use `""` for `description` if there is no description.
  /// @param role The role that will be used to determine the permission ID of the policyholder.
  /// @param strategy The strategy contract that will determine how the action is executed.
  /// @param target The contract called when the action is executed.
  /// @param value The value in wei to be sent when the action is executed.
  /// @param data Data to be called on the target when the action is executed.
  /// @param description A human readable description of the action and the changes it will enact.
  /// @return actionId Action ID of the newly created action.
  function createAction(
    uint8 role,
    ILlamaStrategy strategy,
    address target,
    uint256 value,
    bytes calldata data,
    string memory description
  ) external returns (uint256 actionId) {
    actionId = _createAction(msg.sender, role, strategy, target, value, data, description);
  }

  /// @notice Creates an action via an off-chain signature. The creator needs to hold a policy with the permission ID
  /// of the provided `(target, selector, strategy)`.
  /// @dev Use `""` for `description` if there is no description.
  /// @param policyholder The policyholder that signed the message.
  /// @param role The role that will be used to determine the permission ID of the policyholder.
  /// @param strategy The strategy contract that will determine how the action is executed.
  /// @param target The contract called when the action is executed.
  /// @param value The value in wei to be sent when the action is executed.
  /// @param data Data to be called on the target when the action is executed.
  /// @param description A human readable description of the action and the changes it will enact.
  /// @param v ECDSA signature component: Parity of the `y` coordinate of point `R`
  /// @param r ECDSA signature component: x-coordinate of `R`
  /// @param s ECDSA signature component: `s` value of the signature
  /// @return actionId Action ID of the newly created action.
  function createActionBySig(
    address policyholder,
    uint8 role,
    ILlamaStrategy strategy,
    address target,
    uint256 value,
    bytes calldata data,
    string memory description,
    uint8 v,
    bytes32 r,
    bytes32 s
  ) external returns (uint256 actionId) {
    bytes32 digest = _getCreateActionTypedDataHash(policyholder, role, strategy, target, value, data, description);
    address signer = ecrecover(digest, v, r, s);
    if (signer == address(0) || signer != policyholder) revert InvalidSignature();
    actionId = _createAction(signer, role, strategy, target, value, data, description);
  }

  /// @notice Queue an action by its `actionInfo` struct if it's in Approved state.
  /// @param actionInfo Data required to create an action.
  function queueAction(ActionInfo calldata actionInfo) external {
    Action storage action = actions[actionInfo.id];
    ActionState currentState = getActionState(actionInfo);
    if (currentState != ActionState.Approved) revert InvalidActionState(currentState);

    _queueAction(action, actionInfo);
  }

  /// @notice Execute an action by its `actionInfo` struct if it's in Queued state and `minExecutionTime` has passed.
  /// @param actionInfo Data required to create an action.
  function executeAction(ActionInfo calldata actionInfo) external payable {
    // Initial checks that action is ready to execute.
    Action storage action = actions[actionInfo.id];
    ActionState currentState = getActionState(actionInfo);

    if (currentState != ActionState.Queued) revert InvalidActionState(currentState);
    if (block.timestamp < action.minExecutionTime) revert MinExecutionTimeNotReached();
    if (msg.value != actionInfo.value) revert IncorrectMsgValue();

    action.executed = true;

    // Check pre-execution action guard.
    ILlamaActionGuard guard = action.guard;
    if (guard != ILlamaActionGuard(address(0))) guard.validatePreActionExecution(actionInfo);

    // Execute action.
    (bool success, bytes memory result) =
      executor.execute{value: actionInfo.value}(actionInfo.target, action.isScript, actionInfo.data);

    if (!success) revert FailedActionExecution(result);

    // Check post-execution action guard.
    if (guard != ILlamaActionGuard(address(0))) guard.validatePostActionExecution(actionInfo);

    // Action successfully executed.
    emit ActionExecuted(actionInfo.id, msg.sender, actionInfo.strategy, actionInfo.creator, result);
  }

  /// @notice Cancels an action by its `actionInfo` struct.
  /// @dev Rules for cancelation are defined by the strategy.
  /// @param actionInfo Data required to create an action.
  function cancelAction(ActionInfo calldata actionInfo) external {
    _cancelAction(msg.sender, actionInfo);
  }

  /// @notice Cancels an action by its `actionInfo` struct via an off-chain signature.
  /// @dev Rules for cancelation are defined by the strategy.
  /// @param policyholder The policyholder that signed the message.
  /// @param actionInfo Data required to create an action.
  /// @param v ECDSA signature component: Parity of the `y` coordinate of point `R`
  /// @param r ECDSA signature component: x-coordinate of `R`
  /// @param s ECDSA signature component: `s` value of the signature
  function cancelActionBySig(address policyholder, ActionInfo calldata actionInfo, uint8 v, bytes32 r, bytes32 s)
    external
  {
    bytes32 digest = _getCancelActionTypedDataHash(policyholder, actionInfo);
    address signer = ecrecover(digest, v, r, s);
    if (signer == address(0) || signer != policyholder) revert InvalidSignature();
    _cancelAction(signer, actionInfo);
  }

  /// @notice How policyholders add their support of the approval of an action with a reason.
  /// @dev Use `""` for `reason` if there is no reason.
  /// @param role The role the policyholder uses to cast their approval.
  /// @param actionInfo Data required to create an action.
  /// @param reason The reason given for the approval by the policyholder.
  /// @return The quantity of the cast.
  function castApproval(uint8 role, ActionInfo calldata actionInfo, string calldata reason) external returns (uint96) {
    return _castApproval(msg.sender, role, actionInfo, reason);
  }

  /// @notice How policyholders add their support of the approval of an action via an off-chain signature.
  /// @dev Use `""` for `reason` if there is no reason.
  /// @param policyholder The policyholder that signed the message.
  /// @param role The role the policyholder uses to cast their approval.
  /// @param actionInfo Data required to create an action.
  /// @param reason The reason given for the approval by the policyholder.
  /// @param v ECDSA signature component: Parity of the `y` coordinate of point `R`
  /// @param r ECDSA signature component: x-coordinate of `R`
  /// @param s ECDSA signature component: `s` value of the signature
  /// @return The quantity of the cast.
  function castApprovalBySig(
    address policyholder,
    uint8 role,
    ActionInfo calldata actionInfo,
    string calldata reason,
    uint8 v,
    bytes32 r,
    bytes32 s
  ) external returns (uint96) {
    bytes32 digest = _getCastApprovalTypedDataHash(policyholder, role, actionInfo, reason);
    address signer = ecrecover(digest, v, r, s);
    if (signer == address(0) || signer != policyholder) revert InvalidSignature();
    return _castApproval(signer, role, actionInfo, reason);
  }

  /// @notice How policyholders add their support of the disapproval of an action with a reason.
  /// @dev Use `""` for `reason` if there is no reason.
  /// @param role The role the policyholder uses to cast their disapproval.
  /// @param actionInfo Data required to create an action.
  /// @param reason The reason given for the disapproval by the policyholder.
  /// @return The quantity of the cast.
  function castDisapproval(uint8 role, ActionInfo calldata actionInfo, string calldata reason)
    external
    returns (uint96)
  {
    return _castDisapproval(msg.sender, role, actionInfo, reason);
  }

  /// @notice How policyholders add their support of the disapproval of an action via an off-chain signature.
  /// @dev Use `""` for `reason` if there is no reason.
  /// @param policyholder The policyholder that signed the message.
  /// @param role The role the policyholder uses to cast their disapproval.
  /// @param actionInfo Data required to create an action.
  /// @param reason The reason given for the approval by the policyholder.
  /// @param v ECDSA signature component: Parity of the `y` coordinate of point `R`
  /// @param r ECDSA signature component: x-coordinate of `R`
  /// @param s ECDSA signature component: `s` value of the signature
  /// @return The quantity of the cast.
  function castDisapprovalBySig(
    address policyholder,
    uint8 role,
    ActionInfo calldata actionInfo,
    string calldata reason,
    uint8 v,
    bytes32 r,
    bytes32 s
  ) external returns (uint96) {
    bytes32 digest = _getCastDisapprovalTypedDataHash(policyholder, role, actionInfo, reason);
    address signer = ecrecover(digest, v, r, s);
    if (signer == address(0) || signer != policyholder) revert InvalidSignature();
    return _castDisapproval(signer, role, actionInfo, reason);
  }

  // -------- Instance Management --------

  /// @notice Sets `strategyLogic` authorization status, which determines if it can be used to create new strategies.
  /// @dev Unauthorizing a strategy logic contract will not affect previously deployed strategies.
  /// @dev Be careful not to conflate this with `setStrategyAuthorization`.
  /// @param strategyLogic The strategy logic contract to authorize.
  /// @param authorized `true` to authorize the strategy logic, `false` to unauthorize it.
  function setStrategyLogicAuthorization(ILlamaStrategy strategyLogic, bool authorized) external onlyLlama {
    _setStrategyLogicAuthorization(strategyLogic, authorized);
  }

  /// @notice Deploy new strategies and add them to the mapping of authorized strategies.
  /// @param llamaStrategyLogic address of the Llama strategy logic contract.
  /// @param strategyConfigs Array of new strategy configurations.
  function createStrategies(ILlamaStrategy llamaStrategyLogic, bytes[] calldata strategyConfigs) external onlyLlama {
    _deployStrategies(llamaStrategyLogic, strategyConfigs);
  }

  /// @notice Sets `strategy` authorization status, which determines if it can be used to create actions.
  /// @dev To unauthorize a deployed `strategy`, set `authorized` to `false`.
  /// @dev Be careful not to conflate this with `setStrategyLogicAuthorization`.
  /// @param strategy The address of the deployed strategy contract.
  /// @param authorized `true` to authorize the strategy, `false` to unauthorize it.
  function setStrategyAuthorization(ILlamaStrategy strategy, bool authorized) external onlyLlama {
    _setStrategyAuthorization(strategy, authorized);
  }

  /// @notice Sets `accountLogic` authorization status, which determines if it can be used to create new accounts.
  /// @dev Unauthorizing an account logic contract will not affect previously deployed accounts.
  /// @param accountLogic The account logic contract to authorize.
  /// @param authorized `true` to authorize the account logic, `false` to unauthorize it.
  function setAccountLogicAuthorization(ILlamaAccount accountLogic, bool authorized) external onlyLlama {
    _setAccountLogicAuthorization(accountLogic, authorized);
  }

  /// @notice Deploy new accounts.
  /// @param llamaAccountLogic address of the Llama account logic contract.
  /// @param accountConfigs Array of new account configurations.
  function createAccounts(ILlamaAccount llamaAccountLogic, bytes[] calldata accountConfigs) external onlyLlama {
    _deployAccounts(llamaAccountLogic, accountConfigs);
  }

  /// @notice Sets `guard` as the action guard for the given `target` and `selector`.
  /// @dev To remove a guard, set `guard` to the zero address.
  /// @param target The target contract where the `guard` will apply.
  /// @param selector The function selector where the `guard` will apply.
  function setGuard(address target, bytes4 selector, ILlamaActionGuard guard) external onlyLlama {
    if (target == address(this) || target == address(policy)) revert RestrictedAddress();
    actionGuard[target][selector] = guard;
    emit ActionGuardSet(target, selector, guard);
  }

  /// @notice Sets `script` authorization status, which determines if it can be delegatecalled from the executor.
  /// @dev To unauthorize a `script`, set `authorized` to `false`.
  /// @param script The address of the script contract.
  /// @param authorized `true` to authorize the script, `false` to unauthorize it.
  function setScriptAuthorization(address script, bool authorized) external onlyLlama {
    if (script == address(this) || script == address(policy)) revert RestrictedAddress();
    authorizedScripts[script] = authorized;
    emit ScriptAuthorizationSet(script, authorized);
  }

  // -------- User Nonce Management --------

  /// @notice Increments the caller's nonce for the given `selector`. This is useful for revoking
  /// signatures that have not been used yet.
  /// @param selector The function selector to increment the nonce for.
  function incrementNonce(bytes4 selector) external {
    // Safety: Can never overflow a uint256 by incrementing.
    nonces[msg.sender][selector] = LlamaUtils.uncheckedIncrement(nonces[msg.sender][selector]);
  }

  // -------- Action and State Getters --------

  /// @notice Get an Action struct by `actionId`.
  /// @param actionId ID of the action.
  /// @return The Action struct.
  function getAction(uint256 actionId) external view returns (Action memory) {
    return actions[actionId];
  }

  /// @notice Get the current action state of an action by its `actionInfo` struct.
  /// @param actionInfo Data required to create an action.
  /// @return The current action state of the action.
  function getActionState(ActionInfo calldata actionInfo) public view returns (ActionState) {
    // We don't need an explicit check on the action ID to make sure it exists, because if the
    // action does not exist, the expected payload hash from storage will be `bytes32(0)`, so
    // bypassing this check by providing a non-existent actionId would require finding a collision
    // to get a hash of zero.
    Action storage action = actions[actionInfo.id];
    _validateActionInfoHash(action.infoHash, actionInfo);

    if (action.canceled) return ActionState.Canceled;

    if (action.executed) return ActionState.Executed;

    if (actionInfo.strategy.isActionActive(actionInfo)) return ActionState.Active;

    if (!actionInfo.strategy.isActionApproved(actionInfo)) return ActionState.Failed;

    if (action.minExecutionTime == 0) return ActionState.Approved;

    if (actionInfo.strategy.isActionDisapproved(actionInfo)) return ActionState.Failed;

    if (actionInfo.strategy.isActionExpired(actionInfo)) return ActionState.Expired;

    return ActionState.Queued;
  }

  // ================================
  // ======== Internal Logic ========
  // ================================

  /// @dev Creates an action. The creator needs to hold a policy with the permission ID of the provided
  /// `(target, selector, strategy)`.
  function _createAction(
    address policyholder,
    uint8 role,
    ILlamaStrategy strategy,
    address target,
    uint256 value,
    bytes calldata data,
    string memory description
  ) internal returns (uint256 actionId) {
    if (target == address(executor)) revert CannotSetExecutorAsTarget();
    if (!strategies[strategy].authorized) revert UnauthorizedStrategy();

    PermissionData memory permission = PermissionData(target, bytes4(data), strategy);
    bytes32 permissionId = LlamaUtils.computePermissionId(permission);

    // Typically (such as in Governor contracts) this should check that the caller has permission
    // at `block.number|timestamp - 1` but here we're just checking if the caller *currently* has
    // permission. Technically this introduces a race condition if e.g. an action to revoke a role
    // from someone (or revoke a permission from a role) is ready to be executed at the same time as
    // an action is created, as the order of transactions in the block then affects if action
    // creation would succeed. However, we are ok with this tradeoff because it means we don't need
    // to checkpoint the `canCreateAction` mapping which is simpler and cheaper, and in practice
    // this race condition is unlikely to matter.
    if (!policy.hasPermissionId(policyholder, role, permissionId)) revert PolicyholderDoesNotHavePermission();

    // Update `actionsCount` and create `actionInfo` struct.
    actionId = actionsCount;
    actionsCount = LlamaUtils.uncheckedIncrement(actionsCount); // Safety: Can never overflow a uint256 by incrementing.
    ActionInfo memory actionInfo = ActionInfo(actionId, policyholder, role, strategy, target, value, data);

    // Scope to avoid stack too deep
    {
      // Save action.
      Action storage newAction = actions[actionId];
      newAction.infoHash = _infoHash(actionInfo);
      newAction.creationTime = LlamaUtils.toUint64(block.timestamp);
      newAction.isScript = authorizedScripts[target];

      // Validate action creation.
      strategy.validateActionCreation(actionInfo);

      ILlamaActionGuard guard = actionGuard[target][bytes4(data)];
      if (guard != ILlamaActionGuard(address(0))) {
        guard.validateActionCreation(actionInfo);
        newAction.guard = guard;
      }
    }

    emit ActionCreated(actionId, policyholder, role, strategy, target, value, data, description);
  }

  /// @dev Cancels an action by its `actionInfo` struct.
  function _cancelAction(address policyholder, ActionInfo calldata actionInfo) internal {
    Action storage action = actions[actionInfo.id];
    _validateActionInfoHash(action.infoHash, actionInfo);

    // We don't need an explicit check on action existence because if it doesn't exist the strategy will be the zero
    // address, and Solidity will revert since there is no code at the zero address.
    actionInfo.strategy.validateActionCancelation(actionInfo, policyholder);

    action.canceled = true;
    emit ActionCanceled(actionInfo.id, policyholder);
  }

  /// @dev How policyholders that have the right role contribute towards the approval of an action with a reason.
  function _castApproval(address policyholder, uint8 role, ActionInfo calldata actionInfo, string memory reason)
    internal
    returns (uint96)
  {
    (Action storage action, uint96 quantity) = _preCastAssertions(actionInfo, policyholder, role, ActionState.Active);

    action.totalApprovals = _newCastCount(action.totalApprovals, quantity);
    approvals[actionInfo.id][policyholder] = true;
    emit ApprovalCast(actionInfo.id, policyholder, role, quantity, reason);

    // We call `getActionState` here to determine if we should queue the action. This works because the ordering
    // in `LlamaCore.getActionState` checks `.isActionActive()` first, and if not, then it calls `.isActionApproved`.
    // If `.isActionActive()` returns `true`, then we don't queue.
    // If `.isActionApproved()` returns `true`, then we queue.
    ActionState currentState = getActionState(actionInfo);
    if (currentState == ActionState.Approved) _queueAction(action, actionInfo);

    return quantity;
  }

  /// @dev How policyholders that have the right role contribute towards the disapproval of an action with a reason.
  function _castDisapproval(address policyholder, uint8 role, ActionInfo calldata actionInfo, string memory reason)
    internal
    returns (uint96)
  {
    (Action storage action, uint96 quantity) = _preCastAssertions(actionInfo, policyholder, role, ActionState.Queued);

    action.totalDisapprovals = _newCastCount(action.totalDisapprovals, quantity);
    disapprovals[actionInfo.id][policyholder] = true;
    emit DisapprovalCast(actionInfo.id, policyholder, role, quantity, reason);
    return quantity;
  }

  /// @dev Updates state of an action to `ActionState::Queued` and emits an event. Used in `queueAction` and
  /// `_castApproval`.
  function _queueAction(Action storage action, ActionInfo calldata actionInfo) internal {
    uint64 minExecutionTime = actionInfo.strategy.minExecutionTime(actionInfo);
    if (minExecutionTime < block.timestamp) revert MinExecutionTimeCannotBeInThePast();
    action.minExecutionTime = minExecutionTime;
    emit ActionQueued(actionInfo.id, msg.sender, actionInfo.strategy, actionInfo.creator, minExecutionTime);
  }

  /// @dev The only `expectedState` values allowed to be passed into this method are Active or Queued.
  function _preCastAssertions(
    ActionInfo calldata actionInfo,
    address policyholder,
    uint8 role,
    ActionState expectedState
  ) internal view returns (Action storage action, uint96 quantity) {
    action = actions[actionInfo.id];
    ActionState currentState = getActionState(actionInfo);
    if (currentState != expectedState) revert InvalidActionState(currentState);

    bool isApproval = expectedState == ActionState.Active;
    bool alreadyCast = isApproval ? approvals[actionInfo.id][policyholder] : disapprovals[actionInfo.id][policyholder];
    if (alreadyCast) revert DuplicateCast();

    // We look up data at `action.creationTime - 1` to avoid race conditions: A user's role balances
    // can change after action creation in the same block, so we can't actually know what the
    // correct values are at the time of action creation.
    uint256 checkpointTime = action.creationTime - 1;
    bool hasRole = policy.hasRole(policyholder, role, checkpointTime);
    if (!hasRole) revert InvalidPolicyholder();

    if (isApproval) {
      actionInfo.strategy.checkIfApprovalEnabled(actionInfo, policyholder, role);
      quantity = actionInfo.strategy.getApprovalQuantityAt(policyholder, role, checkpointTime);
      if (quantity == 0) revert CannotCastWithZeroQuantity(policyholder, role);
    } else {
      if (block.timestamp >= action.minExecutionTime) revert CannotDisapproveAfterMinExecutionTime();
      actionInfo.strategy.checkIfDisapprovalEnabled(actionInfo, policyholder, role);
      quantity = actionInfo.strategy.getDisapprovalQuantityAt(policyholder, role, checkpointTime);
      if (quantity == 0) revert CannotCastWithZeroQuantity(policyholder, role);
    }
  }

  /// @dev Returns the new total count of approvals or disapprovals.
  function _newCastCount(uint96 currentCount, uint96 quantity) internal pure returns (uint96) {
    if (uint256(currentCount) + quantity >= type(uint96).max) return type(uint96).max;
    return currentCount + quantity;
  }

  /// @dev Sets the authorization status for a strategy implementation (logic) contract.
  function _setStrategyLogicAuthorization(ILlamaStrategy strategyLogic, bool authorized) internal {
    authorizedStrategyLogics[strategyLogic] = authorized;
    emit StrategyLogicAuthorizationSet(strategyLogic, authorized);
  }

  /// @dev Deploys new strategies. Takes in the strategy logic contract to be used and an array of configurations to
  /// initialize the new strategies with.
  function _deployStrategies(ILlamaStrategy llamaStrategyLogic, bytes[] calldata strategyConfigs) internal {
    if (!authorizedStrategyLogics[llamaStrategyLogic]) revert UnauthorizedStrategyLogic();

    uint256 strategyLength = strategyConfigs.length;
    for (uint256 i = 0; i < strategyLength; i = LlamaUtils.uncheckedIncrement(i)) {
      bytes32 salt = keccak256(strategyConfigs[i]);
      ILlamaStrategy strategy = ILlamaStrategy(Clones.cloneDeterministic(address(llamaStrategyLogic), salt));
      strategy.initialize(strategyConfigs[i]);
      strategies[strategy].deployed = true;
      _setStrategyAuthorization(strategy, true);
      emit StrategyCreated(strategy, llamaStrategyLogic, strategyConfigs[i]);
    }
  }

  /// @dev Sets the `strategy` authorization status to `authorized`.
  function _setStrategyAuthorization(ILlamaStrategy strategy, bool authorized) internal {
    if (!strategies[strategy].deployed) revert NonExistentStrategy();
    strategies[strategy].authorized = authorized;
    emit StrategyAuthorizationSet(strategy, authorized);
  }

  /// @dev Authorizes an account implementation (logic) contract.
  function _setAccountLogicAuthorization(ILlamaAccount accountLogic, bool authorized) internal {
    authorizedAccountLogics[accountLogic] = authorized;
    emit AccountLogicAuthorizationSet(accountLogic, authorized);
  }

  /// @dev Deploys new accounts. Takes in the account logic contract to be used and an array of configurations to
  /// initialize the new accounts with.
  function _deployAccounts(ILlamaAccount llamaAccountLogic, bytes[] calldata accountConfigs) internal {
    if (!authorizedAccountLogics[llamaAccountLogic]) revert UnauthorizedAccountLogic();

    uint256 accountLength = accountConfigs.length;
    for (uint256 i = 0; i < accountLength; i = LlamaUtils.uncheckedIncrement(i)) {
      bytes32 salt = keccak256(accountConfigs[i]);
      ILlamaAccount account = ILlamaAccount(Clones.cloneDeterministic(address(llamaAccountLogic), salt));
      account.initialize(accountConfigs[i]);
      emit AccountCreated(account, llamaAccountLogic, accountConfigs[i]);
    }
  }

  /// @dev Returns the hash of the `createAction` parameters using the `actionInfo` struct.
  function _infoHash(ActionInfo memory actionInfo) internal pure returns (bytes32) {
    return keccak256(
      abi.encodePacked(
        actionInfo.id,
        actionInfo.creator,
        actionInfo.creatorRole,
        actionInfo.strategy,
        actionInfo.target,
        actionInfo.value,
        actionInfo.data
      )
    );
  }

  /// @dev Validates that the hash of the `actionInfo` struct matches the provided hash.
  function _validateActionInfoHash(bytes32 actualHash, ActionInfo calldata actionInfo) internal pure {
    bytes32 expectedHash = _infoHash(actionInfo);
    if (actualHash != expectedHash) revert InfoHashMismatch();
  }

  /// @dev Returns the current nonce for a given policyholder and selector, and increments it. Used to prevent
  /// replay attacks.
  function _useNonce(address policyholder, bytes4 selector) internal returns (uint256 nonce) {
    nonce = nonces[policyholder][selector];
    nonces[policyholder][selector] = LlamaUtils.uncheckedIncrement(nonce);
  }

  // -------- EIP-712 Getters --------

  /// @dev Returns the EIP-712 domain separator.
  function _getDomainHash() internal view returns (bytes32) {
    return keccak256(
      abi.encode(EIP712_DOMAIN_TYPEHASH, keccak256(bytes(name)), keccak256(bytes("1")), block.chainid, address(this))
    );
  }

  /// @dev Returns the hash of the ABI-encoded EIP-712 message for the `CreateAction` domain, which can be used to
  /// recover the signer.
  function _getCreateActionTypedDataHash(
    address policyholder,
    uint8 role,
    ILlamaStrategy strategy,
    address target,
    uint256 value,
    bytes calldata data,
    string memory description
  ) internal returns (bytes32) {
    // Calculating and storing nonce in memory and using that below, instead of calculating in place to prevent stack
    // too deep error.
    uint256 nonce = _useNonce(policyholder, msg.sig);

    bytes32 createActionHash = keccak256(
      abi.encode(
        CREATE_ACTION_TYPEHASH,
        policyholder,
        role,
        address(strategy),
        target,
        value,
        keccak256(data),
        keccak256(bytes(description)),
        nonce
      )
    );

    return keccak256(abi.encodePacked("\x19\x01", _getDomainHash(), createActionHash));
  }

  /// @dev Returns the hash of the ABI-encoded EIP-712 message for the `CancelAction` domain, which can be used to
  /// recover the signer.
  function _getCancelActionTypedDataHash(address policyholder, ActionInfo calldata actionInfo)
    internal
    returns (bytes32)
  {
    bytes32 cancelActionHash = keccak256(
      abi.encode(CANCEL_ACTION_TYPEHASH, policyholder, _getActionInfoHash(actionInfo), _useNonce(policyholder, msg.sig))
    );

    return keccak256(abi.encodePacked("\x19\x01", _getDomainHash(), cancelActionHash));
  }

  /// @dev Returns the hash of the ABI-encoded EIP-712 message for the `CastApproval` domain, which can be used to
  /// recover the signer.
  function _getCastApprovalTypedDataHash(
    address policyholder,
    uint8 role,
    ActionInfo calldata actionInfo,
    string calldata reason
  ) internal returns (bytes32) {
    bytes32 castApprovalHash = keccak256(
      abi.encode(
        CAST_APPROVAL_TYPEHASH,
        policyholder,
        role,
        _getActionInfoHash(actionInfo),
        keccak256(bytes(reason)),
        _useNonce(policyholder, msg.sig)
      )
    );

    return keccak256(abi.encodePacked("\x19\x01", _getDomainHash(), castApprovalHash));
  }

  /// @dev Returns the hash of the ABI-encoded EIP-712 message for the `CastDisapproval` domain, which can be used to
  /// recover the signer.
  function _getCastDisapprovalTypedDataHash(
    address policyholder,
    uint8 role,
    ActionInfo calldata actionInfo,
    string calldata reason
  ) internal returns (bytes32) {
    bytes32 castDisapprovalHash = keccak256(
      abi.encode(
        CAST_DISAPPROVAL_TYPEHASH,
        policyholder,
        role,
        _getActionInfoHash(actionInfo),
        keccak256(bytes(reason)),
        _useNonce(policyholder, msg.sig)
      )
    );

    return keccak256(abi.encodePacked("\x19\x01", _getDomainHash(), castDisapprovalHash));
  }

  /// @dev Returns the hash of `actionInfo`.
  function _getActionInfoHash(ActionInfo calldata actionInfo) internal pure returns (bytes32) {
    return keccak256(
      abi.encode(
        ACTION_INFO_TYPEHASH,
        actionInfo.id,
        actionInfo.creator,
        actionInfo.creatorRole,
        address(actionInfo.strategy),
        actionInfo.target,
        actionInfo.value,
        keccak256(actionInfo.data)
      )
    );
  }
}

// File: lib/openzeppelin-contracts/contracts/token/ERC20/extensions/draft-IERC20Permit.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (token/ERC20/extensions/draft-IERC20Permit.sol)

pragma solidity ^0.8.0;

/**
 * @dev Interface of the ERC20 Permit extension allowing approvals to be made via signatures, as defined in
 * https://eips.ethereum.org/EIPS/eip-2612[EIP-2612].
 *
 * Adds the {permit} method, which can be used to change an account's ERC20 allowance (see {IERC20-allowance}) by
 * presenting a message signed by the account. By not relying on {IERC20-approve}, the token holder account doesn't
 * need to send a transaction, and thus is not required to hold Ether at all.
 */
interface IERC20Permit {
    /**
     * @dev Sets `value` as the allowance of `spender` over ``owner``'s tokens,
     * given ``owner``'s signed approval.
     *
     * IMPORTANT: The same issues {IERC20-approve} has related to transaction
     * ordering also apply here.
     *
     * Emits an {Approval} event.
     *
     * Requirements:
     *
     * - `spender` cannot be the zero address.
     * - `deadline` must be a timestamp in the future.
     * - `v`, `r` and `s` must be a valid `secp256k1` signature from `owner`
     * over the EIP712-formatted function arguments.
     * - the signature must use ``owner``'s current nonce (see {nonces}).
     *
     * For more information on the signature format, see the
     * https://eips.ethereum.org/EIPS/eip-2612#specification[relevant EIP
     * section].
     */
    function permit(
        address owner,
        address spender,
        uint256 value,
        uint256 deadline,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) external;

    /**
     * @dev Returns the current nonce for `owner`. This value must be
     * included whenever a signature is generated for {permit}.
     *
     * Every successful call to {permit} increases ``owner``'s nonce by one. This
     * prevents a signature from being used multiple times.
     */
    function nonces(address owner) external view returns (uint256);

    /**
     * @dev Returns the domain separator used in the encoding of the signature for {permit}, as defined by {EIP712}.
     */
    // solhint-disable-next-line func-name-mixedcase
    function DOMAIN_SEPARATOR() external view returns (bytes32);
}

// File: lib/openzeppelin-contracts/contracts/utils/introspection/IERC165.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/introspection/IERC165.sol)

pragma solidity ^0.8.0;

/**
 * @dev Interface of the ERC165 standard, as defined in the
 * https://eips.ethereum.org/EIPS/eip-165[EIP].
 *
 * Implementers can declare support of contract interfaces, which can then be
 * queried by others ({ERC165Checker}).
 *
 * For an implementation, see {ERC165}.
 */
interface IERC165 {
    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified[EIP section]
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30 000 gas.
     */
    function supportsInterface(bytes4 interfaceId) external view returns (bool);
}

// File: lib/openzeppelin-contracts/contracts/token/ERC721/IERC721Receiver.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.6.0) (token/ERC721/IERC721Receiver.sol)

pragma solidity ^0.8.0;

/**
 * @title ERC721 token receiver interface
 * @dev Interface for any contract that wants to support safeTransfers
 * from ERC721 asset contracts.
 */
interface IERC721Receiver {
    /**
     * @dev Whenever an {IERC721} `tokenId` token is transferred to this contract via {IERC721-safeTransferFrom}
     * by `operator` from `from`, this function is called.
     *
     * It must return its Solidity selector to confirm the token transfer.
     * If any other value is returned or the interface is not implemented by the recipient, the transfer will be reverted.
     *
     * The selector can be obtained in Solidity with `IERC721Receiver.onERC721Received.selector`.
     */
    function onERC721Received(
        address operator,
        address from,
        uint256 tokenId,
        bytes calldata data
    ) external returns (bytes4);
}

// File: lib/openzeppelin-contracts/contracts/token/ERC1155/utils/ERC1155Receiver.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (token/ERC1155/utils/ERC1155Receiver.sol)

pragma solidity ^0.8.0;

import "../IERC1155Receiver.sol";
import "../../../utils/introspection/ERC165.sol";

/**
 * @dev _Available since v3.1._
 */
abstract contract ERC1155Receiver is ERC165, IERC1155Receiver {
    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override(ERC165, IERC165) returns (bool) {
        return interfaceId == type(IERC1155Receiver).interfaceId || super.supportsInterface(interfaceId);
    }
}

// File: src/lib/Structs.sol



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

import {ILlamaAccount} from "src/interfaces/ILlamaAccount.sol";
import {ILlamaActionGuard} from "src/interfaces/ILlamaActionGuard.sol";
import {ILlamaStrategy} from "src/interfaces/ILlamaStrategy.sol";
import {RoleDescription} from "src/lib/UDVTs.sol";

/// @dev Data required to create an action.
struct ActionInfo {
  uint256 id; // ID of the action.
  address creator; // Address that created the action.
  uint8 creatorRole; // The role that created the action.
  ILlamaStrategy strategy; // Strategy used to govern the action.
  address target; // Contract being called by an action.
  uint256 value; // Value in wei to be sent when the action is executed.
  bytes data; // Data to be called on the target when the action is executed.
}

/// @dev Data that represents an action.
struct Action {
  // Instead of storing all data required to execute an action in storage, we only save the hash to
  // make action creation cheaper. The hash is computed by taking the keccak256 hash of the concatenation of each
  // field in the `ActionInfo` struct.
  bytes32 infoHash;
  bool executed; // Has action executed.
  bool canceled; // Is action canceled.
  bool isScript; // Is the action's target a script.
  ILlamaActionGuard guard; // The action's guard. This is the address(0) if no guard is set on the action's target and
    // selector pair.
  uint64 creationTime; // The timestamp when action was created (used for policy snapshots).
  uint64 minExecutionTime; // Only set when an action is queued. The timestamp when action execution can begin.
  uint96 totalApprovals; // The total quantity of policyholder approvals.
  uint96 totalDisapprovals; // The total quantity of policyholder disapprovals.
}

/// @dev Data that represents a permission.
struct PermissionData {
  address target; // Contract being called by an action.
  bytes4 selector; // Selector of the function being called by an action.
  ILlamaStrategy strategy; // Strategy used to govern the action.
}

/// @dev Data required to assign/revoke a role to/from a policyholder.
struct RoleHolderData {
  uint8 role; // ID of the role to set (uint8 ensures onchain enumerability when burning policies).
  address policyholder; // Policyholder to assign the role to.
  uint96 quantity; // Quantity of the role to assign to the policyholder, i.e. their (dis)approval quantity.
  uint64 expiration; // When the role expires.
}

/// @dev Data required to assign/revoke a permission to/from a role.
struct RolePermissionData {
  uint8 role; // ID of the role to set (uint8 ensures onchain enumerability when burning policies).
  PermissionData permissionData; // The `(target, selector, strategy)` tuple that will be keccak256 hashed to
    // generate the permission ID to assign or unassign to the role
  bool hasPermission; // Whether to assign the permission or remove the permission.
}

/// @dev Configuration of a new Llama instance.
struct LlamaInstanceConfig {
  string name; // The name of the Llama instance.
  ILlamaStrategy strategyLogic; // The initial strategy implementation (logic) contract.
  ILlamaAccount accountLogic; // The initial account implementation (logic) contract.
  bytes[] initialStrategies; // Array of initial strategy configurations.
  bytes[] initialAccounts; // Array of initial account configurations.
  LlamaPolicyConfig policyConfig; // Configuration of the instance's policy.
}

/// @dev Configuration of a new Llama policy.
struct LlamaPolicyConfig {
  RoleDescription[] roleDescriptions; // The initial role descriptions.
  RoleHolderData[] roleHolders; // The `role`, `policyholder`, `quantity` and `expiration` of the initial role holders.
  RolePermissionData[] rolePermissions; // The `role`, `permissionData`, and  the `hasPermission` boolean.
  string color; // The primary color of the SVG representation of the instance's policy (e.g. #00FF00).
  string logo; // The SVG string representing the logo for the deployed Llama instance's NFT.
}

// File: lib/openzeppelin-contracts/contracts/proxy/Clones.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (proxy/Clones.sol)

pragma solidity ^0.8.0;

/**
 * @dev https://eips.ethereum.org/EIPS/eip-1167[EIP 1167] is a standard for
 * deploying minimal proxy contracts, also known as "clones".
 *
 * > To simply and cheaply clone contract functionality in an immutable way, this standard specifies
 * > a minimal bytecode implementation that delegates all calls to a known, fixed address.
 *
 * The library includes functions to deploy a proxy using either `create` (traditional deployment) or `create2`
 * (salted deterministic deployment). It also includes functions to predict the addresses of clones deployed using the
 * deterministic method.
 *
 * _Available since v3.4._
 */
library Clones {
    /**
     * @dev Deploys and returns the address of a clone that mimics the behaviour of `implementation`.
     *
     * This function uses the create opcode, which should never revert.
     */
    function clone(address implementation) internal returns (address instance) {
        /// @solidity memory-safe-assembly
        assembly {
            // Cleans the upper 96 bits of the `implementation` word, then packs the first 3 bytes
            // of the `implementation` address with the bytecode before the address.
            mstore(0x00, or(shr(0xe8, shl(0x60, implementation)), 0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000))
            // Packs the remaining 17 bytes of `implementation` with the bytecode after the address.
            mstore(0x20, or(shl(0x78, implementation), 0x5af43d82803e903d91602b57fd5bf3))
            instance := create(0, 0x09, 0x37)
        }
        require(instance != address(0), "ERC1167: create failed");
    }

    /**
     * @dev Deploys and returns the address of a clone that mimics the behaviour of `implementation`.
     *
     * This function uses the create2 opcode and a `salt` to deterministically deploy
     * the clone. Using the same `implementation` and `salt` multiple time will revert, since
     * the clones cannot be deployed twice at the same address.
     */
    function cloneDeterministic(address implementation, bytes32 salt) internal returns (address instance) {
        /// @solidity memory-safe-assembly
        assembly {
            // Cleans the upper 96 bits of the `implementation` word, then packs the first 3 bytes
            // of the `implementation` address with the bytecode before the address.
            mstore(0x00, or(shr(0xe8, shl(0x60, implementation)), 0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000))
            // Packs the remaining 17 bytes of `implementation` with the bytecode after the address.
            mstore(0x20, or(shl(0x78, implementation), 0x5af43d82803e903d91602b57fd5bf3))
            instance := create2(0, 0x09, 0x37, salt)
        }
        require(instance != address(0), "ERC1167: create2 failed");
    }

    /**
     * @dev Computes the address of a clone deployed using {Clones-cloneDeterministic}.
     */
    function predictDeterministicAddress(
        address implementation,
        bytes32 salt,
        address deployer
    ) internal pure returns (address predicted) {
        /// @solidity memory-safe-assembly
        assembly {
            let ptr := mload(0x40)
            mstore(add(ptr, 0x38), deployer)
            mstore(add(ptr, 0x24), 0x5af43d82803e903d91602b57fd5bf3ff)
            mstore(add(ptr, 0x14), implementation)
            mstore(ptr, 0x3d602d80600a3d3981f3363d3d373d3d3d363d73)
            mstore(add(ptr, 0x58), salt)
            mstore(add(ptr, 0x78), keccak256(add(ptr, 0x0c), 0x37))
            predicted := keccak256(add(ptr, 0x43), 0x55)
        }
    }

    /**
     * @dev Computes the address of a clone deployed using {Clones-cloneDeterministic}.
     */
    function predictDeterministicAddress(address implementation, bytes32 salt)
        internal
        view
        returns (address predicted)
    {
        return predictDeterministicAddress(implementation, salt, address(this));
    }
}

// File: src/interfaces/ILlamaActionGuard.sol



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

import {ActionInfo} from "src/lib/Structs.sol";

/// @title Llama Action Guard Interface
/// @author Llama (devsdosomething@llama.xyz)
/// @notice Executes checks on action creation and execution to verify that the action is allowed.
/// @dev Methods are not `view` because (1) an action guard may write to it's own storage, and (2)
/// Having `view` methods that can revert isn't great UX. Allowing guards to write to their own
/// storage is useful to persist state between calls to the various guard methods. For example, a
/// guard may:
///   - Store the USD price of a token during action creation in `validateActionCreation`.
///   - Verify the price has not changed by more than a given amount during `validatePreActionExecution`
///     and save off the current USD value of an account.
///   - Verify the USD value of an account has not decreased by more than a certain amount during
///     execution, i.e. between `validatePreActionExecution` and `validatePostActionExecution`.
interface ILlamaActionGuard {
  /// @notice Reverts if action creation is not allowed.
  /// @param actionInfo Data required to create an action.
  function validateActionCreation(ActionInfo calldata actionInfo) external;

  /// @notice Called immediately before action execution, and reverts if the action is not allowed
  /// to be executed.
  /// @param actionInfo Data required to create an action.
  function validatePreActionExecution(ActionInfo calldata actionInfo) external;

  /// @notice Called immediately after action execution, and reverts if the just-executed
  /// action should not have been allowed to execute.
  /// @param actionInfo Data required to create an action.
  function validatePostActionExecution(ActionInfo calldata actionInfo) external;
}

// File: src/interfaces/ILlamaPolicyMetadata.sol



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

/// @title Llama Policy Metadata
/// @author Llama (devsdosomething@llama.xyz)
/// @notice Interface for utility contract to compute Llama policy metadata.
interface ILlamaPolicyMetadata {
  /// @notice Initializes a new clone of the policy metadata contract.
  /// @dev This function is called by the `_setAndInitializePolicyMetadata` function in the `LlamaPolicy` contract. The
  /// `initializer` modifier ensures that this function can be invoked at most once.
  /// @param config The policy metadata configuration, encoded as bytes to support differing initialization arguments in
  /// different policy metadata logic contracts.
  /// @return This return statement must be hardcoded to `true` to ensure that initializing an EOA
  /// (like the zero address) will revert.
  function initialize(bytes memory config) external returns (bool);

  /// @notice Returns the token URI for a given Llama policy ID.
  /// @param name The name of the Llama instance.
  /// @param executor The executor of the Llama instance.
  /// @param tokenId The token ID of the Llama policyholder.
  function getTokenURI(string memory name, address executor, uint256 tokenId) external view returns (string memory);

  /// @notice Returns the contract URI for a Llama instance's policies.
  /// @param name The name of the Llama instance.
  /// @param executor The executor of the Llama instance.
  function getContractURI(string memory name, address executor) external view returns (string memory);
}

// File: src/interfaces/ILlamaStrategy.sol



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

import {ActionInfo} from "src/lib/Structs.sol";
import {LlamaCore} from "src/LlamaCore.sol";
import {LlamaPolicy} from "src/LlamaPolicy.sol";

/// @title Llama Strategy Interface
/// @author Llama (devsdosomething@llama.xyz)
/// @notice This is the interface for Llama strategies which determine the rules of an action's process.
/// @dev The interface is sorted by the stage of the action's lifecycle in which the method's are used.
interface ILlamaStrategy {
  // -------- For Inspection --------
  // These are not strictly required by the core, but are useful for inspecting a strategy contract.

  /// @notice Returns the address of the Llama core that this strategy is registered to.
  function llamaCore() external view returns (LlamaCore);

  /// @notice Returns the name of the Llama policy that this strategy is registered to.
  function policy() external view returns (LlamaPolicy);

  // -------- At Strategy Creation --------

  /// @notice Initializes a new clone of the strategy.
  /// @dev This function is called by the `_deployStrategies` function in the `LlamaCore` contract. The `initializer`
  /// modifier ensures that this function can be invoked at most once.
  /// @param config The strategy configuration, encoded as bytes to support differing constructor arguments in
  /// different strategies.
  /// @return This return statement must be hardcoded to `true` to ensure that initializing an EOA
  /// (like the zero address) will revert.
  function initialize(bytes memory config) external returns (bool);

  // -------- At Action Creation --------

  /// @notice Reverts if action creation is not allowed.
  /// @param actionInfo Data required to create an action.
  function validateActionCreation(ActionInfo calldata actionInfo) external view;

  // -------- When Casting Approval --------

  /// @notice Reverts if approvals are not allowed with this strategy for the given policyholder when approving with
  /// role.
  /// @param actionInfo Data required to create an action.
  /// @param policyholder Address of the policyholder.
  /// @param role The role of the policyholder being used to cast approval.
  function checkIfApprovalEnabled(ActionInfo calldata actionInfo, address policyholder, uint8 role) external view;

  /// @notice Get the quantity of an approval of a policyholder at a specific timestamp.
  /// @param policyholder Address of the policyholder.
  /// @param role The role to check quantity for.
  /// @param timestamp The timestamp at which to get the approval quantity.
  /// @return The quantity of the policyholder's approval.
  function getApprovalQuantityAt(address policyholder, uint8 role, uint256 timestamp) external view returns (uint96);

  // -------- When Casting Disapproval --------

  /// @notice Reverts if disapprovals are not allowed with this strategy for the given policyholder when disapproving
  /// with role.
  /// @param actionInfo Data required to create an action.
  /// @param policyholder Address of the policyholder.
  /// @param role The role of the policyholder being used to cast disapproval.
  function checkIfDisapprovalEnabled(ActionInfo calldata actionInfo, address policyholder, uint8 role) external view;

  /// @notice Get the quantity of a disapproval of a policyholder at a specific timestamp.
  /// @param policyholder Address of the policyholder.
  /// @param role The role to check quantity for.
  /// @param timestamp The timestamp at which to get the disapproval quantity.
  /// @return The quantity of the policyholder's disapproval.
  function getDisapprovalQuantityAt(address policyholder, uint8 role, uint256 timestamp) external view returns (uint96);

  // -------- When Queueing --------

  /// @notice Returns the earliest timestamp, in seconds, at which an action can be executed.
  /// @param actionInfo Data required to create an action.
  /// @return The earliest timestamp at which an action can be executed.
  function minExecutionTime(ActionInfo calldata actionInfo) external view returns (uint64);

  // -------- When Canceling --------

  /// @notice Reverts if the action cannot be canceled.
  /// @param actionInfo Data required to create an action.
  /// @param caller Policyholder initiating the cancelation.
  function validateActionCancelation(ActionInfo calldata actionInfo, address caller) external view;

  // -------- When Determining Action State --------
  // These are used during casting of approvals and disapprovals, when queueing, and when executing.

  /// @notice Get whether an action is currently active.
  /// @param actionInfo Data required to create an action.
  /// @return Boolean value that is `true` if the action is currently active, `false` otherwise.
  function isActionActive(ActionInfo calldata actionInfo) external view returns (bool);

  /// @notice Get whether an action has passed the approval process.
  /// @param actionInfo Data required to create an action.
  /// @return Boolean value that is `true` if the action has passed the approval process.
  function isActionApproved(ActionInfo calldata actionInfo) external view returns (bool);

  /// @notice Get whether an action has been vetoed during the disapproval process.
  /// @param actionInfo Data required to create an action.
  /// @return Boolean value that is `true` if the action has been vetoed during the disapproval process.
  function isActionDisapproved(ActionInfo calldata actionInfo) external view returns (bool);

  /// @notice Returns `true` if the action is expired, `false` otherwise.
  /// @param actionInfo Data required to create an action.
  /// @return Boolean value that is `true` if the action is expired.
  function isActionExpired(ActionInfo calldata actionInfo) external view returns (bool);
}

// File: src/lib/Enums.sol



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

/// @dev Possible states of an action during its lifecycle.
enum ActionState {
  Active, // Action created and approval period begins.
  Canceled, // Action canceled by creator.
  Failed, // Action approval failed.
  Approved, // Action approval succeeded and ready to be queued.
  Queued, // Action queued for queueing duration and disapproval period begins.
  Expired, // block.timestamp is greater than Action's executionTime + expirationDelay.
  Executed // Action has executed successfully.
}

// File: src/LlamaExecutor.sol



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

/// @title Llama Executor
/// @author Llama (devsdosomething@llama.xyz)
/// @notice The exit point of a Llama instance. It calls the target contract during action execution.
contract LlamaExecutor {
  /// @dev Only callable by a Llama instance's core contract.
  error OnlyLlamaCore();

  /// @notice The core contract for this Llama instance.
  address public immutable LLAMA_CORE;

  /// @dev This contract is deployed from the core's `initialize` function.
  constructor() {
    LLAMA_CORE = msg.sender;
  }

  /// @notice Called by `executeAction` in the core contract to make the call described by the action.
  /// @dev Using a separate executor contract ensures `target` being delegatecalled cannot write to `LlamaCore`'s
  /// storage. By using a sole executor for calls and delegatecalls,
  /// a Llama instance is represented by one contract address.
  /// @param target The contract called when the action is executed.
  /// @param isScript A boolean that determines if the target is a script and should be delegatecalled.
  /// @param data Data to be called on the `target` when the action is executed.
  /// @return success A boolean that indicates if the call succeeded.
  /// @return result The data returned by the function being called.
  function execute(address target, bool isScript, bytes calldata data)
    external
    payable
    returns (bool success, bytes memory result)
  {
    if (msg.sender != LLAMA_CORE) revert OnlyLlamaCore();
    (success, result) = isScript ? target.delegatecall(data) : target.call{value: msg.value}(data);
  }
}

// File: src/LlamaPolicy.sol



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

import {Clones} from "@openzeppelin/proxy/Clones.sol";

import {LibString} from "@solady/utils/LibString.sol";

import {ILlamaPolicyMetadata} from "src/interfaces/ILlamaPolicyMetadata.sol";
import {PolicyholderCheckpoints} from "src/lib/PolicyholderCheckpoints.sol";
import {SupplyCheckpoints} from "src/lib/SupplyCheckpoints.sol";
import {ERC721NonTransferableMinimalProxy} from "src/lib/ERC721NonTransferableMinimalProxy.sol";
import {LlamaUtils} from "src/lib/LlamaUtils.sol";
import {LlamaPolicyConfig, PermissionData} from "src/lib/Structs.sol";
import {RoleDescription} from "src/lib/UDVTs.sol";
import {LlamaExecutor} from "src/LlamaExecutor.sol";

/// @title Llama Policy
/// @author Llama (devsdosomething@llama.xyz)
/// @notice An ERC721 contract where each token is non-transferable, functions as the respective policy for a given
/// policyholder and has roles assigned to `create`, `approve` and `disapprove` actions.
/// @dev The roles and permissions determine how the policyholder can interact with the Llama core contract.
contract LlamaPolicy is ERC721NonTransferableMinimalProxy {
  using PolicyholderCheckpoints for PolicyholderCheckpoints.History;
  using SupplyCheckpoints for SupplyCheckpoints.History;

  // ======================================
  // ======== Errors and Modifiers ========
  // ======================================

  /// @dev Roleholder cannot be set at the same timestamp as an action creation.
  error ActionCreationAtSameTimestamp();

  /// @dev Thrown when revoking a policy from an address without one
  /// @param userAddress The address of the possible policyholder.
  error AddressDoesNotHoldPolicy(address userAddress);

  /// @dev Cannot set "all holders" role.
  error AllHoldersRole();

  /// @dev Policy can only be initialized once.
  error AlreadyInitialized();

  /// @dev The indices would result in `Panic: Index Out of Bounds`.
  /// @dev Thrown when the `end` index is greater than array length or when the `start` index is greater than the `end`
  /// index.
  error InvalidIndices();

  /// @dev Thrown when the provided policyholder and role are not in the expected state for the function.
  error InvalidRoleHolderInput();

  /// @dev Policy tokens cannot be transferred.
  error NonTransferableToken();

  /// @dev Only callable by a Llama instance's executor.
  error OnlyLlama();

  /// @dev Only callable by the Llama Factory.
  error OnlyLlamaFactory();

  /// @dev Operations can only occur on initialized roles.
  error RoleNotInitialized(uint8 role);

  /// @dev Checks that the caller is the Llama executor and reverts if not.
  modifier onlyLlama() {
    if (msg.sender != llamaExecutor) revert OnlyLlama();
    _;
  }

  /// @dev Ensures that none of the ERC721 `transfer` and `approval` functions can be called, so that the policies are
  /// non-transferable.
  modifier nonTransferableToken() {
    _; // We put this ahead of the revert so we don't get an unreachable code warning.
    revert NonTransferableToken();
  }

  // ========================
  // ======== Events ========
  // ========================

  /// @dev Emitted when a policyholder is assigned a role.
  event RoleAssigned(address indexed policyholder, uint8 indexed role, uint64 expiration, uint96 quantity);

  /// @dev Emitted when a role is initialized with a description.
  event RoleInitialized(uint8 indexed role, RoleDescription description);

  /// @dev Emitted when a permission ID is assigned to a role.
  event RolePermissionAssigned(
    uint8 indexed role, bytes32 indexed permissionId, PermissionData permissionData, bool hasPermission
  );

  /// @dev Emitted when a new Llama policy metadata contract is set.
  event PolicyMetadataSet(
    ILlamaPolicyMetadata policyMetadata, ILlamaPolicyMetadata indexed policyMetadataLogic, bytes initializationData
  );

  /// @dev Emitted when an expired role is explicitly revoked from a policyholder.
  event ExpiredRoleRevoked(address indexed caller, address indexed policyholder, uint8 indexed role);

  // =================================================
  // ======== Constants and Storage Variables ========
  // =================================================

  /// @dev A special role used to reference all policyholders.
  uint8 internal constant ALL_HOLDERS_ROLE = 0;

  /// @dev At deployment, this role is given permission to call the `setRolePermission` function.
  /// However, this may change depending on how the Llama instance is configured. This is done to mitigate the chances
  /// of deploying a misconfigured Llama instance that is unusable. See the documentation for more info.
  uint8 internal constant BOOTSTRAP_ROLE = 1;

  /// @dev Tracks total supplies of a given role. There are two notions of total supply:
  ///   - The `numberOfHolders` is simply the number of policyholders that hold the role.
  ///   - The `totalQuantity` is the sum of the quantity of the role for each policyholder that
  ///     holds the role.
  /// Both versions of supply are tracked to enable different types of strategies.
  mapping(uint8 role => SupplyCheckpoints.History) internal roleSupplyCkpts;

  /// @dev Checkpoints a token ID's "balance" (quantity) of a given role. The quantity of the
  /// role is how much quantity the role-holder gets when approving/disapproving (regardless of
  /// strategy).
  mapping(uint256 tokenId => mapping(uint8 role => PolicyholderCheckpoints.History)) internal roleBalanceCkpts;

  /// @notice Returns `true` if the role can create actions with the given permission ID.
  mapping(uint8 role => mapping(bytes32 permissionId => bool hasPermission)) public canCreateAction;

  /// @notice The highest role ID that has been initialized.
  uint8 public numRoles;

  /// @notice The address of the `LlamaExecutor` of this instance.
  address public llamaExecutor;

  /// @notice The Llama policy metadata contract.
  ILlamaPolicyMetadata public llamaPolicyMetadata;

  // ======================================================
  // ======== Contract Creation and Initialization ========
  // ======================================================

  /// @dev This contract is deployed as a minimal proxy from the core's `initialize` function. The
  /// `_disableInitializers` locks the implementation (logic) contract, preventing any future initialization of it.
  constructor() {
    _disableInitializers();
  }

  /// @notice Initializes a new `LlamaPolicy` clone.
  /// @dev This function is called by the `initialize` function in the `LlamaCore` contract. The `initializer` modifier
  /// ensures that this function can be invoked at most once.
  /// @param _name The ERC-721 name of the policy NFT.
  /// @param config The struct that contains the configuration for this instance's policy.
  /// @param policyMetadataLogic The `LlamaPolicyMetadata` implementation (logic) contract.
  /// @param executor The instance's `LlamaExecutor`.
  /// @param bootstrapPermissionData The permission data that hashes to the permission ID that allows policyholders to
  /// change role permissions.
  function initialize(
    string memory _name,
    LlamaPolicyConfig calldata config,
    ILlamaPolicyMetadata policyMetadataLogic,
    address executor,
    PermissionData memory bootstrapPermissionData
  ) external initializer {
    __initializeERC721MinimalProxy(_name, string.concat("LL-", LibString.replace(LibString.upper(_name), " ", "-")));
    llamaExecutor = executor;

    // Initialize the roles.
    emit RoleInitialized(ALL_HOLDERS_ROLE, RoleDescription.wrap("All Holders"));
    for (uint256 i = 0; i < config.roleDescriptions.length; i = LlamaUtils.uncheckedIncrement(i)) {
      _initializeRole(config.roleDescriptions[i]);
    }

    // Assign the role holders.
    for (uint256 i = 0; i < config.roleHolders.length; i = LlamaUtils.uncheckedIncrement(i)) {
      _setRoleHolder(
        config.roleHolders[i].role,
        config.roleHolders[i].policyholder,
        config.roleHolders[i].quantity,
        config.roleHolders[i].expiration
      );
    }

    // Assign the role permissions.
    for (uint256 i = 0; i < config.rolePermissions.length; i = LlamaUtils.uncheckedIncrement(i)) {
      _setRolePermission(
        config.rolePermissions[i].role,
        config.rolePermissions[i].permissionData,
        config.rolePermissions[i].hasPermission
      );
    }

    // Must have assigned roles during initialization, otherwise the system cannot be used. However,
    // we do not check that roles were assigned "properly" as there is no single correct way, so
    // this is more of a sanity check, not a guarantee that the system will work after initialization.
    if (numRoles == 0 || getRoleSupplyAsNumberOfHolders(ALL_HOLDERS_ROLE) == 0) revert InvalidRoleHolderInput();

    // Gives holders of role ID 1 permission to change role permissions. This is required to reduce the chance that an
    // instance is deployed with an invalid configuration that results in the instance being unusable.
    _setRolePermission(BOOTSTRAP_ROLE, bootstrapPermissionData, true);

    _setAndInitializePolicyMetadata(policyMetadataLogic, abi.encode(config.color, config.logo));
  }

  // ===========================================
  // ======== External and Public Logic ========
  // ===========================================

  // -------- Role and Permission Management --------

  /// @notice Initializes the next unassigned role with the given `description`.
  /// @param description The description of the role to initialize.
  function initializeRole(RoleDescription description) external onlyLlama {
    _initializeRole(description);
  }

  /// @notice Assigns a role to a policyholder.
  /// @param role ID of the role to set (uint8 ensures onchain enumerability when burning policies).
  /// @param policyholder Policyholder to assign the role to.
  /// @param quantity Quantity of the role to assign to the policyholder, i.e. their (dis)approval quantity.
  /// @param expiration When the role expires.
  function setRoleHolder(uint8 role, address policyholder, uint96 quantity, uint64 expiration) external onlyLlama {
    _setRoleHolder(role, policyholder, quantity, expiration);
  }

  /// @notice Assigns a permission ID to a role.
  /// @param role ID of the role to assign permission to.
  /// @param permissionData The `(target, selector, strategy)` tuple that will be keccak256 hashed to generate the
  /// permission ID to assign or unassign to the role.
  /// @param hasPermission Whether to assign the permission or remove the permission.
  function setRolePermission(uint8 role, PermissionData memory permissionData, bool hasPermission) external onlyLlama {
    _setRolePermission(role, permissionData, hasPermission);
  }

  /// @notice Revokes a policyholder's expired role.
  /// @param role Role that has expired.
  /// @param policyholder Policyholder that held the role.
  /// @dev This function needs to be explicitly called to revoke expired roles by monitoring through offchain
  /// infrastructure, otherwise expired roles can continue to create actions (if they have the right permissions) and
  /// take part in the approval/disapproval process if the strategy allows it.
  function revokeExpiredRole(uint8 role, address policyholder) external {
    // Read the most recent checkpoint for the policyholder's role balance.
    if (!isRoleExpired(policyholder, role)) revert InvalidRoleHolderInput();
    _setRoleHolder(role, policyholder, 0, 0);
    emit ExpiredRoleRevoked(msg.sender, policyholder, role);
  }

  /// @notice Revokes all roles from the `policyholder` and burns their policy.
  /// @param policyholder Policyholder to revoke all roles from.
  function revokePolicy(address policyholder) external onlyLlama {
    if (balanceOf(policyholder) == 0) revert AddressDoesNotHoldPolicy(policyholder);
    // We start from i = 1 here because a value of zero is reserved for the "all holders" role, and
    // that will get removed automatically when the token is burned. Similarly, use we `<=` to make sure
    // the last role is also revoked.
    for (uint256 i = 1; i <= numRoles; i = LlamaUtils.uncheckedIncrement(i)) {
      if (hasRole(policyholder, uint8(i))) _setRoleHolder(uint8(i), policyholder, 0, 0);
    }
    _burn(policyholder);
  }

  /// @notice Updates the description of a role.
  /// @param role ID of the role to update.
  /// @param description New description of the role.
  function updateRoleDescription(uint8 role, RoleDescription description) external onlyLlama {
    if (role > numRoles) revert RoleNotInitialized(role);
    emit RoleInitialized(role, description);
  }

  // -------- Metadata --------

  /// @notice Sets the Llama policy metadata contract which contains the function body for `tokenURI()` and
  /// `contractURI()`.
  /// @dev This is handled by a separate contract to ensure contract size stays under 24kB.
  /// @param llamaPolicyMetadataLogic The logic contract address for the Llama policy metadata contract.
  /// @param config The configuration data used to initialize the Llama policy metadata logic contract.
  function setAndInitializePolicyMetadata(ILlamaPolicyMetadata llamaPolicyMetadataLogic, bytes memory config)
    external
    onlyLlama
  {
    _setAndInitializePolicyMetadata(llamaPolicyMetadataLogic, config);
  }

  // -------- Role and Permission Getters --------

  /// @notice Returns the latest quantity of the `role` for the given `policyholder`. The returned value is the
  /// quantity of the role when approving/disapproving (regardless of strategy).
  /// @param policyholder Policyholder to get the role quantity for.
  /// @param role ID of the role.
  /// @return The latest quantity of the role for the given policyholder.
  function getQuantity(address policyholder, uint8 role) external view returns (uint96) {
    uint256 tokenId = _tokenId(policyholder);
    return roleBalanceCkpts[tokenId][role].latest();
  }

  /// @notice Returns the past quantity of the `role` for the given `policyholder` at `timestamp`. The returned
  /// value is the quantity of the role when approving/disapproving (regardless of strategy).
  /// @param policyholder Policyholder to get the role quantity for.
  /// @param role ID of the role.
  /// @param timestamp Timestamp at which to get the quantity of the role for the given policyholder.
  /// @return The past quantity of the role for the given policyholder at `timestamp`.
  function getPastQuantity(address policyholder, uint8 role, uint256 timestamp) external view returns (uint96) {
    uint256 tokenId = _tokenId(policyholder);
    return roleBalanceCkpts[tokenId][role].getAtProbablyRecentTimestamp(timestamp);
  }

  /// @notice Returns the latest total number of role holders for given `role`.
  /// @param role ID of the role.
  /// @return numberOfHolders The latest total number of role holders for given `role`.
  function getRoleSupplyAsNumberOfHolders(uint8 role) public view returns (uint96 numberOfHolders) {
    (numberOfHolders,) = roleSupplyCkpts[role].latest();
  }

  /// @notice Returns the past total number of role holders for given `role` at `timestamp`.
  /// @param role ID of the role.
  /// @param timestamp Timestamp at which to get the past total number of role holders for given `role`.
  /// @return numberOfHolders The past total number of role holders for given `role` at `timestamp`.
  function getPastRoleSupplyAsNumberOfHolders(uint8 role, uint256 timestamp)
    external
    view
    returns (uint96 numberOfHolders)
  {
    (numberOfHolders,) = roleSupplyCkpts[role].getAtProbablyRecentTimestamp(timestamp);
  }

  /// @notice Returns the latest sum of quantity across all role holders for given `role`.
  /// @param role ID of the role.
  /// @return totalQuantity The latest sum of quantity across all role holders for given `role`.
  function getRoleSupplyAsQuantitySum(uint8 role) external view returns (uint96 totalQuantity) {
    (, totalQuantity) = roleSupplyCkpts[role].latest();
  }

  /// @notice Returns the sum of quantity across all role holders for given `role` at `timestamp`.
  /// @param role ID of the role.
  /// @param timestamp Timestamp at which to get the sum of quantity across all role holders for given `role`.
  /// @return totalQuantity The past sum of quantity across all role holders for given `role` at `timestamp`.
  function getPastRoleSupplyAsQuantitySum(uint8 role, uint256 timestamp) external view returns (uint96 totalQuantity) {
    (, totalQuantity) = roleSupplyCkpts[role].getAtProbablyRecentTimestamp(timestamp);
  }

  /// @notice Returns all policyholder checkpoints for the given `policyholder` and `role`.
  /// @param policyholder Policyholder to get the checkpoints for.
  /// @param role ID of the role.
  /// @return All policyholder checkpoints for the given `policyholder` and `role`.
  function roleBalanceCheckpoints(address policyholder, uint8 role)
    external
    view
    returns (PolicyholderCheckpoints.History memory)
  {
    uint256 tokenId = _tokenId(policyholder);
    return roleBalanceCkpts[tokenId][role];
  }

  /// @notice Returns all supply checkpoints for the given `role`.
  /// @param role ID of the role.
  /// @return All supply checkpoints for the given `role`.
  function roleSupplyCheckpoints(uint8 role) external view returns (SupplyCheckpoints.History memory) {
    return roleSupplyCkpts[role];
  }

  /// @notice Returns all policyholder checkpoints for the given policyholder and role between `start` and
  /// `end`, where `start` is inclusive and `end` is exclusive.
  /// @param policyholder Policyholder to get the checkpoints for.
  /// @param role Role held by policyholder to get the checkpoints for.
  /// @param start Start index of the checkpoints to get from their checkpoint history array. This index is inclusive.
  /// @param end End index of the checkpoints to get from their checkpoint history array. This index is exclusive.
  /// @return All policyholder checkpoints for the given policyholder and role between `start` and `end`.
  function roleBalanceCheckpoints(address policyholder, uint8 role, uint256 start, uint256 end)
    external
    view
    returns (PolicyholderCheckpoints.History memory)
  {
    if (start > end) revert InvalidIndices();
    uint256 checkpointsLength = roleBalanceCkpts[_tokenId(policyholder)][role]._checkpoints.length;
    if (end > checkpointsLength) revert InvalidIndices();

    uint256 tokenId = _tokenId(policyholder);
    uint256 sliceLength = end - start;
    PolicyholderCheckpoints.Checkpoint[] memory checkpoints = new PolicyholderCheckpoints.Checkpoint[](sliceLength);
    for (uint256 i = start; i < end; i = LlamaUtils.uncheckedIncrement(i)) {
      checkpoints[i - start] = roleBalanceCkpts[tokenId][role]._checkpoints[i];
    }
    return PolicyholderCheckpoints.History(checkpoints);
  }

  /// @notice Returns all supply checkpoints for the given role between `start` and
  /// `end`, where `start` is inclusive and `end` is exclusive.
  /// @param role Role held by policyholder to get the checkpoints for.
  /// @param start Start index of the checkpoints to get from their checkpoint history array. This index is inclusive.
  /// @param end End index of the checkpoints to get from their checkpoint history array. This index is exclusive.
  /// @return All supply checkpoints for the given role between `start` and `end`.
  function roleSupplyCheckpoints(uint8 role, uint256 start, uint256 end)
    external
    view
    returns (SupplyCheckpoints.History memory)
  {
    if (start > end) revert InvalidIndices();
    uint256 checkpointsLength = roleSupplyCkpts[role]._checkpoints.length;
    if (end > checkpointsLength) revert InvalidIndices();

    uint256 sliceLength = end - start;
    SupplyCheckpoints.Checkpoint[] memory checkpoints = new SupplyCheckpoints.Checkpoint[](sliceLength);
    for (uint256 i = start; i < end; i = LlamaUtils.uncheckedIncrement(i)) {
      checkpoints[i - start] = roleSupplyCkpts[role]._checkpoints[i];
    }
    return SupplyCheckpoints.History(checkpoints);
  }

  /// @notice Returns the number of policyholder checkpoints for the given `policyholder` and `role`.
  /// @dev Useful for knowing the max index when requesting a range of checkpoints in `roleBalanceCheckpoints`.
  /// @param policyholder Policyholder to get the number of checkpoints for.
  /// @param role ID of the role.
  /// @return The number of policyholder checkpoints for the given `policyholder` and `role`.
  function roleBalanceCheckpointsLength(address policyholder, uint8 role) external view returns (uint256) {
    uint256 tokenId = _tokenId(policyholder);
    return roleBalanceCkpts[tokenId][role]._checkpoints.length;
  }

  /// @notice Returns the number of supply checkpoints for the given `role`.
  /// @dev Useful for knowing the max index when requesting a range of checkpoints in `roleSupplyCheckpoints`.
  /// @param role ID of the role.
  /// @return The number of supply checkpoints for the given `role`.
  function roleSupplyCheckpointsLength(uint8 role) external view returns (uint256) {
    return roleSupplyCkpts[role]._checkpoints.length;
  }

  /// @notice Returns `true` if the `policyholder` has the `role`, `false` otherwise.
  /// @param policyholder Policyholder to check if they have the role.
  /// @param role ID of the role.
  /// @return `true` if the `policyholder` has the `role`, `false` otherwise.
  function hasRole(address policyholder, uint8 role) public view returns (bool) {
    uint96 quantity = roleBalanceCkpts[_tokenId(policyholder)][role].latest();
    return quantity > 0;
  }

  /// @notice Returns `true` if the `policyholder` has the `role` at `timestamp`, `false` otherwise.
  /// @param policyholder Policyholder to check if they have the role.
  /// @param role ID of the role.
  /// @param timestamp Timestamp to check if the role was held at.
  /// @return `true` if the `policyholder` has the `role` at `timestamp`, `false` otherwise.
  function hasRole(address policyholder, uint8 role, uint256 timestamp) external view returns (bool) {
    uint256 quantity = roleBalanceCkpts[_tokenId(policyholder)][role].getAtProbablyRecentTimestamp(timestamp);
    return quantity > 0;
  }

  /// @notice Returns `true` if the given `policyholder` has a given `permissionId` under the `role`,
  /// `false` otherwise.
  /// @param policyholder Policyholder to check if they have the permission under the role.
  /// @param role ID of the role.
  /// @param permissionId ID of the permission.
  /// @return `true` if the given `policyholder` has a given `permissionId` under the `role`, `false` otherwise.
  function hasPermissionId(address policyholder, uint8 role, bytes32 permissionId) external view returns (bool) {
    uint96 quantity = roleBalanceCkpts[_tokenId(policyholder)][role].latest();
    return quantity > 0 && canCreateAction[role][permissionId];
  }

  /// @notice Returns `true` if the `role` held by `policyholder` is expired, `false` otherwise.
  /// @param policyholder Policyholder to check if their role is expired.
  /// @param role ID of the role.
  /// @return `true` if the `role` held by `policyholder` is expired, `false` otherwise.
  function isRoleExpired(address policyholder, uint8 role) public view returns (bool) {
    (,, uint64 expiration, uint96 quantity) = roleBalanceCkpts[_tokenId(policyholder)][role].latestCheckpoint();
    return quantity > 0 && block.timestamp > expiration;
  }

  /// @notice Returns the expiration timestamp of the `role` held by `policyholder`.
  /// @param policyholder Policyholder to get the expiration timestamp of their role.
  /// @param role ID of the role.
  /// @return The expiration timestamp of the `role` held by `policyholder`.
  function roleExpiration(address policyholder, uint8 role) external view returns (uint64) {
    (,, uint64 expiration,) = roleBalanceCkpts[_tokenId(policyholder)][role].latestCheckpoint();
    return expiration;
  }

  /// @notice Returns the total number of policies in existence.
  /// @dev This is just an alias for convenience/familiarity.
  /// @return The total number of policies in existence.
  function totalSupply() external view returns (uint256) {
    return getRoleSupplyAsNumberOfHolders(ALL_HOLDERS_ROLE);
  }

  // -------- ERC-721 Getters --------

  /// @notice Returns the token URI for the given `tokenId` of this Llama instance.
  /// @param tokenId The ID of the policy token.
  /// @return The token URI for the given `tokenId` of this Llama instance.
  function tokenURI(uint256 tokenId) public view override returns (string memory) {
    ownerOf(tokenId); // ensure token exists, will revert with NOT_MINTED error if not
    return llamaPolicyMetadata.getTokenURI(name, llamaExecutor, tokenId);
  }

  /// @notice Returns a URI for the storefront-level metadata for your contract.
  /// @return The contract URI for the given Llama instance.
  function contractURI() public view returns (string memory) {
    return llamaPolicyMetadata.getContractURI(name, llamaExecutor);
  }

  // -------- ERC-721 Methods --------

  /// @dev overriding `transferFrom` to disable transfers
  function transferFrom(address, /* from */ address, /* to */ uint256 /* policyId */ )
    public
    pure
    override
    nonTransferableToken
  {}

  /// @dev overriding `safeTransferFrom` to disable transfers
  function safeTransferFrom(address, /* from */ address, /* to */ uint256 /* id */ )
    public
    pure
    override
    nonTransferableToken
  {}

  /// @dev overriding `safeTransferFrom` to disable transfers
  function safeTransferFrom(address, /* from */ address, /* to */ uint256, /* policyId */ bytes calldata /* data */ )
    public
    pure
    override
    nonTransferableToken
  {}

  /// @dev overriding `approve` to disable approvals
  function approve(address, /* spender */ uint256 /* id */ ) public pure override nonTransferableToken {}

  /// @dev overriding `approve` to disable approvals
  function setApprovalForAll(address, /* operator */ bool /* approved */ ) public pure override nonTransferableToken {}

  // ================================
  // ======== Internal Logic ========
  // ================================

  /// @dev Initializes the next unassigned role with the given `description`.
  function _initializeRole(RoleDescription description) internal {
    numRoles += 1;
    emit RoleInitialized(numRoles, description);
  }

  /// @dev Checks if the conditions are met for a `role` to be updated.
  function _assertValidRoleHolderUpdate(uint8 role, uint96 quantity, uint64 expiration) internal view {
    // Ensure role is initialized.
    if (role > numRoles) revert RoleNotInitialized(role);

    // Cannot set the ALL_HOLDERS_ROLE because this is handled in the _mint / _burn methods and can
    // create duplicate entries if set here.
    if (role == ALL_HOLDERS_ROLE) revert AllHoldersRole();

    // An expiration of zero is only allowed if the role is being removed. Roles are removed when
    // the quantity is zero. In other words, the relationships that are required between the role
    // quantity and expiration fields are:
    //   - quantity > 0 && expiration > block.timestamp: This means you are adding a role
    //   - quantity == 0 && expiration == 0: This means you are removing a role
    bool case1 = quantity > 0 && expiration > block.timestamp;
    bool case2 = quantity == 0 && expiration == 0;
    if (!(case1 || case2)) revert InvalidRoleHolderInput();
  }

  /// @dev Sets the `role` for the given `policyholder` to the given `quantity` and `expiration`.
  function _setRoleHolder(uint8 role, address policyholder, uint96 quantity, uint64 expiration) internal {
    _assertValidRoleHolderUpdate(role, quantity, expiration);

    // Save off whether or not the policyholder has a nonzero quantity of this role. This is used
    // below when updating the total supply of the role. The policy contract has an invariant that
    // even when a role is expired, i.e. `block.timestamp > expiration`, that role is still active
    // until explicitly revoked with `revokeExpiredRole`. Based on the assertions above for
    // determining valid inputs to this method, this means we know if a user had a role simply by
    // checking if the quantity is nonzero, and we don't need to check the expiration when setting
    // the `hadRole` and `willHaveRole` variables.
    uint256 tokenId = _tokenId(policyholder);
    uint96 initialQuantity = roleBalanceCkpts[tokenId][role].latest();
    bool hadRole = initialQuantity > 0;
    bool willHaveRole = quantity > 0;

    // Now we update the policyholder's role balance checkpoint.
    roleBalanceCkpts[tokenId][role].push(willHaveRole ? quantity : 0, expiration);

    // If they don't hold a policy, we mint one for them. This means that even if you use 0 quantity
    // and 0 expiration, a policy is still minted even though they hold no roles. This is because
    // they do hold the ALL_HOLDERS_ROLE simply by having a policy, so we allow this.
    if (balanceOf(policyholder) == 0) _mint(policyholder);

    // Lastly we update the total supply of the role. If the expiration is zero, it means the role
    // was removed. Determining how to update total supply requires knowing if the policyholder currently
    // has a nonzero quantity of this role. This is strictly a quantity check and ignores the
    // expiration because this is used to determine whether or not to update the total supply.
    uint96 quantityDiff;
    unchecked {
      // Safety: Can never underflow due to ternary operator check.
      quantityDiff = initialQuantity > quantity ? initialQuantity - quantity : quantity - initialQuantity;
    }

    (uint96 numberOfHolders, uint96 totalQuantity) = roleSupplyCkpts[role].latest();

    if (hadRole && !willHaveRole) {
      roleSupplyCkpts[role].push(numberOfHolders - 1, totalQuantity - quantityDiff);
    } else if (!hadRole && willHaveRole) {
      roleSupplyCkpts[role].push(numberOfHolders + 1, totalQuantity + quantityDiff);
    } else if (hadRole && willHaveRole && initialQuantity > quantity) {
      roleSupplyCkpts[role].push(numberOfHolders, totalQuantity - quantityDiff);
    } else if (hadRole && willHaveRole && initialQuantity < quantity) {
      roleSupplyCkpts[role].push(numberOfHolders, totalQuantity + quantityDiff);
    } else {
      // There are two ways to reach this branch, both of which are no-ops:
      //   1. `hadRole` and `willHaveRole` are both false. We allow this without reverting so you can give
      //      someone a policy with only the `ALL_HOLDERS_ROLE` by passing in any other role that won't be set.
      //   2. `hadRole` and `willHaveRole` are both true, and `initialQuantity == quantity`. We allow this without
      //      reverting so that you can update the expiration of an existing role.
    }
    emit RoleAssigned(policyholder, role, expiration, quantity);
  }

  /// @dev Sets a role's permission along with whether that permission is valid or not.
  function _setRolePermission(uint8 role, PermissionData memory permissionData, bool hasPermission) internal {
    if (role > numRoles) revert RoleNotInitialized(role);
    bytes32 permissionId = LlamaUtils.computePermissionId(permissionData);
    canCreateAction[role][permissionId] = hasPermission;
    emit RolePermissionAssigned(role, permissionId, permissionData, hasPermission);
  }

  /// @dev Mints a policyholder's policy.
  function _mint(address policyholder) internal {
    uint256 tokenId = _tokenId(policyholder);
    ERC721NonTransferableMinimalProxy._mint(policyholder, tokenId);

    (uint96 numberOfHolders, uint96 totalQuantity) = roleSupplyCkpts[ALL_HOLDERS_ROLE].latest();
    unchecked {
      // Safety: Can never overflow a uint96 by incrementing.
      roleSupplyCkpts[ALL_HOLDERS_ROLE].push(numberOfHolders + 1, totalQuantity + 1);
    }

    roleBalanceCkpts[tokenId][ALL_HOLDERS_ROLE].push(1, type(uint64).max);
    emit RoleAssigned(policyholder, ALL_HOLDERS_ROLE, type(uint64).max, 1);
  }

  /// @dev Burns a policyholder's policy.
  function _burn(address policyholder) internal {
    uint256 tokenId = _tokenId(policyholder);
    ERC721NonTransferableMinimalProxy._burn(tokenId);

    (uint96 numberOfHolders, uint96 totalQuantity) = roleSupplyCkpts[ALL_HOLDERS_ROLE].latest();
    unchecked {
      // Safety: Can never underflow, since we only burn tokens that currently exist.
      roleSupplyCkpts[ALL_HOLDERS_ROLE].push(numberOfHolders - 1, totalQuantity - 1);
    }

    roleBalanceCkpts[tokenId][ALL_HOLDERS_ROLE].push(0, 0);
    emit RoleAssigned(policyholder, ALL_HOLDERS_ROLE, 0, 0);
  }

  /// @dev Sets the Llama policy metadata contract.
  function _setAndInitializePolicyMetadata(ILlamaPolicyMetadata llamaPolicyMetadataLogic, bytes memory config) internal {
    llamaPolicyMetadata =
      ILlamaPolicyMetadata(Clones.cloneDeterministic(address(llamaPolicyMetadataLogic), keccak256(config)));
    llamaPolicyMetadata.initialize(config);
    emit PolicyMetadataSet(llamaPolicyMetadata, llamaPolicyMetadataLogic, config);
  }

  /// @dev Returns the token ID for a `policyholder`.
  function _tokenId(address policyholder) internal pure returns (uint256) {
    return uint256(uint160(policyholder));
  }
}

// File: lib/openzeppelin-contracts/contracts/token/ERC1155/IERC1155Receiver.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.5.0) (token/ERC1155/IERC1155Receiver.sol)

pragma solidity ^0.8.0;

import "../../utils/introspection/IERC165.sol";

/**
 * @dev _Available since v3.1._
 */
interface IERC1155Receiver is IERC165 {
    /**
     * @dev Handles the receipt of a single ERC1155 token type. This function is
     * called at the end of a `safeTransferFrom` after the balance has been updated.
     *
     * NOTE: To accept the transfer, this must return
     * `bytes4(keccak256("onERC1155Received(address,address,uint256,uint256,bytes)"))`
     * (i.e. 0xf23a6e61, or its own function selector).
     *
     * @param operator The address which initiated the transfer (i.e. msg.sender)
     * @param from The address which previously owned the token
     * @param id The ID of the token being transferred
     * @param value The amount of tokens being transferred
     * @param data Additional data with no specified format
     * @return `bytes4(keccak256("onERC1155Received(address,address,uint256,uint256,bytes)"))` if transfer is allowed
     */
    function onERC1155Received(
        address operator,
        address from,
        uint256 id,
        uint256 value,
        bytes calldata data
    ) external returns (bytes4);

    /**
     * @dev Handles the receipt of a multiple ERC1155 token types. This function
     * is called at the end of a `safeBatchTransferFrom` after the balances have
     * been updated.
     *
     * NOTE: To accept the transfer(s), this must return
     * `bytes4(keccak256("onERC1155BatchReceived(address,address,uint256[],uint256[],bytes)"))`
     * (i.e. 0xbc197c81, or its own function selector).
     *
     * @param operator The address which initiated the batch transfer (i.e. msg.sender)
     * @param from The address which previously owned the token
     * @param ids An array containing ids of each token being transferred (order and length must match values array)
     * @param values An array containing amounts of each token being transferred (order and length must match ids array)
     * @param data Additional data with no specified format
     * @return `bytes4(keccak256("onERC1155BatchReceived(address,address,uint256[],uint256[],bytes)"))` if transfer is allowed
     */
    function onERC1155BatchReceived(
        address operator,
        address from,
        uint256[] calldata ids,
        uint256[] calldata values,
        bytes calldata data
    ) external returns (bytes4);
}

// File: lib/openzeppelin-contracts/contracts/utils/introspection/ERC165.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/introspection/ERC165.sol)

pragma solidity ^0.8.0;

import "./IERC165.sol";

/**
 * @dev Implementation of the {IERC165} interface.
 *
 * Contracts that want to implement ERC165 should inherit from this contract and override {supportsInterface} to check
 * for the additional interface id that will be supported. For example:
 *
 * ```solidity
 * function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
 *     return interfaceId == type(MyInterface).interfaceId || super.supportsInterface(interfaceId);
 * }
 * ```
 *
 * Alternatively, {ERC165Storage} provides an easier to use but more expensive implementation.
 */
abstract contract ERC165 is IERC165 {
    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        return interfaceId == type(IERC165).interfaceId;
    }
}

// File: src/lib/UDVTs.sol



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

// @dev We use this UDVT for stronger typing of the Role Description.
type RoleDescription is bytes32;

// File: lib/solady/src/utils/LibString.sol



// 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)
library LibString {
    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                        CUSTOM ERRORS                       */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

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

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                         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 {
                // Store the function selector of `HexLengthInsufficient()`.
                mstore(0x00, 0x2194895a)
                // Revert with (offset, size).
                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 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 toHexStringChecksumed(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, and(add(o, 31), not(31))) // 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 }
                }
            }
        }
    }

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

    // For performance and bytecode compactness, all indices of the following operations
    // are byte (ASCII) offsets, not UTF character offsets.

    /// @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, 32)) { h := keccak256(search, searchLength) }
                let m := shl(3, sub(32, and(searchLength, 31)))
                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)
            // Zeroize the slot after the string.
            let last := add(add(result, 0x20), k)
            mstore(last, 0)
            // Allocate memory for the length and the bytes,
            // rounded up to a multiple of 32.
            mstore(0x40, and(add(last, 31), not(31)))
            // Store the length of the result.
            mstore(result, k)
        }
    }

    /// @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(32, and(searchLength, 31)))
                let s := mload(add(search, 0x20))

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

                if iszero(lt(searchLength, 32)) {
                    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 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 }
                }
                // Zeroize the slot after the string.
                mstore(output, 0)
                // Store the length.
                let resultLength := sub(output, add(result, 0x20))
                mstore(result, resultLength)
                // Allocate memory for the length and the bytes,
                // rounded up to a multiple of 32.
                mstore(0x40, add(result, and(add(resultLength, 63), not(31))))
            }
        }
    }

    /// @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(31)
                // Copy the `subject` one word at a time, backwards.
                for { let o := and(add(resultLength, 31), 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, 63), 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, 32)) { h := keccak256(search, searchLength) }
                let m := shl(3, sub(32, and(searchLength, 31)))
                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(31)
            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, 31), 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, 63), 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(31)
            result := mload(0x40)
            let aLength := mload(a)
            // Copy `a` one word at a time, backwards.
            for { let o := and(add(mload(a), 32), 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, mload(a))
            // Copy `b` one word at a time, backwards.
            for { let o := and(add(bLength, 32), 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, 31), w))
        }
    }

    /// @dev Returns a copy of the string in either lowercase or UPPERCASE.
    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)), 67108863)
                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 }
                }
                // Restore the result.
                result := mload(0x40)
                // Stores the string length.
                mstore(result, length)
                // Zeroize the slot after the string.
                let last := add(add(result, 0x20), length)
                mstore(last, 0)
                // Allocate memory for the length and the bytes,
                // rounded up to a multiple of 32.
                mstore(0x40, and(add(last, 31), not(31)))
            }
        }
    }

    /// @dev Returns a lowercased copy of the string.
    function lower(string memory subject) internal pure returns (string memory result) {
        result = toCase(subject, false);
    }

    /// @dev Returns an UPPERCASED copy of the string.
    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 {
            for {
                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))
            } 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, 31)))
                result := add(result, shr(5, t))
            }
            let last := result
            // Zeroize the slot after the string.
            mstore(last, 0)
            // Restore the result to the start of the free memory.
            result := mload(0x40)
            // Store the length of the result.
            mstore(result, sub(last, add(result, 0x20)))
            // Allocate memory for the length and the bytes,
            // rounded up to a multiple of 32.
            mstore(0x40, and(add(last, 31), not(31)))
        }
    }

    /// @dev Escapes the string to be used within double-quotes in a JSON.
    function escapeJSON(string memory s) internal pure returns (string memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            for {
                let end := add(s, mload(s))
                result := add(mload(0x40), 0x20)
                // 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))
            } 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)
            }
            let last := result
            // Zeroize the slot after the string.
            mstore(last, 0)
            // Restore the result to the start of the free memory.
            result := mload(0x40)
            // Store the length of the result.
            mstore(result, sub(last, add(result, 0x20)))
            // Allocate memory for the length and the bytes,
            // rounded up to a multiple of 32.
            mstore(0x40, and(add(last, 31), not(31)))
        }
    }

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

    /// @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 behaviour 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 behaviour 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)
        }
    }
}

// File: src/lib/PolicyholderCheckpoints.sol



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

import {LlamaUtils} from "src/lib/LlamaUtils.sol";

/**
 * @dev This library defines the `History` struct, for checkpointing values as they change at different points in
 * time, and later looking up past values by block timestamp.
 *
 * To create a history of checkpoints define a variable type `PolicyholderCheckpoints.History` in your contract, and store a new
 * checkpoint for the current transaction timestamp using the {push} function.
 *
 * @dev This was created by modifying then running the OpenZeppelin `Checkpoints.js` script, which generated a version
 * of this library that uses a 64 bit `timestamp` and 96 bit `quantity` field in the `Checkpoint` struct. The struct
 * was then modified to add a 64 bit `expiration` field. For simplicity, safe cast and math methods were inlined from
 * the OpenZeppelin versions at the same commit. We disable forge-fmt for this file to simplify diffing against the
 * original OpenZeppelin version: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/d00acef4059807535af0bd0dd0ddf619747a044b/contracts/utils/Checkpoints.sol
 */
library PolicyholderCheckpoints {
    struct History {
        Checkpoint[] _checkpoints;
    }

    struct Checkpoint {
        uint64 timestamp;
        uint64 expiration;
        uint96 quantity;
    }

    /**
     * @dev Returns the quantity at a given block timestamp. If a checkpoint is not available at that time, the closest
     * one before it is returned, or zero otherwise. Similar to {upperLookup} but optimized for the case when the
     * searched checkpoint is probably "recent", defined as being among the last sqrt(N) checkpoints where N is the
     * timestamp of checkpoints.
     */
    function getAtProbablyRecentTimestamp(History storage self, uint256 timestamp) internal view returns (uint96) {
        require(timestamp < block.timestamp, "PolicyholderCheckpoints: timestamp is not in the past");
        uint64 _timestamp = LlamaUtils.toUint64(timestamp);

        uint256 len = self._checkpoints.length;

        uint256 low = 0;
        uint256 high = len;

        if (len > 5) {
            uint256 mid = len - sqrt(len);
            if (_timestamp < _unsafeAccess(self._checkpoints, mid).timestamp) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        uint256 pos = _upperBinaryLookup(self._checkpoints, _timestamp, low, high);

        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1).quantity;
    }

    /**
     * @dev Pushes a `quantity` and `expiration` onto a History so that it is stored as the checkpoint for the current
     * `timestamp`.
     *
     * Returns previous quantity and new quantity.
     *
     * @dev Note that the order of the `expiration` and `quantity` parameters is reversed from the ordering used
     * everywhere else in this file. The struct and other methods have the order as `(expiration, quantity)` but this
     * method has it as `(quantity, expiration)`. As a result, use caution when editing this method to avoid
     * accidentally introducing a bug or breaking change.
     */
    function push(History storage self, uint256 quantity, uint256 expiration) internal returns (uint96, uint96) {
        return _insert(self._checkpoints, LlamaUtils.toUint64(block.timestamp), LlamaUtils.toUint64(expiration), LlamaUtils.toUint96(quantity));
    }

    /**
     * @dev Returns the quantity in the most recent checkpoint, or zero if there are no checkpoints.
     */
    function latest(History storage self) internal view returns (uint96) {
        uint256 pos = self._checkpoints.length;
        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1).quantity;
    }

    /**
     * @dev Returns whether there is a checkpoint in the structure (i.e. it is not empty), and if so the timestamp and
     * quantity in the most recent checkpoint.
     */
    function latestCheckpoint(History storage self)
        internal
        view
        returns (
            bool exists,
            uint64 timestamp,
            uint64 expiration,
            uint96 quantity
        )
    {
        uint256 pos = self._checkpoints.length;
        if (pos == 0) {
            return (false, 0, 0, 0);
        } else {
            Checkpoint memory ckpt = _unsafeAccess(self._checkpoints, pos - 1);
            return (true, ckpt.timestamp, ckpt.expiration, ckpt.quantity);
        }
    }

    /**
     * @dev Returns the number of checkpoints.
     */
    function length(History storage self) internal view returns (uint256) {
        return self._checkpoints.length;
    }

    /**
     * @dev Pushes a (`timestamp`, `expiration`, `quantity`) pair into an ordered list of checkpoints, either by inserting a new
     * checkpoint, or by updating the last one.
     */
    function _insert(
        Checkpoint[] storage self,
        uint64 timestamp,
        uint64 expiration,
        uint96 quantity
    ) private returns (uint96, uint96) {
        uint256 pos = self.length;

        if (pos > 0) {
            // Copying to memory is important here.
            Checkpoint memory last = _unsafeAccess(self, pos - 1);

            // Checkpoints timestamps must be increasing.
            require(last.timestamp <= timestamp, "Role Checkpoint: invalid timestamp");

            // Update or push new checkpoint
            if (last.timestamp == timestamp) {
                Checkpoint storage ckpt = _unsafeAccess(self, pos - 1);
                ckpt.quantity = quantity;
                ckpt.expiration = expiration;
            } else {
                self.push(Checkpoint({timestamp: timestamp, expiration: expiration, quantity: quantity}));
            }
            return (last.quantity, quantity);
        } else {
            self.push(Checkpoint({timestamp: timestamp, expiration: expiration, quantity: quantity}));
            return (0, quantity);
        }
    }

    /**
     * @dev Return the index of the oldest checkpoint whose timestamp is greater than the search timestamp, or `high`
     * if there is none. `low` and `high` define a section where to do the search, with inclusive `low` and exclusive
     * `high`.
     *
     * WARNING: `high` should not be greater than the array's length.
     */
    function _upperBinaryLookup(
        Checkpoint[] storage self,
        uint64 timestamp,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        while (low < high) {
            uint256 mid = average(low, high);
            if (_unsafeAccess(self, mid).timestamp > timestamp) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return high;
    }

    /**
     * @dev Return the index of the oldest checkpoint whose timestamp is greater or equal than the search timestamp, or
     * `high` if there is none. `low` and `high` define a section where to do the search, with inclusive `low` and
     * exclusive `high`.
     *
     * WARNING: `high` should not be greater than the array's length.
     */
    function _lowerBinaryLookup(
        Checkpoint[] storage self,
        uint64 timestamp,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        while (low < high) {
            uint256 mid = average(low, high);
            if (_unsafeAccess(self, mid).timestamp < timestamp) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return high;
    }

    function _unsafeAccess(Checkpoint[] storage self, uint256 pos)
        private
        pure
        returns (Checkpoint storage result)
    {
        assembly {
            mstore(0, self.slot)
            result.slot := add(keccak256(0, 0x20), pos)
        }
    }

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

    /**
     * @dev This was copied from Solmate v7 https://github.com/transmissions11/solmate/blob/e8f96f25d48fe702117ce76c79228ca4f20206cb/src/utils/FixedPointMathLib.sol
     * @notice The math utils in solmate v7 were reviewed/audited by spearbit as part of the art gobblers audit, and are more efficient than the v6 versions.
     */
    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))
        }
    }
}

// File: src/lib/SupplyCheckpoints.sol



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

import {LlamaUtils} from "src/lib/LlamaUtils.sol";

/**
 * @dev This library defines the `History` struct, for checkpointing values as they change at different points in
 * time, and later looking up past values by block timestamp.
 *
 * To create a history of checkpoints define a variable type `SupplyCheckpoints.History` in your contract, and store a
 * new checkpoint for the current transaction timestamp using the {push} function.
 *
 * @dev This was created by modifying then running the OpenZeppelin `Checkpoints.js` script, which generated a version
 * of this library that uses a 64 bit `timestamp` and 96 bit `quantity` field in the `Checkpoint` struct. The struct
 * was then modified to work with the below `Checkpoint` struct. For simplicity, safe cast and math methods were inlined
 * from the OpenZeppelin versions at the same commit. We disable forge-fmt for this file to simplify diffing against the
 * original OpenZeppelin version: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/d00acef4059807535af0bd0dd0ddf619747a044b/contracts/utils/Checkpoints.sol
 */
library SupplyCheckpoints {
    struct History {
        Checkpoint[] _checkpoints;
    }

    struct Checkpoint {
        uint64 timestamp;
        uint96 numberOfHolders;
        uint96 totalQuantity;
    }

    /**
     * @dev Returns the supply quantities at a given block timestamp. If a checkpoint is not available at that time, the closest
     * one before it is returned, or zero otherwise. Similar to {upperLookup} but optimized for the case when the
     * searched checkpoint is probably "recent", defined as being among the last sqrt(N) checkpoints where N is the
     * timestamp of checkpoints.
     */
    function getAtProbablyRecentTimestamp(History storage self, uint256 timestamp)
      internal
      view
      returns (uint96 numberOfHolders, uint96 totalQuantity)
    {
        require(timestamp < block.timestamp, "SupplyCheckpoints: timestamp is not in the past");
        uint64 _timestamp = LlamaUtils.toUint64(timestamp);

        uint256 len = self._checkpoints.length;

        uint256 low = 0;
        uint256 high = len;

        if (len > 5) {
            uint256 mid = len - sqrt(len);
            if (_timestamp < _unsafeAccess(self._checkpoints, mid).timestamp) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        uint256 pos = _upperBinaryLookup(self._checkpoints, _timestamp, low, high);

        return pos == 0 ? (0, 0) : _unsafeSupplyAccess(self._checkpoints, pos - 1);
    }

    /**
     * @dev Pushes the `numberOfHolders` and `totalQuantity` supplies onto a History so that it is stored as the
     * checkpoint for the current `timestamp`.
     *
     * For simplicity, this method does not return anything, since the return values are not needed by Llama.
     */
    function push(History storage self, uint256 numberOfHolders, uint256 totalQuantity) internal {
        _insert(self._checkpoints, LlamaUtils.toUint64(block.timestamp), LlamaUtils.toUint96(numberOfHolders), LlamaUtils.toUint96(totalQuantity));
    }

    /**
     * @dev Returns the supplies in the most recent checkpoint, or zeros if there are no checkpoints.
     */
    function latest(History storage self) internal view returns (uint96 numberOfHolders, uint96 totalQuantity) {
        uint256 pos = self._checkpoints.length;
        return pos == 0 ? (0, 0) : _unsafeSupplyAccess(self._checkpoints, pos - 1);
    }

    /**
     * @dev Returns whether there is a checkpoint in the structure (i.e. it is not empty), and if so the timestamp and
     * supplies in the most recent checkpoint.
     */
    function latestCheckpoint(History storage self)
        internal
        view
        returns (
            bool exists,
            uint64 timestamp,
            uint96 numberOfHolders,
            uint96 totalQuantity
        )
    {
        uint256 pos = self._checkpoints.length;
        if (pos == 0) {
            return (false, 0, 0, 0);
        } else {
            Checkpoint memory ckpt = _unsafeAccess(self._checkpoints, pos - 1);
            return (true, ckpt.timestamp, ckpt.numberOfHolders, ckpt.totalQuantity);
        }
    }

    /**
     * @dev Returns the number of checkpoints.
     */
    function length(History storage self) internal view returns (uint256) {
        return self._checkpoints.length;
    }

    /**
     * @dev Pushes a (`timestamp`, `numberOfHolders`, `totalQuantity`) pair into an ordered list of checkpoints, either
     * by inserting a new checkpoint, or by updating the last one.
     *
     * For simplicity, this method does not return anything, since the return values are not needed by Llama.
     */
    function _insert(
        Checkpoint[] storage self,
        uint64 timestamp,
        uint96 numberOfHolders,
        uint96 totalQuantity
    ) private {
        uint256 pos = self.length;

        if (pos > 0) {
            // Copying to memory is important here.
            Checkpoint memory last = _unsafeAccess(self, pos - 1);

            // Checkpoints timestamps must be increasing.
            require(last.timestamp <= timestamp, "Supply Checkpoint: invalid timestamp");

            // Update or push new checkpoint
            if (last.timestamp == timestamp) {
                Checkpoint storage ckpt = _unsafeAccess(self, pos - 1);
                ckpt.numberOfHolders = numberOfHolders;
                ckpt.totalQuantity = totalQuantity;
            } else {
                self.push(Checkpoint({timestamp: timestamp, numberOfHolders: numberOfHolders, totalQuantity: totalQuantity}));
            }
        } else {
            self.push(Checkpoint({timestamp: timestamp, numberOfHolders: numberOfHolders, totalQuantity: totalQuantity}));
        }
    }

    /**
     * @dev Return the index of the oldest checkpoint whose timestamp is greater than the search timestamp, or `high`
     * if there is none. `low` and `high` define a section where to do the search, with inclusive `low` and exclusive
     * `high`.
     *
     * WARNING: `high` should not be greater than the array's length.
     */
    function _upperBinaryLookup(
        Checkpoint[] storage self,
        uint64 timestamp,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        while (low < high) {
            uint256 mid = average(low, high);
            if (_unsafeAccess(self, mid).timestamp > timestamp) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return high;
    }

    /**
     * @dev Return the index of the oldest checkpoint whose timestamp is greater or equal than the search timestamp, or
     * `high` if there is none. `low` and `high` define a section where to do the search, with inclusive `low` and
     * exclusive `high`.
     *
     * WARNING: `high` should not be greater than the array's length.
     */
    function _lowerBinaryLookup(
        Checkpoint[] storage self,
        uint64 timestamp,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        while (low < high) {
            uint256 mid = average(low, high);
            if (_unsafeAccess(self, mid).timestamp < timestamp) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return high;
    }

    function _unsafeAccess(Checkpoint[] storage self, uint256 pos)
        private
        pure
        returns (Checkpoint storage result)
    {
        assembly {
            mstore(0, self.slot)
            result.slot := add(keccak256(0, 0x20), pos)
        }
    }

    function _unsafeSupplyAccess(Checkpoint[] storage self, uint256 pos)
        private
        view
        returns (uint96 numberOfHolders, uint96 totalQuantity)
    {
        Checkpoint storage result;
        assembly {
            mstore(0, self.slot)
            result.slot := add(keccak256(0, 0x20), pos)
        }
        numberOfHolders = result.numberOfHolders;
        totalQuantity = result.totalQuantity;
    }

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

    /**
     * @dev This was copied from Solmate v7 https://github.com/transmissions11/solmate/blob/e8f96f25d48fe702117ce76c79228ca4f20206cb/src/utils/FixedPointMathLib.sol
     * @notice The math utils in solmate v7 were reviewed/audited by spearbit as part of the art gobblers audit, and are more efficient than the v6 versions.
     */
    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))
        }
    }
}

// File: src/lib/ERC721NonTransferableMinimalProxy.sol



// SPDX-License-Identifier: AGPL-3.0-only
// forgefmt: disable-start
pragma solidity ^0.8.0;

import {Initializable} from "@openzeppelin/proxy/utils/Initializable.sol";

/// @title ERC721 Non-Transferable Minimal Proxy
/// @notice This contract is a modified version of Solmate's ERC721 contract
/// @notice Modern, minimalist, and gas efficient ERC-721 implementation as a minimal proxy.
/// @author Solmate / Llama (https://github.com/transmissions11/solmate/blob/34d20fc027fe8d50da71428687024a29dc01748b/src/tokens/ERC721.sol)
abstract contract ERC721NonTransferableMinimalProxy is Initializable {
  /*//////////////////////////////////////////////////////////////
                                 EVENTS
    //////////////////////////////////////////////////////////////*/

  event Transfer(address indexed from, address indexed to, uint256 indexed id);

  event Approval(address indexed owner, address indexed spender, uint256 indexed id);

  event ApprovalForAll(address indexed owner, address indexed operator, bool approved);

  /*//////////////////////////////////////////////////////////////
                         METADATA STORAGE/LOGIC
    //////////////////////////////////////////////////////////////*/

  string public name;

  string public symbol;

  function tokenURI(uint256 id) public view virtual returns (string memory);

  /*//////////////////////////////////////////////////////////////
                      ERC721 BALANCE/OWNER STORAGE
    //////////////////////////////////////////////////////////////*/

  mapping(uint256 => address) internal _ownerOf;

  mapping(address => uint256) internal _balanceOf;

  function ownerOf(uint256 id) public view virtual returns (address owner) {
    require((owner = _ownerOf[id]) != address(0), "NOT_MINTED");
  }

  function balanceOf(address owner) public view virtual returns (uint256) {
    require(owner != address(0), "ZERO_ADDRESS");

    return _balanceOf[owner];
  }

  /*//////////////////////////////////////////////////////////////
                         ERC721 APPROVAL STORAGE
    //////////////////////////////////////////////////////////////*/

  mapping(uint256 => address) public getApproved;

  mapping(address => mapping(address => bool)) public isApprovedForAll;

  /*//////////////////////////////////////////////////////////////
                               CONSTRUCTOR
    //////////////////////////////////////////////////////////////*/

  function __initializeERC721MinimalProxy (string memory _name, string memory _symbol) internal {
    name = _name;
    symbol = _symbol;
  }

  /*//////////////////////////////////////////////////////////////
                              ERC721 LOGIC
    //////////////////////////////////////////////////////////////*/

  function approve(address spender, uint256 id) public virtual {
    address owner = _ownerOf[id];

    require(msg.sender == owner || isApprovedForAll[owner][msg.sender], "NOT_AUTHORIZED");

    getApproved[id] = spender;

    emit Approval(owner, spender, id);
  }

  function setApprovalForAll(address operator, bool approved) public virtual {
    isApprovedForAll[msg.sender][operator] = approved;

    emit ApprovalForAll(msg.sender, operator, approved);
  }

  function transferFrom(address from, address to, uint256 id) public virtual {
    require(from == _ownerOf[id], "WRONG_FROM");

    require(to != address(0), "INVALID_RECIPIENT");

    require(msg.sender == from || isApprovedForAll[from][msg.sender] || msg.sender == getApproved[id], "NOT_AUTHORIZED");

    // Underflow of the sender's balance is impossible because we check for
    // ownership above and the recipient's balance can't realistically overflow.
    unchecked {
      _balanceOf[from]--;

      _balanceOf[to]++;
    }

    _ownerOf[id] = to;

    delete getApproved[id];

    emit Transfer(from, to, id);
  }

  function safeTransferFrom(address from, address to, uint256 id) public virtual;

  function safeTransferFrom(address from, address to, uint256 id, bytes calldata data) public virtual;

  /*//////////////////////////////////////////////////////////////
                              ERC165 LOGIC
    //////////////////////////////////////////////////////////////*/

  function supportsInterface(bytes4 interfaceId) public view virtual returns (bool) {
    return interfaceId == 0x01ffc9a7 // ERC165 Interface ID for ERC165
      || interfaceId == 0x80ac58cd // ERC165 Interface ID for ERC721
      || interfaceId == 0x5b5e139f; // ERC165 Interface ID for ERC721Metadata
  }

  /*//////////////////////////////////////////////////////////////
                        INTERNAL MINT/BURN LOGIC
    //////////////////////////////////////////////////////////////*/

  function _mint(address to, uint256 id) internal virtual {
    require(to != address(0), "INVALID_RECIPIENT");

    require(_ownerOf[id] == address(0), "ALREADY_MINTED");

    // Counter overflow is incredibly unrealistic.
    unchecked {
      _balanceOf[to]++;
    }

    _ownerOf[id] = to;

    emit Transfer(address(0), to, id);
  }

  function _burn(uint256 id) internal virtual {
    address owner = _ownerOf[id];

    require(owner != address(0), "NOT_MINTED");

    // Ownership check above ensures no underflow.
    unchecked {
      _balanceOf[owner]--;
    }

    delete _ownerOf[id];

    delete getApproved[id];

    emit Transfer(owner, address(0), id);
  }

  /*//////////////////////////////////////////////////////////////
                        INTERNAL SAFE MINT LOGIC
    //////////////////////////////////////////////////////////////*/

  function _safeMint(address to, uint256 id) internal virtual {
    _mint(to, id);

    require(
      to.code.length == 0
        || ERC721TokenReceiver(to).onERC721Received(msg.sender, address(0), id, "")
          == ERC721TokenReceiver.onERC721Received.selector,
      "UNSAFE_RECIPIENT"
    );
  }

  function _safeMint(address to, uint256 id, bytes memory data) internal virtual {
    _mint(to, id);

    require(
      to.code.length == 0
        || ERC721TokenReceiver(to).onERC721Received(msg.sender, address(0), id, data)
          == ERC721TokenReceiver.onERC721Received.selector,
      "UNSAFE_RECIPIENT"
    );
  }
}

/// @notice A generic interface for a contract which properly accepts ERC721 tokens.
/// @author Solmate (https://github.com/transmissions11/solmate/blob/main/src/tokens/ERC721.sol)
abstract contract ERC721TokenReceiver {
  function onERC721Received(address, address, uint256, bytes calldata) external virtual returns (bytes4) {
    return ERC721TokenReceiver.onERC721Received.selector;
  }
}