// File: contracts/safex/MatchingEngine.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;
import {IOrderbookFactory} from "./interfaces/IOrderbookFactory.sol";
import {IOrderbook, ExchangeOrderbook} from "./interfaces/IOrderbook.sol";
import {TransferHelper} from "./libraries/TransferHelper.sol";
import {Initializable} from "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";
import {IWETH} from "./interfaces/IWETH.sol";
import {ReentrancyGuard} from "@openzeppelin/contracts/security/ReentrancyGuard.sol";

interface IRevenue {
    function report(
        uint32 uid,
        address token,
        uint256 amount,
        bool isAdd
    ) external;

    function isReportable(
        address token,
        uint32 uid
    ) external view returns (bool);

    function refundFee(address to, address token, uint256 amount) external;

    function feeOf(uint32 uid, bool isMaker) external returns (uint32 feeNum);
}

// Onchain Matching engine for the orders
contract MatchingEngine is Initializable, ReentrancyGuard {
    // fee recipient
    address private feeTo;
    // fee denominator
    uint32 public immutable feeDenom = 1000000;
    // Factories
    address public orderbookFactory;
    // WETH
    address public WETH;

    // events
    event OrderCanceled(
        address orderbook,
        uint256 id,
        bool isBid,
        address indexed owner
    );

    event OrderMatched(
        address indexed orderbook,
        uint256 id,
        bool isBid,
        address sender,
        address owner,
        uint256 amount,
        uint256 price
    );

    event OrderPlaced(
        address orderbook,
        address indexed sender,
        uint256 price,
        bool isBid,
        uint256 orderId
    );

    event PairAdded(address orderbook, address base, address quote);

    error TooManyMatches(uint256 n);
    error InvalidFeeRate(uint256 feeNum, uint256 feeDenom);
    error NotContract(address newImpl);
    error InvalidRole(bytes32 role, address sender);
    error OrderSizeTooSmall(uint256 amount, uint256 minRequired);

    constructor() {}

    receive() external payable {
        assert(msg.sender == WETH); // only accept ETH via fallback from the WETH contract
    }

    /**
     * @dev Initialize the matching engine with orderbook factory and listing requirements.
     * It can be called only once.
     * @param orderbookFactory_ address of orderbook factory
     * @param treasury_ address of treasury contract
     * @param WETH_ address of wrapped ether contract
     *
     * Requirements:
     * - `msg.sender` must have the default admin role.
     */
    function initialize(
        address orderbookFactory_,
        address treasury_,
        address WETH_
    ) external initializer {
        orderbookFactory = orderbookFactory_;
        feeTo = treasury_;
        WETH = WETH_;
    }

    /**
     * @dev Executes a market buy order,
     * buys the base asset using the quote asset at the best available price in the orderbook up to `n` orders,
     * and make an order at the market price.
     * @param base The address of the base asset for the trading pair
     * @param quote The address of the quote asset for the trading pair
     * @param quoteAmount The amount of quote asset to be used for the market buy order
     * @param isMaker Boolean indicating if a order should be made at the market price in orderbook
     * @param n The maximum number of orders to match in the orderbook
     * @return clear True if the order was successfully executed, otherwise false.
     */
    function marketBuy(
        address base,
        address quote,
        uint256 quoteAmount,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) public nonReentrant returns (bool clear) {
        // reuse quoteAmount variable as minRequired from _deposit to avoid stack too deep error
        (uint256 withoutFee, address orderbook) = _deposit(
            base,
            quote,
            0,
            quoteAmount,
            true,
            uid,
            isMaker
        );
        // negate on give if the asset is not the base
        uint256 lmp;
        // reuse withoutFee variable due to stack too deep error
        (withoutFee, lmp, clear) = _limitOrder(
            orderbook,
            withoutFee,
            quote,
            true,
            type(uint256).max,
            n
        );
        // add make order on market price
        _detMake(
            base,
            quote,
            orderbook,
            withoutFee,
            lmp == 0 ? mktPrice(base, quote) : lmp,
            true,
            isMaker
        );
        return true;
    }

    /**
     * @dev Executes a market sell order,
     * sells the base asset for the quote asset at the best available price in the orderbook up to `n` orders,
     * and make an order at the market price.
     * @param base The address of the base asset for the trading pair
     * @param quote The address of the quote asset for the trading pair
     * @param baseAmount The amount of base asset to be sold in the market sell order
     * @param isMaker Boolean indicating if an order should be made at the market price in orderbook
     * @param n The maximum number of orders to match in the orderbook
     * @return clear True if the order was successfully executed, otherwise false.
     */
    function marketSell(
        address base,
        address quote,
        uint256 baseAmount,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) public nonReentrant returns (bool clear) {
        (uint256 withoutFee, address orderbook) = _deposit(
            base,
            quote,
            0,
            baseAmount,
            false,
            uid,
            isMaker
        );
        // negate on give if the asset is not the base
        uint256 lmp;
        // reuse withoutFee variable for storing remaining amount after matching due to stack too deep error
        (withoutFee, lmp, clear) = _limitOrder(
            orderbook,
            withoutFee,
            base,
            false,
            0,
            n
        );
        _detMake(
            base,
            quote,
            orderbook,
            withoutFee,
            lmp == 0 ? mktPrice(base, quote) : lmp,
            false,
            isMaker
        );
        return true;
    }

    /**
     * @dev Executes a market buy order,
     * buys the base asset using the quote asset at the best available price in the orderbook up to `n` orders,
     * and make an order at the market price with quote asset as native Ethereum(or other network currencies).
     * @param base The address of the base asset for the trading pair
     * @param isMaker Boolean indicating if a order should be made at the market price in orderbook
     * @param n The maximum number of orders to match in the orderbook
     * @return bool True if the order was successfully executed, otherwise false.
     */
    function marketBuyETH(
        address base,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) external payable returns (bool) {
        IWETH(WETH).deposit{value: msg.value}();
        return marketBuy(base, WETH, msg.value, isMaker, n, uid);
    }

    /**
     * @dev Executes a market sell order,
     * sells the base asset for the quote asset at the best available price in the orderbook up to `n` orders,
     * and make an order at the market price with base asset as native Ethereum(or other network currencies).
     * @param quote The address of the quote asset for the trading pair
     * @param isMaker Boolean indicating if an order should be made at the market price in orderbook
     * @param n The maximum number of orders to match in the orderbook
     * @return bool True if the order was successfully executed, otherwise false.
     */
    function marketSellETH(
        address quote,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) external payable returns (bool) {
        IWETH(WETH).deposit{value: msg.value}();
        return marketSell(WETH, quote, msg.value, isMaker, n, uid);
    }

    /**
     * @dev Executes a limit buy order,
     * places a limit order in the orderbook for buying the base asset using the quote asset at a specified price,
     * and make an order at the limit price.
     * @param base The address of the base asset for the trading pair
     * @param quote The address of the quote asset for the trading pair
     * @param price The price, base/quote regardless of decimals of the assets in the pair represented with 8 decimals (if 1000, base is 1000x quote)
     * @param quoteAmount The amount of quote asset to be used for the limit buy order
     * @param isMaker Boolean indicating if an order should be made at the limit price
     * @param n The maximum number of orders to match in the orderbook
     * @return clear True if the order was successfully executed, otherwise false.
     */
    function limitBuy(
        address base,
        address quote,
        uint256 price,
        uint256 quoteAmount,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) public nonReentrant returns (bool clear) {
        (uint256 withoutFee, address orderbook) = _deposit(
            base,
            quote,
            price,
            quoteAmount,
            true,
            uid,
            isMaker
        );
        // negate on give if the asset is not the base
        uint256 lmp;
        // reuse withoutFee variable for storing remaining amount after matching due to stack too deep error
        (withoutFee, lmp, clear) = _limitOrder(
            orderbook,
            withoutFee,
            quote,
            true,
            price,
            n
        );

        _detMake(
            base,
            quote,
            orderbook,
            withoutFee,
            clear ? price : lmp == 0 ? price : lmp,
            true,
            isMaker
        );
        return true;
    }

    /**
     * @dev Executes a limit sell order,
     * places a limit order in the orderbook for selling the base asset for the quote asset at a specified price,
     * and makes an order at the limit price.
     * @param base The address of the base asset for the trading pair
     * @param quote The address of the quote asset for the trading pair
     * @param price The price, base/quote regardless of decimals of the assets in the pair represented with 8 decimals (if 1000, base is 1000x quote)
     * @param baseAmount The amount of base asset to be used for the limit sell order
     * @param isMaker Boolean indicating if an order should be made at the limit price
     * @param n The maximum number of orders to match in the orderbook
     * @return clear  True if the order was successfully executed, otherwise false.
     */
    function limitSell(
        address base,
        address quote,
        uint256 price,
        uint256 baseAmount,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) public nonReentrant returns (bool clear) {
        (uint256 withoutFee, address orderbook) = _deposit(
            base,
            quote,
            price,
            baseAmount,
            false,
            uid,
            isMaker
        );
        // negate on give if the asset is not the base
        uint256 lmp;
        // reuse withoutFee variable for storing remaining amount after matching due to stack too deep error
        (withoutFee, lmp, clear) = _limitOrder(
            orderbook,
            withoutFee,
            base,
            false,
            price,
            n
        );
        _detMake(
            base,
            quote,
            orderbook,
            withoutFee,
            clear ? price : lmp == 0 ? price : lmp,
            false,
            isMaker
        );
        return true;
    }

    /**
     * @dev Executes a limit buy order,
     * places a limit order in the orderbook for buying the base asset using the quote asset at a specified price,
     * and make an order at the limit price with quote asset as native Ethereum(or network currencies).
     * @param base The address of the base asset for the trading pair
     * @param isMaker Boolean indicating if a order should be made at the market price in orderbook
     * @param n The maximum number of orders to match in the orderbook
     * @return bool True if the order was successfully executed, otherwise false.
     */
    function limitBuyETH(
        address base,
        uint256 price,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) external payable returns (bool) {
        IWETH(WETH).deposit{value: msg.value}();
        return limitBuy(base, WETH, price, msg.value, isMaker, n, uid);
    }

    /**
     * @dev Executes a limit sell order,
     * places a limit order in the orderbook for selling the base asset for the quote asset at a specified price,
     * and makes an order at the limit price with base asset as native Ethereum(or network currencies).
     * @param quote The address of the quote asset for the trading pair
     * @param isMaker Boolean indicating if an order should be made at the market price in orderbook
     * @param n The maximum number of orders to match in the orderbook
     * @return bool True if the order was successfully executed, otherwise false.
     */
    function limitSellETH(
        address quote,
        uint256 price,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) external payable returns (bool) {
        IWETH(WETH).deposit{value: msg.value}();
        return limitSell(WETH, quote, price, msg.value, isMaker, n, uid);
    }

    /**
     * @dev Creates an orderbook for a new trading pair and returns its address
     * @param base The address of the base asset for the trading pair
     * @param quote The address of the quote asset for the trading pair
     * @return book The address of the newly created orderbook
     */
    function addPair(
        address base,
        address quote
    ) public returns (address book) {
        // create orderbook for the pair
        address orderBook = IOrderbookFactory(orderbookFactory).createBook(
            base,
            quote
        );
        emit PairAdded(orderBook, base, quote);
        return orderBook;
    }

    /**
     * @dev Cancels an order in an orderbook by the given order ID and order type.
     * @param orderbook The address of the orderbook to cancel the order in
     * @param price The price of the order to cancel
     * @param orderId The ID of the order to cancel
     * @param isBid Boolean indicating if the order to cancel is an ask order
     * @return bool True if the order was successfully canceled, otherwise false.
     */
    function cancelOrder(
        address orderbook,
        uint256 price,
        uint32 orderId,
        bool isBid,
        uint32 uid
    ) public nonReentrant returns (bool) {
        (address base, address quote) = IOrderbookFactory(orderbookFactory)
            .getBaseQuote(orderbook);

        uint256 remaining = IOrderbook(orderbook).cancelOrder(
            isBid,
            price,
            orderId,
            msg.sender
        );
        // decrease point from orderbook
        if (uid != 0 && IRevenue(feeTo).isReportable(msg.sender, uid)) {
            // report cancelation to accountant
            IRevenue(feeTo).report(uid, isBid ? quote : base, remaining, false);
            // refund fee from treasury to sender
            IRevenue(feeTo).refundFee(
                msg.sender,
                isBid ? quote : base,
                (remaining * 100) / feeDenom
            );
        }

        emit OrderCanceled(orderbook, orderId, isBid, msg.sender);
        return true;
    }

    function cancelOrders(
        address[] memory orderbook,
        uint256[] memory prices,
        uint32[] memory orderIds,
        bool[] memory isBid,
        uint32 uid
    ) external returns (bool) {
        for (uint32 i = 0; i < orderIds.length; i++) {
            cancelOrder(orderbook[i], prices[i], orderIds[i], isBid[i], uid);
        }
        return true;
    }

    /**
     * @dev Cancels an order in an orderbook by the given order ID and order type.
     * @param base The address of the base asset for the trading pair
     * @param quote The address of the quote asset for the trading pair
     * @param price The price of the order to rematch
     * @param orderId The ID of the order to cancel
     * @param isBid Boolean indicating if the order to cancel is an ask order
     * @param uid The ID of the user
     * @return bool True if the order was successfully rematched, otherwise false.
     */
    function rematchOrder(
        address base,
        address quote,
        uint256 price,
        uint32 orderId,
        bool isBid,
        bool isMarket,
        bool isMaker,
        uint32 n,
        uint32 uid
    ) external nonReentrant returns (bool) {
        address orderbook = IOrderbookFactory(orderbookFactory).getBookByPair(
            base,
            quote
        );
        uint256 remaining = IOrderbook(orderbook).cancelOrder(
            isBid,
            price,
            orderId,
            msg.sender
        );
        if (isBid) {
            if (isMarket) {
                return marketBuy(base, quote, remaining, isMaker, n, uid);
            } else {
                return limitBuy(base, quote, price, remaining, isMaker, n, uid);
            }
        } else {
            if (isMarket) {
                return marketSell(base, quote, remaining, isMaker, n, uid);
            } else {
                return
                    limitSell(base, quote, price, remaining, isMaker, n, uid);
            }
        }
    }

    /**
     * @dev Returns the address of the orderbook with the given ID.
     * @param id The ID of the orderbook to retrieve.
     * @return The address of the orderbook.
     */
    function getOrderbookById(uint256 id) external view returns (address) {
        return IOrderbookFactory(orderbookFactory).getBook(id);
    }

    /**
     * @dev Returns the base and quote asset addresses for the given orderbook.
     * @param orderbook The address of the orderbook to retrieve the base and quote asset addresses for.
     * @return base The address of the base asset.
     * @return quote The address of the quote asset.
     */
    function getBaseQuote(
        address orderbook
    ) external view returns (address base, address quote) {
        return IOrderbookFactory(orderbookFactory).getBaseQuote(orderbook);
    }

    /**
     * @dev returns addresses of pairs in OrderbookFactory registry
     * @return pairs list of pairs from start to end
     */
    function getPairs(
        uint256 start,
        uint256 end
    ) external view returns (IOrderbookFactory.Pair[] memory pairs) {
        return IOrderbookFactory(orderbookFactory).getPairs(start, end);
    }

    /**
     * @dev returns addresses of pairs in OrderbookFactory registry
     * @return pairs list of pairs from start to end
     */
    function getPairsWithIds(
        uint256[] memory ids
    ) external view returns (IOrderbookFactory.Pair[] memory pairs) {
        return IOrderbookFactory(orderbookFactory).getPairsWithIds(ids);
    }

    /**
     * @dev returns addresses of pairs in OrderbookFactory registry
     * @return names list of pair names from start to end
     */
    function getPairNames(
        uint256 start,
        uint256 end
    ) external view returns (string[] memory names) {
        return IOrderbookFactory(orderbookFactory).getPairNames(start, end);
    }

    /**
     * @dev returns addresses of pairs in OrderbookFactory registry
     * @return names list of pair names from start to end
     */
    function getPairNamesWithIds(
        uint256[] memory ids
    ) external view returns (string[] memory names) {
        return IOrderbookFactory(orderbookFactory).getPairNamesWithIds(ids);
    }

    /**
     * @dev returns addresses of pairs in OrderbookFactory registry
     * @return mktPrices list of mktPrices from start to end
     */
    function getMktPrices(
        uint256 start,
        uint256 end
    ) external view returns (uint256[] memory mktPrices) {
        IOrderbookFactory.Pair[] memory pairs = IOrderbookFactory(
            orderbookFactory
        ).getPairs(start, end);
        mktPrices = new uint256[](pairs.length);
        for (uint256 i = 0; i < pairs.length; i++) {
            try this.mktPrice(pairs[i].base, pairs[i].quote) returns (
                uint256 price
            ) {
                uint256 p = price;
                mktPrices[i] = p;
            } catch {
                uint256 p = 0;
                mktPrices[i] = p;
            }
        }
        return mktPrices;
    }

    /**
     * @dev returns addresses of pairs in OrderbookFactory registry
     * @return mktPrices list of mktPrices from start to end
     */
    function getMktPricesWithIds(
        uint256[] memory ids
    ) external view returns (uint256[] memory mktPrices) {
        IOrderbookFactory.Pair[] memory pairs = IOrderbookFactory(
            orderbookFactory
        ).getPairsWithIds(ids);
        mktPrices = new uint256[](pairs.length);
        for (uint256 i = 0; i < pairs.length; i++) {
            try this.mktPrice(pairs[i].base, pairs[i].quote) returns (
                uint256 price
            ) {
                uint256 p = price;
                mktPrices[i] = p;
            } catch {
                uint256 p = 0;
                mktPrices[i] = p;
            }
        }
        return mktPrices;
    }

    /**
     * @dev Returns prices in the ask/bid orderbook for the given trading pair.
     * @param base The address of the base asset for the trading pair.
     * @param quote The address of the quote asset for the trading pair.
     * @param isBid Boolean indicating if the orderbook to retrieve prices from is an ask orderbook.
     * @param n The number of prices to retrieve.
     */
    function getPrices(
        address base,
        address quote,
        bool isBid,
        uint32 n
    ) external view returns (uint256[] memory) {
        address orderbook = getBookByPair(base, quote);
        return IOrderbook(orderbook).getPrices(isBid, n);
    }

    /**
     * @dev Returns orders in the ask/bid orderbook for the given trading pair in a price.
     * @param base The address of the base asset for the trading pair.
     * @param quote The address of the quote asset for the trading pair.
     * @param isBid Boolean indicating if the orderbook to retrieve orders from is an ask orderbook.
     * @param price The price to retrieve orders from.
     * @param n The number of orders to retrieve.
     */
    function getOrders(
        address base,
        address quote,
        bool isBid,
        uint256 price,
        uint32 n
    ) external view returns (ExchangeOrderbook.Order[] memory) {
        address orderbook = getBookByPair(base, quote);
        return IOrderbook(orderbook).getOrders(isBid, price, n);
    }

    /**
     * @dev Returns an order in the ask/bid orderbook for the given trading pair with order id.
     * @param base The address of the base asset for the trading pair.
     * @param quote The address of the quote asset for the trading pair.
     * @param isBid Boolean indicating if the orderbook to retrieve orders from is an ask orderbook.
     * @param orderId The order id to retrieve.
     */
    function getOrder(
        address base,
        address quote,
        bool isBid,
        uint32 orderId
    ) external view returns (ExchangeOrderbook.Order memory) {
        address orderbook = getBookByPair(base, quote);
        return IOrderbook(orderbook).getOrder(isBid, orderId);
    }

    /**
     * @dev Returns order ids in the ask/bid orderbook for the given trading pair in a price.
     * @param base The address of the base asset for the trading pair.
     * @param quote The address of the quote asset for the trading pair.
     * @param isBid Boolean indicating if the orderbook to retrieve orders from is an ask orderbook.
     * @param price The price to retrieve orders from.
     * @param n The number of order ids to retrieve.
     */
    function getOrderIds(
        address base,
        address quote,
        bool isBid,
        uint256 price,
        uint32 n
    ) external view returns (uint32[] memory) {
        address orderbook = getBookByPair(base, quote);
        return IOrderbook(orderbook).getOrderIds(isBid, price, n);
    }

    /**
     * @dev Returns the address of the orderbook for the given base and quote asset addresses.
     * @param base The address of the base asset for the trading pair.
     * @param quote The address of the quote asset for the trading pair.
     * @return book The address of the orderbook.
     */
    function getBookByPair(
        address base,
        address quote
    ) public view returns (address book) {
        return IOrderbookFactory(orderbookFactory).getBookByPair(base, quote);
    }

    function heads(
        address base,
        address quote
    ) external view returns (uint256 bidHead, uint256 askHead) {
        address orderbook = getBookByPair(base, quote);
        return IOrderbook(orderbook).heads();
    }

    function mktPrice(
        address base,
        address quote
    ) public view returns (uint256) {
        address orderbook = getBookByPair(base, quote);
        return IOrderbook(orderbook).mktPrice();
    }

    /**
     * @dev return converted amount from base to quote or vice versa
     * @param base address of base asset
     * @param quote address of quote asset
     * @param amount amount of base or quote asset
     * @param isBid if true, amount is quote asset, otherwise base asset
     * @return converted converted amount from base to quote or vice versa.
     * if true, amount is quote asset, otherwise base asset
     * if orderbook does not exist, return 0
     */
    function convert(
        address base,
        address quote,
        uint256 amount,
        bool isBid
    ) public view returns (uint256 converted) {
        address orderbook = getBookByPair(base, quote);
        if (base == quote) {
            return amount;
        } else if (orderbook == address(0)) {
            return 0;
        } else {
            return IOrderbook(orderbook).assetValue(amount, isBid);
        }
    }

    /**
     * @dev Internal function which makes an order on the orderbook.
     * @param orderbook The address of the orderbook contract for the trading pair
     * @param withoutFee The remaining amount of the asset after the market order has been executed
     * @param price The price, base/quote regardless of decimals of the assets in the pair represented with 8 decimals (if 1000, base is 1000x quote)
     * @param isBid Boolean indicating if the order is a buy (false) or a sell (true)
     */
    function _makeOrder(
        address orderbook,
        uint256 withoutFee,
        uint256 price,
        bool isBid
    ) internal {
        uint32 id;
        // create order
        if (isBid) {
            id = IOrderbook(orderbook).placeBid(msg.sender, price, withoutFee);
        } else {
            id = IOrderbook(orderbook).placeAsk(msg.sender, price, withoutFee);
        }
        emit OrderPlaced(orderbook, msg.sender, price, isBid, id);
    }

    /**
     * @dev Match bid if `isBid` is true, match ask if `isBid` is false.
     */
    function _matchAt(
        address orderbook,
        address give,
        bool isBid,
        uint256 amount,
        uint256 price,
        uint32 i,
        uint32 n
    ) internal returns (uint256 remaining, uint32 k) {
        if (n > 20) {
            revert TooManyMatches(n);
        }
        remaining = amount;
        while (
            remaining > 0 &&
            !IOrderbook(orderbook).isEmpty(!isBid, price) &&
            i < n
        ) {
            // fpop OrderLinkedList by price, if ask you get bid order, if bid you get ask order. Get quote asset on bid order on buy, base asset on ask order on sell
            (uint32 orderId, uint256 required) = IOrderbook(orderbook).fpop(
                !isBid,
                price,
                remaining
            );
            // order exists, and amount is not 0
            if (remaining <= required) {
                // set last matching price
                IOrderbook(orderbook).setLmp(price);
                // execute order
                TransferHelper.safeTransfer(give, orderbook, remaining);
                address owner = IOrderbook(orderbook).execute(
                    orderId,
                    !isBid,
                    price,
                    msg.sender,
                    remaining
                );
                // emit event order matched
                emit OrderMatched(
                    orderbook,
                    orderId,
                    isBid,
                    msg.sender,
                    owner,
                    remaining,
                    price
                );
                // end loop as remaining is 0
                return (0, n);
            }
            // order is null
            else if (required == 0) {
                ++i;
                continue;
            }
            // remaining >= depositAmount
            else {
                remaining -= required;
                TransferHelper.safeTransfer(give, orderbook, required);
                address owner = IOrderbook(orderbook).execute(
                    orderId,
                    !isBid,
                    price,
                    msg.sender,
                    required
                );
                // emit event order matched
                emit OrderMatched(
                    orderbook,
                    orderId,
                    isBid,
                    msg.sender,
                    owner,
                    required,
                    price
                );
                ++i;
            }
        }
        k = i;
        return (remaining, k);
    }

    /**
     * @dev Executes limit order by matching orders in the orderbook based on the provided limit price.
     * @param orderbook The address of the orderbook to execute the limit order on.
     * @param amount The amount of asset to trade.
     * @param give The address of the asset to be traded.
     * @param isBid True if the order is an ask (sell) order, false if it is a bid (buy) order.
     * @param limitPrice The maximum price at which the order can be executed.
     * @param n The maximum number of matches to execute.
     * @return remaining The remaining amount of asset that was not traded.
     */
    function _limitOrder(
        address orderbook,
        uint256 amount,
        address give,
        bool isBid,
        uint256 limitPrice,
        uint32 n
    ) internal returns (uint256 remaining, uint256 lmp, bool clear) {
        remaining = amount;
        lmp = 0;
        uint32 i = 0;
        if (isBid) {
            // check if there is any matching ask order until matching ask order price is lower than the limit bid Price
            uint256 askHead = IOrderbook(orderbook).askHead();
            while (
                remaining > 0 && askHead != 0 && askHead <= limitPrice && i < n
            ) {
                lmp = askHead;
                (remaining, i) = _matchAt(
                    orderbook,
                    give,
                    isBid,
                    remaining,
                    askHead,
                    i,
                    n
                );
                // i == 0 when orders are all empty and only head price is left
                askHead = i == 0 ? 0 : IOrderbook(orderbook).askHead();
            }
            // set last match price
            if (lmp != 0) {
                IOrderbook(orderbook).setLmp(lmp);
            }
            return (remaining, lmp, askHead == 0);
        } else {
            // check if there is any maching bid order until matching bid order price is higher than the limit ask price
            uint256 bidHead = IOrderbook(orderbook).bidHead();
            while (
                remaining > 0 && bidHead != 0 && bidHead >= limitPrice && i < n
            ) {
                lmp = bidHead;
                (remaining, i) = _matchAt(
                    orderbook,
                    give,
                    isBid,
                    remaining,
                    bidHead,
                    i,
                    n
                );
                // i == 0 when orders are all empty and only head price is left
                bidHead = i == 0 ? 0 : IOrderbook(orderbook).bidHead();
            }
            // set last match price
            if (lmp != 0) {
                IOrderbook(orderbook).setLmp(lmp);
            }
            return (remaining, lmp, bidHead == 0);
        }
    }

    /**
     * @dev Determines if an order can be made at the market price,
     * and if so, makes the an order on the orderbook.
     * If an order cannot be made, transfers the remaining asset to either the orderbook or the user.
     * @param base The address of the base asset for the trading pair
     * @param quote The address of the quote asset for the trading pair
     * @param orderbook The address of the orderbook contract for the trading pair
     * @param remaining The remaining amount of the asset after the market order has been taken
     * @param price The price used to determine if an order can be made
     * @param isBid Boolean indicating if the order was a buy (true) or a sell (false)
     * @param isMaker Boolean indicating if an order is for storing in orderbook
     */
    function _detMake(
        address base,
        address quote,
        address orderbook,
        uint256 remaining,
        uint256 price,
        bool isBid,
        bool isMaker
    ) internal {
        if (remaining > 0) {
            address stopTo = isMaker ? orderbook : msg.sender;
            TransferHelper.safeTransfer(
                isBid ? quote : base,
                stopTo,
                remaining
            );
            if (isMaker) _makeOrder(orderbook, remaining, price, isBid);
        }
    }

    /**
     * @dev Deposit amount of asset to the contract with the given asset information and subtracts the fee.
     * @param base The address of the base asset.
     * @param quote The address of the quote asset.
     * @param amount The amount of asset to deposit.
     * @param isBid Whether it is an ask order or not.
     * If ask, the quote asset is transferred to the contract.
     * @return withoutFee The amount of asset without the fee.
     * @return book The address of the orderbook for the given asset pair.
     */
    function _deposit(
        address base,
        address quote,
        uint256 price,
        uint256 amount,
        bool isBid,
        uint32 uid,
        bool isMaker
    ) internal returns (uint256 withoutFee, address book) {
        // get orderbook address from the base and quote asset
        book = getBookByPair(base, quote);
        if (book == address(0)) {
            book = addPair(base, quote);
        }
        // check if amount is valid in case of both market and limit
        uint256 converted = _convert(book, price, amount, !isBid);

        if (converted == 0) {
            revert OrderSizeTooSmall(amount, _convert(book, price, 1, isBid));
        }
        // check if sender has uid
        uint256 fee = _fee(base, quote, amount, isBid, uid, isMaker);
        withoutFee = amount - fee;
        if (isBid) {
            // transfer input asset give user to this contract
            if (quote != WETH) {
                TransferHelper.safeTransferFrom(
                    quote,
                    msg.sender,
                    address(this),
                    amount
                );
            }
            TransferHelper.safeTransfer(quote, feeTo, fee);
        } else {
            // transfer input asset give user to this contract
            if (base != WETH) {
                TransferHelper.safeTransferFrom(
                    base,
                    msg.sender,
                    address(this),
                    amount
                );
            }
            TransferHelper.safeTransfer(base, feeTo, fee);
        }

        return (withoutFee, book);
    }

    function _fee(
        address base,
        address quote,
        uint256 amount,
        bool isBid,
        uint32 uid,
        bool isMaker
    ) internal returns (uint256 fee) {
        if (uid != 0 && IRevenue(feeTo).isReportable(msg.sender, uid)) {
            uint32 feeNum = IRevenue(feeTo).feeOf(uid, isMaker);
            // report fee to accountant
            IRevenue(feeTo).report(uid, isBid ? quote : base, amount, true);
            return (amount * feeNum) / feeDenom;
        } else {
            return amount / 1000;
        }
    }

    /**
     * @dev return converted amount from base to quote or vice versa
     * @param orderbook address of orderbook
     * @param price price of base/quote regardless of decimals of the assets in the pair represented with 8 decimals (if 1000, base is 1000x quote) proposed by a trader
     * @param amount amount of base or quote asset
     * @param isBid if true, amount is quote asset, otherwise base asset
     * @return converted converted amount from base to quote or vice versa.
     * if true, amount is quote asset, otherwise base asset
     * if orderbook does not exist, return 0
     */
    function _convert(
        address orderbook,
        uint256 price,
        uint256 amount,
        bool isBid
    ) internal view returns (uint256 converted) {
        if (orderbook == address(0)) {
            return 0;
        } else {
            return
                price == 0
                    ? IOrderbook(orderbook).assetValue(amount, isBid)
                    : IOrderbook(orderbook).convert(price, amount, isBid);
        }
    }
}

