Repository

https://github.com/igormuba/DEX/tree/master/Class9

What Will I Learn?

• Filling orders of the same price
• Filling order of different price (respecting the limit sell order)
• Removing a link on the top of the linked list

Requirements

• Internet connection.
• Code editor.
• Browser.

Difficulty

• Advanced.

Tutorial Contents

Introduction

On the previous class, we have finished the function that is designed to remove an item from the queue, that is, for a user to remove it's an order form the book. What it does, actually, is remove all the volume of the order from a user on a token at a price point.

With that, we have finished the functions to store and remove orders. But still, we have one function for the exchange that is very important, but also a bit complex. The buy and sell orders, once called, need, first, to try to fill orders from the other book, doing the best effort to get the best deal for the user.

So, if a user is trying to sell a token (limit order, explained in a previous tutorial) but wants to receive at least a price "x" for his tokens, the exchange will automatically fill his order with the volume of orders on the buy book, but only the buy orders which the price is "greater than, or at least equal to, x". I did a simple implementation for you to understand the logic.

On this tutorial, I will go in depth and explain the logic behind "filling" an order, before storing the remaining (if any) volume left after filling all the volume at the limit price on the other book. Sounds complicated, but the logic is simple once you understand how limit orders work. The implementation is a bit big but also, nothing that would require you to be a genius to do. Because of how big it is I will explain in depth the implementation in logic here, applied to the sell order, and on the next tutorial briefly explain how to do the same on the buying side, and proceed with the testings and demonstrations on how it works in practice.

Previously

We already have a "sell" function, but so far it worked just to store the order in case of none of the volume on the buying book matched the limit price. The function from previous tutorials looks like this, without the logic to fill the buy orders:

function sellToken(address _token, uint _price, uint _amount) public{
//all from here is already implemented
        Token storage loadedToken = tokenList[_token];
        uint ethRequired = _price*_amount;
        
        require(ethRequired>=_amount);
        require(ethRequired>=_price);
        require(tokenBalance[msg.sender][_token]>=_amount);
        require(tokenBalance[msg.sender][_token]-_amount>=0);
        require(ethBalance[msg.sender]+ethRequired>=ethBalance[msg.sender]);
        
        tokenBalance[msg.sender][_token]-=_amount;
        
        if(loadedToken.amountBuyPrices==0||loadedToken.maxBuyPrice<_price){
            storeSellOrder(_token, _price, _amount, msg.sender);
//all until here is already implemented
        }else {
            //here is where the logic to fill the buy book goes
        }
}

So, as you can see, in case we don't fall into the if statement, that means there is volume on the buy book to fill our order, even if just a tiny bit, it does not need to be filled completely, as, in the end, we will store the remaining!

Now, inside the else, we will need two loops, the outer (first) will run from the highest buy price to the lowest (the limit sell given) until the buying price is lower than the limit price by the seller, or until the order is completely filled. The inner (second) will run through the queue of orders at the price given on the run of the outer loop.

The outer loop

Inside the else of the sell function, we add:

uint sellPrice = loadedToken.maxBuyPrice;
uint remainingAmount=_amount;
uint offerPointer;
while (sellPrice>=_price && remainingAmount > 0){

    }
if (remainingAmount>0){
    sellToken(_token, _price, remainingAmount);
}

The sellPrice is the current price (changes accordingly to the outer loop), it starts at the highest price of the buy book.
remainingAmount is the volume left of the sell order that still needs to be filled by the buy orders, it starts at the full volume of the order and goes down as it is filled. Later, if there is a remaining that couldn't be filled, it will be stored as a sell order on the sell book.
offerPointer will be used to iterate through the offers on the queue of the price on the inner loop (it will be defined by the outer loop at each run).

As said previously, the outer loop will run from price to price, from the highest price on the buy book, until it or reaches the limit sell price or it fills all the volume of the sell order.

I will show how the logic inside the outer loop works later.

After the outer loop finishes, we check if there is still volume left on the selling order, if there is, we call the sellToken function again, and it should fall into the if statement that stores the order.

The inner loop

The inner loop, inside the outer one, looks like this:

offerPointer = loadedToken.buyBook[sellPrice].offerPointer;
while(offerPointer<=loadedToken.buyBook[sellPrice].offerLength && remainingAmount>0){

}
sellPrice=loadedToken.maxBuyPrice;

So, inside the outer loop, we start by starting the offerPointer with the pointer of the queue of the of the price order given by the outer loop.

After the inner loop finishes, we update the prices of the token books, more on that later, that is why we do sellPrice=loadedToken.maxBuyPrice;.

Inside the inner loop

Inside the inner loop we have the following structure:

// stores the amount of the volume at the current pointer on the queue of the current price
uint volumeAtPointer = loadedToken.buyBook[sellPrice].offers[offerPointer].amount;
if (volumeAtPointer<=remainingAmount){
//if there will be no buy volume left on this price point after the sell is filled
}else{
//if there will be buy volume left on this price point
}
                    
