// File: @openzeppelin/contracts/access/AccessControl.sol



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

pragma solidity ^0.8.0;

import "./IAccessControl.sol";
import "../utils/Context.sol";
import "../utils/Strings.sol";
import "../utils/introspection/ERC165.sol";

/**
 * @dev Contract module that allows children to implement role-based access
 * control mechanisms. This is a lightweight version that doesn't allow enumerating role
 * members except through off-chain means by accessing the contract event logs. Some
 * applications may benefit from on-chain enumerability, for those cases see
 * {AccessControlEnumerable}.
 *
 * Roles are referred to by their `bytes32` identifier. These should be exposed
 * in the external API and be unique. The best way to achieve this is by
 * using `public constant` hash digests:
 *
 * ```
 * bytes32 public constant MY_ROLE = keccak256("MY_ROLE");
 * ```
 *
 * Roles can be used to represent a set of permissions. To restrict access to a
 * function call, use {hasRole}:
 *
 * ```
 * function foo() public {
 *     require(hasRole(MY_ROLE, msg.sender));
 *     ...
 * }
 * ```
 *
 * Roles can be granted and revoked dynamically via the {grantRole} and
 * {revokeRole} functions. Each role has an associated admin role, and only
 * accounts that have a role's admin role can call {grantRole} and {revokeRole}.
 *
 * By default, the admin role for all roles is `DEFAULT_ADMIN_ROLE`, which means
 * that only accounts with this role will be able to grant or revoke other
 * roles. More complex role relationships can be created by using
 * {_setRoleAdmin}.
 *
 * WARNING: The `DEFAULT_ADMIN_ROLE` is also its own admin: it has permission to
 * grant and revoke this role. Extra precautions should be taken to secure
 * accounts that have been granted it.
 */
abstract contract AccessControl is Context, IAccessControl, ERC165 {
    struct RoleData {
        mapping(address => bool) members;
        bytes32 adminRole;
    }

    mapping(bytes32 => RoleData) private _roles;

    bytes32 public constant DEFAULT_ADMIN_ROLE = 0x00;

    /**
     * @dev Modifier that checks that an account has a specific role. Reverts
     * with a standardized message including the required role.
     *
     * The format of the revert reason is given by the following regular expression:
     *
     *  /^AccessControl: account (0x[0-9a-f]{40}) is missing role (0x[0-9a-f]{64})$/
     *
     * _Available since v4.1._
     */
    modifier onlyRole(bytes32 role) {
        _checkRole(role);
        _;
    }

    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        return interfaceId == type(IAccessControl).interfaceId || super.supportsInterface(interfaceId);
    }

    /**
     * @dev Returns `true` if `account` has been granted `role`.
     */
    function hasRole(bytes32 role, address account) public view virtual override returns (bool) {
        return _roles[role].members[account];
    }

    /**
     * @dev Revert with a standard message if `_msgSender()` is missing `role`.
     * Overriding this function changes the behavior of the {onlyRole} modifier.
     *
     * Format of the revert message is described in {_checkRole}.
     *
     * _Available since v4.6._
     */
    function _checkRole(bytes32 role) internal view virtual {
        _checkRole(role, _msgSender());
    }

    /**
     * @dev Revert with a standard message if `account` is missing `role`.
     *
     * The format of the revert reason is given by the following regular expression:
     *
     *  /^AccessControl: account (0x[0-9a-f]{40}) is missing role (0x[0-9a-f]{64})$/
     */
    function _checkRole(bytes32 role, address account) internal view virtual {
        if (!hasRole(role, account)) {
            revert(
                string(
                    abi.encodePacked(
                        "AccessControl: account ",
                        Strings.toHexString(uint160(account), 20),
                        " is missing role ",
                        Strings.toHexString(uint256(role), 32)
                    )
                )
            );
        }
    }

    /**
     * @dev Returns the admin role that controls `role`. See {grantRole} and
     * {revokeRole}.
     *
     * To change a role's admin, use {_setRoleAdmin}.
     */
    function getRoleAdmin(bytes32 role) public view virtual override returns (bytes32) {
        return _roles[role].adminRole;
    }

    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     *
     * May emit a {RoleGranted} event.
     */
    function grantRole(bytes32 role, address account) public virtual override onlyRole(getRoleAdmin(role)) {
        _grantRole(role, account);
    }

    /**
     * @dev Revokes `role` from `account`.
     *
     * If `account` had been granted `role`, emits a {RoleRevoked} event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     *
     * May emit a {RoleRevoked} event.
     */
    function revokeRole(bytes32 role, address account) public virtual override onlyRole(getRoleAdmin(role)) {
        _revokeRole(role, account);
    }

    /**
     * @dev Revokes `role` from the calling account.
     *
     * Roles are often managed via {grantRole} and {revokeRole}: this function's
     * purpose is to provide a mechanism for accounts to lose their privileges
     * if they are compromised (such as when a trusted device is misplaced).
     *
     * If the calling account had been revoked `role`, emits a {RoleRevoked}
     * event.
     *
     * Requirements:
     *
     * - the caller must be `account`.
     *
     * May emit a {RoleRevoked} event.
     */
    function renounceRole(bytes32 role, address account) public virtual override {
        require(account == _msgSender(), "AccessControl: can only renounce roles for self");

        _revokeRole(role, account);
    }

    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event. Note that unlike {grantRole}, this function doesn't perform any
     * checks on the calling account.
     *
     * May emit a {RoleGranted} event.
     *
     * [WARNING]
     * ====
     * This function should only be called from the constructor when setting
     * up the initial roles for the system.
     *
     * Using this function in any other way is effectively circumventing the admin
     * system imposed by {AccessControl}.
     * ====
     *
     * NOTE: This function is deprecated in favor of {_grantRole}.
     */
    function _setupRole(bytes32 role, address account) internal virtual {
        _grantRole(role, account);
    }

    /**
     * @dev Sets `adminRole` as ``role``'s admin role.
     *
     * Emits a {RoleAdminChanged} event.
     */
    function _setRoleAdmin(bytes32 role, bytes32 adminRole) internal virtual {
        bytes32 previousAdminRole = getRoleAdmin(role);
        _roles[role].adminRole = adminRole;
        emit RoleAdminChanged(role, previousAdminRole, adminRole);
    }

    /**
     * @dev Grants `role` to `account`.
     *
     * Internal function without access restriction.
     *
     * May emit a {RoleGranted} event.
     */
    function _grantRole(bytes32 role, address account) internal virtual {
        if (!hasRole(role, account)) {
            _roles[role].members[account] = true;
            emit RoleGranted(role, account, _msgSender());
        }
    }

    /**
     * @dev Revokes `role` from `account`.
     *
     * Internal function without access restriction.
     *
     * May emit a {RoleRevoked} event.
     */
    function _revokeRole(bytes32 role, address account) internal virtual {
        if (hasRole(role, account)) {
            _roles[role].members[account] = false;
            emit RoleRevoked(role, account, _msgSender());
        }
    }
}