// File: contracts/safex/interfaces/IOrderbookFactory.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

interface IOrderbookFactory {
    struct Pair {
        address base;
        address quote;
    }

    function createBook(address bid_, address ask_) external returns (address orderbook);

    function getBook(uint256 bookId_) external view returns (address orderbook);

    function getBookByPair(address base, address quote) external view returns (address book);

    function getBaseQuote(address orderbook) external view returns (address base, address quote);

    function allPairsLength() external view returns (uint256);

    /// Address of a manager
    function engine() external view returns (address);

    function getPairs(uint256 start, uint256 end) external view returns (Pair[] memory);

    function getPairsWithIds(uint256[] memory ids) external view returns (Pair[] memory);

    function getPairNames(uint256 start, uint256 end) external view returns (string[] memory names);

    function getPairNamesWithIds(uint256[] memory ids) external view returns (string[] memory names);
}

// File: contracts/safex/interfaces/IOrderbook.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

import "../libraries/ExchangeOrderbook.sol";

interface IOrderbook {
    function initialize(uint256 id, address base_, address quote_, address engine_) external;

    function fpop(bool isBid, uint256 price, uint256 remaining) external returns (uint32 orderId, uint256 required);

    function setLmp(uint256 lmp) external;

    function mktPrice() external view returns (uint256);