if(offerPointer==loadedToken.buyBook[sellPrice].offerLength && loadedToken.buyBook[sellPrice].offers[offerPointer].amount==0){
//if the pointer reaches the end of the queue and there is no volume at the current pointer
}
offerPointer++; //increases the pointer

The if (volumeAtPointer<=remainingAmount) means that the code inside will run if the volume of the buy order at the current pointer on the queue of the current price will be completely filled. That is, the sell order is bigger or equal to the buy order, so the stored buy order will be completely filled.

The else from the if above runs otherwise, that means, there is at least something remaining on the stored buy order after the sell is filled.

The last it checks if the queue has ended.

The stored buy order is completely filled.

The first if from the decision branch above does the following:

//the amount of ETH required from the buyer
uint ethRequiredNow = volumeAtPointer*sellPrice;
//requires that the seller has enough tokens to fill the buyer order
require(tokenBalance[msg.sender][_token]>=volumeAtPointer);
//requires that the seller won't underflow
require(tokenBalance[msg.sender][_token]-volumeAtPointer>=0);
//reduces the token balance of the seller first toa void race condition
tokenBalance[msg.sender][_token]-=volumeAtPointer;
//adds the token balance to the buyer
tokenBalance[loadedToken.buyBook[sellPrice].offers[offerPointer].maker][_token]+=volumeAtPointer;
//removes the stored buy order from the queue
loadedToken.buyBook[sellPrice].offers[offerPointer].amount=0;
//adds the ETH to the seller
ethBalance[msg.sender]+=ethRequiredNow;
// moves the pointer
loadedToken.buyBook[sellPrice].offerPointer++;
//reduces the remaining of the order to proceed with the next operations
remainingAmount-=volumeAtPointer;

The above seems pretty straight forward, we fill all the order (this is why the seller is, counter-intuitively, the "passive" here) at that price/pointer, and move to the next pointer and the next operations. A few comments I want to make sure you understand:

• There are many other security checks you need to do, but I have implemented the basics(underflow, overflow, and race condition) so you can be mindful of them, but the security here is not enough for a real decentralized exchange
• Doing ethBalance[msg.sender]+=ethRequiredNow; won't cause, by itself, a race condition because the buy order is already placed, which means the buyer was already deducted from the ETH balance on his account.

The stored order fills the seller and has something left

In this case, the stored buy order is enough to fill all of the seller's order, and still, have something left for the next seller to sell to.

//requires there is a remaining
require(volumeAtPointer-remainingAmount>0);
//the seller defines the amount of ETH moved now
ethRequired = remainingAmount*sellPrice;
//requires that the seller indeed has the tokens to sell
require(tokenBalance[msg.sender][_token]>=remainingAmount);
//reduces the token balance from the seller
tokenBalance[msg.sender][_token]-=remainingAmount;
//reduces the selling volume from the buy order
loadedToken.buyBook[sellPrice].offers[offerPointer].amount-=remainingAmount;
//credits the ETH to the seller
ethBalance[msg.sender]+=ethRequired;
tokenBalance[loadedToken.buyBook[sellPrice].offers[offerPointer].maker][_token]+=remainingAmount;
//"closes" the remaining of the sell order, for the next operations
remainingAmount=0;

Notice that now the "active" order is the seller, that is, the volume of the seller defines how much ETH the operation moves, on the last section the buyer order did that, as that was the smaller one.

Last thing

What is left is for us to update the linked list:

//if all the offers at this price point have been filled
if(offerPointer==loadedToken.buyBook[sellPrice].offerLength && loadedToken.buyBook[sellPrice].offers[offerPointer].amount==0){
//there is one less price (completely filled)
    loadedToken.amountBuyPrices--;
//if we fill all buy orders
    if (sellPrice==loadedToken.buyBook[sellPrice].lowerPrice || loadedToken.buyBook[sellPrice].lowerPrice==0){
//no order left on the book
        loadedToken.maxBuyPrice=0;
    }else {
//removes the price from the linked list
        loadedToken.maxBuyPrice=loadedToken.buyBook[sellPrice].lowerPrice;
//remembers it is the last item on the linked list
        loadedToken.buyBook[loadedToken.buyBook[sellPrice].lowerPrice].higherPrice=loadedToken.maxBuyPrice;
    }
    }
offerPointer++;

What it does is to remove the highest buy price on the list. The loops will keep on running and updating themselves until the order is completely filled and we fall into the statement:

if (remainingAmount>0){
    sellToken(_token, _price, remainingAmount);
}

That will call the function that we are currently in, but this time will go to the if(loadedToken.amountBuyPrices==0||loadedToken.maxBuyPrice<_price) branch, that will store the order on the sell book!

Curriculum

Latest tutorial of the series:

• (Part 9) Decentralized Exchange - Removing Orders/Items From The Queue(PT 8)

First tutorial of the series:

• (Part 1) Decentralized Exchange - Smart Contract API, Order Book And Orders (PT 1)

Beneficiaries

This post has as beneficiaries

• @utopian.pay with 5%
• @steempeak with 1%

using the SteemPeak beneficiary tool