// File: @openzeppelin/contracts/access/IAccessControl.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (access/IAccessControl.sol)

pragma solidity ^0.8.0;

/**
 * @dev External interface of AccessControl declared to support ERC165 detection.
 */
interface IAccessControl {
    /**
     * @dev Emitted when `newAdminRole` is set as ``role``'s admin role, replacing `previousAdminRole`
     *
     * `DEFAULT_ADMIN_ROLE` is the starting admin for all roles, despite
     * {RoleAdminChanged} not being emitted signaling this.
     *
     * _Available since v3.1._
     */
    event RoleAdminChanged(bytes32 indexed role, bytes32 indexed previousAdminRole, bytes32 indexed newAdminRole);

    /**
     * @dev Emitted when `account` is granted `role`.
     *
     * `sender` is the account that originated the contract call, an admin role
     * bearer except when using {AccessControl-_setupRole}.
     */
    event RoleGranted(bytes32 indexed role, address indexed account, address indexed sender);

    /**
     * @dev Emitted when `account` is revoked `role`.
     *
     * `sender` is the account that originated the contract call:
     *   - if using `revokeRole`, it is the admin role bearer
     *   - if using `renounceRole`, it is the role bearer (i.e. `account`)
     */
    event RoleRevoked(bytes32 indexed role, address indexed account, address indexed sender);

    /**
     * @dev Returns `true` if `account` has been granted `role`.
     */
    function hasRole(bytes32 role, address account) external view returns (bool);

    /**
     * @dev Returns the admin role that controls `role`. See {grantRole} and
     * {revokeRole}.
     *
     * To change a role's admin, use {AccessControl-_setRoleAdmin}.
     */
    function getRoleAdmin(bytes32 role) external view returns (bytes32);

    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     */
    function grantRole(bytes32 role, address account) external;

    /**
     * @dev Revokes `role` from `account`.
     *
     * If `account` had been granted `role`, emits a {RoleRevoked} event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     */
    function revokeRole(bytes32 role, address account) external;

    /**
     * @dev Revokes `role` from the calling account.
     *
     * Roles are often managed via {grantRole} and {revokeRole}: this function's
     * purpose is to provide a mechanism for accounts to lose their privileges
     * if they are compromised (such as when a trusted device is misplaced).
     *
     * If the calling account had been granted `role`, emits a {RoleRevoked}
     * event.
     *
     * Requirements:
     *
     * - the caller must be `account`.
     */
    function renounceRole(bytes32 role, address account) external;
}

// File: @openzeppelin/contracts/utils/Context.sol



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

pragma solidity ^0.8.0;

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

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

// File: @openzeppelin/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: @openzeppelin/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: @openzeppelin/contracts/utils/Strings.sol



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