    function assetValue(uint256 amount, bool isBid) external view returns (uint256 converted);

    function isEmpty(bool isBid, uint256 price) external view returns (bool);

    function getRequired(bool isBid, uint256 price, uint32 orderId) external view returns (uint256 required);

    function convert(uint256 price, uint256 amount, bool isBid) external view returns (uint256 converted);

    function placeAsk(address owner, uint256 price, uint256 amount) external returns (uint32 orderId);

    function placeBid(address owner, uint256 price, uint256 amount) external returns (uint32 orderId);

    function cancelOrder(bool isBid, uint256 price, uint32 orderId, address owner)
        external
        returns (uint256 remaining);

    function execute(uint32 orderId, bool isBid, uint256 price, address sender, uint256 amount)
        external
        returns (address owner);

    function heads() external view returns (uint256 bidHead, uint256 askHead);

    function askHead() external view returns (uint256);

    function bidHead() external view returns (uint256);

    function getPrices(bool isBid, uint32 n) external view returns (uint256[] memory);

    function getOrders(bool isBid, uint256 price, uint32 n) external view returns (ExchangeOrderbook.Order[] memory);

    function getOrder(bool isBid, uint32 orderId) external view returns (ExchangeOrderbook.Order memory);

    function getOrderIds(bool isBid, uint256 price, uint32 n) external view returns (uint32[] memory);

