book.cpp
1#include "itch/book/book.hpp"23#include <algorithm>4#include <limits>5#include <stdexcept>6#include <utility>78namespace itch {910Book::Book(std::string target) : target_(std::move(target)) {}1112std::optional<LiveOrder> Book::order(uint64_t id) const {13 auto it = orders_.find(id);14 if (it == orders_.end()) {15 return std::nullopt;16 }17 return LiveOrder{id, it->second.side, it->second.shares, it->second.price};18}1920BookState Book::state() const {21 BookState state{locate_, {}, {}, {}};22 for (const auto& entry : orders_) {23 state.orders.push_back(24 {entry.first, entry.second.side, entry.second.shares, entry.second.price});25 }26 std::sort(state.orders.begin(), state.orders.end(), [](const LiveOrder& a, const LiveOrder& b) {27 return a.id < b.id;28 });29 for (const auto& level : bids_) {30 state.bids.push_back({level.first, level.second});31 }32 for (const auto& level : asks_) {33 state.asks.push_back({level.first, level.second});34 }35 return state;36}3738void Book::restore(const BookState& state, uint64_t frame) {39 Book restored(target_);40 restored.locate_ = state.locate;41 if (!state.locate && !state.orders.empty()) {42 fail(frame, "checkpoint orders without stock locate");43 }44 for (const auto& order : state.orders) {45 if ((order.side != 'B' && order.side != 'S') || !order.shares || !order.price) {46 fail(frame, "checkpoint invalid live order");47 }48 if (!restored.orders_.emplace(order.id, Order{order.side, order.shares, order.price})49 .second) {50 fail(frame, "checkpoint duplicate order reference");51 }52 restored.change_level(order.side, order.price, order.shares, true, frame);53 }54 const auto computed = restored.state();55 auto equal = [](const std::vector<Level>& a, const std::vector<Level>& b) {56 return a.size() == b.size() &&57 std::equal(a.begin(), a.end(), b.begin(), [](const Level& x, const Level& y) {58 return x.price == y.price && x.shares == y.shares;59 });60 };61 if (!equal(computed.bids, state.bids) || !equal(computed.asks, state.asks)) {62 fail(frame, "checkpoint price levels differ from live orders");63 }64 restored.verify_levels(frame);65 *this = std::move(restored);66}6768void Book::apply_directory(const Event& event) {69 const auto& directory = std::get<Directory>(event.data);70 if (directory.symbol == target_) {71 if (locate_ && *locate_ != event.locate) {72 fail(event.frame, "symbol changed stock locate");73 }74 locate_ = event.locate;75 } else if (locate_ && *locate_ == event.locate) {76 fail(event.frame, "stock locate belongs to another symbol");77 }78}7980bool Book::add_order(const Event& event) {81 const auto& add = std::get<Add>(event.data);82 if (add.symbol != target_) {83 if (locate_ && *locate_ == event.locate) {84 fail(event.frame, "add symbol/locate mismatch");85 }86 return false;87 }88 if (locate_ && *locate_ != event.locate) {89 fail(event.frame, "add symbol/locate mismatch");90 }91 locate_ = event.locate;92 if ((add.side != 'B' && add.side != 'S') || add.shares == 0 || add.price == 0) {93 fail(event.frame, "invalid add fields");94 }95 if (!orders_.emplace(add.id, Order{add.side, add.shares, add.price}).second) {96 fail(event.frame, "duplicate order reference");97 }98 change_level(add.side, add.price, add.shares, true, event.frame);99 return true;100}101102void Book::change_order(const Event& event) {103 uint64_t old_id = 0;104 if (event.type == 'E' || event.type == 'C' || event.type == 'X') {105 old_id = std::get<Reduce>(event.data).id;106 } else if (event.type == 'D') {107 old_id = std::get<Delete>(event.data).id;108 } else {109 old_id = std::get<Replace>(event.data).old_id;110 }111112 auto it = orders_.find(old_id);113 if (it == orders_.end()) {114 fail(event.frame, "unknown order reference (possible missing/out-of-order event)");115 }116 const Order old = it->second;117118 if (event.type == 'E' || event.type == 'C' || event.type == 'X') {119 const uint32_t removed = std::get<Reduce>(event.data).shares;120 if (removed == 0 || removed > old.shares) {121 fail(event.frame, "invalid share reduction");122 }123 change_level(old.side, old.price, removed, false, event.frame);124 if (removed == old.shares) {125 orders_.erase(it);126 } else {127 it->second.shares -= removed;128 }129 } else if (event.type == 'D') {130 change_level(old.side, old.price, old.shares, false, event.frame);131 orders_.erase(it);132 } else {133 const auto& replacement = std::get<Replace>(event.data);134 if (replacement.shares == 0 || replacement.price == 0 || replacement.new_id == old_id ||135 orders_.count(replacement.new_id)) {136 fail(event.frame, "invalid replacement");137 }138 change_level(old.side, old.price, old.shares, false, event.frame);139 orders_.erase(it);140 orders_.emplace(replacement.new_id, Order{old.side, replacement.shares, replacement.price});141 change_level(old.side, replacement.price, replacement.shares, true, event.frame);142 }143}144145std::optional<Snapshot> Book::apply(const Event& event, size_t max_depth, bool check_book) {146 if (event.type == 'R') {147 apply_directory(event);148 return std::nullopt;149 }150 if (event.type == 'A' || event.type == 'F') {151 if (!add_order(event)) {152 return std::nullopt;153 }154 } else {155 if (!locate_ || event.locate != *locate_) {156 return std::nullopt;157 }158 change_order(event);159 }160 if (check_book) {161 verify_levels(event.frame);162 }163 return snapshot(event, max_depth);164}165166[[noreturn]] void Book::fail(uint64_t frame, const char* reason) {167 throw std::runtime_error("frame " + std::to_string(frame) + ": " + reason);168}169170void Book::change_level(char side, uint32_t price, uint32_t shares, bool add, uint64_t frame) {171 auto& levels = side == 'B' ? bids_ : asks_;172 const uint64_t current = levels.count(price) ? levels.at(price) : 0;173 if (add) {174 if (current > std::numeric_limits<uint64_t>::max() - shares) {175 fail(frame, "depth overflow");176 }177 levels[price] = current + shares;178 } else {179 if (current < shares) {180 fail(frame, "depth underflow");181 }182 if (current == shares) {183 levels.erase(price);184 } else {185 levels[price] = current - shares;186 }187 }188}189190void Book::verify_levels(uint64_t frame) const {191 std::map<uint32_t, uint64_t> expected_bids, expected_asks;192 for (const auto& entry : orders_) {193 const Order& order = entry.second;194 if ((order.side != 'B' && order.side != 'S') || order.shares == 0 || order.price == 0) {195 fail(frame, "book invariant: invalid live order");196 }197 auto& expected = order.side == 'B' ? expected_bids : expected_asks;198 if (expected[order.price] > std::numeric_limits<uint64_t>::max() - order.shares) {199 fail(frame, "book invariant: depth overflow");200 }201 expected[order.price] += order.shares;202 }203 if (expected_bids != bids_ || expected_asks != asks_) {204 fail(frame, "book invariant: price levels differ from live orders");205 }206}207208Snapshot Book::snapshot(const Event& event, size_t max_depth) const {209 Snapshot result{event.frame, event.timestamp, event.type, {}, {}, bids_.size(), asks_.size()};210 for (auto it = bids_.rbegin(); it != bids_.rend() && result.bids.size() < max_depth; ++it) {211 result.bids.push_back({it->first, it->second});212 }213 for (auto it = asks_.begin(); it != asks_.end() && result.asks.size() < max_depth; ++it) {214 result.asks.push_back({it->first, it->second});215 }216 return result;217}218219} // namespace itch