pragma solidity ^0.8.0;

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

    /**
     * @dev Converts a `uint256` to its ASCII `string` decimal representation.
     */
    function toString(uint256 value) internal pure returns (string memory) {
        // Inspired by OraclizeAPI's implementation - MIT licence
        // https://github.com/oraclize/ethereum-api/blob/b42146b063c7d6ee1358846c198246239e9360e8/oraclizeAPI_0.4.25.sol

        if (value == 0) {
            return "0";
        }
        uint256 temp = value;
        uint256 digits;
        while (temp != 0) {
            digits++;
            temp /= 10;
        }
        bytes memory buffer = new bytes(digits);
        while (value != 0) {
            digits -= 1;
            buffer[digits] = bytes1(uint8(48 + uint256(value % 10)));
            value /= 10;
        }
        return string(buffer);
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation.
     */
    function toHexString(uint256 value) internal pure returns (string memory) {
        if (value == 0) {
            return "0x00";
        }
        uint256 temp = value;
        uint256 length = 0;
        while (temp != 0) {
            length++;
            temp >>= 8;
        }
        return toHexString(value, length);
    }

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

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

// File: src/contracts/AvabotRouter.sol



// SPDX-License-Identifier: GPL-3.0-only
pragma solidity ^0.8.0;
pragma experimental ABIEncoderV2;

import "./interface/IAvabotRouter.sol";
import "./interface/IAdapter.sol";
import "./interface/IUniV2likeAdapter.sol";
import "./interface/IERC20.sol";
import "./interface/IWETH.sol";
import "./lib/SafeERC20.sol";
import "./lib/Maintainable.sol";
import "./lib/AvabotViewUtils.sol";
import "./lib/Recoverable.sol";
import "./lib/SafeERC20.sol";
import "./interface/IUniswapFactory.sol";

contract AvabotRouter is Maintainable, Recoverable, IAvabotRouter {
    using SafeERC20 for IERC20;
    using OfferUtils for Offer;

    address public immutable WNATIVE;
    address public constant NATIVE = address(0);
    string public constant NAME = "AvabotRouter";
    uint256 public constant FEE_DENOMINATOR = 1e4;
    uint256 public MIN_FEE = 0;
    address public FEE_CLAIMER;
    address[] public TRUSTED_TOKENS;
    address[] public ADAPTERS;

    // Avabot
    error TransferToZeroAddressAttempt();
    error TokenTransferFailed(address token, address dest, uint256 amount);
    error CallerIsNotFeeClaimer(address caller);
    error TransactionTooOld();

    event AvabotSwapFee(address indexed _token, address indexed _sender, string _referral, uint256 _feeAmount);

    modifier onlyFeeClaimer() {
        _checkFeeClaimer();
        _;
    }

    modifier checkDeadline(uint256 deadline) {
        _checkDeadline(deadline);
        _;
    }

    function _checkFeeClaimer() internal view virtual {
        address msgSender = _msgSender();
        if (msgSender != FEE_CLAIMER) revert CallerIsNotFeeClaimer(msgSender);
    }

    function _checkDeadline(uint256 deadline) internal view virtual {
        if (deadline < block.timestamp) revert TransactionTooOld();
    }

    constructor(
        address[] memory _adapters,
        address[] memory _trustedTokens,
        address _feeClaimer,
        address _wrapped_native
    ) {
        setAllowanceForWrapping(_wrapped_native);
        setTrustedTokens(_trustedTokens);
        setFeeClaimer(_feeClaimer);
        setAdapters(_adapters);
        WNATIVE = _wrapped_native;
    }

    // -- SETTERS --

    function setAllowanceForWrapping(address _wnative) public onlyMaintainer {
        IERC20(_wnative).safeApprove(_wnative, type(uint256).max);
    }

    function setTrustedTokens(address[] memory _trustedTokens) public override onlyMaintainer {
        emit UpdatedTrustedTokens(_trustedTokens);
        TRUSTED_TOKENS = _trustedTokens;
    }

    function setAdapters(address[] memory _adapters) public override onlyMaintainer {
        emit UpdatedAdapters(_adapters);
        ADAPTERS = _adapters;
    }

    function setMinFee(uint256 _fee) external override onlyMaintainer {
        emit UpdatedMinFee(MIN_FEE, _fee);
        MIN_FEE = _fee;
    }

    function setFeeClaimer(address _claimer) public override onlyMaintainer {
        emit UpdatedFeeClaimer(FEE_CLAIMER, _claimer);
        FEE_CLAIMER = _claimer;
    }

    //  -- GENERAL --

    function trustedTokensCount() external view override returns (uint256) {
        return TRUSTED_TOKENS.length;
    }

    function adaptersCount() external view override returns (uint256) {
        return ADAPTERS.length;
    }

    // Fallback
    receive() external payable {}

    // -- HELPERS --

    function _applyFee(uint256 _amountIn, uint256 _fee) internal view returns (uint256) {
        require(_fee >= MIN_FEE, "AvabotRouter: Insufficient fee");
        return (_amountIn * (FEE_DENOMINATOR - _fee)) / FEE_DENOMINATOR;
    }

    function _wrap(uint256 _amount) internal {
        IWETH(WNATIVE).deposit{ value: _amount }();
    }

    function _unwrap(uint256 _amount) internal {
        IWETH(WNATIVE).withdraw(_amount);
    }

    /**
     * @notice Return tokens to user
     * @dev Pass address(0) for ETH
     * @param _token address
     * @param _amount tokens to return
     * @param _to address where funds should be sent to
     */
    function _returnTokensTo(
        address _token,
        uint256 _amount,
        address _to
    ) internal {
        if (address(this) != _to) {
            if (_token == NATIVE) {
                payable(_to).transfer(_amount);
            } else {
                IERC20(_token).safeTransfer(_to, _amount);
            }
        }
    }

    function _transferFrom(
        address token,
        address _from,
        address _to,
        uint256 _amount
    ) internal {
        if (_from != address(this)) IERC20(token).safeTransferFrom(_from, _to, _amount);
        else IERC20(token).safeTransfer(_to, _amount);
    }

    // -- QUERIES --

    /**
     * Query single adapter
     */
    function queryAdapter(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint8 _index
    ) external view override returns (uint256) {
        IAdapter _adapter = IAdapter(ADAPTERS[_index]);
        uint256 amountOut = _adapter.query(_amountIn, _tokenIn, _tokenOut);
        return amountOut;
    }

    /**
     * Query specified adapters
     */
    function queryNoSplit(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint8[] calldata _options
    ) public view override returns (Query memory) {
        Query memory bestQuery;
        for (uint8 i; i < _options.length; i++) {
            address _adapter = ADAPTERS[_options[i]];
            uint256 amountOut = IAdapter(_adapter).query(_amountIn, _tokenIn, _tokenOut);
            if (i == 0 || amountOut > bestQuery.amountOut) {
                bestQuery = Query(_adapter, _tokenIn, _tokenOut, amountOut);
            }
        }
        return bestQuery;
    }

    /**
     * Query all adapters
     */
    function queryNoSplit(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut
    ) public view override returns (Query memory) {
        Query memory bestQuery;
        for (uint8 i; i < ADAPTERS.length; i++) {
            address _adapter = ADAPTERS[i];
            uint256 amountOut = IAdapter(_adapter).query(_amountIn, _tokenIn, _tokenOut);
            if (i == 0 || amountOut > bestQuery.amountOut) {
                bestQuery = Query(_adapter, _tokenIn, _tokenOut, amountOut);
            }
        }
        return bestQuery;
    }

    /**
     * Return path with best returns between two tokens
     * Takes gas-cost into account
     */
    function findBestPathWithGas(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint256 _maxSteps,
        uint256 _gasPrice
    ) external view override returns (FormattedOffer memory) {
        require(_maxSteps > 0 && _maxSteps < 5, "AvabotRouter: Invalid max-steps");
        Offer memory queries = OfferUtils.newOffer(_amountIn, _tokenIn);
        uint256 gasPriceInExitTkn = _gasPrice > 0 ? getGasPriceInExitTkn(_gasPrice, _tokenOut) : 0;
        queries = _findBestPath(_amountIn, _tokenIn, _tokenOut, _maxSteps, queries, gasPriceInExitTkn);
        if (queries.adapters.length == 0) {
            queries.amounts = "";
            queries.path = "";
        }
        return queries.format();
    }

    // Find the market price between gas-asset(native) and token-out and express gas price in token-out
    function getGasPriceInExitTkn(uint256 _gasPrice, address _tokenOut) internal view returns (uint256 price) {
        // Avoid low-liquidity price appreciation (https://github.com/yieldyak/yak-aggregator/issues/20)
        FormattedOffer memory gasQuery = findBestPath(1e18, WNATIVE, _tokenOut, 2);
        if (gasQuery.path.length != 0) {
            // Leave result in nWei to preserve precision for assets with low decimal places
            price = (gasQuery.amounts[gasQuery.amounts.length - 1] * _gasPrice) / 1e9;
        }
    }

    /**
     * Return path with best returns between two tokens
     */
    function findBestPath(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint256 _maxSteps
    ) public view override returns (FormattedOffer memory) {
        require(_maxSteps > 0 && _maxSteps < 5, "AvabotRouter: Invalid max-steps");
        Offer memory queries = OfferUtils.newOffer(_amountIn, _tokenIn);
        queries = _findBestPath(_amountIn, _tokenIn, _tokenOut, _maxSteps, queries, 0);
        // If no paths are found return empty struct
        if (queries.adapters.length == 0) {
            queries.amounts = "";
            queries.path = "";
        }
        return queries.format();
    }

    function _findBestPath(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint256 _maxSteps,
        Offer memory _queries,
        uint256 _tknOutPriceNwei
    ) internal view returns (Offer memory) {
        Offer memory bestOption = _queries.clone();
        uint256 bestAmountOut;
        uint256 gasEstimate;
        bool withGas = _tknOutPriceNwei != 0;

        // First check if there is a path directly from tokenIn to tokenOut
        Query memory queryDirect = queryNoSplit(_amountIn, _tokenIn, _tokenOut);

        if (queryDirect.amountOut != 0) {
            if (withGas) {
                gasEstimate = IAdapter(queryDirect.adapter).swapGasEstimate();
            }
            bestOption.addToTail(queryDirect.amountOut, queryDirect.adapter, queryDirect.tokenOut, gasEstimate);
            bestAmountOut = queryDirect.amountOut;
        }
        // Only check the rest if they would go beyond step limit (Need at least 2 more steps)
        if (_maxSteps > 1 && _queries.adapters.length / 32 <= _maxSteps - 2) {
            // Check for paths that pass through trusted tokens
            for (uint256 i = 0; i < TRUSTED_TOKENS.length; i++) {
                if (_tokenIn == TRUSTED_TOKENS[i]) {
                    continue;
                }
                // Loop through all adapters to find the best one for swapping tokenIn for one of the trusted tokens
                Query memory bestSwap = queryNoSplit(_amountIn, _tokenIn, TRUSTED_TOKENS[i]);
                if (bestSwap.amountOut == 0) {
                    continue;
                }
                // Explore options that connect the current path to the tokenOut
                Offer memory newOffer = _queries.clone();
                if (withGas) {
                    gasEstimate = IAdapter(bestSwap.adapter).swapGasEstimate();
                }
                newOffer.addToTail(bestSwap.amountOut, bestSwap.adapter, bestSwap.tokenOut, gasEstimate);
                newOffer = _findBestPath(
                    bestSwap.amountOut,
                    TRUSTED_TOKENS[i],
                    _tokenOut,
                    _maxSteps,
                    newOffer,
                    _tknOutPriceNwei
                ); // Recursive step
                address tokenOut = newOffer.getTokenOut();
                uint256 amountOut = newOffer.getAmountOut();
                // Check that the last token in the path is the tokenOut and update the new best option if neccesary
                if (_tokenOut == tokenOut && amountOut > bestAmountOut) {
                    if (newOffer.gasEstimate > bestOption.gasEstimate) {
                        uint256 gasCostDiff = (_tknOutPriceNwei * (newOffer.gasEstimate - bestOption.gasEstimate)) /
                            1e9;
                        uint256 priceDiff = amountOut - bestAmountOut;
                        if (gasCostDiff > priceDiff) {
                            continue;
                        }
                    }
                    bestAmountOut = amountOut;
                    bestOption = newOffer;
                }
            }
        }
        return bestOption;
    }

    // -- SWAPPERS --
    // Avabot: fee on transfer default, only fee on transfer adapter
    function _swapNoSplit(
        Trade calldata _trade,
        address _from,
        address _to,
        uint256 _fee,
        uint256 _deadline,
        string memory _referral
    ) internal checkDeadline(_deadline) returns (uint256) {
        {
            uint256 totalAmountIn;
            if (_fee > 0 || MIN_FEE > 0) {
                if (_trade.path[_trade.path.length - 1] != WNATIVE) {
                    totalAmountIn = _applyFee(_trade.amountIn, _fee);
                    emit AvabotSwapFee(_trade.path[0], msg.sender, _referral, _trade.amountIn - totalAmountIn);
                } else {
                    totalAmountIn = _trade.amountIn;
                }
            } else {
                totalAmountIn = _trade.amountIn;
            }
            if(IAdapter(_trade.adapters[0]).isUniV2like()) {
                address factory = IUniV2likeAdapter(_trade.adapters[0]).factory();
                _transferFrom(_trade.path[0], _from, IUniswapFactory(factory).getPair(_trade.path[0], _trade.path[1]), totalAmountIn);
            } else {
                _transferFrom(_trade.path[0], _from, _trade.adapters[0], totalAmountIn);
            }
        }

        uint256[] memory amounts = new uint256[](2);
        // stack too deep explain
        // amounts[0]: _toBalance
        // amounts[1]: _swapAmount

        for (uint256 i = 0; i < _trade.adapters.length; i++) {
            // All adapters should transfer output token to the following target
            // All targets are the adapters, expect for the last swap where tokens are sent out
            address targetAddress;
            if (_trade.path[_trade.path.length - 1] == WNATIVE) {
                targetAddress = i < _trade.adapters.length - 1 ? _trade.adapters[i + 1] : address(this);
            } else {
                targetAddress = i < _trade.adapters.length - 1 ? _trade.adapters[i + 1] : _to;
            }

            amounts[0] = IERC20(_trade.path[i + 1]).balanceOf(targetAddress);
            IAdapter(_trade.adapters[i]).swap(0, 0, _trade.path[i], _trade.path[i + 1], targetAddress);
            if (i == _trade.adapters.length - 1) {
                uint256 diff = IERC20(_trade.path[i + 1]).balanceOf(targetAddress) - amounts[0];
                require(diff >= _trade.amountOut, "AvabotRouter: Insufficient output amount");
                amounts[1] = diff;
            }
        }

        uint256 totalAmountOut;
        if (_fee > 0 || MIN_FEE > 0) {
            if (_trade.path[_trade.path.length - 1] == WNATIVE) {
                totalAmountOut = _applyFee(amounts[1], _fee);
                require(totalAmountOut >= _trade.amountOut, "AvabotRouter: Insufficient output amount");
                emit AvabotSwapFee(
                    _trade.path[_trade.path.length - 1],
                    msg.sender,
                    _referral,
                    amounts[1] - totalAmountOut
                );
            } else {
                totalAmountOut = amounts[1];
            }
        } else {
            totalAmountOut = amounts[1];
        }
        if (_trade.path[_trade.path.length - 1] == WNATIVE && _to != address(this)) {
            IERC20(_trade.path[_trade.path.length - 1]).safeTransfer(_to, totalAmountOut);
        }
        emit AvabotSwap(
            _trade.path[0],
            _trade.path[_trade.path.length - 1],
            _trade.amountIn,
            totalAmountOut,
            msg.sender,
            _fee
        );
        return totalAmountOut;
    }

    function swapNoSplit(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata _referral
    ) public override {
        _swapNoSplit(_trade, msg.sender, msg.sender, _fee, _deadline, _referral);
    }

    function swapNoSplitFromETH(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata _referral
    ) external payable override {
        require(_trade.path[0] == WNATIVE, "AvabotRouter: Path needs to begin with WETH");
        _wrap(_trade.amountIn);
        _swapNoSplit(_trade, address(this), msg.sender, _fee, _deadline, _referral);
    }

    function swapNoSplitToETH(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata _referral
    ) public override {
        require(_trade.path[_trade.path.length - 1] == WNATIVE, "AvabotRouter: Path needs to end with WETH");
        uint256 returnAmount = _swapNoSplit(_trade, msg.sender, address(this), _fee, _deadline, _referral);
        _unwrap(returnAmount);
        _returnTokensTo(NATIVE, returnAmount, msg.sender);
    }

    /**
     * Swap token to token without the need to approve the first token
     */
    function swapNoSplitWithPermit(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata _referral,
        uint8 _v,
        bytes32 _r,
        bytes32 _s
    ) external override {
        IERC20(_trade.path[0]).permit(msg.sender, address(this), _trade.amountIn, _deadline, _v, _r, _s);
        swapNoSplit(_trade, _fee, _deadline, _referral);
    }

    /**
     * Swap token to ETH without the need to approve the first token
     */
    function swapNoSplitToETHWithPermit(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata _referral,
        uint8 _v,
        bytes32 _r,
        bytes32 _s
    ) external override {
        IERC20(_trade.path[0]).permit(msg.sender, address(this), _trade.amountIn, _deadline, _v, _r, _s);
        swapNoSplitToETH(_trade, _fee, _deadline, _referral);
    }

    // Avabot

    /**
     * @dev Utility method to be able to transfer native tokens out of Smart Account
     * @notice only owner/ signatory of Smart Account with enough gas to spend can call this method
     * @notice While enabling multisig module and renouncing ownership this will not work
     * @param _dest Destination address
     * @param _amount Amount of native tokens
     */
    function transfer(address payable _dest, uint256 _amount) external onlyFeeClaimer {
        if (_dest == address(0)) revert TransferToZeroAddressAttempt();
        bool success;
        assembly {
            success := call(gas(), _dest, _amount, 0, 0, 0, 0)
        }
        if (!success) revert TokenTransferFailed(address(0), _dest, _amount);
    }

    /**
     * @dev Utility method to be able to transfer ERC20 tokens out of Smart Account
     * @notice only owner/ signatory of Smart Account with enough gas to spend can call this method
     * @notice While enabling multisig module and renouncing ownership this will not work
     * @param _token Token address
     * @param _dest Destination/ Receiver address
     * @param _amount Amount of tokens
     */
    function pullTokens(
        address _token,
        address _dest,
        uint256 _amount
    ) external onlyFeeClaimer {
        if (_dest == address(0)) revert TransferToZeroAddressAttempt();
        IERC20(_token).safeTransfer(_dest, _amount);
    }
}

// File: src/contracts/interface/IAdapter.sol



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

interface IAdapter {
    function isUniV2like() external view returns (bool);

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

    function swapGasEstimate() external view returns (uint256);

    function swap(
        uint256,
        uint256,
        address,
        address,
        address
    ) external;

    function query(
        uint256,
        address,
        address
    ) external view returns (uint256);
}

// File: src/contracts/interface/IAvabotRouter.sol



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


struct Query {
    address adapter;
    address tokenIn;
    address tokenOut;
    uint256 amountOut;
}
struct Offer {
    bytes amounts;
    bytes adapters;
    bytes path;
    uint256 gasEstimate;
}
struct FormattedOffer {
    uint256[] amounts;
    address[] adapters;
    address[] path;
    uint256 gasEstimate;
}
struct Trade {
    uint256 amountIn;
    uint256 amountOut;
    address[] path;
    address[] adapters;
}

interface IAvabotRouter {

    event UpdatedTrustedTokens(address[] _newTrustedTokens);
    event UpdatedAdapters(address[] _newAdapters);
    event UpdatedMinFee(uint256 _oldMinFee, uint256 _newMinFee);
    event UpdatedFeeClaimer(address _oldFeeClaimer, address _newFeeClaimer);
    event AvabotSwap(address indexed _tokenIn, address indexed _tokenOut, uint256 _amountIn, uint256 _amountOut, address sender, uint256 _fee);

    // admin
    function setTrustedTokens(address[] memory _trustedTokens) external;
    function setAdapters(address[] memory _adapters) external;
    function setFeeClaimer(address _claimer) external;
    function setMinFee(uint256 _fee) external;

    // misc
    function trustedTokensCount() external view returns (uint256);
    function adaptersCount() external view returns (uint256);

    // query

    function queryAdapter(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint8 _index
    ) external returns (uint256);

    function queryNoSplit(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint8[] calldata _options
    ) external view returns (Query memory);

    function queryNoSplit(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut
    ) external view returns (Query memory);

    function findBestPathWithGas(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint256 _maxSteps,
        uint256 _gasPrice
    ) external view returns (FormattedOffer memory);

    function findBestPath(
        uint256 _amountIn,
        address _tokenIn,
        address _tokenOut,
        uint256 _maxSteps
    ) external view returns (FormattedOffer memory);

    // swap

    function swapNoSplit(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata referal
    ) external;

    function swapNoSplitFromETH(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata referal
    ) external payable;

    function swapNoSplitToETH(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata referal
    ) external; 

    function swapNoSplitWithPermit(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata referal,
        uint8 _v,
        bytes32 _r,
        bytes32 _s
    ) external;

    function swapNoSplitToETHWithPermit(
        Trade calldata _trade,
        uint256 _fee,
        uint256 _deadline,
        string calldata referal,
        uint8 _v,
        bytes32 _r,
        bytes32 _s
    ) external;

}
// File: src/contracts/interface/IERC20.sol



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

interface IERC20 {
    event Approval(address, address, uint256);
    event Transfer(address, address, uint256);

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

    function decimals() external view returns (uint8);

    function transferFrom(
        address,
        address,
        uint256
    ) external returns (bool);

    function allowance(address, address) external view returns (uint256);

    function approve(address, uint256) external returns (bool);

    function transfer(address, uint256) external returns (bool);

    function balanceOf(address) external view returns (uint256);

    function nonces(address) external view returns (uint256); // Only tokens that support permit

    function permit(
        address,
        address,
        uint256,
        uint256,
        uint8,
        bytes32,
        bytes32
    ) external; // Only tokens that support permit

    function swap(address, uint256) external; // Only Avalanche bridge tokens

    function swapSupply(address) external view returns (uint256); // Only Avalanche bridge tokens

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

// File: src/contracts/interface/IUniswapFactory.sol



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

interface IUniswapFactory {
    function getPair(address tokenA, address tokenB) external view returns (address pair);
}

// File: src/contracts/interface/IUniV2likeAdapter.sol



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

import "./IAdapter.sol";

interface IUniV2likeAdapter is IAdapter {
    function factory() external view returns (address);
}

// File: src/contracts/interface/IWETH.sol



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

import "./IERC20.sol";

interface IWETH is IERC20 {
    function withdraw(uint256 amount) external;

    function deposit() external payable;
}

// File: src/contracts/lib/AvabotViewUtils.sol



// SPDX-License-Identifier: GPL-3.0-only
pragma solidity >=0.8.4;

import { Offer, FormattedOffer } from "../interface/IAvabotRouter.sol";
import "./TypeConversion.sol";


library OfferUtils {
    using TypeConversion for address;
    using TypeConversion for uint256;
    using TypeConversion for bytes;

    function newOffer(
        uint _amountIn,
        address _tokenIn
    ) internal pure returns (Offer memory offer) {
        offer.amounts = _amountIn.toBytes();
        offer.path = _tokenIn.toBytes();
    }

    /**
     * Makes a deep copy of Offer struct
     */
    function clone(Offer memory _queries) internal pure returns (Offer memory) {
        return Offer(_queries.amounts, _queries.adapters, _queries.path, _queries.gasEstimate);
    }

    /**
     * Appends new elements to the end of Offer struct
     */
    function addToTail(
        Offer memory _queries,
        uint256 _amount,
        address _adapter,
        address _tokenOut,
        uint256 _gasEstimate
    ) internal pure {
        _queries.path = bytes.concat(_queries.path, _tokenOut.toBytes());
        _queries.adapters = bytes.concat(_queries.adapters, _adapter.toBytes());
        _queries.amounts = bytes.concat(_queries.amounts, _amount.toBytes());
        _queries.gasEstimate += _gasEstimate;
    }

    /**
     * Formats elements in the Offer object from byte-arrays to integers and addresses
     */
    function format(Offer memory _queries) internal pure returns (FormattedOffer memory) {
        return
            FormattedOffer(
                _queries.amounts.toUints(),
                _queries.adapters.toAddresses(),
                _queries.path.toAddresses(),
                _queries.gasEstimate
            );
    }

    function getTokenOut(
        Offer memory _offer
    ) internal pure returns (address tokenOut) {
        tokenOut = _offer.path.toAddress(_offer.path.length);  // Last 32 bytes
    }

    function getAmountOut(
        Offer memory _offer
    ) internal pure returns (uint amountOut) {
        amountOut = _offer.amounts.toUint(_offer.path.length);  // Last 32 bytes
    }

}

library FormattedOfferUtils {
    using TypeConversion for address;
    using TypeConversion for uint256;
    using TypeConversion for bytes;

    /**
     * Appends new elements to the end of FormattedOffer
     */
    function addToTail(
        FormattedOffer memory offer, 
        uint256 amountOut, 
        address wrapper,
        address tokenOut,
        uint256 gasEstimate
    ) internal pure {
        offer.amounts = bytes.concat(abi.encodePacked(offer.amounts), amountOut.toBytes()).toUints();
        offer.adapters = bytes.concat(abi.encodePacked(offer.adapters), wrapper.toBytes()).toAddresses();
        offer.path = bytes.concat(abi.encodePacked(offer.path), tokenOut.toBytes()).toAddresses();
        offer.gasEstimate += gasEstimate;
    }

    /**
     * Appends new elements to the beginning of FormattedOffer
     */
    function addToHead(
        FormattedOffer memory offer, 
        uint256 amountOut, 
        address wrapper,
        address tokenOut,
        uint256 gasEstimate
    ) internal pure {
        offer.amounts = bytes.concat(amountOut.toBytes(), abi.encodePacked(offer.amounts)).toUints();
        offer.adapters = bytes.concat(wrapper.toBytes(), abi.encodePacked(offer.adapters)).toAddresses();
        offer.path = bytes.concat(tokenOut.toBytes(), abi.encodePacked(offer.path)).toAddresses();
        offer.gasEstimate += gasEstimate;
    }

    function getAmountOut(FormattedOffer memory offer) internal pure returns (uint256) {
        return offer.amounts[offer.amounts.length - 1];
    }

}
// File: src/contracts/lib/Maintainable.sol



// SPDX-License-Identifier: MIT

pragma solidity ^0.8.0;

import "@openzeppelin/contracts/access/AccessControl.sol";

/**
 * @dev Contract module which extends the basic access control mechanism of Ownable
 * to include many maintainers, whom only the owner (DEFAULT_ADMIN_ROLE) may add and
 * remove.
 *
 * By default, the owner account will be the one that deploys the contract. This can
 * later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available this modifier:
 * `onlyMaintainer`, which can be applied to your functions to restrict their use to
 * the accounts with the role of maintainer.
 */

abstract contract Maintainable is Context, AccessControl {
    bytes32 public constant MAINTAINER_ROLE = keccak256("MAINTAINER_ROLE");

    constructor() {
        address msgSender = _msgSender();
        // members of the DEFAULT_ADMIN_ROLE alone may revoke and grant role membership
        _setupRole(DEFAULT_ADMIN_ROLE, msgSender);
        _setupRole(MAINTAINER_ROLE, msgSender);
    }

    function addMaintainer(address addedMaintainer) public virtual {
        grantRole(MAINTAINER_ROLE, addedMaintainer);
    }

    function removeMaintainer(address removedMaintainer) public virtual {
        revokeRole(MAINTAINER_ROLE, removedMaintainer);
    }

    function renounceRole(bytes32 role) public virtual {
        address msgSender = _msgSender();
        renounceRole(role, msgSender);
    }

    function transferOwnership(address newOwner) public virtual {
        address msgSender = _msgSender();
        grantRole(DEFAULT_ADMIN_ROLE, newOwner);
        renounceRole(DEFAULT_ADMIN_ROLE, msgSender);
    }

    modifier onlyMaintainer() {
        address msgSender = _msgSender();
        require(hasRole(MAINTAINER_ROLE, msgSender), "Maintainable: Caller is not a maintainer");
        _;
    }
}

// File: src/contracts/lib/Recoverable.sol



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

import "./SafeERC20.sol";
import "./Maintainable.sol";


abstract contract Recoverable is Maintainable {
    using SafeERC20 for IERC20;

    event Recovered(
        address indexed _asset, 
        uint amount
    );

    /**
     * @notice Recover ERC20 from contract
     * @param _tokenAddress token address
     * @param _tokenAmount amount to recover
     */
    function recoverERC20(address _tokenAddress, uint _tokenAmount) external onlyMaintainer {
        require(_tokenAmount > 0, "Nothing to recover");
        IERC20(_tokenAddress).safeTransfer(msg.sender, _tokenAmount);
        emit Recovered(_tokenAddress, _tokenAmount);
    }

    /**
     * @notice Recover native asset from contract
     * @param _amount amount
     */
    function recoverNative(uint _amount) external onlyMaintainer {
        require(_amount > 0, "Nothing to recover");
        payable(msg.sender).transfer(_amount);
        emit Recovered(address(0), _amount);
    }

}
// File: src/contracts/lib/SafeERC20.sol



// This is a simplified version of OpenZepplin's SafeERC20 library
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
pragma experimental ABIEncoderV2;

import "../interface/IERC20.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 ERC20;` statement to your contract,
 * which allows you to call the safe operations as `token.safeTransfer(...)`, etc.
 */
library SafeERC20 {
    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));
    }

    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'
        // solhint-disable-next-line max-line-length
        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));
    }

    /**
     * @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.

        // A Solidity high level call has three parts:
        //  1. The target address is checked to verify it contains contract code
        //  2. The call itself is made, and success asserted
        //  3. The return value is decoded, which in turn checks the size of the returned data.
        // solhint-disable-next-line max-line-length

        // solhint-disable-next-line avoid-low-level-calls
        (bool success, bytes memory returndata) = address(token).call(data);
        require(success, "SafeERC20: low-level call failed");

        if (returndata.length > 0) {
            // Return data is optional
            // solhint-disable-next-line max-line-length
            require(abi.decode(returndata, (bool)), "SafeERC20: ERC20 operation did not succeed");
        }
    }
}

// File: src/contracts/lib/TypeConversion.sol



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


library TypeConversion {

    function toBytes12(address x) internal pure returns (bytes12 y) {
        assembly { y := x }
    }

    function toBytes32(address x) internal pure returns (bytes32 y) {
        assembly { y := x }
    }

    function toAddress(bytes32 x) internal pure returns (address y) {
        assembly { y := x }
    }

    function toBytes(address x) internal pure returns (bytes memory y) {
        y = new bytes(32);
        assembly { mstore(add(y, 32), x) }
    }

    function toBytes(bytes32 x) internal pure returns (bytes memory y) {
        y = new bytes(32);
        assembly { mstore(add(y, 32), x) }
    }

    function toBytes(uint x) internal pure returns (bytes memory y) {
        y = new bytes(32);
        assembly { mstore(add(y, 32), x) }
    }

    function toAddress(
        bytes memory x,
        uint offset
    ) internal pure returns (address y) {
        assembly { y := mload(add(x, offset)) }
    }

    function toUint(
        bytes memory x,
        uint offset
    ) internal pure returns (uint y) {
        assembly { y := mload(add(x, offset)) }
    }

    function toBytes12(
        bytes memory x,
        uint offset
    ) internal pure returns (bytes12 y) {
        assembly { y := mload(add(x, offset)) }
    }

    function toBytes32(
        bytes memory x,
        uint offset
    ) internal pure returns (bytes32 y) {
        assembly { y := mload(add(x, offset)) }
    }

    function toAddresses(
        bytes memory xs
    ) internal pure returns (address[] memory ys) {
        ys = new address[](xs.length/32);
        for (uint i=0; i < xs.length/32; i++) {
            ys[i] = toAddress(xs, i*32 + 32);
        }
    }

    function toUints(
        bytes memory xs
    ) internal pure returns (uint[] memory ys) {
        ys = new uint[](xs.length/32);
        for (uint i=0; i < xs.length/32; i++) {
            ys[i] = toUint(xs, i*32 + 32);
        }
    }

    function toBytes32s(
        bytes memory xs
    ) internal pure returns (bytes32[] memory ys) {
        ys = new bytes32[](xs.length/32);
        for (uint i=0; i < xs.length/32; i++) {
            ys[i] = toBytes32(xs, i*32 + 32);
        }
    }

}