    function getBaseQuote() external view returns(address base, address quote);
}

// File: contracts/safex/libraries/TransferHelper.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

// helper methods for interacting with ERC20 tokens and sending ETH that do not consistently return true/false
library TransferHelper {
    function safeApprove(address token, address to, uint256 value) internal {
        // bytes4(keccak256(bytes("approve(address,uint256)")));
        (bool success, bytes memory data) = token.call(abi.encodeWithSelector(0x095ea7b3, to, value));
        require(success && (data.length == 0 || abi.decode(data, (bool))), "AF");
    }

    function safeTransfer(address token, address to, uint256 value) internal {
        // bytes4(keccak256(bytes("transfer(address,uint256)")));
        (bool success, bytes memory data) = token.call(abi.encodeWithSelector(0xa9059cbb, to, value));
        require(success && (data.length == 0 || abi.decode(data, (bool))), "TF");
    }

    function safeTransferFrom(address token, address from, address to, uint256 value) internal {
        // bytes4(keccak256(bytes("transferFrom(address,address,uint256)")));
        (bool success, bytes memory data) = token.call(abi.encodeWithSelector(0x23b872dd, from, to, value));
        require(success && (data.length == 0 || abi.decode(data, (bool))), "TFF");
    }

    function safeTransferETH(address to, uint256 value) internal {
        (bool success,) = to.call{value: value}(new bytes(0));
        require(success, "ETF");
    }

    function decimals(address token) internal view returns (uint8) {
        // bytes4(keccak256(bytes("decimals()")));
        (bool success, bytes memory data) = token.staticcall(abi.encodeWithSelector(0x313ce567));
        require(success, "DF");
        return abi.decode(data, (uint8));
    }
}

