Contract Name:
TrieFactory
Contract Source Code:
// SPDX-License-Identifier: BUSL-1.1
// Central Limit Order Book (CLOB) exchange
// (c) Long Gamma Labs, 2023.
pragma solidity ^0.8.26;
import {Trie} from "./Trie.sol";
import {ITrieFactory} from "./ITrieFactory.sol";
/// @title Trie Factory for Protocol
/// @dev Factory for creating instances of Trie
contract TrieFactory is ITrieFactory {
/// @dev Creates a new Trie
/// @param lob The address to pass to the Trie constructor
/// @return The address of the newly created Trie
function createTrie(address lob) external returns (address) {
Trie trie = new Trie(lob);
return address(trie);
}
}
// SPDX-License-Identifier: BUSL-1.1
// Central Limit Order Book (CLOB) exchange
// (c) Long Gamma Labs, 2023.
pragma solidity ^0.8.26;
import {Errors} from "./Errors.sol";
import {ITrie} from "./ITrie.sol";
struct Node {
uint64 left;
uint64 right;
uint64 total_shares_value_ptr;
}
struct Leaf {
uint64 trader_id;
uint128 remain_shares;
uint64 initial_shares_value_ptr;
}
struct ExecutionResult {
uint128 executed_shares;
uint128 executed_value;
uint128 total_shares;
uint128 total_value;
uint64 right_child;
uint64 xor_map;
}
/// @title Trie data structure for Protocol
/// @dev This contract implements a trie for efficient order management in an on-chain limit order book.
contract Trie is ITrie {
address immutable lob_address;
// Since we have a prefix tree, we can immediately get all the keys in the rightmost branch.
// Each right key represents a part of best_offer, the length of which is determined
// by the non-zero bit in rightmost_map. That is, the number of non-zero bits
// in rightmost_map equals the number of nodes in the rightmost branch.
uint64 public best_offer = 0;
uint64 public rightmost_map = 0x0;
// The rightmost branch is unique: it only stores the total_shares and total_amount of the left child,
// so deleting or adding new nodes can start directly from the corresponding node on the rightmost branch.
uint64 highest_allocated_pointer;
uint64 last_free_pointer;
mapping (uint64 => Leaf) leaves;
mapping (uint64 => Node) nodes;
mapping (uint64 => uint256) arena;
modifier onlyLOBPermission() {
require(msg.sender == lob_address, Errors.Forbidden());
_;
}
constructor(address _lob_address) {
lob_address = _lob_address;
}
/// @dev Adds an order to the order book.
/// @param trader_id The ID of the trader placing the order, must be be greater than 0.
/// @param order_id The ID of the order being placed, must be unique and be pointer to leaf.
/// @param shares The total number of shares in the order, must be greater than 0.
/// @param value The total value of the order, must be greater than 0.
/// All restrictions on parameters must be satisfied by the logic of the LOB contract
function addOrder(uint64 trader_id, uint64 order_id, uint128 shares, uint128 value) virtual public onlyLOBPermission {
uint64 ptr = allocateMemory();
saveSharesValueToArena(ptr, shares, value);
leaves[order_id] = Leaf({
trader_id: trader_id,
remain_shares: shares,
initial_shares_value_ptr: ptr
});
uint256 map = rightmost_map;
if (map == 0x0) {
// This means the trie is empty.
best_offer = order_id;
rightmost_map = 0x1;
return;
}
// We climb the rightmost branch until we go through it all, which means we need to add a new root,
// or to a node that matches our added order_id.
(uint64 node_id, bool success) = findRightmostMatchingNode(order_id);
if (success) {
// We found the node that matches order_id.
addOrderToNodes(order_id, node_id, shares, value);
} else {
// We have reached the root of the tree, we need to add a new node, which will become the new root
// of the tree. New node`s descendant will be new order_id leaf.
// note: node_id here is the root node_id
addOrderAndUpdateRoot(order_id, node_id, shares, value);
}
}
/// @dev Removes an order with a specific order_id associated with a trader identified by order_trader_id.
/// @param order_id The ID of the order to be removed.
/// @param order_trader_id The ID of the trader associated with the order.
/// Only needed for verification purposes.
/// @return total_shares The total number of shares for the order.
/// @return remain_shares The remaining number of shares for the order.
function removeOrder(uint64 order_id, uint64 order_trader_id) virtual public onlyLOBPermission
returns (uint128 total_shares, uint128 remain_shares) {
Leaf memory leaf = leaves[order_id];
require(leaf.trader_id != 0x0, Errors.EmptyOrderError());
// An important validation check for the provided address. It prevents unauthorized order removal.
require(leaf.trader_id == order_trader_id, Errors.WrongOwner());
uint128 total_value;
(total_shares, total_value) = loadSharesValueFromArena(leaf.initial_shares_value_ptr);
remain_shares = leaf.remain_shares;
uint128 remain_value = uint128(uint256(remain_shares) * uint256(total_value) / uint256(total_shares));
// To prevent double claims.
delete leaves[order_id];
freeMemory(leaf.initial_shares_value_ptr);
uint64 local_best_offer = best_offer;
if (order_id > local_best_offer) {
return (total_shares, 0);
}
if (order_id == local_best_offer) {
removeBestOffer();
return (total_shares, remain_shares);
}
(uint64 node_id, bool success) = findRightmostMatchingNode(order_id);
if (!success) {
return (total_shares, 0);
}
bool found = removeOrderFromNodes(order_id, node_id, remain_shares, remain_value);
if (found) {
return (total_shares, remain_shares);
} else {
return (total_shares, 0);
}
}
/// @dev Claims executed shares for an order with a specific order_id associated with a trader identified
/// by order_trader_id. This operation does not remove the order from the order book.
/// @param order_id The ID of the order for which executed shares are being claimed.
/// @param order_trader_id The ID of the trader associated with the order.
/// Only needed for verification purposes.
/// @return executed_shares The number of executed shares for the order.
/// @return remain_shares The remaining number of shares for the order after execution.
function claimExecuted(uint64 order_id, uint64 order_trader_id) virtual public onlyLOBPermission
returns (uint128 executed_shares, uint128 remain_shares) {
Leaf memory leaf = leaves[order_id];
if (leaf.trader_id == 0x0) {
return (0, 0);
}
// An important validation check for the provided address. It prevents unauthorized order claim.
require(leaf.trader_id == order_trader_id, Errors.WrongOwner());
remain_shares = leaf.remain_shares;
(uint128 total_shares, uint128 total_value) = loadSharesValueFromArena(leaf.initial_shares_value_ptr);
uint64 local_best_offer = best_offer;
if (order_id > local_best_offer) {
remain_shares = 0;
} else {
(uint64 node_id, bool success) = findRightmostMatchingNode(order_id);
if (!success || !isOrderInTree(node_id, order_id)) {
remain_shares = 0;
}
}
executed_shares = total_shares - remain_shares;
if (executed_shares == 0) {
return (0, remain_shares);
}
if (remain_shares == 0) {
delete leaves[order_id];
freeMemory(leaf.initial_shares_value_ptr);
} else {
uint128 remain_value = uint128(
uint256(remain_shares) * uint256(total_value) / uint256(total_shares)
);
saveSharesValueToArena(
leaf.initial_shares_value_ptr,
remain_shares,
remain_value
);
}
}
/// @dev Retrieves information about an order based on the given order_id.
/// @param order_id The ID of the order to retrieve information for.
/// @return total_shares The total number of shares for the order.
/// @return remain_shares The remaining number of shares for the order.
/// Unlike removeOrder, it does not require the existence of an order and works even on claimed and canceled
/// orders, returning zeros.
function getOrderInfo(uint64 order_id) public view
returns (uint128 total_shares, uint128 remain_shares) {
Leaf memory leaf = leaves[order_id];
if (leaf.trader_id == 0x0) {
return (0, 0);
}
remain_shares = leaf.remain_shares;
(total_shares, ) = loadSharesValueFromArena(leaf.initial_shares_value_ptr);
// works correctly in case of empty trie too: best_offer = 0x0
if (order_id > best_offer) {
return (total_shares, 0);
}
(uint64 node_id, bool success) = findRightmostMatchingNode(order_id);
if (!success) {
return (total_shares, 0);
}
if (isOrderInTree(node_id, order_id)) {
return (total_shares, remain_shares);
} else {
return (total_shares, 0);
}
}
/// @dev Executes matching orders using a "right" approach, striving to fulfill orders
/// as much as possible towards the right side.
/// @param order_id The price identifier of the order, not associated with a real order ID.
/// @param order_total_shares The total number of shares for the order being executed.
function executeRight(uint64 order_id, uint128 order_total_shares) virtual public onlyLOBPermission
returns (uint128 executed_shares, uint128 executed_value) {
// Conceptually the most complex function in the contract.
// Since we have to rebuild rightmost branch.
uint64 local_best_offer = best_offer;
// Works correctly in case of empty trie too: best_offer = 0x0
if (order_id > local_best_offer) {
return (0, 0);
}
// Here we climb up the rightmost branch, similar to how it happens in findRightmostMatchingNode.
// But, unfortunately, here we can no longer limit yourself to just node_id, and we have to read the node
// completely. This happens because node_id contains information only about the price of orders,
// but not about volumes.
// Starting with rightmost leaf.
Leaf memory leaf = leaves[local_best_offer];
(uint128 initial_shares, uint128 initial_value) = loadSharesValueFromArena(leaf.initial_shares_value_ptr);
uint128 remain_shares = leaf.remain_shares;
if (order_total_shares < remain_shares) {
executed_shares = order_total_shares;
executed_value = uint128(uint256(executed_shares) * uint256(initial_value) / uint256(initial_shares));
// initial_value / initial_shares is exact price
unchecked {
leaf.remain_shares -= executed_shares;
}
leaves[local_best_offer] = leaf;
return (executed_shares, executed_value);
}
// Full execution of rightmost leaf.
executed_shares = remain_shares;
executed_value = uint128(uint256(remain_shares) * uint256(initial_value) / uint256(initial_shares));
uint64 map = rightmost_map;
(uint64 node_id, uint64 k) = calcNextRightMostNodeId(local_best_offer, map);
uint64 xor_map = 0x1;
// Now climbing on nodes.
while (node_id != 0x0) {
// We ascend along the rightmost branch from the bottom and attempt to execute the entire subtree at once.
// Initially, we try to execute the order - the rightmost descendant.
// Then, at each step, we essentially try to execute the entire subtree with the top at the left child
// of the current node on the rightmost branch.
// Since we have a prefix tree, we can guarantee that the keys of all descendants
// of any node are not less than the key of the node itself. To improve this estimation, we can take
// not the node_id of the node itself, but the node_id of its left child.
xor_map ^= k;
Node memory node = nodes[node_id];
uint64 ptr = node.total_shares_value_ptr;
(uint128 node_total_shares, uint128 node_total_value) = loadSharesValueFromArena(ptr);
uint64 price_key = extractKeyFrom(node.left);
// we can fully execute subtree if
if (((order_id ^ 0x1) <= price_key)
// all its leaves has higher or equal price than our order's price
&& // (we are using price_key as lower bound) and
(order_total_shares >= (node_total_shares + executed_shares))
// it has less or equal shares than our order's
) {
// full execution
executed_shares += node_total_shares;
executed_value += node_total_value;
eraseNode(node_id, ptr);
} else {
ExecutionResult memory execution_result = executeRightRec(
order_id, node.left, (order_total_shares - executed_shares)
);
executed_shares += execution_result.executed_shares;
executed_value += execution_result.executed_value;
xor_map ^= execution_result.xor_map;
if (execution_result.right_child != 0x0) {
// we are partially executed, dont need to execute anymore
(node_id, ) = calcNextRightMostNodeId(node_id, map);
if (node_id != 0x0) {
nodes[node_id].right = execution_result.right_child;
}
break;
}
}
(node_id, k) = calcNextRightMostNodeId(node_id, map);
}
if (xor_map != 0x0) {
// we have to change the rightmost map
rightmost_map ^= xor_map;
if (rightmost_map == 0x0) {
best_offer = 0x0;
}
}
}
/// @dev Preview the execution of an order on the right.
/// @param order_id The ID of the order to be executed.
/// @param max_shares The maximum number of shares to execute.
/// @param max_value The maximum value of shares to execute.
/// @return executed_shares The number of shares executed.
/// @return executed_value The value of the executed shares.
function previewExecuteRight(uint64 order_id, uint128 max_shares, uint128 max_value) public view
returns (uint128 executed_shares, uint128 executed_value) {
uint64 local_best_offer = best_offer;
if (order_id > local_best_offer || max_shares == 0 || max_value == 0) {
return (0, 0);
}
uint64 node_id = local_best_offer;
uint64 k = 0x1;
uint64 path_map = rightmost_map ^ 0x1;
// This is a depth-first search implementation. Same idea in assembleOrderbookFromOrders.
while (true) {
if ((node_id & 0x1) == 0x1) {
// leaf case
(uint128 leaf_executed_shares, uint128 leaf_executed_value, bool full) = previewExecuteLeaf(
order_id,
node_id,
max_shares - executed_shares,
max_value - executed_value
);
executed_shares += leaf_executed_shares;
executed_value += leaf_executed_value;
if (!full) {
break;
}
} else {
// node case
(uint128 node_shares, uint128 node_value) = loadSharesValueFromArena(
nodes[node_id].total_shares_value_ptr
);
uint64 price_key = extractKeyFrom(nodes[node_id].left);
// check if we can execute this node fully
if (((order_id ^ 0x1) > price_key)
|| ((max_shares - executed_shares) < node_shares)
|| ((max_value - executed_value) < node_value)
) {
// we cant
unchecked {
k = ~(node_id - 1) & node_id;
}
path_map ^= k;
node_id = nodes[node_id].right;
continue;
} else {
// we can
executed_shares += node_shares;
executed_value += node_value;
}
}
(node_id, k) = calcNextRightMostNodeId(node_id, path_map);
if (node_id == 0x0) {
break;
}
path_map ^= k;
node_id = nodes[node_id].left;
}
}
/// @dev Assembles an order book from the orders in the trie.
/// @param max_price_levels The maximum number of price levels to include in the order book.
/// @return array_price_ids An array of price IDs for each level in the order book.
/// @return array_shares An array of the total shares for each level in the order book.
function assembleOrderbookFromOrders(uint24 max_price_levels) external view
returns (uint24[] memory array_price_ids, uint128[] memory array_shares) {
uint64 local_best_offer = best_offer;
if (local_best_offer == 0x0 || max_price_levels == 0) {
array_price_ids = new uint24[](0);
array_shares = new uint128[](0);
return (array_price_ids, array_shares);
}
array_price_ids = new uint24[](max_price_levels);
array_shares = new uint128[](max_price_levels);
array_price_ids[0] = uint24(local_best_offer >> 40);
uint24 price_level = 0;
uint64 node_id = local_best_offer;
uint64 k = 0x1;
uint64 path_map = rightmost_map ^ 0x1;
// This is a depth-first search implementation. However, we don't start from the root, but
// from the far right element, as if we had already descended here.
while (true) {
if ((node_id & type(uint40).max) != 0x0) {
uint24 c_price = uint24(node_id >> 40);
if (c_price != array_price_ids[price_level]) {
++price_level;
if (price_level == max_price_levels) {
return (array_price_ids, array_shares);
}
array_price_ids[price_level] = c_price;
}
(uint128 total_shares, ) = extractSharesValueForNode(node_id);
array_shares[price_level] += total_shares;
(node_id, k) = calcNextRightMostNodeId(node_id, path_map);
if (node_id == 0x0) {
break;
}
path_map ^= k;
node_id = nodes[node_id].left; // this is why it works for rightmost branch nodes too
} else {
unchecked {
k = ~(node_id - 1) & node_id;
}
path_map ^= k;
node_id = nodes[node_id].right;
}
}
uint24 actual_length = price_level + 1;
if (actual_length < max_price_levels) {
// Cropping the returned arrays to their actual length.
uint24[] memory cropped_array_price_ids = new uint24[](actual_length);
uint128[] memory cropped_array_shares = new uint128[](actual_length);
for(uint24 i = 0; i < actual_length; ++i) {
cropped_array_price_ids[i] = array_price_ids[i];
cropped_array_shares[i] = array_shares[i];
}
return (cropped_array_price_ids, cropped_array_shares);
}
}
/// @dev Finds the rightmost node that matches the given order_id.
/// @param order_id The ID of the order to find the matching node for.
/// @return node_id The ID of the found node or root.
/// @return success Indicates whether the search was successful.
/// This algo finds the lowest node in branch that meets the given criteria.
function findRightmostMatchingNode(uint64 order_id) internal view returns (uint64 node_id, bool success) {
uint256 map = rightmost_map;
uint64 local_best_offer = best_offer;
// We climb the rightmost branch until we go through it all.
uint256 mask = ~uint256(0x1);
while (true) {
if (((local_best_offer ^ order_id) & mask) == 0x0) {
// We found the node that matches order_id.
uint256 k = (~mask & (mask >> 1));
// Extracts the bit that determines the length.
// Shifting works correctly for the case of 64 bits.
node_id = uint64((local_best_offer & mask) ^ k);
return (node_id, true);
}
map = map & mask;
if (map == 0x0) {
// We have reached the root of the tree,
uint256 k = (~mask & (mask >> 1));
// Extracts the bit that determines the length.
// Shifting works correctly for the case of 64 bits.
uint64 root_node_id = uint64((local_best_offer & mask) ^ k);
return (root_node_id, false);
}
unchecked { // we just checked that map != 0
mask = ~(map ^ (map - 1));
}
}
}
/// @dev Normalizes the branch of the tree up to the specified stop node.
/// @param stop_node_id The ID of the node where normalization stops, must exist.
/// @return extra_total_shares The total number of extra shares added during normalization.
/// @return extra_total_value The total value associated with the extra shares added during normalization.
/// @return new_rightmost_map The new rightmost map after normalization.
function normalizeBranch(uint64 stop_node_id)
internal returns (uint128 extra_total_shares, uint128 extra_total_value, uint64 new_rightmost_map) {
uint256 map = rightmost_map;
uint64 local_best_offer = best_offer;
// loading leaf data
Leaf memory leaf = leaves[local_best_offer];
(uint128 initial_shares, uint128 initial_value) = loadSharesValueFromArena(leaf.initial_shares_value_ptr);
extra_total_shares = leaf.remain_shares;
extra_total_value = uint128(uint256(extra_total_shares) * uint256(initial_value) / uint256(initial_shares));
map ^= 0x1;
if (stop_node_id == local_best_offer) {
return (extra_total_shares, extra_total_value, uint64(map));
}
uint256 mask;
unchecked { // we are guaranteed to have a stop order higher
mask = ~(map ^ (map - 1));
}
while (true) {
uint256 k = (~mask & (mask >> 1));
// Shifting works correctly for the case of 64 bits.
map ^= k;
uint64 node_id = uint64((local_best_offer & mask) ^ k);
uint64 node_ptr = nodes[node_id].total_shares_value_ptr;
(uint128 node_total_shares, uint128 node_total_value) = loadSharesValueFromArena(node_ptr);
uint128 initial_total_shares = node_total_shares;
uint128 initial_total_value = node_total_value;
node_total_shares += extra_total_shares;
node_total_value += extra_total_value;
saveSharesValueToArena(node_ptr, node_total_shares, node_total_value);
extra_total_shares += initial_total_shares;
extra_total_value += initial_total_value;
if (node_id == stop_node_id) {
break;
}
unchecked { // we are guaranteed to have a stop order higher
mask = ~(map ^ (map - 1));
}
}
new_rightmost_map = uint64(map);
}
/// @dev Converts the regular right branch to rightmost branch starting from the given start_node_id.
/// @param start_node_id The starting node_id for the conversion. Must me on the rightmost branch.
/// @return xor_map The XOR diff with rightmost map generated during the conversion.
function convertToRightmost(uint64 start_node_id) internal returns (uint64 xor_map) {
xor_map = 0x1; // including leaf node
uint64 node_id = start_node_id;
Node memory node;
while ((node_id & 0x1) != 0x1) {
// untill we reach leaf
node = nodes[node_id];
uint64 ptr = node.total_shares_value_ptr;
uint64 child_node_id = node.right;
(uint128 child_shares, uint128 child_value) = extractSharesValueForNode(child_node_id);
removeFromArenaValues(ptr, child_shares, child_value);
uint64 k;
unchecked {
k = ~(node_id - 1) & node_id;
// Extracts the bit that determines the length.
// Valid node always is greater than 0.
}
xor_map ^= k;
node_id = child_node_id;
}
best_offer = node_id;
}
/// @dev Updates root node and adds a new order as a descendant of new root.
/// @param order_id The ID of the new order.
/// @param root_node_id The ID of the root node in the tree.
/// @param shares The number of shares for the new order.
/// @param value The value associated with the new order.
function addOrderAndUpdateRoot(uint64 order_id, uint64 root_node_id, uint128 shares, uint128 value) internal {
uint64 extra_node_id = calcCommonParent(order_id, root_node_id);
Node memory extra_node;
uint64 extra_node_k;
unchecked {
extra_node_k = ~(extra_node_id - 1) & extra_node_id;
// Extracts the bit that determines the length.
// Valid node always is greater than 0.
}
uint64 free_ptr = allocateMemory();
uint64 new_rightmost_map;
if (root_node_id < order_id) {
// inserting node to the right
uint128 extra_total_shares;
uint128 extra_total_value;
(extra_total_shares, extra_total_value, new_rightmost_map) = normalizeBranch(root_node_id);
saveSharesValueToArena(free_ptr, extra_total_shares, extra_total_value);
extra_node = Node({
left: root_node_id,
right: order_id,
total_shares_value_ptr: free_ptr
});
new_rightmost_map ^= extra_node_k ^ 0x1; // 0x1 for new leaf
best_offer = order_id;
} else {
// inserting node to the left
saveSharesValueToArena(free_ptr, shares, value);
extra_node = Node({
left: order_id,
right: root_node_id,
total_shares_value_ptr: free_ptr
});
new_rightmost_map = rightmost_map ^ extra_node_k;
}
rightmost_map = new_rightmost_map;
nodes[extra_node_id] = extra_node;
}
/// @dev Adds an order to the nodes based on the provided order_id, node_id, shares, and value.
/// @param order_id The ID of the order to add.
/// @param node_id The ID of the node where the order should be added. Must be the lowest node in rightmost branch
/// that matches order_id.
/// @param shares The number of shares for the order.
/// @param value The value associated with the order.
function addOrderToNodes(uint64 order_id, uint64 node_id, uint128 shares, uint128 value) internal {
// we now for sure that node_id is not a leaf
Node memory node = nodes[node_id];
if (matchesNode(order_id, node.left)) {
uint64 node_ptr = node.total_shares_value_ptr;
addToArenaValues(node_ptr, shares, value);
addOrderToNonRightmostNodeDescendants(node.left, order_id, shares, value);
return;
} // node.right can't match order_id
// so no "else" logic needs here
// so we are inserting new node here, in current node
uint64 extra_node_id;
Node memory extra_node;
uint64 free_ptr = allocateMemory();
if (order_id < node_id) {
uint64 node_ptr = node.total_shares_value_ptr;
addToArenaValues(node_ptr, shares, value);
extra_node_id = calcCommonParent(order_id, node.left);
if (node.left > order_id) {
extra_node = Node(order_id, node.left, free_ptr);
} else {
extra_node = Node(node.left, order_id, free_ptr);
}
(uint128 child_shares, uint128 child_value) = extractSharesValueForNode(node.left);
saveSharesValueToArena(free_ptr, shares + child_shares, value + child_value);
node.left = extra_node_id;
} else {
// here we must properly rebuild the rightmost branch
extra_node_id = calcCommonParent(order_id, node.right);
uint64 extra_node_k;
unchecked {
extra_node_k = ~(extra_node_id - 1) & extra_node_id;
// Extracts the bit that determines the length.
// Valid node always is greater than 0.
}
if (node.right > order_id) {
saveSharesValueToArena(free_ptr, shares, value);
extra_node = Node(order_id, node.right, free_ptr);
rightmost_map ^= extra_node_k;
} else {
(uint128 extra_total_shares, uint128 extra_total_value, uint64 new_rightmost_map)
= normalizeBranch(node.right);
rightmost_map = new_rightmost_map ^ extra_node_k ^ 0x1; // 0x1 for new leaf;
best_offer = order_id;
saveSharesValueToArena(free_ptr, extra_total_shares, extra_total_value);
extra_node = Node(node.right, order_id, free_ptr);
}
node.right = extra_node_id;
}
nodes[node_id] = node;
nodes[extra_node_id] = extra_node;
}
/// @dev Adds an order to the descendants of a node that is not the rightmost node.
/// @param node_id The ID of the node from which to start updating. It must match order_id.
/// @param order_id The ID of the order to add.
/// @param shares The total shares associated with the order.
/// @param value The total value associated with the order.
function addOrderToNonRightmostNodeDescendants(
uint64 node_id,
uint64 order_id,
uint128 shares,
uint128 value
) internal {
uint64 next_node_id;
Node memory node;
// Descending the tree starting from node_id until neither child matches order_id,
// indicating a new node insertion point.
while (true) {
node = nodes[node_id];
uint64 ptr = node.total_shares_value_ptr;
addToArenaValues(ptr, shares, value);
if (matchesNode(order_id, node.left)) {
next_node_id = node.left;
} else if (matchesNode(order_id, node.right)) {
next_node_id = node.right;
} else {
break;
}
node_id = next_node_id;
}
uint64 extra_node_id;
Node memory extra_node;
uint64 free_ptr = allocateMemory();
uint64 child_node_id;
if (order_id < node_id) {
// Inserting new (extra) node to the left.
extra_node_id = calcCommonParent(order_id, node.left);
if (node.left > order_id) {
extra_node = Node(order_id, node.left, free_ptr);
} else {
extra_node = Node(node.left, order_id, free_ptr);
}
child_node_id = node.left;
node.left = extra_node_id;
} else {
// Inserting new (extra) node to the right.
extra_node_id = calcCommonParent(order_id, node.right);
if (node.right > order_id) {
extra_node = Node(order_id, node.right, free_ptr);
} else {
extra_node = Node(node.right, order_id, free_ptr);
}
child_node_id = node.right;
node.right = extra_node_id;
}
(uint128 child_shares, uint128 child_value) = extractSharesValueForNode(child_node_id);
saveSharesValueToArena(free_ptr, shares + child_shares, value + child_value);
nodes[node_id] = node;
nodes[extra_node_id] = extra_node;
}
/// @dev Checks if a given order is present in the tree.
/// @param node_id The ID of the starting node identifier from which the search begins.
/// @param order_id The ID of the order to search for in the tree.
/// @return isPresent A boolean value indicating whether the order is present in the tree.
function isOrderInTree(uint64 node_id, uint64 order_id) internal view returns (bool isPresent) {
if (node_id == order_id) {
return true;
}
Node memory node;
while (true) {
node = nodes[node_id];
if (node.left == order_id || node.right == order_id) {
return true;
}
if (matchesNode(order_id, node.left)) {
node_id = node.left;
} else if (matchesNode(order_id, node.right)) {
node_id = node.right;
} else {
return false;
}
}
}
/// @dev Removes best offer order and rebuild rightmost branch if needed.
function removeBestOffer() internal {
uint64 local_best_offer = best_offer;
uint64 map = rightmost_map;
if (map == 0x1) {
// This means there is only one order in the trie.
// We remove it and leave the trie empty.
rightmost_map = 0x0;
best_offer = 0x0;
return;
}
// We need to find the parent node and remove it as well.
// It exists because there are more than one leaf in the tree.
map ^= 0x1;
uint64 mask;
unchecked {
// map > 0 since there are more than one leaf in the tree
mask = ~(map ^ (map - 1));
}
uint64 k = (((mask >> 1) | 0x8000000000000000) & ~mask);
// Removing this node from rightmost map too.
map ^= k;
uint64 node_id = (local_best_offer & mask) ^ k;
Node memory node = nodes[node_id];
eraseNode(node_id, node.total_shares_value_ptr);
uint64 new_right_child = node.left;
// and we have new rightmost branch
uint64 new_rightmost_map = map ^ convertToRightmost(new_right_child);
rightmost_map = new_rightmost_map;
// This means that the node being removed has no "grandfather" node.
if (new_rightmost_map == 0x1) {
return;
}
// We also need to update the right child of the ancestor's ancestor of our order, as we have just removed it.
unchecked {
// map > 0 since there are at least one more ancestor
mask = ~(map ^ (map - 1));
}
k = (((mask >> 1) | 0x8000000000000000) & ~mask);
node_id = (local_best_offer & mask) ^ k;
nodes[node_id].right = new_right_child;
}
/// @dev Removes an order from the nodes based on the provided order_id, node_id, remaining shares, and remaining value.
/// @param order_id The ID of the order to remove.
/// @param node_id The ID of the node from which to remove the order.
/// @param remain_shares The remaining shares of the order.
/// @param remain_value The remaining value of the order.
/// @return found Indicates if the order was found and removed.
function removeOrderFromNodes(
uint64 order_id,
uint64 node_id,
uint128 remain_shares,
uint128 remain_value
) internal returns (bool found) {
Node memory node = nodes[node_id];
if (node.left == order_id) {
eraseNode(node_id, node.total_shares_value_ptr);
uint64 k;
unchecked {
// valid node_id is always greater than 0
k = ~(node_id - 1) & node_id;
}
uint64 map = rightmost_map;
rightmost_map = map ^ k;
uint64 mask;
unchecked {
mask = ~(k ^ (k - 1)); // k > 0
}
map = map & mask;
if (map == 0x0) {
// same case in removeBestOffer - no "grandfather" node.
return true;
}
unchecked {
k = ~(map - 1) & map; // we just checked that map > 0
mask = ~(k ^ (k - 1)); // k > 0
}
uint64 new_right_child = node.right;
node_id = (node_id & mask) ^ k;
nodes[node_id].right = new_right_child;
return true;
}
if (!matchesNode(order_id, node.left)) {
return false;
}
uint64 returned_child;
(found, returned_child) = removeOrderFromNonRightmostNodeDescendants(
node.left, order_id, remain_shares, remain_value
);
if (found) {
removeFromArenaValues(node.total_shares_value_ptr, remain_shares, remain_value);
if (node.left != returned_child){
node.left = returned_child;
nodes[node_id] = node;
}
}
}
/// @dev Recursively removes an order from the descendants of a non-rightmost node.
/// @param node_id The ID of the current node being processed. Must be not a leaf.
/// @param order_id The ID of the order to be removed.
/// @param shares The number of shares associated with the order.
/// @param value The value associated with the order.
/// @return found Indicates if the order was found and removed.
/// @return returned_child The identifier of the child node returned after removal.
function removeOrderFromNonRightmostNodeDescendants(
uint64 node_id,
uint64 order_id,
uint128 shares,
uint128 value
) internal returns (bool found, uint64 returned_child) {
Node memory node = nodes[node_id];
if (node.left == order_id) {
eraseNode(node_id, node.total_shares_value_ptr);
return (true, node.right);
} else if (node.right == order_id) {
eraseNode(node_id, node.total_shares_value_ptr);
return (true, node.left);
}
if (matchesNode(order_id, node.left)) {
(found, returned_child) = removeOrderFromNonRightmostNodeDescendants(node.left, order_id, shares, value);
if (!found) {
return (false, 0x0);
}
removeFromArenaValues(node.total_shares_value_ptr, shares, value);
if (node.left != returned_child){
node.left = returned_child;
nodes[node_id] = node;
}
return (true, node_id);
} else if (matchesNode(order_id, node.right)) {
(found, returned_child) = removeOrderFromNonRightmostNodeDescendants(node.right, order_id, shares, value);
if (!found) {
return (false, 0x0);
}
removeFromArenaValues(node.total_shares_value_ptr, shares, value);
if (node.left != returned_child){
node.right = returned_child;
nodes[node_id] = node;
}
return (true, node_id);
} else {
return (false, 0x0);
}
}
/// @dev Extracts key and mask from a given node_id.
/// @param node_id The ID of the node from which to extract key and mask.
/// @return key The extracted key.
/// @return mask The extracted mask.
function extractKeyAndMaskFrom(uint64 node_id) internal pure returns (uint64 key, uint64 mask) {
unchecked {
// valid node_id is always greater than 0
mask = ~((node_id - 1) ^ node_id);
}
key = node_id & mask;
return (key, mask);
}
/// @dev Extracts key from a given node_id.
/// @param node_id The ID of the node from which to extract key.
/// @return key The extracted key.
function extractKeyFrom(uint64 node_id) internal pure returns (uint64 key) {
uint64 k;
unchecked {
// valid node_id is always greater than 0
k = ~(node_id - 1) & node_id;
}
return node_id ^ k;
}
/// @dev Calculates the common parent node for a given order_id and node_id.
/// @param order_id The ID of the order to calculate the common parent for.
/// @param node_id The ID of the node to calculate the common parent for.
/// @return The calculated common parent node.
function calcCommonParent(uint64 order_id, uint64 node_id) internal pure returns (uint64) {
uint64 key = extractKeyFrom(node_id);
uint256 diff = (order_id ^ 0x1) ^ key;
uint256 mask = ~uint256(type(uint64).max);
uint256 t;
t = mask >> 32; if ((t & diff) == 0x0) { mask = t; }
t = mask >> 16; if ((t & diff) == 0x0) { mask = t; }
t = mask >> 8; if ((t & diff) == 0x0) { mask = t; }
t = mask >> 4; if ((t & diff) == 0x0) { mask = t; }
t = mask >> 2; if ((t & diff) == 0x0) { mask = t; }
t = mask >> 1; if ((t & diff) == 0x0) { mask = t; }
uint256 k = ((mask >> 1) & ~mask);
return uint64((order_id & mask) ^ k);
}
/// @dev Checks if the order_id is a descendant of the node_id.
/// @param order_id The ID of the order to compare with the node_id.
/// @param node_id The ID of the node to compare with the order_id.
/// @return True if the order_id matches the node_id, false otherwise.
function matchesNode(uint64 order_id, uint64 node_id) internal pure returns (bool) {
uint64 mask;
unchecked {
// valid node_id is always greater than 0
mask = ~((node_id - 1) ^ node_id);
}
return ((order_id ^ node_id) & mask) == 0x0;
}
/// @dev Erases the node with the specified node_id.
/// @param node_id The ID of the node of the node to erase.
function eraseNode(uint64 node_id, uint64 ptr) internal virtual {
// Requires a more thoughtful strategy than just erasing everything.
// if ((node_id & 0x1) != 0x1) {
// delete nodes[node_id];
// }
freeMemory(ptr);
}
/// @dev Recursively executes orders using a "right" approach within the order matching process.
/// @param order_id The price identifier of the order, not necessarily associated with a real order ID.
/// @param node_id The ID of the node within the order.
/// @param rest_total_shares The remaining total shares to be executed.
/// @return execution_result An ExecutionResult struct containing the result of the execution.
function executeRightRec(uint64 order_id, uint64 node_id, uint128 rest_total_shares)
internal returns (ExecutionResult memory execution_result) {
if ((node_id & 0x1) == 0x1) {
// leaf execution
return executeLeaf(order_id, node_id, rest_total_shares);
}
// node execution
Node memory node = nodes[node_id];
uint64 node_ptr = node.total_shares_value_ptr;
(uint128 node_shares, uint128 node_value) = loadSharesValueFromArena(node_ptr);
// node.left != 0x0 since it node, not a leaf
uint64 price_key = extractKeyFrom(node.left);
// the same condition in executeRight
if (((order_id ^ 0x1) > price_key) || (rest_total_shares < node_shares)) {
ExecutionResult memory right_execution_result = executeRightRec(order_id, node.right, rest_total_shares);
rest_total_shares -= right_execution_result.executed_shares;
if (right_execution_result.right_child != 0x0) {
removeFromArenaValues(
node_ptr,
right_execution_result.total_shares + right_execution_result.executed_shares,
right_execution_result.total_value + right_execution_result.executed_value
);
if (node.right != right_execution_result.right_child) {
node.right = right_execution_result.right_child;
nodes[node_id] = node;
}
uint64 k;
unchecked {
k = ~(node_id - 1) & node_id;
// Extracts the bit that determines the length.
// Valid node always is greater than 0.
}
execution_result = ExecutionResult({
executed_shares: right_execution_result.executed_shares,
executed_value: right_execution_result.executed_value,
total_shares: node_shares - right_execution_result.executed_shares,
total_value: node_value - right_execution_result.executed_value,
right_child: node_id,
xor_map: right_execution_result.xor_map ^ k
});
} else {
execution_result = executeRightRec(order_id, node.left, rest_total_shares);
execution_result.executed_shares += right_execution_result.executed_shares;
execution_result.executed_value += right_execution_result.executed_value;
}
} else {
// full execution
execution_result = ExecutionResult({
executed_shares: node_shares,
executed_value: node_value,
total_shares: 0,
total_value: 0,
right_child: 0x0,
xor_map: 0x0
});
eraseNode(node_id, node_ptr);
}
}
/// @dev Executes a leaf node within the order matching process.
/// @param order_id The price identifier of the order, not associated with a real order ID.
/// @param leaf_node_id The ID of the leaf node within the order.
/// @param rest_total_shares The remaining total shares to be executed.
/// @return execution_result An ExecutionResult struct containing the result of the execution.
function executeLeaf(uint64 order_id, uint64 leaf_node_id, uint128 rest_total_shares)
internal returns (ExecutionResult memory execution_result) {
Leaf memory leaf = leaves[leaf_node_id];
(uint128 initial_shares, uint128 initial_value) = loadSharesValueFromArena(leaf.initial_shares_value_ptr);
uint128 remain_shares = leaf.remain_shares;
uint128 remain_value = uint128(uint256(remain_shares) * uint256(initial_value) / uint256(initial_shares));
if (leaf_node_id >= order_id) { // both end on 0x1 bit, so we can compare them
// we can execute current leaf
if (remain_shares <= rest_total_shares) {
// full execution
execution_result = ExecutionResult({
executed_shares: remain_shares,
executed_value: remain_value,
total_shares: 0,
total_value: 0,
right_child: 0x0,
xor_map: 0x0
});
} else {
// partial execution
uint128 executed_shares = rest_total_shares;
// Since the operation node.total_value = node.total_shares * price is expected,
// the quotient will always be an integer.
uint128 executed_value = uint128(uint256(rest_total_shares)
* uint256(remain_value) / uint256(remain_shares));
// remain_value / remain_shares = price
unchecked {
leaf.remain_shares -= executed_shares;
}
leaves[leaf_node_id] = leaf;
execution_result = ExecutionResult({
executed_shares: executed_shares,
executed_value: executed_value,
total_shares: remain_shares - executed_shares,
total_value: remain_value - executed_value,
right_child: leaf_node_id,
xor_map: 0x1
});
best_offer = leaf_node_id;
}
} else {
// we can't execute current leaf at all
execution_result = ExecutionResult({
executed_shares: 0,
executed_value: 0,
total_shares: remain_shares,
total_value: remain_value,
right_child: leaf_node_id,
xor_map: 0x1
});
best_offer = leaf_node_id;
}
// A brief comment explaining why in some cases we equate the best offer to the current leaf.
// When executing multiple orders, only one of them may be partially executed. This partially executed order
// becomes the best offer.
// An entirely unexecuted order becomes the best because our algorithm, encountering such behavior,
// stops trying to execute other orders - they are guaranteed to be worse. On the other hand,
// all better orders have already been fully executed.
}
/// @dev Preview the execution of a leaf node.
/// @param order_id The ID of the order to be executed.
/// @param leaf_node_id The ID of the leaf node to be executed.
/// @param rest_shares The remaining shares of the order.
/// @param rest_value The remaining value of shares of the order.
/// @return executed_shares The number of shares executed.
/// @return executed_value The value of the executed shares.
/// @return full A boolean indicating whether the leaf was fully executed (true) or partially executed (false).
function previewExecuteLeaf(uint64 order_id, uint64 leaf_node_id, uint128 rest_shares, uint128 rest_value)
internal view returns (uint128 executed_shares, uint128 executed_value, bool full) {
Leaf memory leaf = leaves[leaf_node_id];
(uint128 initial_shares, uint128 initial_value) = loadSharesValueFromArena(leaf.initial_shares_value_ptr);
uint128 leaf_shares = leaf.remain_shares;
uint128 leaf_value = uint128(uint256(leaf_shares) * uint256(initial_value) / uint256(initial_shares));
if (leaf_node_id >= order_id) { // both end on 0x1 bit, so we can compare them
// we can execute current leaf
// The order of these checks is important and should not be changed.
// We first check if we need to adjust shares based on value,
// then we check if we need to adjust value based on shares.
// This ensures correct handling of partial executions and rounding.
if (rest_value < leaf_value) {
uint128 shares = uint128(uint256(rest_value) * uint256(leaf_shares) / uint256(leaf_value));
// note: This division may not result in an integer, and rounding down is implied
if (shares < rest_shares) {
rest_shares = shares;
}
}
if (rest_shares < leaf_shares) {
uint128 value = uint128(uint256(rest_shares) * uint256(leaf_value) / uint256(leaf_shares));
if (value < rest_value) {
rest_value = value;
}
}
if (rest_shares < leaf_shares) {
// partial execution
return (rest_shares, rest_value, false);
} else {
// full execution
return (leaf_shares, leaf_value, true);
}
} else {
// we can't execute current leaf at all
return (0, 0, false);
}
}
/// @dev Calculates the next rightmost node ID and its associated k-bit based on the given node ID and map.
/// @param node_id The node ID.
/// @param map The map used for calculation.
/// @return The next rightmost node ID and its associated k-bit.
function calcNextRightMostNodeId(uint64 node_id, uint64 map) internal pure returns (uint64, uint64) {
uint64 mask;
unchecked {
mask = ~(node_id ^ (node_id - 1)); // valid node_id is always greater than 0
map &= mask;
}
if (map == 0x0) {
return (0, 0);
}
unchecked {
mask = ~(map ^ (map - 1)); // we just checker map > 0
}
uint64 k = (((mask >> 1) | 0x8000000000000000) & ~mask);
return ((node_id & mask) ^ k, k);
}
/// @dev Packs two uint128 values into a single uint256.
/// @param a The first uint128 value.
/// @param b The second uint128 value.
/// @return p The packed uint256 value.
function packTwoUintsToWord(uint128 a, uint128 b) internal pure returns (uint256 p) {
p = uint256(a) ^ (uint256(b) << 128);
}
/// @dev Unpacks a uint256 value into two uint128 values.
/// @param p The packed uint256 value.
/// @return a The first unpacked uint128 value.
/// @return b The second unpacked uint128 value.
function unPackTwoUintsFromWord(uint256 p) internal pure returns (uint128 a, uint128 b) {
a = uint128(p & 0xffffffffffffffffffffffffffffffff);
b = uint128(p >> 128);
}
/// @dev Allocates memory for storing data.
/// @return ptr The pointer to the allocated memory.
function allocateMemory() internal returns (uint64 ptr) {
if (last_free_pointer == 0x0) {
return (++highest_allocated_pointer);
}
ptr = last_free_pointer;
last_free_pointer = uint64(arena[ptr]);
}
/// @dev Frees the memory at the given pointer.
/// @param ptr The pointer to the memory to be freed.
function freeMemory(uint64 ptr) internal {
require(last_free_pointer != ptr, Errors.PointerAlreadyFreed());
arena[ptr] = packTwoUintsToWord(last_free_pointer, 0x1);
last_free_pointer = ptr;
}
/// @dev Saves the shares and value to the memory at the given pointer.
/// @param ptr The pointer to the memory where the data will be saved.
/// @param shares The shares to be saved.
/// @param value The value to be saved.
function saveSharesValueToArena(uint64 ptr, uint128 shares, uint128 value) internal {
arena[ptr] = packTwoUintsToWord(shares, value);
}
/// @dev Loads the shares and value from the memory at the given pointer.
/// @param ptr The pointer to the memory from where the data will be loaded.
/// @return The shares and value loaded from the memory.
function loadSharesValueFromArena(uint64 ptr) internal view returns (uint128, uint128) {
return unPackTwoUintsFromWord(arena[ptr]);
}
/// @dev Adds shares and value to the data at the given pointer in memory.
/// @param ptr The pointer to the memory where the data will be added.
/// @param adding_shares The shares to be added.
/// @param adding_value The value to be added.
function addToArenaValues(uint64 ptr, uint128 adding_shares, uint128 adding_value) internal {
(uint128 shares, uint128 value) = unPackTwoUintsFromWord(arena[ptr]);
shares += adding_shares;
value += adding_value;
arena[ptr] = packTwoUintsToWord(shares, value);
}
/// @dev Removes shares and value from the data at the given pointer in memory.
/// @param ptr The pointer to the memory from where the data will be removed.
/// @param removing_shares The shares to be removed.
/// @param removing_value The value to be removed.
function removeFromArenaValues(uint64 ptr, uint128 removing_shares, uint128 removing_value) internal {
(uint128 shares, uint128 value) = unPackTwoUintsFromWord(arena[ptr]);
shares -= removing_shares;
value -= removing_value;
arena[ptr] = packTwoUintsToWord(shares, value);
}
/// @dev Extracts the shares and value for a given node.
/// @param node_id The ID of the node.
/// @return The shares and value for the node.
function extractSharesValueForNode(uint64 node_id) internal view returns (uint128, uint128) {
if ((node_id & 0x1) == 0x1) {
// leaf case
Leaf memory leaf = leaves[node_id];
(uint128 initial_shares, uint128 initial_value) = loadSharesValueFromArena(leaf.initial_shares_value_ptr);
uint128 remain_shares = leaf.remain_shares;
uint128 remain_value = uint128(uint256(remain_shares) * uint256(initial_value) / uint256(initial_shares));
return (remain_shares, remain_value);
}
uint64 ptr = nodes[node_id].total_shares_value_ptr;
return loadSharesValueFromArena(ptr);
}
}
// SPDX-License-Identifier: BUSL-1.1
// Central Limit Order Book (CLOB) exchange
// (c) Long Gamma Labs, 2023.
pragma solidity ^0.8.26;
interface ITrieFactory {
function createTrie(address lob) external returns (address);
}
// SPDX-License-Identifier: BUSL-1.1
// Central Limit Order Book (CLOB) exchange
// (c) Long Gamma Labs, 2023.
pragma solidity ^0.8.26;
contract Errors {
error AddressIsZero();
error ArrayLengthMismatch();
error ChainIsUnstableForTrades();
error ClaimNotAllowed();
error CommissionParamTooHigh();
error Disabled();
error EmptyOrderError();
error ExcessiveSignificantFigures();
error Expired();
error Forbidden();
error FractionalNumbersNotAllowed();
error InsufficientTokenXBalance();
error InsufficientTokenYBalance();
error InvalidCommissionRate();
error InvalidFloatingPointRepresentation();
error InvalidMarketMaker();
error InvalidPriceRange();
error InvalidTransfer();
error MarketOnlyAndPostOnlyFlagsConflict();
error MaxCommissionFailure();
error NativeETHDisabled();
error NonceExhaustedFailure();
error NotImplementedYet();
error OnlyOwnerCanCancelOrders();
error PointerAlreadyFreed();
error PriceExceedsMaximumAllowedValue();
error TransferFailed();
error UnknownOrderId();
error UnknownTrader();
error WrongOwner();
error ZeroMaxDelayNotAllowed();
error ZeroRecoveryTimeNotAllowed();
error ZeroTokenTransferNotAllowed();
}
// SPDX-License-Identifier: BUSL-1.1
// Central Limit Order Book (CLOB) exchange
// (c) Long Gamma Labs, 2023.
pragma solidity ^0.8.26;
interface ITrie {
function best_offer() external view returns (uint64);
function rightmost_map() external view returns (uint64);
function addOrder(uint64 trader_id, uint64 order_id, uint128 shares, uint128 value) external;
function removeOrder(uint64 order_id, uint64 order_trader_id) external returns (uint128 total_shares, uint128 remain_shares);
function claimExecuted(uint64 order_id, uint64 order_trader_id) external returns (uint128 executed_shares, uint128 remain_shares);
function getOrderInfo(uint64 order_id) external view returns (uint128 total_shares, uint128 remain_shares);
function executeRight(uint64 order_id, uint128 order_total_shares) external returns (uint128 executed_shares, uint128 executed_value);
function previewExecuteRight(uint64 order_id, uint128 max_shares, uint128 max_value) external view returns (uint128 executed_shares, uint128 executed_value);
function assembleOrderbookFromOrders(uint24 max_price_levels) external view returns (uint24[] memory array_price_ids, uint128[] memory array_shares);
}