// File: node_modules/@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol



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

pragma solidity ^0.8.2;

import "../../utils/AddressUpgradeable.sol";

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

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

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

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

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

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

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

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

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

// File: contracts/safex/interfaces/IWETH.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

interface IWETH {
    function deposit() external payable;

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

    function withdraw(uint256) external;
}

// File: node_modules/@openzeppelin/contracts/security/ReentrancyGuard.sol



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

pragma solidity ^0.8.0;

/**
 * @dev Contract module that helps prevent reentrant calls to a function.
 *
 * Inheriting from `ReentrancyGuard` will make the {nonReentrant} modifier
 * available, which can be applied to functions to make sure there are no nested
 * (reentrant) calls to them.
 *
 * Note that because there is a single `nonReentrant` guard, functions marked as
 * `nonReentrant` may not call one another. This can be worked around by making
 * those functions `private`, and then adding `external` `nonReentrant` entry
 * points to them.
 *
 * TIP: If you would like to learn more about reentrancy and alternative ways
 * to protect against it, check out our blog post
 * https://blog.openzeppelin.com/reentrancy-after-istanbul/[Reentrancy After Istanbul].
 */
abstract contract ReentrancyGuard {
    // Booleans are more expensive than uint256 or any type that takes up a full
    // word because each write operation emits an extra SLOAD to first read the
    // slot's contents, replace the bits taken up by the boolean, and then write
    // back. This is the compiler's defense against contract upgrades and
    // pointer aliasing, and it cannot be disabled.

    // The values being non-zero value makes deployment a bit more expensive,
    // but in exchange the refund on every call to nonReentrant will be lower in
    // amount. Since refunds are capped to a percentage of the total
    // transaction's gas, it is best to keep them low in cases like this one, to
    // increase the likelihood of the full refund coming into effect.
    uint256 private constant _NOT_ENTERED = 1;
    uint256 private constant _ENTERED = 2;

    uint256 private _status;

    constructor() {
        _status = _NOT_ENTERED;
    }

    /**
     * @dev Prevents a contract from calling itself, directly or indirectly.
     * Calling a `nonReentrant` function from another `nonReentrant`
     * function is not supported. It is possible to prevent this from happening
     * by making the `nonReentrant` function external, and making it call a
     * `private` function that does the actual work.
     */
    modifier nonReentrant() {
        _nonReentrantBefore();
        _;
        _nonReentrantAfter();
    }

    function _nonReentrantBefore() private {
        // On the first call to nonReentrant, _status will be _NOT_ENTERED
        require(_status != _ENTERED, "ReentrancyGuard: reentrant call");

        // Any calls to nonReentrant after this point will fail
        _status = _ENTERED;
    }

    function _nonReentrantAfter() private {
        // By storing the original value once again, a refund is triggered (see
        // https://eips.ethereum.org/EIPS/eip-2200)
        _status = _NOT_ENTERED;
    }

    /**
     * @dev Returns true if the reentrancy guard is currently set to "entered", which indicates there is a
     * `nonReentrant` function in the call stack.
     */
    function _reentrancyGuardEntered() internal view returns (bool) {
        return _status == _ENTERED;
    }
}

// File: contracts/safex/libraries/ExchangeOrderbook.sol



// SPDX-License-Identifier: BUSL-1.1

pragma solidity ^0.8.17;

library ExchangeOrderbook {
  // Order struct
  struct Order {
    address owner;
    uint256 depositAmount;
  }

  // Order Linked List
  struct OrderStorage {
    /// Hashmap-style linked list of prices to route orders
    // key: price, value: order indices linked hashmap
    mapping(uint256 => mapping(uint32 => uint32)) list;
    mapping(uint32 => Order) orders;
    mapping(uint32 => bool) canceled;
    // Head of the linked list(i.e. lowest ask price / highest bid price)
    mapping(uint256 => uint32) head;
    // count of the orders, used for array allocation
    uint32 count;
    address engine;
  }

  // for orders, lower depositAmount are next, higher depositAmount comes first
  function _insertId(
    OrderStorage storage self,
    uint256 price,
    uint32 id,
    uint256 amount
  ) internal {
    uint32 last = 0;
    uint32 head = self.head[price];
    mapping(uint32 => uint32) storage list = self.list[price];
    mapping(uint32 => Order) storage orders = self.orders;
    // insert order to the linked list
    // if the list is empty
    if (head == 0 || amount > self.orders[head].depositAmount) {
      self.head[price] = id;
      list[id] = head;
      return;
    }
    // Traverse through list until we find the right spot where id's deposit amount is higher than next
    while (head != 0) {
      // what if order deposit amount is bigger than the next order's deposit amount?
      uint32 next = list[head];
      if (amount < orders[next].depositAmount) {
        // Keep traversing
        head = list[head];
        last = next;
      } else if (amount > orders[next].depositAmount) {
        // This is either order is cancelled or order is at the end of the list
        if (orders[next].depositAmount == 0) {
          // what if next order is canceled and order id still stays in the list?
          // if order is canceled and stays in the list, there is at least a next order in the list
          if (self.canceled[next]) {
            // remove index of cancelled order
            list[head] = list[next];
            delete list[next];
            delete self.canceled[next];
            // skip canceled order
            last = head;
            head = list[head];
          } else {
            // Insert order at the end of the list
            list[head] = id;
            list[id] = 0;
            return;
          }
        }
        // Insert order in the middle of the list
        list[head] = id;
        list[id] = next;
        return;
      }
      // what if there is same order with same deposit amount?
      else if (amount == orders[next].depositAmount) {
        list[id] = list[next];
        list[next] = id;
        return;
      }
    }
  }

  // pop front
  function _fpop(
    OrderStorage storage self,
    uint256 price
  ) internal returns (uint256) {
    uint32 first = self.head[price];
    if (first == 0) {
      return 0;
    }
    uint32 next = self.list[price][first];
    self.head[price] = next;
    delete self.list[price][first];
    return first;
  }

  function _createOrder(
    OrderStorage storage self,
    address owner,
    uint256 depositAmount
  ) internal returns (uint32 id) {
    Order memory order = Order({ owner: owner, depositAmount: depositAmount });
    // prevent order overflow, order id must start from 1
    self.count = self.count == 0 || self.count == type(uint32).max
      ? 1
      : self.count + 1;
    self.orders[self.count] = order;
    return self.count;
  }

  function _decreaseOrder(
    OrderStorage storage self,
    uint256 price,
    uint32 id,
    uint256 amount,
    uint256 dust
  ) internal returns (uint256) {
    uint256 decreased = self.orders[id].depositAmount - amount;
    // remove dust
    if (decreased <= dust) {
      decreased = self.orders[id].depositAmount;
      _deleteOrder(self, price, id);
      return decreased;
    } else {
      self.orders[id].depositAmount = decreased;
      return amount;
    }
  }

  function _deleteOrder(
    OrderStorage storage self,
    uint256 price,
    uint32 id
  ) internal {
    uint32 last = 0;
    uint32 head = self.head[price];
    uint32 next;
    uint16 i;
    mapping(uint32 => uint32) storage list = self.list[price];
    // delete id in the order linked list
    if (head == id) {
      self.head[price] = list[head];
      delete list[id];
    } else {
      // search for the order id in the linked list
      while (head != 0 && i < 30) {
        next = list[head];
        if (next == id) {
          list[head] = list[next];
          delete list[id];
          break;
        }
        last = head;
        head = next;
        ++i;
      }
    }
    // delete order
    delete self.orders[id];
    // add canceled info to see if the order was deleted in the list
    if (i == 30) {
      self.canceled[id] = true;
    }
    return;
  }

  // show n order ids at the price in the orderbook
  function _getOrderIds(
    OrderStorage storage self,
    uint256 price,
    uint32 n
  ) internal view returns (uint32[] memory) {
    uint32 head = self.head[price];
    uint32[] memory orders = new uint32[](n);
    uint32 i = 0;
    while (head != 0 && i < n) {
      orders[i] = head;
      head = self.list[price][head];
      i++;
    }
    return orders;
  }

  function _getOrders(
    OrderStorage storage self,
    uint256 price,
    uint32 n
  ) internal view returns (Order[] memory) {
    uint32 head = self.head[price];
    Order[] memory orders = new Order[](n);
    uint32 i = 0;
    while (head != 0 && i < n) {
      orders[i] = self.orders[head];
      head = self.list[price][head];
      i++;
    }
    return orders;
  }

  function _head(
    OrderStorage storage self,
    uint256 price
  ) internal view returns (uint32) {
    return self.head[price];
  }

  function _isEmpty(
    OrderStorage storage self,
    uint256 price
  ) internal view returns (bool) {
    return self.head[price] == 0;
  }

  function _next(
    OrderStorage storage self,
    uint256 price,
    uint32 curr
  ) internal view returns (uint32) {
    return self.list[price][curr];
  }

  function _getOrder(
    OrderStorage storage self,
    uint32 id
  ) internal view returns (Order memory) {
    return self.orders[id];
  }
}

// File: node_modules/@openzeppelin/contracts-upgradeable/utils/AddressUpgradeable.sol



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

pragma solidity ^0.8.1;

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

        return account.code.length > 0;
    }

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

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

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

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

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

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

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

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

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

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

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

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

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