diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/CursorManager.cpp | 84 | ||||
| -rw-r--r-- | src/HandlerManager.cpp | 50 | ||||
| -rw-r--r-- | src/IdentityManager.cpp | 11 | ||||
| -rw-r--r-- | src/InMemoryBackend.cpp | 14 | ||||
| -rw-r--r-- | src/LifecycleManager.cpp | 127 | ||||
| -rw-r--r-- | src/Merkle.cpp | 1018 | ||||
| -rw-r--r-- | src/MultigroupCodec.cpp | 67 | ||||
| -rw-r--r-- | src/NamespaceReferenceManager.cpp | 112 | ||||
| -rw-r--r-- | src/ObjectManager.cpp | 26 | ||||
| -rw-r--r-- | src/PermissionsManager.cpp | 22 | ||||
| -rw-r--r-- | src/RNT_C_API.cpp | 897 | ||||
| -rw-r--r-- | src/RelationalNT.cpp | 52 | ||||
| -rw-r--r-- | src/SqliteBackend.cpp | 44 | ||||
| -rw-r--r-- | src/TupleCodec.cpp | 39 | ||||
| -rw-r--r-- | src/VM.cpp | 121 |
15 files changed, 1293 insertions, 1391 deletions
diff --git a/src/CursorManager.cpp b/src/CursorManager.cpp index d96909b..0d71b1c 100644 --- a/src/CursorManager.cpp +++ b/src/CursorManager.cpp @@ -3,46 +3,38 @@ #include "ObjectManager.h" #include "TupleCodec.h" -namespace nt -{ - CursorManager::CursorManager(IStorageBackend& backend, - LifecycleManager* lifecycles, +namespace nt { + CursorManager::CursorManager(IStorageBackend& backend, LifecycleManager* lifecycles, ObjectManager* objects) - : backend_(backend) - , lifecycles_(lifecycles) - , objects_(objects) - {} + : backend_(backend), lifecycles_(lifecycles), objects_(objects) { + } // Finds the /system/snapshots/<H> entry that owns a handle's relation, or // nullptr when the relation lives outside the snapshot namespace (tests use // synthetic paths like {"relations", "villager"}). - static ObjectManager::registry* find_parent_snapshot( - ObjectManager& objects, - HandlerManager::handle* handle) - { - if (handle == nullptr || handle->object == nullptr - || handle->object->head == nullptr) + static ObjectManager::registry* find_parent_snapshot(ObjectManager& objects, + HandlerManager::handle* handle) { + if (handle == nullptr || handle->object == nullptr || handle->object->head == nullptr) return nullptr; const auto& p = handle->object->head->path; - if (p.size() != 5) return nullptr; + if (p.size() != 5) + return nullptr; if (p[0] != "system" || p[1] != "snapshots" || p[3] != "relations") return nullptr; - return objects.Find({ p[0], p[1], p[2] }); + return objects.Find({p[0], p[1], p[2]}); } - void CursorManager::LoadPage(cursor* c) - { - auto entries = Merkle<Hash32>::Page(backend_, c->merkle_root, - c->fetch_offset, PAGE_SIZE); + void CursorManager::LoadPage(cursor* c) { + auto entries = Merkle<Hash32>::Page(backend_, c->merkle_root, c->fetch_offset, PAGE_SIZE); c->page.clear(); c->page_position = 0; - for (const auto& entry : entries) - { + for (const auto& entry : entries) { auto bytes = backend_.Get(bin_to_hex(entry.payload)); - if (!bytes) continue; + if (!bytes) + continue; c->page.emplace_back(TupleCodec::Deserialize(*bytes)); } @@ -52,23 +44,23 @@ namespace nt } CursorManager::cursor* CursorManager::Open(HandlerManager::handle* handle, - const std::string& merkle_root) - { + const std::string& merkle_root) { if (handle == nullptr || handle->object == nullptr) return nullptr; const auto label = handle->object->head->type->label; auto pin_snapshot = [&](cursor* c) { - if (lifecycles_ == nullptr || objects_ == nullptr) return; + if (lifecycles_ == nullptr || objects_ == nullptr) + return; auto* snap = find_parent_snapshot(*objects_, handle); - if (snap == nullptr) return; + if (snap == nullptr) + return; lifecycles_->Pin(snap); c->pinned_snapshot = snap; }; - if (label == EPHEMERAL_RELATION) - { + if (label == EPHEMERAL_RELATION) { // Cursor is created exhausted — the JOIN operator writes args and // resets the state before the first probe. The generator is copied // off the registry-owned ephemeral_object_type so Next() never has @@ -78,8 +70,8 @@ namespace nt auto* c = new cursor(); c->is_ephemeral = true; - c->generator = etype->generator; - c->exhausted = true; + c->generator = etype->generator; + c->exhausted = true; pin_snapshot(c); return c; } @@ -91,8 +83,7 @@ namespace nt c->merkle_root = merkle_root; pin_snapshot(c); - if (merkle_root.empty()) - { + if (merkle_root.empty()) { // Empty relation: valid but immediately exhausted. c->exhausted = true; return c; @@ -102,36 +93,39 @@ namespace nt return c; } - Tuple* CursorManager::Next(cursor* c) - { - if (c == nullptr) return nullptr; + Tuple* CursorManager::Next(cursor* c) { + if (c == nullptr) + return nullptr; if (c->page_position < c->page.size()) return &c->page[c->page_position++]; - if (c->exhausted) return nullptr; + if (c->exhausted) + return nullptr; - if (c->is_ephemeral) - { + if (c->is_ephemeral) { c->page = c->generator(c->args, c->fetch_offset, PAGE_SIZE); c->page_position = 0; c->fetch_offset += c->page.size(); if (c->page.size() < PAGE_SIZE) c->exhausted = true; - if (c->page.empty()) return nullptr; + if (c->page.empty()) + return nullptr; return &c->page[c->page_position++]; } LoadPage(c); - if (c->page.empty()) return nullptr; + if (c->page.empty()) + return nullptr; return &c->page[c->page_position++]; } - void CursorManager::Close(cursor* c) - { - if (c == nullptr) { return; } + void CursorManager::Close(cursor* c) { + if (c == nullptr) { + return; + } if (lifecycles_ != nullptr && c->pinned_snapshot != nullptr) lifecycles_->Unpin(c->pinned_snapshot); delete c; } -} +} // namespace nt diff --git a/src/HandlerManager.cpp b/src/HandlerManager.cpp index cb3b723..505b393 100644 --- a/src/HandlerManager.cpp +++ b/src/HandlerManager.cpp @@ -5,44 +5,34 @@ #include "NamespaceReferenceManager.h" #include "PermissionsManager.h" -namespace nt -{ - void HandlerManager::DeallocateHandle(struct handle* handle) - { +namespace nt { + void HandlerManager::DeallocateHandle(struct handle* handle) { delete handle; } - HandlerManager::HandlerManager(ObjectManager& objects, - PermissionsManager& permissions, - IdentityManager& identities, - LifecycleManager& lifecycles, - NamespaceReferenceManager& references) - : objects_(objects) - , permissions_(permissions) - , identities_(identities) - , lifecycles_(lifecycles) - , references_(references) - {} + HandlerManager::HandlerManager(ObjectManager& objects, PermissionsManager& permissions, + IdentityManager& identities, LifecycleManager& lifecycles, + NamespaceReferenceManager& references) + : objects_(objects), permissions_(permissions), identities_(identities), + lifecycles_(lifecycles), references_(references) { + } - struct HandlerManager::handle* HandlerManager::Open(std::vector<std::string> object_path, void* connection_context) - { + struct HandlerManager::handle* HandlerManager::Open(std::vector<std::string> object_path, + void* connection_context) { const auto resolved = references_.Resolve(std::move(object_path)); ObjectManager::registry* retrieved_object = objects_.Find(resolved); - if (permissions_.Access(retrieved_object, (const void*)connection_context) - && identities_.CanOpen(retrieved_object) - && lifecycles_.Contention(retrieved_object)) { + if (permissions_.Access(retrieved_object, (const void*)connection_context) && + identities_.CanOpen(retrieved_object) && lifecycles_.Contention(retrieved_object)) { // Starts monitoring this guy lifecycles_.Monitor(retrieved_object); - return new handle{ retrieved_object, connection_context }; // Return a successful handle - } - else { + return new handle{retrieved_object, connection_context}; // Return a successful handle + } else { // Return something more algebraic instead of null or an int return nullptr; }; } - bool HandlerManager::Close(struct handle* handle) - { + bool HandlerManager::Close(struct handle* handle) { if (handle == nullptr) { return false; } @@ -51,21 +41,19 @@ namespace nt void* connection_context = handle->connection_context; // Checking for permissions here may be relevant. // What if we have a handle but no permission? Spooky - if (permissions_.Access(object, connection_context) - && identities_.CanClose(object) + if (permissions_.Access(object, connection_context) && identities_.CanClose(object) // TODO: I think that in this case we do not need to worry about contention. // But be careful to evaluate this scenario later. //&& lifecycles_.Contention(object) - ) { + ) { // Stops monitoring this guy lifecycles_.Unmonitor(object); DeallocateHandle(handle); return true; // Return a successful handle - } - else { + } else { // Return something more algebraic instead of null or an int. // It's kinda bad to not even report what went wrong. return false; }; } -} +} // namespace nt diff --git a/src/IdentityManager.cpp b/src/IdentityManager.cpp index 93ad705..9b131a9 100644 --- a/src/IdentityManager.cpp +++ b/src/IdentityManager.cpp @@ -1,14 +1,11 @@ #include "IdentityManager.h" -namespace nt -{ - const bool IdentityManager::CanOpen(ObjectManager::registry* object) - { +namespace nt { + const bool IdentityManager::CanOpen(ObjectManager::registry* object) { return object != nullptr; } - const bool IdentityManager::CanClose(ObjectManager::registry* object) - { + const bool IdentityManager::CanClose(ObjectManager::registry* object) { return object != nullptr; } -} +} // namespace nt diff --git a/src/InMemoryBackend.cpp b/src/InMemoryBackend.cpp index 4649da0..8aebc65 100644 --- a/src/InMemoryBackend.cpp +++ b/src/InMemoryBackend.cpp @@ -2,19 +2,17 @@ #include <picosha2.h> -namespace nt -{ - std::string InMemoryBackend::Put(std::vector<uint8_t> value) - { +namespace nt { + std::string InMemoryBackend::Put(std::vector<uint8_t> value) { const std::string hash = picosha2::hash256_hex_string(value.begin(), value.end()); kv_.emplace(hash, std::move(value)); return hash; } - std::optional<std::vector<uint8_t>> InMemoryBackend::Get(const std::string& hash) - { + std::optional<std::vector<uint8_t>> InMemoryBackend::Get(const std::string& hash) { auto it = kv_.find(hash); - if (it == kv_.end()) return std::nullopt; + if (it == kv_.end()) + return std::nullopt; return it->second; } -} +} // namespace nt diff --git a/src/LifecycleManager.cpp b/src/LifecycleManager.cpp index 78e112d..4a12e09 100644 --- a/src/LifecycleManager.cpp +++ b/src/LifecycleManager.cpp @@ -5,55 +5,50 @@ #include <vector> -namespace nt -{ - LifecycleManager::LifecycleManager(ObjectManager& objects, - IStorageBackend& storage) - : objects_(objects), storage_(storage) - {} - - void LifecycleManager::Monitor(ObjectManager::registry* object) - { +namespace nt { + LifecycleManager::LifecycleManager(ObjectManager& objects, IStorageBackend& storage) + : objects_(objects), storage_(storage) { + } + + void LifecycleManager::Monitor(ObjectManager::registry* object) { if (object != nullptr) ++object->head->handle_count; } - void LifecycleManager::Unmonitor(ObjectManager::registry* object) - { - if (object == nullptr || object->head->handle_count == 0) return; + void LifecycleManager::Unmonitor(ObjectManager::registry* object) { + if (object == nullptr || object->head->handle_count == 0) + return; --object->head->handle_count; TryCollect(object); } - void LifecycleManager::Pin(ObjectManager::registry* object) - { + void LifecycleManager::Pin(ObjectManager::registry* object) { if (object != nullptr) ++object->head->reference_count; } - void LifecycleManager::Unpin(ObjectManager::registry* object) - { - if (object == nullptr || object->head->reference_count == 0) return; + void LifecycleManager::Unpin(ObjectManager::registry* object) { + if (object == nullptr || object->head->reference_count == 0) + return; --object->head->reference_count; TryCollect(object); } - bool LifecycleManager::IsEligibleForGC(ObjectManager::registry* object) const - { - if (object == nullptr || object->head == nullptr) return false; - return object->head->handle_count == 0 - && object->head->reference_count == 0; + bool LifecycleManager::IsEligibleForGC(ObjectManager::registry* object) const { + if (object == nullptr || object->head == nullptr) + return false; + return object->head->handle_count == 0 && object->head->reference_count == 0; } - const bool LifecycleManager::Contention(ObjectManager::registry* object) - { + const bool LifecycleManager::Contention(ObjectManager::registry* object) { return object != nullptr; } - void LifecycleManager::TryCollect(ObjectManager::registry* object) - { - if (!IsEligibleForGC(object)) return; - if (object->head == nullptr || object->head->type == nullptr) return; + void LifecycleManager::TryCollect(ObjectManager::registry* object) { + if (!IsEligibleForGC(object)) + return; + if (object->head == nullptr || object->head->type == nullptr) + return; // Named-lifetime types are managed explicitly and must not auto-collect: // BRANCH — named branches persist until a future explicit-delete API @@ -64,48 +59,59 @@ namespace nt // EPHEMERAL_RELATION, TRANSACTION) is purely structurally referenced // and is GC-eligible by counters alone. const auto label = object->head->type->label; - if (label == BRANCH || label == SESSION) return; + if (label == BRANCH || label == SESSION) + return; - if (label == MULTIGROUP) CascadeMultigroup(object); - if (label == BRANCH_TREE) CascadeBranchTree(object); + if (label == MULTIGROUP) + CascadeMultigroup(object); + if (label == BRANCH_TREE) + CascadeBranchTree(object); objects_.Unregister(object->head->path); } - void LifecycleManager::CascadeMultigroup(ObjectManager::registry* multigroup) - { - if (multigroup == nullptr || multigroup->head == nullptr) return; + void LifecycleManager::CascadeMultigroup(ObjectManager::registry* multigroup) { + if (multigroup == nullptr || multigroup->head == nullptr) + return; const auto& mg_path = multigroup->head->path; - if (mg_path.size() < 3) return; + if (mg_path.size() < 3) + return; // /system/snapshots/<hash>/relations/<n> entries are the relation // children pinned by this multigroup. Collect first, mutate after — // Unpin can Unregister the entry we're standing on if its counters // were already zero, and iteration must outlive that mutation. std::vector<ObjectManager::registry*> children; - for (auto* cur = objects_.entries.get(); cur != nullptr; cur = cur->next.get()) - { + for (auto* cur = objects_.entries.get(); cur != nullptr; cur = cur->next.get()) { const auto& p = cur->head->path; - if (p.size() != mg_path.size() + 2) continue; + if (p.size() != mg_path.size() + 2) + continue; bool prefix_match = true; for (size_t i = 0; i < mg_path.size(); ++i) - if (p[i] != mg_path[i]) { prefix_match = false; break; } - if (!prefix_match) continue; - if (p[mg_path.size()] != "relations") continue; + if (p[i] != mg_path[i]) { + prefix_match = false; + break; + } + if (!prefix_match) + continue; + if (p[mg_path.size()] != "relations") + continue; children.push_back(cur); } - for (auto* child : children) Unpin(child); + for (auto* child : children) + Unpin(child); } - void LifecycleManager::CascadeBranchTree(ObjectManager::registry* branch_tree) - { - if (branch_tree == nullptr || branch_tree->head == nullptr) return; + void LifecycleManager::CascadeBranchTree(ObjectManager::registry* branch_tree) { + if (branch_tree == nullptr || branch_tree->head == nullptr) + return; auto* bt = dynamic_cast<ObjectManager::BranchTree*>(branch_tree->object.get()); - if (bt == nullptr || bt->merkle_root.empty()) return; + if (bt == nullptr || bt->merkle_root.empty()) + return; // Page through the (mg_name, mg_hash) tree and collect each referenced // multigroup before unpinning. Decoupling iteration from mutation @@ -113,24 +119,25 @@ namespace nt std::vector<ObjectManager::registry*> mgs; constexpr size_t kPageSize = 1024; size_t offset = 0; - while (true) - { - auto page = Merkle<std::string>::Page(storage_, bt->merkle_root, - offset, kPageSize); - if (page.empty()) break; - for (const auto& entry : page) - { + while (true) { + auto page = Merkle<std::string>::Page(storage_, bt->merkle_root, offset, kPageSize); + if (page.empty()) + break; + for (const auto& entry : page) { static const Hash32 zero{}; - if (entry.payload == zero) continue; + if (entry.payload == zero) + continue; const std::string mg_hash = bin_to_hex(entry.payload); - auto* mg_entry = objects_.Find( - {"system", "snapshots", mg_hash}); - if (mg_entry) mgs.push_back(mg_entry); + auto* mg_entry = objects_.Find({"system", "snapshots", mg_hash}); + if (mg_entry) + mgs.push_back(mg_entry); } - if (page.size() < kPageSize) break; + if (page.size() < kPageSize) + break; offset += page.size(); } - for (auto* mg : mgs) Unpin(mg); + for (auto* mg : mgs) + Unpin(mg); } -} +} // namespace nt diff --git a/src/Merkle.cpp b/src/Merkle.cpp index 760cfce..09329f9 100644 --- a/src/Merkle.cpp +++ b/src/Merkle.cpp @@ -7,604 +7,546 @@ namespace nt { -// ── Wire format constants ──────────────────────────────────────────────────── - -static constexpr uint8_t TAG_LEAF = 0x4C; // 'L' -static constexpr uint8_t TAG_INTERNAL = 0x49; // 'I' - -// ── Byte-order helpers ─────────────────────────────────────────────────────── - -static void write_u32(std::vector<uint8_t>& buf, uint32_t v) -{ - buf.push_back(static_cast<uint8_t>(v >> 24)); - buf.push_back(static_cast<uint8_t>(v >> 16)); - buf.push_back(static_cast<uint8_t>(v >> 8)); - buf.push_back(static_cast<uint8_t>(v )); -} - -static void write_u64(std::vector<uint8_t>& buf, uint64_t v) -{ - buf.push_back(static_cast<uint8_t>(v >> 56)); - buf.push_back(static_cast<uint8_t>(v >> 48)); - buf.push_back(static_cast<uint8_t>(v >> 40)); - buf.push_back(static_cast<uint8_t>(v >> 32)); - buf.push_back(static_cast<uint8_t>(v >> 24)); - buf.push_back(static_cast<uint8_t>(v >> 16)); - buf.push_back(static_cast<uint8_t>(v >> 8)); - buf.push_back(static_cast<uint8_t>(v )); -} - -static uint32_t read_u32(const uint8_t* p) -{ - return (uint32_t(p[0]) << 24) | (uint32_t(p[1]) << 16) - | (uint32_t(p[2]) << 8) | uint32_t(p[3]); -} - -static uint64_t read_u64(const uint8_t* p) -{ - return (uint64_t(p[0]) << 56) | (uint64_t(p[1]) << 48) - | (uint64_t(p[2]) << 40) | (uint64_t(p[3]) << 32) - | (uint64_t(p[4]) << 24) | (uint64_t(p[5]) << 16) - | (uint64_t(p[6]) << 8) | uint64_t(p[7]); -} - -// ── Hex / binary conversion (free, key-agnostic) ───────────────────────────── - -Hash32 hex_to_bin(const std::string& hex) -{ - if (hex.size() != 64) - throw std::invalid_argument( - "Merkle: hash must be exactly 64 hex characters, got " + - std::to_string(hex.size())); - - Hash32 out{}; - auto nibble = [](char c) -> uint8_t { - if (c >= '0' && c <= '9') return static_cast<uint8_t>(c - '0'); - if (c >= 'a' && c <= 'f') return static_cast<uint8_t>(c - 'a' + 10); - if (c >= 'A' && c <= 'F') return static_cast<uint8_t>(c - 'A' + 10); - throw std::invalid_argument(std::string("Merkle: invalid hex character '") + c + "'"); - }; - for (size_t i = 0; i < 32; ++i) - out[i] = static_cast<uint8_t>((nibble(hex[2*i]) << 4) | nibble(hex[2*i+1])); - return out; -} - -std::string bin_to_hex(const Hash32& bin) -{ - static const char HEX[] = "0123456789abcdef"; - std::string out(64, '0'); - for (size_t i = 0; i < 32; ++i) - { - out[2*i] = HEX[(bin[i] >> 4) & 0xF]; - out[2*i+1] = HEX[bin[i] & 0xF]; + // ── Wire format constants ──────────────────────────────────────────────────── + + static constexpr uint8_t TAG_LEAF = 0x4C; // 'L' + static constexpr uint8_t TAG_INTERNAL = 0x49; // 'I' + + // ── Byte-order helpers ─────────────────────────────────────────────────────── + + static void write_u32(std::vector<uint8_t>& buf, uint32_t v) { + buf.push_back(static_cast<uint8_t>(v >> 24)); + buf.push_back(static_cast<uint8_t>(v >> 16)); + buf.push_back(static_cast<uint8_t>(v >> 8)); + buf.push_back(static_cast<uint8_t>(v)); } - return out; -} -// ── Key codec: per-Key serialisation primitives ────────────────────────────── + static void write_u64(std::vector<uint8_t>& buf, uint64_t v) { + buf.push_back(static_cast<uint8_t>(v >> 56)); + buf.push_back(static_cast<uint8_t>(v >> 48)); + buf.push_back(static_cast<uint8_t>(v >> 40)); + buf.push_back(static_cast<uint8_t>(v >> 32)); + buf.push_back(static_cast<uint8_t>(v >> 24)); + buf.push_back(static_cast<uint8_t>(v >> 16)); + buf.push_back(static_cast<uint8_t>(v >> 8)); + buf.push_back(static_cast<uint8_t>(v)); + } -namespace { + static uint32_t read_u32(const uint8_t* p) { + return (uint32_t(p[0]) << 24) | (uint32_t(p[1]) << 16) | (uint32_t(p[2]) << 8) | + uint32_t(p[3]); + } -template<typename Key> -struct KeyCodec; // primary template intentionally undefined + static uint64_t read_u64(const uint8_t* p) { + return (uint64_t(p[0]) << 56) | (uint64_t(p[1]) << 48) | (uint64_t(p[2]) << 40) | + (uint64_t(p[3]) << 32) | (uint64_t(p[4]) << 24) | (uint64_t(p[5]) << 16) | + (uint64_t(p[6]) << 8) | uint64_t(p[7]); + } -template<> -struct KeyCodec<Hash32> { - static void write(std::vector<uint8_t>& buf, const Hash32& k) { - buf.insert(buf.end(), k.begin(), k.end()); + // ── Hex / binary conversion (free, key-agnostic) ───────────────────────────── + + Hash32 hex_to_bin(const std::string& hex) { + if (hex.size() != 64) + throw std::invalid_argument("Merkle: hash must be exactly 64 hex characters, got " + + std::to_string(hex.size())); + + Hash32 out{}; + auto nibble = [](char c) -> uint8_t { + if (c >= '0' && c <= '9') + return static_cast<uint8_t>(c - '0'); + if (c >= 'a' && c <= 'f') + return static_cast<uint8_t>(c - 'a' + 10); + if (c >= 'A' && c <= 'F') + return static_cast<uint8_t>(c - 'A' + 10); + throw std::invalid_argument(std::string("Merkle: invalid hex character '") + c + "'"); + }; + for (size_t i = 0; i < 32; ++i) + out[i] = static_cast<uint8_t>((nibble(hex[2 * i]) << 4) | nibble(hex[2 * i + 1])); + return out; } - // Returns key and advances *p_inout by the number of consumed bytes. - static Hash32 read(const uint8_t*& p) { - Hash32 k; - std::memcpy(k.data(), p, 32); - p += 32; - return k; + + std::string bin_to_hex(const Hash32& bin) { + static const char HEX[] = "0123456789abcdef"; + std::string out(64, '0'); + for (size_t i = 0; i < 32; ++i) { + out[2 * i] = HEX[(bin[i] >> 4) & 0xF]; + out[2 * i + 1] = HEX[bin[i] & 0xF]; + } + return out; + } + + // ── Key codec: per-Key serialisation primitives ────────────────────────────── + + namespace { + + template <typename Key> struct KeyCodec; // primary template intentionally undefined + + template <> struct KeyCodec<Hash32> { + static void write(std::vector<uint8_t>& buf, const Hash32& k) { + buf.insert(buf.end(), k.begin(), k.end()); + } + // Returns key and advances *p_inout by the number of consumed bytes. + static Hash32 read(const uint8_t*& p) { + Hash32 k; + std::memcpy(k.data(), p, 32); + p += 32; + return k; + } + static size_t encoded_size(const Hash32&) { + return 32; + } + }; + + template <> struct KeyCodec<std::string> { + static void write(std::vector<uint8_t>& buf, const std::string& k) { + write_u32(buf, static_cast<uint32_t>(k.size())); + buf.insert(buf.end(), k.begin(), k.end()); + } + static std::string read(const uint8_t*& p) { + uint32_t len = read_u32(p); + p += 4; + std::string k(reinterpret_cast<const char*>(p), len); + p += len; + return k; + } + static size_t encoded_size(const std::string& k) { + return 4 + k.size(); + } + }; + + } // anonymous namespace + + // ── Node serialisation ─────────────────────────────────────────────────────── + + template <typename Key> std::vector<uint8_t> Merkle<Key>::encode_leaf(const LeafNode& n) { + std::vector<uint8_t> buf; + size_t payload_size = 0; + for (const auto& e : n.entries) + payload_size += KeyCodec<Key>::encoded_size(e.key) + 32; + buf.reserve(1 + 4 + payload_size); + + buf.push_back(TAG_LEAF); + write_u32(buf, static_cast<uint32_t>(n.entries.size())); + for (const auto& e : n.entries) { + KeyCodec<Key>::write(buf, e.key); + buf.insert(buf.end(), e.payload.begin(), e.payload.end()); + } + return buf; } - static size_t encoded_size(const Hash32&) { return 32; } -}; - -template<> -struct KeyCodec<std::string> { - static void write(std::vector<uint8_t>& buf, const std::string& k) { - write_u32(buf, static_cast<uint32_t>(k.size())); - buf.insert(buf.end(), k.begin(), k.end()); + + template <typename Key> + std::vector<uint8_t> Merkle<Key>::encode_internal(const InternalNode& n) { + std::vector<uint8_t> buf; + size_t payload_size = 0; + for (const auto& e : n.entries) + payload_size += 8 + KeyCodec<Key>::encoded_size(e.min_key) + 32; + buf.reserve(1 + 4 + payload_size); + + buf.push_back(TAG_INTERNAL); + write_u32(buf, static_cast<uint32_t>(n.entries.size())); + for (const auto& e : n.entries) { + write_u64(buf, e.leaf_count); + KeyCodec<Key>::write(buf, e.min_key); + buf.insert(buf.end(), e.child_hash.begin(), e.child_hash.end()); + } + return buf; } - static std::string read(const uint8_t*& p) { - uint32_t len = read_u32(p); - p += 4; - std::string k(reinterpret_cast<const char*>(p), len); - p += len; - return k; + + template <typename Key> + typename Merkle<Key>::LeafNode Merkle<Key>::decode_leaf(const std::vector<uint8_t>& bytes) { + uint32_t count = read_u32(bytes.data() + 1); + LeafNode n; + n.entries.reserve(count); + const uint8_t* p = bytes.data() + 5; + for (uint32_t i = 0; i < count; ++i) { + LeafEntry e; + e.key = KeyCodec<Key>::read(p); + std::memcpy(e.payload.data(), p, 32); + p += 32; + n.entries.push_back(std::move(e)); + } + return n; } - static size_t encoded_size(const std::string& k) { return 4 + k.size(); } -}; - -} // anonymous namespace - -// ── Node serialisation ─────────────────────────────────────────────────────── - -template<typename Key> -std::vector<uint8_t> Merkle<Key>::encode_leaf(const LeafNode& n) -{ - std::vector<uint8_t> buf; - size_t payload_size = 0; - for (const auto& e : n.entries) - payload_size += KeyCodec<Key>::encoded_size(e.key) + 32; - buf.reserve(1 + 4 + payload_size); - - buf.push_back(TAG_LEAF); - write_u32(buf, static_cast<uint32_t>(n.entries.size())); - for (const auto& e : n.entries) - { - KeyCodec<Key>::write(buf, e.key); - buf.insert(buf.end(), e.payload.begin(), e.payload.end()); + + template <typename Key> + typename Merkle<Key>::InternalNode + Merkle<Key>::decode_internal(const std::vector<uint8_t>& bytes) { + uint32_t count = read_u32(bytes.data() + 1); + InternalNode n; + n.entries.reserve(count); + const uint8_t* p = bytes.data() + 5; + for (uint32_t i = 0; i < count; ++i) { + ChildEntry e; + e.leaf_count = read_u64(p); + p += 8; + e.min_key = KeyCodec<Key>::read(p); + std::memcpy(e.child_hash.data(), p, 32); + p += 32; + n.entries.push_back(std::move(e)); + } + return n; } - return buf; -} - -template<typename Key> -std::vector<uint8_t> Merkle<Key>::encode_internal(const InternalNode& n) -{ - std::vector<uint8_t> buf; - size_t payload_size = 0; - for (const auto& e : n.entries) - payload_size += 8 + KeyCodec<Key>::encoded_size(e.min_key) + 32; - buf.reserve(1 + 4 + payload_size); - - buf.push_back(TAG_INTERNAL); - write_u32(buf, static_cast<uint32_t>(n.entries.size())); - for (const auto& e : n.entries) - { - write_u64(buf, e.leaf_count); - KeyCodec<Key>::write(buf, e.min_key); - buf.insert(buf.end(), e.child_hash.begin(), e.child_hash.end()); + + template <typename Key> bool Merkle<Key>::is_leaf_bytes(const std::vector<uint8_t>& bytes) { + return !bytes.empty() && bytes[0] == TAG_LEAF; } - return buf; -} - -template<typename Key> -typename Merkle<Key>::LeafNode Merkle<Key>::decode_leaf(const std::vector<uint8_t>& bytes) -{ - uint32_t count = read_u32(bytes.data() + 1); - LeafNode n; - n.entries.reserve(count); - const uint8_t* p = bytes.data() + 5; - for (uint32_t i = 0; i < count; ++i) - { - LeafEntry e; - e.key = KeyCodec<Key>::read(p); - std::memcpy(e.payload.data(), p, 32); - p += 32; - n.entries.push_back(std::move(e)); + + // ── Storage helpers ────────────────────────────────────────────────────────── + + template <typename Key> + std::vector<uint8_t> Merkle<Key>::load_node(IStorageBackend& store, + const std::string& hash_hex) { + auto opt = store.Get(hash_hex); + if (!opt) + throw std::runtime_error("Merkle: node not found: " + hash_hex); + return std::move(*opt); } - return n; -} - -template<typename Key> -typename Merkle<Key>::InternalNode Merkle<Key>::decode_internal(const std::vector<uint8_t>& bytes) -{ - uint32_t count = read_u32(bytes.data() + 1); - InternalNode n; - n.entries.reserve(count); - const uint8_t* p = bytes.data() + 5; - for (uint32_t i = 0; i < count; ++i) - { - ChildEntry e; - e.leaf_count = read_u64(p); - p += 8; - e.min_key = KeyCodec<Key>::read(p); - std::memcpy(e.child_hash.data(), p, 32); - p += 32; - n.entries.push_back(std::move(e)); + + template <typename Key> + std::string Merkle<Key>::store_leaf(IStorageBackend& store, const LeafNode& n) { + return store.Put(encode_leaf(n)); } - return n; -} - -template<typename Key> -bool Merkle<Key>::is_leaf_bytes(const std::vector<uint8_t>& bytes) -{ - return !bytes.empty() && bytes[0] == TAG_LEAF; -} - -// ── Storage helpers ────────────────────────────────────────────────────────── - -template<typename Key> -std::vector<uint8_t> Merkle<Key>::load_node(IStorageBackend& store, - const std::string& hash_hex) -{ - auto opt = store.Get(hash_hex); - if (!opt) - throw std::runtime_error("Merkle: node not found: " + hash_hex); - return std::move(*opt); -} - -template<typename Key> -std::string Merkle<Key>::store_leaf(IStorageBackend& store, const LeafNode& n) -{ - return store.Put(encode_leaf(n)); -} - -template<typename Key> -std::string Merkle<Key>::store_internal(IStorageBackend& store, const InternalNode& n) -{ - return store.Put(encode_internal(n)); -} - -template<typename Key> -Key Merkle<Key>::subtree_min_key(IStorageBackend& store, const std::string& node_hex) -{ - auto bytes = load_node(store, node_hex); - if (is_leaf_bytes(bytes)) - { - auto leaf = decode_leaf(bytes); - assert(!leaf.entries.empty() && "Merkle invariant: leaf node must never be empty"); - return leaf.entries.front().key; + + template <typename Key> + std::string Merkle<Key>::store_internal(IStorageBackend& store, const InternalNode& n) { + return store.Put(encode_internal(n)); } - auto node = decode_internal(bytes); - assert(!node.entries.empty() && "Merkle invariant: internal node must never be empty"); - return node.entries.front().min_key; -} - -// ── Routing helper ─────────────────────────────────────────────────────────── - -template<typename Key> -size_t Merkle<Key>::route(const InternalNode& node, const Key& target) -{ - assert(!node.entries.empty() && "Merkle invariant: internal node must never be empty"); - assert(std::is_sorted(node.entries.begin(), node.entries.end(), - [](const ChildEntry& a, const ChildEntry& b) { - return a.min_key < b.min_key; - }) && "Merkle invariant: internal node entries must be sorted by min_key"); - - // Rightmost child whose min_key ≤ target. - // Defaults to 0 (leftmost) when target < all min_keys. - size_t idx = 0; - for (size_t i = 1; i < node.entries.size(); ++i) - { - if (!(target < node.entries[i].min_key)) - idx = i; - else - break; + + template <typename Key> + Key Merkle<Key>::subtree_min_key(IStorageBackend& store, const std::string& node_hex) { + auto bytes = load_node(store, node_hex); + if (is_leaf_bytes(bytes)) { + auto leaf = decode_leaf(bytes); + assert(!leaf.entries.empty() && "Merkle invariant: leaf node must never be empty"); + return leaf.entries.front().key; + } + auto node = decode_internal(bytes); + assert(!node.entries.empty() && "Merkle invariant: internal node must never be empty"); + return node.entries.front().min_key; } - return idx; -} - -// ── Insert ─────────────────────────────────────────────────────────────────── - -template<typename Key> -std::string Merkle<Key>::Insert(IStorageBackend& store, - const std::string& root_hex, - const Key& key, - const Hash32& payload) -{ - if (root_hex.empty()) - { - LeafNode leaf; - leaf.entries.push_back({ key, payload }); - return store_leaf(store, leaf); + + // ── Routing helper ─────────────────────────────────────────────────────────── + + template <typename Key> size_t Merkle<Key>::route(const InternalNode& node, const Key& target) { + assert(!node.entries.empty() && "Merkle invariant: internal node must never be empty"); + assert(std::is_sorted(node.entries.begin(), node.entries.end(), + [](const ChildEntry& a, const ChildEntry& b) { + return a.min_key < b.min_key; + }) && + "Merkle invariant: internal node entries must be sorted by min_key"); + + // Rightmost child whose min_key ≤ target. + // Defaults to 0 (leftmost) when target < all min_keys. + size_t idx = 0; + for (size_t i = 1; i < node.entries.size(); ++i) { + if (!(target < node.entries[i].min_key)) + idx = i; + else + break; + } + return idx; } - auto result = insert_into(store, root_hex, key, payload); - if (!result.did_split) - return result.new_hash; + // ── Insert ─────────────────────────────────────────────────────────────────── + + template <typename Key> + std::string Merkle<Key>::Insert(IStorageBackend& store, const std::string& root_hex, + const Key& key, const Hash32& payload) { + if (root_hex.empty()) { + LeafNode leaf; + leaf.entries.push_back({key, payload}); + return store_leaf(store, leaf); + } + + auto result = insert_into(store, root_hex, key, payload); + if (!result.did_split) + return result.new_hash; + + // Root split: wrap both halves in a new internal root. + Key left_min = subtree_min_key(store, result.new_hash); + + InternalNode new_root; + + ChildEntry left; + left.leaf_count = result.leaf_count; + left.min_key = left_min; + left.child_hash = hex_to_bin(result.new_hash); + new_root.entries.push_back(std::move(left)); + + ChildEntry right; + right.leaf_count = result.split_leaf_count; + right.min_key = result.split_min_key; + right.child_hash = hex_to_bin(result.split_hash); + new_root.entries.push_back(std::move(right)); + + return store_internal(store, new_root); + } + + template <typename Key> + typename Merkle<Key>::InsertResult + Merkle<Key>::insert_into(IStorageBackend& store, const std::string& node_hex, const Key& key, + const Hash32& payload) { + auto bytes = load_node(store, node_hex); + + // ── Leaf node ─────────────────────────────────────────────────────────── + if (is_leaf_bytes(bytes)) { + auto leaf = decode_leaf(bytes); + + auto pos = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key, + [](const LeafEntry& e, const Key& k) { return e.key < k; }); + if (pos != leaf.entries.end() && !(key < pos->key)) { + // Key already present — update payload if it changed, else no-op. + if (pos->payload == payload) { + InsertResult r; + r.new_hash = node_hex; + r.leaf_count = leaf.entries.size(); + return r; + } + pos->payload = payload; + InsertResult r; + r.new_hash = store_leaf(store, leaf); + r.leaf_count = leaf.entries.size(); + return r; + } + + leaf.entries.insert(pos, LeafEntry{key, payload}); - // Root split: wrap both halves in a new internal root. - Key left_min = subtree_min_key(store, result.new_hash); - - InternalNode new_root; - - ChildEntry left; - left.leaf_count = result.leaf_count; - left.min_key = left_min; - left.child_hash = hex_to_bin(result.new_hash); - new_root.entries.push_back(std::move(left)); - - ChildEntry right; - right.leaf_count = result.split_leaf_count; - right.min_key = result.split_min_key; - right.child_hash = hex_to_bin(result.split_hash); - new_root.entries.push_back(std::move(right)); - - return store_internal(store, new_root); -} - -template<typename Key> -typename Merkle<Key>::InsertResult Merkle<Key>::insert_into(IStorageBackend& store, - const std::string& node_hex, - const Key& key, - const Hash32& payload) -{ - auto bytes = load_node(store, node_hex); - - // ── Leaf node ─────────────────────────────────────────────────────────── - if (is_leaf_bytes(bytes)) - { - auto leaf = decode_leaf(bytes); - - auto pos = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key, - [](const LeafEntry& e, const Key& k) { - return e.key < k; - }); - if (pos != leaf.entries.end() && !(key < pos->key)) - { - // Key already present — update payload if it changed, else no-op. - if (pos->payload == payload) - { + if (leaf.entries.size() <= B) { InsertResult r; - r.new_hash = node_hex; + r.new_hash = store_leaf(store, leaf); r.leaf_count = leaf.entries.size(); return r; } - pos->payload = payload; + + // Split leaf at midpoint. + size_t mid = leaf.entries.size() / 2; + LeafNode left_leaf, right_leaf; + left_leaf.entries = {leaf.entries.begin(), + leaf.entries.begin() + static_cast<ptrdiff_t>(mid)}; + right_leaf.entries = {leaf.entries.begin() + static_cast<ptrdiff_t>(mid), + leaf.entries.end()}; + InsertResult r; - r.new_hash = store_leaf(store, leaf); - r.leaf_count = leaf.entries.size(); + r.new_hash = store_leaf(store, left_leaf); + r.leaf_count = left_leaf.entries.size(); + r.did_split = true; + r.split_leaf_count = right_leaf.entries.size(); + r.split_min_key = right_leaf.entries.front().key; + r.split_hash = store_leaf(store, right_leaf); return r; } - leaf.entries.insert(pos, LeafEntry{ key, payload }); + // ── Internal node ─────────────────────────────────────────────────────── + auto node = decode_internal(bytes); + + size_t child_idx = route(node, key); + auto child_result = + insert_into(store, bin_to_hex(node.entries[child_idx].child_hash), key, payload); - if (leaf.entries.size() <= B) - { + node.entries[child_idx].leaf_count = child_result.leaf_count; + node.entries[child_idx].child_hash = hex_to_bin(child_result.new_hash); + + // Update min_key for the modified child — only child 0 can have its min + // decrease (routing guarantees min_key[i>0] ≤ inserted key, so inserting + // below min_key[i>0] is impossible). + if (child_idx == 0) + node.entries[0].min_key = subtree_min_key(store, child_result.new_hash); + + uint64_t total = 0; + for (const auto& e : node.entries) + total += e.leaf_count; + + if (!child_result.did_split) { + InsertResult r; + r.new_hash = store_internal(store, node); + r.leaf_count = total; + return r; + } + + // Insert the right sibling immediately after child_idx. + ChildEntry sibling; + sibling.leaf_count = child_result.split_leaf_count; + sibling.min_key = child_result.split_min_key; + sibling.child_hash = hex_to_bin(child_result.split_hash); + node.entries.insert(node.entries.begin() + static_cast<ptrdiff_t>(child_idx) + 1, + std::move(sibling)); + total += child_result.split_leaf_count; + + if (node.entries.size() <= B) { InsertResult r; - r.new_hash = store_leaf(store, leaf); - r.leaf_count = leaf.entries.size(); + r.new_hash = store_internal(store, node); + r.leaf_count = total; return r; } - // Split leaf at midpoint. - size_t mid = leaf.entries.size() / 2; - LeafNode left_leaf, right_leaf; - left_leaf.entries = { leaf.entries.begin(), - leaf.entries.begin() + static_cast<ptrdiff_t>(mid) }; - right_leaf.entries = { leaf.entries.begin() + static_cast<ptrdiff_t>(mid), - leaf.entries.end() }; + // Split this internal node. + size_t mid = node.entries.size() / 2; + InternalNode left_node, right_node; + left_node.entries = {node.entries.begin(), + node.entries.begin() + static_cast<ptrdiff_t>(mid)}; + right_node.entries = {node.entries.begin() + static_cast<ptrdiff_t>(mid), + node.entries.end()}; + + uint64_t left_count = 0, right_count = 0; + for (const auto& e : left_node.entries) + left_count += e.leaf_count; + for (const auto& e : right_node.entries) + right_count += e.leaf_count; InsertResult r; - r.new_hash = store_leaf(store, left_leaf); - r.leaf_count = left_leaf.entries.size(); - r.did_split = true; - r.split_leaf_count = right_leaf.entries.size(); - r.split_min_key = right_leaf.entries.front().key; - r.split_hash = store_leaf(store, right_leaf); + r.new_hash = store_internal(store, left_node); + r.leaf_count = left_count; + r.did_split = true; + r.split_leaf_count = right_count; + r.split_min_key = right_node.entries.front().min_key; + r.split_hash = store_internal(store, right_node); return r; } - // ── Internal node ─────────────────────────────────────────────────────── - auto node = decode_internal(bytes); - - size_t child_idx = route(node, key); - auto child_result = insert_into(store, - bin_to_hex(node.entries[child_idx].child_hash), - key, - payload); + // ── Remove ─────────────────────────────────────────────────────────────────── + + template <typename Key> + std::string Merkle<Key>::Remove(IStorageBackend& store, const std::string& root_hex, + const Key& key) { + if (root_hex.empty()) + return ""; + auto result = remove_from(store, root_hex, key); + if (result.new_hash.empty()) + return ""; + + // Collapse: if the root is an internal node with a single child, skip it. + auto bytes = load_node(store, result.new_hash); + if (!is_leaf_bytes(bytes)) { + auto node = decode_internal(bytes); + if (node.entries.size() == 1) + return bin_to_hex(node.entries[0].child_hash); + } + return result.new_hash; + } - node.entries[child_idx].leaf_count = child_result.leaf_count; - node.entries[child_idx].child_hash = hex_to_bin(child_result.new_hash); + template <typename Key> + typename Merkle<Key>::RemoveResult + Merkle<Key>::remove_from(IStorageBackend& store, const std::string& node_hex, const Key& key) { + auto bytes = load_node(store, node_hex); + + // ── Leaf node ─────────────────────────────────────────────────────────── + if (is_leaf_bytes(bytes)) { + auto leaf = decode_leaf(bytes); + auto it = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key, + [](const LeafEntry& e, const Key& k) { return e.key < k; }); + if (it == leaf.entries.end() || key < it->key) + return {node_hex, leaf.entries.size()}; // not found — no change + + leaf.entries.erase(it); + if (leaf.entries.empty()) + return {"", 0}; + return {store_leaf(store, leaf), leaf.entries.size()}; + } - // Update min_key for the modified child — only child 0 can have its min - // decrease (routing guarantees min_key[i>0] ≤ inserted key, so inserting - // below min_key[i>0] is impossible). - if (child_idx == 0) - node.entries[0].min_key = subtree_min_key(store, child_result.new_hash); + // ── Internal node ─────────────────────────────────────────────────────── + auto node = decode_internal(bytes); - uint64_t total = 0; - for (const auto& e : node.entries) total += e.leaf_count; + size_t child_idx = route(node, key); + auto child_result = remove_from(store, bin_to_hex(node.entries[child_idx].child_hash), key); + + if (child_result.new_hash.empty()) { + node.entries.erase(node.entries.begin() + static_cast<ptrdiff_t>(child_idx)); + if (node.entries.empty()) + return {"", 0}; + } else { + node.entries[child_idx].leaf_count = child_result.leaf_count; + node.entries[child_idx].child_hash = hex_to_bin(child_result.new_hash); + // The min of any child might have changed if we removed its minimum entry. + node.entries[child_idx].min_key = subtree_min_key(store, child_result.new_hash); + } - if (!child_result.did_split) - { - InsertResult r; - r.new_hash = store_internal(store, node); - r.leaf_count = total; - return r; + uint64_t total = 0; + for (const auto& e : node.entries) + total += e.leaf_count; + return {store_internal(store, node), total}; } - // Insert the right sibling immediately after child_idx. - ChildEntry sibling; - sibling.leaf_count = child_result.split_leaf_count; - sibling.min_key = child_result.split_min_key; - sibling.child_hash = hex_to_bin(child_result.split_hash); - node.entries.insert(node.entries.begin() + static_cast<ptrdiff_t>(child_idx) + 1, - std::move(sibling)); - total += child_result.split_leaf_count; - - if (node.entries.size() <= B) - { - InsertResult r; - r.new_hash = store_internal(store, node); - r.leaf_count = total; - return r; + // ── Get ────────────────────────────────────────────────────────────────────── + + template <typename Key> + std::optional<Hash32> Merkle<Key>::Get(IStorageBackend& store, const std::string& root_hex, + const Key& key) { + if (root_hex.empty()) + return std::nullopt; + return get_from(store, root_hex, key); } - // Split this internal node. - size_t mid = node.entries.size() / 2; - InternalNode left_node, right_node; - left_node.entries = { node.entries.begin(), - node.entries.begin() + static_cast<ptrdiff_t>(mid) }; - right_node.entries = { node.entries.begin() + static_cast<ptrdiff_t>(mid), - node.entries.end() }; - - uint64_t left_count = 0, right_count = 0; - for (const auto& e : left_node.entries) left_count += e.leaf_count; - for (const auto& e : right_node.entries) right_count += e.leaf_count; - - InsertResult r; - r.new_hash = store_internal(store, left_node); - r.leaf_count = left_count; - r.did_split = true; - r.split_leaf_count = right_count; - r.split_min_key = right_node.entries.front().min_key; - r.split_hash = store_internal(store, right_node); - return r; -} - -// ── Remove ─────────────────────────────────────────────────────────────────── - -template<typename Key> -std::string Merkle<Key>::Remove(IStorageBackend& store, - const std::string& root_hex, - const Key& key) -{ - if (root_hex.empty()) return ""; - auto result = remove_from(store, root_hex, key); - if (result.new_hash.empty()) return ""; - - // Collapse: if the root is an internal node with a single child, skip it. - auto bytes = load_node(store, result.new_hash); - if (!is_leaf_bytes(bytes)) - { + template <typename Key> + std::optional<Hash32> Merkle<Key>::get_from(IStorageBackend& store, const std::string& node_hex, + const Key& key) { + auto bytes = load_node(store, node_hex); + if (is_leaf_bytes(bytes)) { + auto leaf = decode_leaf(bytes); + auto it = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key, + [](const LeafEntry& e, const Key& k) { return e.key < k; }); + if (it == leaf.entries.end() || key < it->key) + return std::nullopt; + return it->payload; + } auto node = decode_internal(bytes); - if (node.entries.size() == 1) - return bin_to_hex(node.entries[0].child_hash); + size_t child_idx = route(node, key); + return get_from(store, bin_to_hex(node.entries[child_idx].child_hash), key); } - return result.new_hash; -} - -template<typename Key> -typename Merkle<Key>::RemoveResult Merkle<Key>::remove_from(IStorageBackend& store, - const std::string& node_hex, - const Key& key) -{ - auto bytes = load_node(store, node_hex); - - // ── Leaf node ─────────────────────────────────────────────────────────── - if (is_leaf_bytes(bytes)) - { - auto leaf = decode_leaf(bytes); - auto it = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key, - [](const LeafEntry& e, const Key& k) { - return e.key < k; - }); - if (it == leaf.entries.end() || key < it->key) - return { node_hex, leaf.entries.size() }; // not found — no change - - leaf.entries.erase(it); - if (leaf.entries.empty()) - return { "", 0 }; - return { store_leaf(store, leaf), leaf.entries.size() }; + + // ── Page ───────────────────────────────────────────────────────────────────── + + template <typename Key> + std::vector<typename Merkle<Key>::Entry> Merkle<Key>::Page(IStorageBackend& store, + const std::string& root_hex, + size_t offset, size_t limit) { + if (root_hex.empty() || limit == 0) + return {}; + std::vector<Entry> out; + out.reserve(limit); + size_t skip = offset; + page_from(store, root_hex, skip, limit, out); + return out; } - // ── Internal node ─────────────────────────────────────────────────────── - auto node = decode_internal(bytes); + template <typename Key> + void Merkle<Key>::page_from(IStorageBackend& store, const std::string& node_hex, size_t& offset, + size_t limit, std::vector<Entry>& out) { + auto bytes = load_node(store, node_hex); - size_t child_idx = route(node, key); - auto child_result = remove_from(store, - bin_to_hex(node.entries[child_idx].child_hash), - key); + if (is_leaf_bytes(bytes)) { + auto leaf = decode_leaf(bytes); + const size_t available = leaf.entries.size(); - if (child_result.new_hash.empty()) - { - node.entries.erase(node.entries.begin() + static_cast<ptrdiff_t>(child_idx)); - if (node.entries.empty()) return { "", 0 }; - } - else - { - node.entries[child_idx].leaf_count = child_result.leaf_count; - node.entries[child_idx].child_hash = hex_to_bin(child_result.new_hash); - // The min of any child might have changed if we removed its minimum entry. - node.entries[child_idx].min_key = subtree_min_key(store, child_result.new_hash); - } + if (offset >= available) { + offset -= available; + return; + } - uint64_t total = 0; - for (const auto& e : node.entries) total += e.leaf_count; - return { store_internal(store, node), total }; -} - -// ── Get ────────────────────────────────────────────────────────────────────── - -template<typename Key> -std::optional<Hash32> Merkle<Key>::Get(IStorageBackend& store, - const std::string& root_hex, - const Key& key) -{ - if (root_hex.empty()) return std::nullopt; - return get_from(store, root_hex, key); -} - -template<typename Key> -std::optional<Hash32> Merkle<Key>::get_from(IStorageBackend& store, - const std::string& node_hex, - const Key& key) -{ - auto bytes = load_node(store, node_hex); - if (is_leaf_bytes(bytes)) - { - auto leaf = decode_leaf(bytes); - auto it = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key, - [](const LeafEntry& e, const Key& k) { - return e.key < k; - }); - if (it == leaf.entries.end() || key < it->key) - return std::nullopt; - return it->payload; - } - auto node = decode_internal(bytes); - size_t child_idx = route(node, key); - return get_from(store, bin_to_hex(node.entries[child_idx].child_hash), key); -} - -// ── Page ───────────────────────────────────────────────────────────────────── - -template<typename Key> -std::vector<typename Merkle<Key>::Entry> Merkle<Key>::Page(IStorageBackend& store, - const std::string& root_hex, - size_t offset, - size_t limit) -{ - if (root_hex.empty() || limit == 0) return {}; - std::vector<Entry> out; - out.reserve(limit); - size_t skip = offset; - page_from(store, root_hex, skip, limit, out); - return out; -} - -template<typename Key> -void Merkle<Key>::page_from(IStorageBackend& store, - const std::string& node_hex, - size_t& offset, - size_t limit, - std::vector<Entry>& out) -{ - auto bytes = load_node(store, node_hex); - - if (is_leaf_bytes(bytes)) - { - auto leaf = decode_leaf(bytes); - const size_t available = leaf.entries.size(); - - if (offset >= available) - { - offset -= available; + for (size_t i = offset; i < available && out.size() < limit; ++i) + out.push_back(Entry{leaf.entries[i].key, leaf.entries[i].payload}); + + offset = 0; return; } - for (size_t i = offset; i < available && out.size() < limit; ++i) - out.push_back(Entry{ leaf.entries[i].key, leaf.entries[i].payload }); - - offset = 0; - return; - } + auto node = decode_internal(bytes); - auto node = decode_internal(bytes); + for (const auto& entry : node.entries) { + if (out.size() >= limit) + break; - for (const auto& entry : node.entries) - { - if (out.size() >= limit) break; + if (offset >= entry.leaf_count) { + offset -= entry.leaf_count; + continue; + } - if (offset >= entry.leaf_count) - { - offset -= entry.leaf_count; - continue; + page_from(store, bin_to_hex(entry.child_hash), offset, limit, out); } - - page_from(store, bin_to_hex(entry.child_hash), offset, limit, out); } -} -// ── Explicit instantiations ────────────────────────────────────────────────── + // ── Explicit instantiations ────────────────────────────────────────────────── -template class Merkle<Hash32>; -template class Merkle<std::string>; + template class Merkle<Hash32>; + template class Merkle<std::string>; } // namespace nt diff --git a/src/MultigroupCodec.cpp b/src/MultigroupCodec.cpp index 3deaa23..0d0cf14 100644 --- a/src/MultigroupCodec.cpp +++ b/src/MultigroupCodec.cpp @@ -4,81 +4,68 @@ #include <map> -namespace nt::MultigroupCodec -{ +namespace nt::MultigroupCodec { // A relation with zero tuples reports an empty merkle_root externally. // The merkle tree's payload type is fixed-width Hash32, so the codec // maps "" ↔ the all-zero hash. The collision probability with a real // SHA256 hitting all-zero (2^-256) is treated as unreachable. - static nt::Hash32 encode_payload(const std::string& hex) - { - if (hex.empty()) return nt::Hash32{}; + static nt::Hash32 encode_payload(const std::string& hex) { + if (hex.empty()) + return nt::Hash32{}; return nt::hex_to_bin(hex); } - static std::string decode_payload(const nt::Hash32& bin) - { + static std::string decode_payload(const nt::Hash32& bin) { static const nt::Hash32 zero{}; - if (bin == zero) return ""; + if (bin == zero) + return ""; return nt::bin_to_hex(bin); } - std::string Build(IStorageBackend& store, - const std::vector<RelationEntry>& relations) - { + std::string Build(IStorageBackend& store, const std::vector<RelationEntry>& relations) { std::map<std::string, std::string> canonical; for (const auto& [name, root_hex] : relations) canonical[name] = root_hex; std::string root; for (const auto& [name, root_hex] : canonical) - root = nt::Merkle<std::string>::Insert(store, root, name, - encode_payload(root_hex)); + root = nt::Merkle<std::string>::Insert(store, root, name, encode_payload(root_hex)); return root; } - std::vector<RelationEntry> List(IStorageBackend& store, - const std::string& root_hex) - { + std::vector<RelationEntry> List(IStorageBackend& store, const std::string& root_hex) { std::vector<RelationEntry> out; constexpr size_t kPageSize = 1024; size_t offset = 0; - while (true) - { - auto page = nt::Merkle<std::string>::Page(store, root_hex, - offset, kPageSize); - if (page.empty()) break; + while (true) { + auto page = nt::Merkle<std::string>::Page(store, root_hex, offset, kPageSize); + if (page.empty()) + break; for (auto& entry : page) - out.emplace_back(std::move(entry.key), - decode_payload(entry.payload)); - if (page.size() < kPageSize) break; + out.emplace_back(std::move(entry.key), decode_payload(entry.payload)); + if (page.size() < kPageSize) + break; offset += page.size(); } return out; } - std::string InsertOne(IStorageBackend& store, - const std::string& root_hex, - const std::string& relation_name, - const std::string& relation_root_hex) - { + std::string InsertOne(IStorageBackend& store, const std::string& root_hex, + const std::string& relation_name, const std::string& relation_root_hex) { return nt::Merkle<std::string>::Insert(store, root_hex, relation_name, - encode_payload(relation_root_hex)); + encode_payload(relation_root_hex)); } - std::string RemoveOne(IStorageBackend& store, - const std::string& root_hex, - const std::string& relation_name) - { + std::string RemoveOne(IStorageBackend& store, const std::string& root_hex, + const std::string& relation_name) { return nt::Merkle<std::string>::Remove(store, root_hex, relation_name); } - std::string Lookup(IStorageBackend& store, - const std::string& root_hex, - const std::string& relation_name) - { + std::string Lookup(IStorageBackend& store, const std::string& root_hex, + const std::string& relation_name) { auto found = nt::Merkle<std::string>::Get(store, root_hex, relation_name); - if (!found) return ""; + if (!found) + return ""; return decode_payload(*found); } -} +} // namespace nt::MultigroupCodec diff --git a/src/NamespaceReferenceManager.cpp b/src/NamespaceReferenceManager.cpp index 455d077..0d99b73 100644 --- a/src/NamespaceReferenceManager.cpp +++ b/src/NamespaceReferenceManager.cpp @@ -2,58 +2,48 @@ #include "Merkle.h" -namespace nt -{ +namespace nt { NamespaceReferenceManager::NamespaceReferenceManager(ObjectManager& objects, - IStorageBackend& storage) - : objects_(objects), storage_(storage) - {} + IStorageBackend& storage) + : objects_(objects), storage_(storage) { + } // Resolves the multigroup hash that `mg_name` currently maps to inside the // branch-tree rooted at `branch_tree_root`. Returns the empty string when // the branch is unborn (empty root) or the multigroup is absent. - static std::string lookup_mg_hash(IStorageBackend& storage, - const std::string& branch_tree_root, - const std::string& mg_name) - { - if (branch_tree_root.empty()) return ""; + static std::string lookup_mg_hash(IStorageBackend& storage, const std::string& branch_tree_root, + const std::string& mg_name) { + if (branch_tree_root.empty()) + return ""; auto found = Merkle<std::string>::Get(storage, branch_tree_root, mg_name); - if (!found) return ""; + if (!found) + return ""; // All-zero payload = "no snapshot bound" sentinel matching MultigroupCodec. static const Hash32 zero{}; - if (*found == zero) return ""; + if (*found == zero) + return ""; return bin_to_hex(*found); } - std::vector<std::string> NamespaceReferenceManager::Resolve( - std::vector<std::string> path) const - { + std::vector<std::string> + NamespaceReferenceManager::Resolve(std::vector<std::string> path) const { constexpr int kMaxReparseDepth = 30; - for (int depth = 0; depth < kMaxReparseDepth; ++depth) - { + for (int depth = 0; depth < kMaxReparseDepth; ++depth) { // /system/sessions/<X>/branches/<name>/multigroups/<mg>/<sub>... // — per-session override takes precedence; absent override falls // back to the global branch. Requires at minimum the literal // "multigroups" qualifier and an mg name. - if (path.size() > 6 - && path[0] == "system" - && path[1] == "sessions" - && path[3] == "branches" - && path[5] == "multigroups") - { - const std::vector<std::string> session_path{ - "system", "sessions", path[2] - }; + if (path.size() > 6 && path[0] == "system" && path[1] == "sessions" && + path[3] == "branches" && path[5] == "multigroups") { + const std::vector<std::string> session_path{"system", "sessions", path[2]}; auto* session_entry = objects_.Find(session_path); std::string branch_tree_root; - if (session_entry && session_entry->object) - { - auto* session = dynamic_cast<ObjectManager::Session*>( - session_entry->object.get()); - if (session) - { + if (session_entry && session_entry->object) { + auto* session = + dynamic_cast<ObjectManager::Session*>(session_entry->object.get()); + if (session) { auto it = session->branch_overrides.find(path[4]); if (it != session->branch_overrides.end()) branch_tree_root = it->second; @@ -61,27 +51,21 @@ namespace nt } // No session-level override — defer to the global branch's HEAD. - if (branch_tree_root.empty()) - { - const std::vector<std::string> branch_path{ - "system", "branches", path[4] - }; + if (branch_tree_root.empty()) { + const std::vector<std::string> branch_path{"system", "branches", path[4]}; auto* bentry = objects_.Find(branch_path); - if (bentry && bentry->object) - { - auto* branch = dynamic_cast<ObjectManager::Branch*>( - bentry->object.get()); - if (branch) branch_tree_root = branch->target_hash; + if (bentry && bentry->object) { + auto* branch = dynamic_cast<ObjectManager::Branch*>(bentry->object.get()); + if (branch) + branch_tree_root = branch->target_hash; } } - const std::string mg_hash = - lookup_mg_hash(storage_, branch_tree_root, path[6]); - if (mg_hash.empty()) return path; + const std::string mg_hash = lookup_mg_hash(storage_, branch_tree_root, path[6]); + if (mg_hash.empty()) + return path; - std::vector<std::string> rewritten{ - "system", "snapshots", mg_hash - }; + std::vector<std::string> rewritten{"system", "snapshots", mg_hash}; for (size_t i = 7; i < path.size(); ++i) rewritten.push_back(path[i]); @@ -94,28 +78,22 @@ namespace nt // Requires the literal "multigroups" qualifier and an mg name. A // bare /system/branches/<name> path opens the branch object itself // and is returned unchanged. - if (path.size() > 4 - && path[0] == "system" - && path[1] == "branches" - && path[3] == "multigroups") - { - const std::vector<std::string> branch_path{ - "system", "branches", path[2] - }; + if (path.size() > 4 && path[0] == "system" && path[1] == "branches" && + path[3] == "multigroups") { + const std::vector<std::string> branch_path{"system", "branches", path[2]}; auto* entry = objects_.Find(branch_path); - if (!entry || !entry->object) return path; + if (!entry || !entry->object) + return path; - auto* branch = - dynamic_cast<ObjectManager::Branch*>(entry->object.get()); - if (!branch) return path; + auto* branch = dynamic_cast<ObjectManager::Branch*>(entry->object.get()); + if (!branch) + return path; - const std::string mg_hash = - lookup_mg_hash(storage_, branch->target_hash, path[4]); - if (mg_hash.empty()) return path; + const std::string mg_hash = lookup_mg_hash(storage_, branch->target_hash, path[4]); + if (mg_hash.empty()) + return path; - std::vector<std::string> rewritten{ - "system", "snapshots", mg_hash - }; + std::vector<std::string> rewritten{"system", "snapshots", mg_hash}; for (size_t i = 5; i < path.size(); ++i) rewritten.push_back(path[i]); @@ -129,4 +107,4 @@ namespace nt // Cycle guard tripped — surface as a lookup miss. return {}; } -} +} // namespace nt diff --git a/src/ObjectManager.cpp b/src/ObjectManager.cpp index 67504c3..70e622b 100644 --- a/src/ObjectManager.cpp +++ b/src/ObjectManager.cpp @@ -1,11 +1,8 @@ #include "ObjectManager.h" -namespace nt -{ - void ObjectManager::Register(std::vector<std::string> path, - std::unique_ptr<IObject> object, - std::unique_ptr<object_type> type) - { +namespace nt { + void ObjectManager::Register(std::vector<std::string> path, std::unique_ptr<IObject> object, + std::unique_ptr<object_type> type) { auto head = std::make_unique<registry_head>(); head->reference_count = 0; head->handle_count = 0; @@ -19,11 +16,9 @@ namespace nt entries = std::move(entry); } - ObjectManager::registry* ObjectManager::Find(const std::vector<std::string> object_path) - { + ObjectManager::registry* ObjectManager::Find(const std::vector<std::string> object_path) { registry* current = entries.get(); - while (current != nullptr) - { + while (current != nullptr) { if (current->head->path == object_path) return current; current = current->next.get(); @@ -31,13 +26,10 @@ namespace nt return nullptr; } - bool ObjectManager::Unregister(const std::vector<std::string>& object_path) - { + bool ObjectManager::Unregister(const std::vector<std::string>& object_path) { std::unique_ptr<registry>* slot = &entries; - while (slot->get() != nullptr) - { - if ((*slot)->head->path == object_path) - { + while (slot->get() != nullptr) { + if ((*slot)->head->path == object_path) { *slot = std::move((*slot)->next); return true; } @@ -45,4 +37,4 @@ namespace nt } return false; } -} +} // namespace nt diff --git a/src/PermissionsManager.cpp b/src/PermissionsManager.cpp index ddd49eb..bcdfdd7 100644 --- a/src/PermissionsManager.cpp +++ b/src/PermissionsManager.cpp @@ -1,19 +1,17 @@ #include "PermissionsManager.h" -namespace nt -{ - std::set<AUTH_CLAIM> PermissionsManager::Firewall(AUTH_METHOD method) - { +namespace nt { + std::set<AUTH_CLAIM> PermissionsManager::Firewall(AUTH_METHOD method) { return {}; } - const bool PermissionsManager::Access(const ObjectManager::registry* object, const void* connection_context) - { - // Checks the security descriptor on the head of the object we find in the ObjectManager::registry - // Then additionally check other metadata yet to be defined in the connection_context, - // like user group, policy, etc. - // Yet to decide if this should be summoned at every attempt to get ahold of an object, - // that might produce significant overhead. How can we solve this? + const bool PermissionsManager::Access(const ObjectManager::registry* object, + const void* connection_context) { + // Checks the security descriptor on the head of the object we find in the + // ObjectManager::registry Then additionally check other metadata yet to be defined in the + // connection_context, like user group, policy, etc. Yet to decide if this should be + // summoned at every attempt to get ahold of an object, that might produce significant + // overhead. How can we solve this? return object != nullptr; } -} +} // namespace nt diff --git a/src/RNT_C_API.cpp b/src/RNT_C_API.cpp index c92d03b..abd683c 100644 --- a/src/RNT_C_API.cpp +++ b/src/RNT_C_API.cpp @@ -3,13 +3,13 @@ #include "CursorManager.h" #include "HandlerManager.h" #include "IdentityManager.h" +#include "InMemoryBackend.h" #include "LifecycleManager.h" #include "Merkle.h" #include "MultigroupCodec.h" #include "NamespaceReferenceManager.h" #include "ObjectManager.h" #include "PermissionsManager.h" -#include "InMemoryBackend.h" #include "SqliteBackend.h" #include "TupleCodec.h" #include "VM.h" @@ -34,129 +34,119 @@ // contended again. // --------------------------------------------------------------------------- -namespace -{ - struct Runtime - { +namespace { + struct Runtime { std::unique_ptr<nt::IStorageBackend> storage; - nt::ObjectManager objects; + nt::ObjectManager objects; nt::PermissionsManager permissions; - nt::IdentityManager identities; + nt::IdentityManager identities; std::unique_ptr<nt::LifecycleManager> lifecycles; std::unique_ptr<nt::NamespaceReferenceManager> references; std::unique_ptr<nt::HandlerManager> handler; - std::unique_ptr<nt::CursorManager> cursors; + std::unique_ptr<nt::CursorManager> cursors; }; static std::unique_ptr<Runtime> g_rt; - static bool g_init_done = false; - bool is_initialized() { return g_init_done; } - - static std::vector<std::string> split_path(const char* path) - { + static std::vector<std::string> split_path(const char* path) { std::vector<std::string> parts; - if (!path) return parts; + if (!path) + return parts; std::string s(path); - if (!s.empty() && s[0] == '/') s.erase(0, 1); + if (!s.empty() && s[0] == '/') + s.erase(0, 1); std::stringstream ss(s); std::string part; while (std::getline(ss, part, '/')) - if (!part.empty()) parts.push_back(part); + if (!part.empty()) + parts.push_back(part); return parts; } - static std::vector<nt::Attribute> parse_kv(const char* kv) - { + static std::vector<nt::Attribute> parse_kv(const char* kv) { std::vector<nt::Attribute> attrs; - if (!kv) return attrs; + if (!kv) + return attrs; std::stringstream ss(kv); std::string line; - while (std::getline(ss, line)) - { - if (line.empty()) continue; + while (std::getline(ss, line)) { + if (line.empty()) + continue; const auto pos = line.find('='); - if (pos == std::string::npos) continue; - attrs.push_back({ line.substr(0, pos), line.substr(pos + 1) }); + if (pos == std::string::npos) + continue; + attrs.push_back({line.substr(0, pos), line.substr(pos + 1)}); } return attrs; } - static std::string tuple_to_kv(nt::Tuple* t) - { + static std::string tuple_to_kv(nt::Tuple* t) { std::string out; t->Reset(); const nt::Attribute* a = t->Next(); - while (a) - { + while (a) { out += a->name + "=" + a->value + "\n"; a = t->Next(); } return out; } - static char* heap_str(const std::string& s) - { + static char* heap_str(const std::string& s) { char* p = new char[s.size() + 1]; std::memcpy(p, s.data(), s.size()); p[s.size()] = '\0'; return p; } - static std::unique_ptr<nt::ObjectManager::object_type> make_relation_type() - { - auto t = std::make_unique<nt::ObjectManager::object_type>(); - t->label = RELATION; + static std::unique_ptr<nt::ObjectManager::object_type> make_relation_type() { + auto t = std::make_unique<nt::ObjectManager::object_type>(); + t->label = RELATION; t->disposable = false; - t->methods = { OPEN, CLOSE }; + t->methods = {OPEN, CLOSE}; t->exclusive = false; return t; } - static std::unique_ptr<nt::ObjectManager::object_type> make_branch_type() - { - auto t = std::make_unique<nt::ObjectManager::object_type>(); - t->label = BRANCH; + static std::unique_ptr<nt::ObjectManager::object_type> make_branch_type() { + auto t = std::make_unique<nt::ObjectManager::object_type>(); + t->label = BRANCH; t->disposable = false; - t->methods = { OPEN, CLOSE }; + t->methods = {OPEN, CLOSE}; // Branches are mutable reference heads: serialize writers through // LifecycleManager::Contention. t->exclusive = true; return t; } - static std::unique_ptr<nt::ObjectManager::object_type> make_multigroup_type() - { - auto t = std::make_unique<nt::ObjectManager::object_type>(); - t->label = MULTIGROUP; + static std::unique_ptr<nt::ObjectManager::object_type> make_multigroup_type() { + auto t = std::make_unique<nt::ObjectManager::object_type>(); + t->label = MULTIGROUP; t->disposable = false; - t->methods = { OPEN, CLOSE }; + t->methods = {OPEN, CLOSE}; // Multigroup snapshots are immutable and content-addressed; concurrent // readers never contend. GC is gated by reference_count only. t->exclusive = false; return t; } - static std::unique_ptr<nt::ObjectManager::object_type> make_branch_tree_type() - { - auto t = std::make_unique<nt::ObjectManager::object_type>(); - t->label = BRANCH_TREE; + static std::unique_ptr<nt::ObjectManager::object_type> make_branch_tree_type() { + auto t = std::make_unique<nt::ObjectManager::object_type>(); + t->label = BRANCH_TREE; t->disposable = false; - t->methods = { OPEN, CLOSE }; + t->methods = {OPEN, CLOSE}; // Branch-tree blobs are immutable content-addressed merkle roots; // GC is gated by reference_count only. t->exclusive = false; return t; } - static std::unique_ptr<nt::ObjectManager::object_type> make_session_type() - { - auto t = std::make_unique<nt::ObjectManager::object_type>(); - t->label = SESSION; + static std::unique_ptr<nt::ObjectManager::object_type> make_session_type() { + auto t = std::make_unique<nt::ObjectManager::object_type>(); + t->label = SESSION; // Sessions live only as long as their connection; rnt_session_close // removes them via ObjectManager::Unregister. t->disposable = true; - t->methods = { OPEN, CLOSE }; + t->methods = {OPEN, CLOSE}; // Multiple readers/writers may consult a session concurrently to read // overrides; contention is only enforced when an exclusive mutator // (set_branch) is wired up. Default to non-exclusive for now. @@ -168,18 +158,15 @@ namespace // drawn from std::random_device-seeded mt19937_64; we do not need // cryptographic strength here, just enough entropy that two concurrent // rnt_session_open calls cannot collide. - static std::string random_session_hash() - { - static thread_local std::mt19937_64 rng{ std::random_device{}() }; + static std::string random_session_hash() { + static thread_local std::mt19937_64 rng{std::random_device{}()}; static const char hex[] = "0123456789abcdef"; std::string out; out.reserve(64); - for (int i = 0; i < 4; ++i) - { + for (int i = 0; i < 4; ++i) { uint64_t v = rng(); - for (int b = 0; b < 8; ++b) - { + for (int b = 0; b < 8; ++b) { uint8_t byte = static_cast<uint8_t>(v & 0xFF); out.push_back(hex[(byte >> 4) & 0xF]); out.push_back(hex[byte & 0xF]); @@ -198,26 +185,28 @@ namespace // Each child Relation is Pinned by its parent Multigroup at creation time. // LifecycleManager::CascadeMultigroup releases these pins when the // multigroup itself becomes GC-eligible. - static std::string register_snapshot( - const std::vector<nt::MultigroupCodec::RelationEntry>& relations) - { - if (!g_rt) return {}; + static std::string + register_snapshot(const std::vector<nt::MultigroupCodec::RelationEntry>& relations) { + if (!g_rt) + return {}; const std::string hash = nt::MultigroupCodec::Build(*g_rt->storage, relations); - if (hash.empty()) return {}; + if (hash.empty()) + return {}; const auto snap_path = split_path(("/system/snapshots/" + hash).c_str()); - if (g_rt->objects.Find(snap_path) != nullptr) return hash; + if (g_rt->objects.Find(snap_path) != nullptr) + return hash; auto mg = std::make_unique<nt::ObjectManager::Multigroup>(); mg->merkle_root = hash; g_rt->objects.Register(snap_path, std::move(mg), make_multigroup_type()); - for (const auto& [name, root] : relations) - { - const auto rel_path = split_path( - ("/system/snapshots/" + hash + "/relations/" + name).c_str()); - if (g_rt->objects.Find(rel_path) != nullptr) continue; + for (const auto& [name, root] : relations) { + const auto rel_path = + split_path(("/system/snapshots/" + hash + "/relations/" + name).c_str()); + if (g_rt->objects.Find(rel_path) != nullptr) + continue; auto rel = std::make_unique<nt::ObjectManager::Relation>(); rel->merkle_root = root; @@ -232,22 +221,21 @@ namespace // Enumerates (mg_name, mg_hash) pairs in a branch-tree. static std::vector<std::pair<std::string, std::string>> - list_branch_tree(const std::string& branch_tree_root) - { + list_branch_tree(const std::string& branch_tree_root) { std::vector<std::pair<std::string, std::string>> out; - if (branch_tree_root.empty()) return out; + if (branch_tree_root.empty()) + return out; constexpr size_t kPageSize = 1024; size_t offset = 0; - while (true) - { - auto page = nt::Merkle<std::string>::Page(*g_rt->storage, - branch_tree_root, - offset, kPageSize); - if (page.empty()) break; + while (true) { + auto page = + nt::Merkle<std::string>::Page(*g_rt->storage, branch_tree_root, offset, kPageSize); + if (page.empty()) + break; for (auto& entry : page) - out.emplace_back(std::move(entry.key), - nt::bin_to_hex(entry.payload)); - if (page.size() < kPageSize) break; + out.emplace_back(std::move(entry.key), nt::bin_to_hex(entry.payload)); + if (page.size() < kPageSize) + break; offset += page.size(); } return out; @@ -257,20 +245,20 @@ namespace // takes one structural pin on each multigroup the tree references. The // pins are mirrored by LifecycleManager::CascadeBranchTree at GC time. // Idempotent: a second call with the same hash returns immediately. - static void register_branch_tree(const std::string& tree_root) - { - if (tree_root.empty()) return; - const auto bt_path = split_path( - ("/system/branch_trees/" + tree_root).c_str()); - if (g_rt->objects.Find(bt_path) != nullptr) return; + static void register_branch_tree(const std::string& tree_root) { + if (tree_root.empty()) + return; + const auto bt_path = split_path(("/system/branch_trees/" + tree_root).c_str()); + if (g_rt->objects.Find(bt_path) != nullptr) + return; auto bt = std::make_unique<nt::ObjectManager::BranchTree>(); bt->merkle_root = tree_root; g_rt->objects.Register(bt_path, std::move(bt), make_branch_tree_type()); - for (const auto& [_, mg_hash] : list_branch_tree(tree_root)) - { - if (mg_hash.empty()) continue; + for (const auto& [_, mg_hash] : list_branch_tree(tree_root)) { + if (mg_hash.empty()) + continue; const auto p = split_path(("/system/snapshots/" + mg_hash).c_str()); g_rt->lifecycles->Pin(g_rt->objects.Find(p)); } @@ -281,20 +269,16 @@ namespace // a no-op advance never sees a pinned BranchTree's ref_count briefly hit // zero and trigger cascade collection of every mg it references. static void rebind_branch_tree_pin(const std::string& old_tree_root, - const std::string& new_tree_root) - { - if (old_tree_root == new_tree_root) return; - if (!new_tree_root.empty()) - { + const std::string& new_tree_root) { + if (old_tree_root == new_tree_root) + return; + if (!new_tree_root.empty()) { register_branch_tree(new_tree_root); - const auto p = split_path( - ("/system/branch_trees/" + new_tree_root).c_str()); + const auto p = split_path(("/system/branch_trees/" + new_tree_root).c_str()); g_rt->lifecycles->Pin(g_rt->objects.Find(p)); } - if (!old_tree_root.empty()) - { - const auto p = split_path( - ("/system/branch_trees/" + old_tree_root).c_str()); + if (!old_tree_root.empty()) { + const auto p = split_path(("/system/branch_trees/" + old_tree_root).c_str()); g_rt->lifecycles->Unpin(g_rt->objects.Find(p)); } } @@ -302,36 +286,36 @@ namespace // Looks up the mg_hash currently bound to `mg_name` in the branch's tree. // Returns empty string when the branch is unborn or the mg is absent. static std::string lookup_branch_mg(const nt::ObjectManager::Branch& branch, - const std::string& mg_name) - { - if (branch.target_hash.empty()) return ""; - auto found = nt::Merkle<std::string>::Get(*g_rt->storage, - branch.target_hash, mg_name); - if (!found) return ""; + const std::string& mg_name) { + if (branch.target_hash.empty()) + return ""; + auto found = nt::Merkle<std::string>::Get(*g_rt->storage, branch.target_hash, mg_name); + if (!found) + return ""; static const nt::Hash32 zero{}; - if (*found == zero) return ""; + if (*found == zero) + return ""; return nt::bin_to_hex(*found); } // Reads the (relation_name, root) list of a specific multigroup under a // branch. Returns empty for unborn branches or absent multigroups. - static std::vector<nt::MultigroupCodec::RelationEntry> read_mg_relations( - const nt::ObjectManager::Branch& branch, - const std::string& mg_name) - { + static std::vector<nt::MultigroupCodec::RelationEntry> + read_mg_relations(const nt::ObjectManager::Branch& branch, const std::string& mg_name) { const std::string mg_hash = lookup_branch_mg(branch, mg_name); - if (mg_hash.empty()) return {}; + if (mg_hash.empty()) + return {}; return nt::MultigroupCodec::List(*g_rt->storage, mg_hash); } // Looks up a branch object by path. Returns nullptr when the path does not // resolve to a BRANCH. - static nt::ObjectManager::Branch* find_branch( - const std::vector<std::string>& branch_path) - { + static nt::ObjectManager::Branch* find_branch(const std::vector<std::string>& branch_path) { auto* entry = g_rt->objects.Find(branch_path); - if (!entry || !entry->object || !entry->head) return nullptr; - if (entry->head->type->label != BRANCH) return nullptr; + if (!entry || !entry->object || !entry->head) + return nullptr; + if (entry->head->type->label != BRANCH) + return nullptr; return dynamic_cast<nt::ObjectManager::Branch*>(entry->object.get()); } @@ -341,15 +325,15 @@ namespace // path, the multigroup name, and the relation name. Returns false for // any other path shape. static bool split_branch_mg_relation(const std::vector<std::string>& parts, - std::vector<std::string>& branch_path_out, - std::string& mg_name_out, - std::string& relation_name_out) - { - if (parts.size() != 7) return false; - if (parts[0] != "system" || parts[1] != "branches" - || parts[3] != "multigroups" || parts[5] != "relations") return false; - branch_path_out = { "system", "branches", parts[2] }; - mg_name_out = parts[4]; + std::vector<std::string>& branch_path_out, + std::string& mg_name_out, std::string& relation_name_out) { + if (parts.size() != 7) + return false; + if (parts[0] != "system" || parts[1] != "branches" || parts[3] != "multigroups" || + parts[5] != "relations") + return false; + branch_path_out = {"system", "branches", parts[2]}; + mg_name_out = parts[4]; relation_name_out = parts[6]; return true; } @@ -367,20 +351,21 @@ namespace // Pin/unpin transitions are applied via rebind_branch_tree_pin: new mgs // are pinned before old mgs are unpinned, so an unchanged advance never // briefly drops a multigroup's ref_count to zero. - static std::string commit_relation_update( - nt::ObjectManager::Branch& branch, - const std::string& mg_name, - const std::string& relation_name, - const std::string& new_root) - { + static std::string commit_relation_update(nt::ObjectManager::Branch& branch, + const std::string& mg_name, + const std::string& relation_name, + const std::string& new_root) { auto relations = read_mg_relations(branch, mg_name); auto it = std::find_if(relations.begin(), relations.end(), [&](const auto& e) { return e.first == relation_name; }); - if (it != relations.end()) it->second = new_root; - else relations.emplace_back(relation_name, new_root); + if (it != relations.end()) + it->second = new_root; + else + relations.emplace_back(relation_name, new_root); const std::string new_mg_hash = register_snapshot(relations); - if (new_mg_hash.empty()) return {}; + if (new_mg_hash.empty()) + return {}; const nt::Hash32 mg_payload = nt::hex_to_bin(new_mg_hash); const std::string new_tree_root = nt::Merkle<std::string>::Insert( @@ -397,8 +382,7 @@ namespace // doesn't exist, or the relation is absent. static std::string read_relation_root(const nt::ObjectManager::Branch& branch, const std::string& mg_name, - const std::string& relation_name) - { + const std::string& relation_name) { const auto relations = read_mg_relations(branch, mg_name); auto it = std::find_if(relations.begin(), relations.end(), [&](const auto& e) { return e.first == relation_name; }); @@ -415,19 +399,20 @@ namespace * are collected here so they can be released atomically when the plan is * freed or transferred to a VmCursor. */ - struct PlanWrapper - { - nt::PlanNode* root = nullptr; - std::vector<std::unique_ptr<nt::PlanNode>> nodes; // owns every node in subtree - std::vector<nt::CursorManager::cursor*> cursors; // one per SCAN leaf - std::vector<nt::HandlerManager::handle*> handles; // one per SCAN leaf + struct PlanWrapper { + nt::PlanNode* root = nullptr; + std::vector<std::unique_ptr<nt::PlanNode>> nodes; // owns every node in subtree + std::vector<nt::CursorManager::cursor*> cursors; // one per SCAN leaf + std::vector<nt::HandlerManager::handle*> handles; // one per SCAN leaf }; - static void free_plan_wrapper(PlanWrapper* pw) - { - if (!pw) return; - for (auto* c : pw->cursors) g_rt->cursors->Close(c); - for (auto* h : pw->handles) g_rt->handler->Close(h); + static void free_plan_wrapper(PlanWrapper* pw) { + if (!pw) + return; + for (auto* c : pw->cursors) + g_rt->cursors->Close(c); + for (auto* h : pw->handles) + g_rt->handler->Close(h); delete pw; } @@ -436,30 +421,163 @@ namespace * during plan construction. After rnt_vm_execute_plan the caller drives * it with rnt_vm_cursor_next / rnt_vm_cursor_close. */ - struct VmCursor - { - nt::VM vm; - nt::PlanNode* root; - std::vector<std::unique_ptr<nt::PlanNode>> nodes; - std::vector<nt::CursorManager::cursor*> cursors; - std::vector<nt::HandlerManager::handle*> handles; - - explicit VmCursor(nt::CursorManager& cm, PlanWrapper* pw) - : vm(cm), root(pw->root) - { - nodes = std::move(pw->nodes); + struct VmCursor { + nt::VM vm; + nt::PlanNode* root; + std::vector<std::unique_ptr<nt::PlanNode>> nodes; + std::vector<nt::CursorManager::cursor*> cursors; + std::vector<nt::HandlerManager::handle*> handles; + + explicit VmCursor(nt::CursorManager& cm, PlanWrapper* pw) : vm(cm), root(pw->root) { + nodes = std::move(pw->nodes); cursors = std::move(pw->cursors); handles = std::move(pw->handles); - delete pw; // struct itself; resources transferred above + delete pw; // struct itself; resources transferred above } - ~VmCursor() - { - for (auto* c : cursors) g_rt->cursors->Close(c); - for (auto* h : handles) g_rt->handler->Close(h); + ~VmCursor() { + for (auto* c : cursors) + g_rt->cursors->Close(c); + for (auto* h : handles) + g_rt->handler->Close(h); } }; -} + + // ---- Plan builders -------------------------------------------------- + // Pure construction: each builder receives only its operator's context and + // assumes the runtime is already initialised. rnt_plan_assemble is the sole + // caller and performs that check once before dispatching here. + + PlanWrapper* build_scan(const PlanArgsScan& a) { + if (!a.relation_path) + return nullptr; + + // Open a handle to the stored relation through the full manager pipeline. + // Open() runs NamespaceReferenceManager::Resolve internally, so the handle + // lands on the resolved /system/snapshots/<hash>/relations/<n> entry when + // the caller passed a branch-relative path. + const auto parts = split_path(a.relation_path); + auto* h = g_rt->handler->Open(parts, nullptr); + if (!h) + return nullptr; + + // Read the Merkle root straight from the handle's object — Resolve has + // already pointed it at the snapshot-bound Relation entry. + std::string merkle_root; + if (h->object && h->object->object) { + auto* rel = dynamic_cast<nt::ObjectManager::Relation*>(h->object->object.get()); + if (rel) + merkle_root = rel->merkle_root; + } + + auto* c = g_rt->cursors->Open(h, merkle_root); + if (!c) { + g_rt->handler->Close(h); + return nullptr; + } + + auto node = std::make_unique<nt::PlanNode>(); + node->op = nt::FOL_OPERATION_SCAN; + node->scan_cursor = c; + + auto* pw = new PlanWrapper(); + pw->root = node.get(); + pw->nodes.push_back(std::move(node)); + pw->cursors.push_back(c); + pw->handles.push_back(h); + return pw; + } + + PlanWrapper* build_join(const PlanArgsJoin& a) { + auto* l = static_cast<PlanWrapper*>(a.left); + auto* r = static_cast<PlanWrapper*>(a.right); + + if (!l || !r) { + free_plan_wrapper(l); + free_plan_wrapper(r); + return nullptr; + } + + auto node = std::make_unique<nt::PlanNode>(); + node->op = nt::FOL_OPERATION_JOIN; + node->left = l->root; + node->right = r->root; + + auto* pw = new PlanWrapper(); + pw->root = node.get(); + pw->nodes.push_back(std::move(node)); + + // Absorb child resources into the new wrapper. + for (auto& n : l->nodes) + pw->nodes.push_back(std::move(n)); + for (auto& n : r->nodes) + pw->nodes.push_back(std::move(n)); + for (auto* c : l->cursors) + pw->cursors.push_back(c); + for (auto* c : r->cursors) + pw->cursors.push_back(c); + for (auto* h : l->handles) + pw->handles.push_back(h); + for (auto* h : r->handles) + pw->handles.push_back(h); + + delete l; + delete r; + return pw; + } + + PlanWrapper* build_take(const PlanArgsTake& a) { + auto* s = static_cast<PlanWrapper*>(a.source); + if (!s) + return nullptr; + + auto node = std::make_unique<nt::PlanNode>(); + node->op = nt::FOL_OPERATION_TAKE; + node->left = s->root; + node->take_limit = a.limit; + + auto* pw = new PlanWrapper(); + pw->root = node.get(); + pw->nodes.push_back(std::move(node)); + + for (auto& n : s->nodes) + pw->nodes.push_back(std::move(n)); + for (auto* c : s->cursors) + pw->cursors.push_back(c); + for (auto* h : s->handles) + pw->handles.push_back(h); + + delete s; + return pw; + } + + PlanWrapper* build_project(const PlanArgsProject& a) { + auto* s = static_cast<PlanWrapper*>(a.source); + if (!s) + return nullptr; + + auto node = std::make_unique<nt::PlanNode>(); + node->op = nt::FOL_OPERATION_PROJECT; + node->left = s->root; + + if (a.attrs) + for (const char** p = a.attrs; *p; ++p) + node->project_attrs.emplace(*p); + + auto* pw = new PlanWrapper(); + pw->root = node.get(); + pw->nodes.push_back(std::move(node)); + for (auto& n : s->nodes) + pw->nodes.push_back(std::move(n)); + for (auto* c : s->cursors) + pw->cursors.push_back(c); + for (auto* h : s->handles) + pw->handles.push_back(h); + + delete s; + return pw; + } +} // namespace // --------------------------------------------------------------------------- // Public C API @@ -469,71 +587,59 @@ namespace // Object registration → Tuple storage → Cursor / VM plan builder // --------------------------------------------------------------------------- -int rnt_init(const char* driver, const char* storage_path) -{ - try - { +int rnt_init(const char* driver, const char* storage_path) { + try { auto rt = std::make_unique<Runtime>(); const std::string drv = driver ? driver : "sqlite"; if (drv == "memory") rt->storage = std::make_unique<nt::InMemoryBackend>(); else - rt->storage = std::make_unique<nt::SqliteBackend>( - storage_path ? storage_path : ":memory:"); + rt->storage = + std::make_unique<nt::SqliteBackend>(storage_path ? storage_path : ":memory:"); - rt->lifecycles = std::make_unique<nt::LifecycleManager>( - rt->objects, *rt->storage); - rt->references = std::make_unique<nt::NamespaceReferenceManager>( - rt->objects, *rt->storage); + rt->lifecycles = std::make_unique<nt::LifecycleManager>(rt->objects, *rt->storage); + rt->references = std::make_unique<nt::NamespaceReferenceManager>(rt->objects, *rt->storage); rt->handler = std::make_unique<nt::HandlerManager>( - rt->objects, rt->permissions, rt->identities, *rt->lifecycles, - *rt->references); - rt->cursors = std::make_unique<nt::CursorManager>( - *rt->storage, rt->lifecycles.get(), &rt->objects); + rt->objects, rt->permissions, rt->identities, *rt->lifecycles, *rt->references); + rt->cursors = + std::make_unique<nt::CursorManager>(*rt->storage, rt->lifecycles.get(), &rt->objects); g_rt = std::move(rt); // Register the default branch on first boot so that // rnt_open_handle("/system/branches/master") always succeeds. const auto master_path = split_path("/system/branches/master"); - if (g_rt->objects.Find(master_path) == nullptr) - { - auto branch = std::make_unique<nt::ObjectManager::Branch>(); + if (g_rt->objects.Find(master_path) == nullptr) { + auto branch = std::make_unique<nt::ObjectManager::Branch>(); branch->name = "master"; - g_rt->objects.Register(master_path, std::move(branch), - make_branch_type()); + g_rt->objects.Register(master_path, std::move(branch), make_branch_type()); } - g_init_done = true; return 0; - } - catch (...) - { + } catch (...) { g_rt.reset(); return -1; } } -int rnt_firewall(const char* /*auth_method*/, char** claims_out) -{ - if (!is_initialized() || !claims_out) return -1; +int rnt_firewall(const char* /*auth_method*/, char** claims_out) { // PermissionsManager::Firewall is stubbed; grant all claims for now. *claims_out = heap_str("READ WRITE"); return 0; } -int rnt_session_open(void* connection_context, char** session_hash_out) -{ - if (!is_initialized() || !session_hash_out) return -1; +int rnt_session_open(void* connection_context, char** session_hash_out) { + if (!session_hash_out) + return -1; // Retry on the astronomically unlikely event of a hash collision against // an already-registered session. std::string hash; - for (int attempts = 0; attempts < 8; ++attempts) - { + for (int attempts = 0; attempts < 8; ++attempts) { hash = random_session_hash(); const auto session_path = split_path(("/system/sessions/" + hash).c_str()); - if (g_rt->objects.Find(session_path) != nullptr) continue; + if (g_rt->objects.Find(session_path) != nullptr) + continue; auto session = std::make_unique<nt::ObjectManager::Session>(); session->connection_context = connection_context; @@ -544,16 +650,17 @@ int rnt_session_open(void* connection_context, char** session_hash_out) return -1; } -int rnt_session_close(const char* session_hash) -{ - if (!is_initialized() || !session_hash) return -1; - const auto session_path = split_path( - ("/system/sessions/" + std::string(session_hash)).c_str()); +int rnt_session_close(const char* session_hash) { + if (!session_hash) + return -1; + const auto session_path = split_path(("/system/sessions/" + std::string(session_hash)).c_str()); auto* entry = g_rt->objects.Find(session_path); - if (!entry || !entry->object) return -1; + if (!entry || !entry->object) + return -1; auto* session = dynamic_cast<nt::ObjectManager::Session*>(entry->object.get()); - if (!session) return -1; + if (!session) + return -1; // Release every pin this session was holding before the entry disappears, // so the dependent multigroups become GC-eligible. @@ -564,29 +671,29 @@ int rnt_session_close(const char* session_hash) return g_rt->objects.Unregister(session_path) ? 0 : -1; } -int rnt_session_set_branch(const char* session_hash, - const char* branch_name, - const char* target_hash) -{ - if (!is_initialized() || !session_hash || !branch_name || !target_hash) +int rnt_session_set_branch(const char* session_hash, const char* branch_name, + const char* target_hash) { + if (!session_hash || !branch_name || !target_hash) return -1; - const auto session_path = split_path( - ("/system/sessions/" + std::string(session_hash)).c_str()); + const auto session_path = split_path(("/system/sessions/" + std::string(session_hash)).c_str()); auto* entry = g_rt->objects.Find(session_path); - if (!entry || !entry->object || !entry->head) return -1; - if (entry->head->type->label != SESSION) return -1; + if (!entry || !entry->object || !entry->head) + return -1; + if (entry->head->type->label != SESSION) + return -1; auto* session = dynamic_cast<nt::ObjectManager::Session*>(entry->object.get()); - if (!session) return -1; + if (!session) + return -1; const std::string hash(target_hash); std::string old_hash; auto it = session->branch_overrides.find(branch_name); - if (it != session->branch_overrides.end()) old_hash = it->second; + if (it != session->branch_overrides.end()) + old_hash = it->second; - if (hash.empty()) - { + if (hash.empty()) { session->branch_overrides.erase(branch_name); rebind_branch_tree_pin(old_hash, ""); return 0; @@ -594,58 +701,66 @@ int rnt_session_set_branch(const char* session_hash, // target_hash is a branch-tree root — a content-addressed blob produced // by an earlier commit. Reject if unknown. - if (!g_rt->storage->Get(hash)) return -1; + if (!g_rt->storage->Get(hash)) + return -1; session->branch_overrides[branch_name] = hash; rebind_branch_tree_pin(old_hash, hash); return 0; } -rnt_handle_t rnt_open_handle(const char* path, const char* /*claims*/) -{ - if (!is_initialized() || !path) return nullptr; +rnt_handle_t rnt_open_handle(const char* path, const char* /*claims*/) { + if (!path) + return nullptr; return g_rt->handler->Open(split_path(path), nullptr); } -int rnt_close_handle(rnt_handle_t handle) -{ - if (!is_initialized() || !handle) return -1; +int rnt_close_handle(rnt_handle_t handle) { + if (!handle) + return -1; auto* h = static_cast<nt::HandlerManager::handle*>(handle); return g_rt->handler->Close(h) ? 0 : -1; } -int rnt_branch_target(rnt_handle_t handle, char** target_hash_out) -{ - if (!is_initialized() || !handle || !target_hash_out) return -1; +int rnt_branch_target(rnt_handle_t handle, char** target_hash_out) { + if (!handle || !target_hash_out) + return -1; auto* h = static_cast<nt::HandlerManager::handle*>(handle); - if (!h->object || !h->object->head) return -1; - if (h->object->head->type->label != BRANCH) return -1; + if (!h->object || !h->object->head) + return -1; + if (h->object->head->type->label != BRANCH) + return -1; auto* branch = dynamic_cast<nt::ObjectManager::Branch*>(h->object->object.get()); - if (!branch) return -1; + if (!branch) + return -1; *target_hash_out = heap_str(branch->target_hash); return 0; } -int rnt_branch_advance(const char* branch_path, const char* new_hash) -{ - if (!is_initialized() || !branch_path || !new_hash) return -1; +int rnt_branch_advance(const char* branch_path, const char* new_hash) { + if (!branch_path || !new_hash) + return -1; auto* entry = g_rt->objects.Find(split_path(branch_path)); - if (!entry || !entry->object || !entry->head) return -1; - if (entry->head->type->label != BRANCH) return -1; + if (!entry || !entry->object || !entry->head) + return -1; + if (entry->head->type->label != BRANCH) + return -1; auto* branch = dynamic_cast<nt::ObjectManager::Branch*>(entry->object.get()); - if (!branch) return -1; + if (!branch) + return -1; const std::string hash(new_hash); // Non-empty branch-tree roots must already exist in the KV store. The // branch tree is a content-addressed blob produced by an earlier mutation // through commit_relation_update; advancing to an unknown root is treated // as a caller bug. - if (!hash.empty() && !g_rt->storage->Get(hash)) return -1; + if (!hash.empty() && !g_rt->storage->Get(hash)) + return -1; const std::string old_hash = branch->target_hash; branch->target_hash = hash; @@ -653,9 +768,9 @@ int rnt_branch_advance(const char* branch_path, const char* new_hash) return 0; } -int rnt_register_relation(const char* path) -{ - if (!is_initialized() || !path) return -1; +int rnt_register_relation(const char* path) { + if (!path) + return -1; const auto parts = split_path(path); std::vector<std::string> branch_path; @@ -664,34 +779,36 @@ int rnt_register_relation(const char* path) return -1; auto* branch = find_branch(branch_path); - if (!branch) return -1; + if (!branch) + return -1; // Idempotent: if the relation is already present in the named mg's // current snapshot, the call succeeds without producing a new snapshot. const auto current = read_mg_relations(*branch, mg_name); const bool already_present = std::any_of( - current.begin(), current.end(), - [&](const auto& e) { return e.first == relation_name; }); - if (already_present) return 0; + current.begin(), current.end(), [&](const auto& e) { return e.first == relation_name; }); + if (already_present) + return 0; // Empty merkle_root signals a relation with no tuples. - return commit_relation_update(*branch, mg_name, relation_name, "").empty() - ? -1 : 0; + return commit_relation_update(*branch, mg_name, relation_name, "").empty() ? -1 : 0; } -int rnt_register_branch(const char* path, const char* target_hash) -{ - if (!is_initialized() || !path) return -1; +int rnt_register_branch(const char* path, const char* target_hash) { + if (!path) + return -1; const auto parts = split_path(path); - if (g_rt->objects.Find(parts) != nullptr) return 0; + if (g_rt->objects.Find(parts) != nullptr) + return 0; const std::string hash = target_hash ? target_hash : ""; // Non-empty target_hash is a branch-tree root produced by an earlier // commit; it must already exist as a KV blob. - if (!hash.empty() && !g_rt->storage->Get(hash)) return -1; + if (!hash.empty() && !g_rt->storage->Get(hash)) + return -1; - auto branch = std::make_unique<nt::ObjectManager::Branch>(); - branch->name = parts.empty() ? "" : parts.back(); + auto branch = std::make_unique<nt::ObjectManager::Branch>(); + branch->name = parts.empty() ? "" : parts.back(); branch->target_hash = hash; g_rt->objects.Register(parts, std::move(branch), make_branch_type()); @@ -699,16 +816,18 @@ int rnt_register_branch(const char* path, const char* target_hash) return 0; } -int rnt_list_relations(const char* branch_mg_path, char** out) -{ - if (!is_initialized() || !branch_mg_path || !out) return -1; +int rnt_list_relations(const char* branch_mg_path, char** out) { + if (!branch_mg_path || !out) + return -1; const auto parts = split_path(branch_mg_path); - if (parts.size() != 5) return -1; - if (parts[0] != "system" || parts[1] != "branches" - || parts[3] != "multigroups") return -1; + if (parts.size() != 5) + return -1; + if (parts[0] != "system" || parts[1] != "branches" || parts[3] != "multigroups") + return -1; - auto* branch = find_branch({ "system", "branches", parts[2] }); - if (!branch) return -1; + auto* branch = find_branch({"system", "branches", parts[2]}); + if (!branch) + return -1; const auto relations = read_mg_relations(*branch, parts[4]); std::string result; for (const auto& [name, root] : relations) @@ -717,11 +836,12 @@ int rnt_list_relations(const char* branch_mg_path, char** out) return 0; } -int rnt_list_branch_multigroups(const char* branch_path, char** out) -{ - if (!is_initialized() || !branch_path || !out) return -1; +int rnt_list_branch_multigroups(const char* branch_path, char** out) { + if (!branch_path || !out) + return -1; auto* branch = find_branch(split_path(branch_path)); - if (!branch) return -1; + if (!branch) + return -1; const auto mgs = list_branch_tree(branch->target_hash); std::string result; for (const auto& [name, mg_hash] : mgs) @@ -730,15 +850,17 @@ int rnt_list_branch_multigroups(const char* branch_path, char** out) return 0; } -int rnt_list_snapshot_relations(const char* snapshot_hash, char** out) -{ - if (!is_initialized() || !snapshot_hash || !out) return -1; +int rnt_list_snapshot_relations(const char* snapshot_hash, char** out) { + if (!snapshot_hash || !out) + return -1; const std::string hash(snapshot_hash); const auto snap_path = split_path(("/system/snapshots/" + hash).c_str()); auto* entry = g_rt->objects.Find(snap_path); - if (!entry || !entry->object) return -1; + if (!entry || !entry->object) + return -1; auto* mg = dynamic_cast<nt::ObjectManager::Multigroup*>(entry->object.get()); - if (!mg) return -1; + if (!mg) + return -1; const auto relations = nt::MultigroupCodec::List(*g_rt->storage, mg->merkle_root); std::string result; for (const auto& [name, root] : relations) @@ -747,9 +869,9 @@ int rnt_list_snapshot_relations(const char* snapshot_hash, char** out) return 0; } -int rnt_link_tuple(const char* relation_path, const char* kv_attrs, char** hash_out) -{ - if (!is_initialized() || !relation_path || !kv_attrs || !hash_out) return -1; +int rnt_link_tuple(const char* relation_path, const char* kv_attrs, char** hash_out) { + if (!relation_path || !kv_attrs || !hash_out) + return -1; const auto parts = split_path(relation_path); std::vector<std::string> branch_path; @@ -758,16 +880,16 @@ int rnt_link_tuple(const char* relation_path, const char* kv_attrs, char** hash_ return -1; auto* branch = find_branch(branch_path); - if (!branch) return -1; + if (!branch) + return -1; const std::string old_root = read_relation_root(*branch, mg_name, relation_name); - auto bytes = nt::TupleCodec::Serialize(parse_kv(kv_attrs)); + auto bytes = nt::TupleCodec::Serialize(parse_kv(kv_attrs)); const auto tuple_hash = g_rt->storage->Put(std::move(bytes)); - const auto tuple_bin = nt::hex_to_bin(tuple_hash); + const auto tuple_bin = nt::hex_to_bin(tuple_hash); const std::string new_root = - nt::Merkle<nt::Hash32>::Insert(*g_rt->storage, old_root, - tuple_bin, tuple_bin); + nt::Merkle<nt::Hash32>::Insert(*g_rt->storage, old_root, tuple_bin, tuple_bin); if (commit_relation_update(*branch, mg_name, relation_name, new_root).empty()) return -1; @@ -776,9 +898,9 @@ int rnt_link_tuple(const char* relation_path, const char* kv_attrs, char** hash_ return 0; } -int rnt_unlink_tuple(const char* relation_path, const char* tuple_hash) -{ - if (!is_initialized() || !relation_path || !tuple_hash) return -1; +int rnt_unlink_tuple(const char* relation_path, const char* tuple_hash) { + if (!relation_path || !tuple_hash) + return -1; const auto parts = split_path(relation_path); std::vector<std::string> branch_path; @@ -787,20 +909,19 @@ int rnt_unlink_tuple(const char* relation_path, const char* tuple_hash) return -1; auto* branch = find_branch(branch_path); - if (!branch) return -1; + if (!branch) + return -1; const std::string old_root = read_relation_root(*branch, mg_name, relation_name); const std::string new_root = - nt::Merkle<nt::Hash32>::Remove(*g_rt->storage, old_root, - nt::hex_to_bin(tuple_hash)); + nt::Merkle<nt::Hash32>::Remove(*g_rt->storage, old_root, nt::hex_to_bin(tuple_hash)); - return commit_relation_update(*branch, mg_name, relation_name, new_root).empty() - ? -1 : 0; + return commit_relation_update(*branch, mg_name, relation_name, new_root).empty() ? -1 : 0; } -int rnt_clear_relation(const char* relation_path) -{ - if (!is_initialized() || !relation_path) return -1; +int rnt_clear_relation(const char* relation_path) { + if (!relation_path) + return -1; const auto parts = split_path(relation_path); std::vector<std::string> branch_path; @@ -809,15 +930,15 @@ int rnt_clear_relation(const char* relation_path) return -1; auto* branch = find_branch(branch_path); - if (!branch) return -1; + if (!branch) + return -1; - return commit_relation_update(*branch, mg_name, relation_name, "").empty() - ? -1 : 0; + return commit_relation_update(*branch, mg_name, relation_name, "").empty() ? -1 : 0; } -int rnt_relation_root(const char* relation_path, char** root_hash_out) -{ - if (!is_initialized() || !relation_path || !root_hash_out) return -1; +int rnt_relation_root(const char* relation_path, char** root_hash_out) { + if (!relation_path || !root_hash_out) + return -1; const auto parts = split_path(relation_path); std::vector<std::string> branch_path; @@ -826,7 +947,8 @@ int rnt_relation_root(const char* relation_path, char** root_hash_out) return -1; auto* branch = find_branch(branch_path); - if (!branch) return -1; + if (!branch) + return -1; // Distinguish "relation registered but empty" (returns 0 with empty hash) // from "relation not in this multigroup's snapshot" (returns -1). Without @@ -834,174 +956,101 @@ int rnt_relation_root(const char* relation_path, char** root_hash_out) const auto relations = read_mg_relations(*branch, mg_name); auto it = std::find_if(relations.begin(), relations.end(), [&](const auto& e) { return e.first == relation_name; }); - if (it == relations.end()) return -1; + if (it == relations.end()) + return -1; *root_hash_out = heap_str(it->second); return 0; } -rnt_cursor_t rnt_cursor_open(rnt_handle_t handle) -{ - if (!is_initialized() || !handle) return nullptr; +rnt_cursor_t rnt_cursor_open(rnt_handle_t handle) { + if (!handle) + return nullptr; auto* h = static_cast<nt::HandlerManager::handle*>(handle); std::string merkle_root; - if (h->object && h->object->head && - h->object->head->type->label == RELATION) - { + if (h->object && h->object->head && h->object->head->type->label == RELATION) { auto* rel = dynamic_cast<nt::ObjectManager::Relation*>(h->object->object.get()); - if (rel) merkle_root = rel->merkle_root; + if (rel) + merkle_root = rel->merkle_root; } return g_rt->cursors->Open(h, merkle_root); } -int rnt_cursor_next(rnt_cursor_t cursor, char** tuple_out) -{ - if (!is_initialized() || !cursor || !tuple_out) return -1; +int rnt_cursor_next(rnt_cursor_t cursor, char** tuple_out) { + if (!cursor || !tuple_out) + return -1; auto* c = static_cast<nt::CursorManager::cursor*>(cursor); nt::Tuple* t = g_rt->cursors->Next(c); - if (!t) { *tuple_out = nullptr; return 0; } + if (!t) { + *tuple_out = nullptr; + return 0; + } *tuple_out = heap_str(tuple_to_kv(t)); return 1; } -int rnt_cursor_close(rnt_cursor_t cursor) -{ - if (!is_initialized() || !cursor) return -1; +int rnt_cursor_close(rnt_cursor_t cursor) { + if (!cursor) + return -1; g_rt->cursors->Close(static_cast<nt::CursorManager::cursor*>(cursor)); return 0; } -void rnt_free_string(char* s) { delete[] s; } -void rnt_free_bytes(uint8_t* p) { delete[] p; } +void rnt_free_string(char* s) { + delete[] s; +} +void rnt_free_bytes(uint8_t* p) { + delete[] p; +} // --------------------------------------------------------------------------- // VM plan builder // --------------------------------------------------------------------------- -rnt_plan_t rnt_plan_scan(const char* relation_path) -{ - if (!is_initialized() || !relation_path) return nullptr; - - // Open a handle to the stored relation through the full manager pipeline. - // Open() runs NamespaceReferenceManager::Resolve internally, so the handle - // lands on the resolved /system/snapshots/<hash>/relations/<n> entry when - // the caller passed a branch-relative path. - const auto parts = split_path(relation_path); - auto* h = g_rt->handler->Open(parts, nullptr); - if (!h) return nullptr; - - // Read the Merkle root straight from the handle's object — Resolve has - // already pointed it at the snapshot-bound Relation entry. - std::string merkle_root; - if (h->object && h->object->object) - { - auto* rel = dynamic_cast<nt::ObjectManager::Relation*>(h->object->object.get()); - if (rel) merkle_root = rel->merkle_root; +rnt_plan_t rnt_plan_assemble(PlanAction action) { + switch (action.operation) { + case nt::FOL_OPERATION_SCAN: + return build_scan(action.scan); + case nt::FOL_OPERATION_JOIN: + return build_join(action.join); + case nt::FOL_OPERATION_TAKE: + return build_take(action.take); + case nt::FOL_OPERATION_PROJECT: + return build_project(action.project); } - auto* c = g_rt->cursors->Open(h, merkle_root); - if (!c) - { - g_rt->handler->Close(h); - return nullptr; - } - - auto node = std::make_unique<nt::PlanNode>(); - node->op = nt::PlanNode::Op::SCAN; - node->scan_cursor = c; - - auto* pw = new PlanWrapper(); - pw->root = node.get(); - pw->nodes.push_back(std::move(node)); - pw->cursors.push_back(c); - pw->handles.push_back(h); - return pw; -} - -rnt_plan_t rnt_plan_join(rnt_plan_t left, rnt_plan_t right) -{ - if (!left || !right) - { - free_plan_wrapper(static_cast<PlanWrapper*>(left)); - free_plan_wrapper(static_cast<PlanWrapper*>(right)); - return nullptr; - } - - auto* l = static_cast<PlanWrapper*>(left); - auto* r = static_cast<PlanWrapper*>(right); - - auto node = std::make_unique<nt::PlanNode>(); - node->op = nt::PlanNode::Op::JOIN; - node->left = l->root; - node->right = r->root; - - auto* pw = new PlanWrapper(); - pw->root = node.get(); - pw->nodes.push_back(std::move(node)); - - // Absorb child resources into the new wrapper. - for (auto& n : l->nodes) pw->nodes.push_back(std::move(n)); - for (auto& n : r->nodes) pw->nodes.push_back(std::move(n)); - for (auto* c : l->cursors) pw->cursors.push_back(c); - for (auto* c : r->cursors) pw->cursors.push_back(c); - for (auto* h : l->handles) pw->handles.push_back(h); - for (auto* h : r->handles) pw->handles.push_back(h); - - delete l; - delete r; - return pw; + return nullptr; } -rnt_plan_t rnt_plan_take(rnt_plan_t source, size_t limit) -{ - if (!source) return nullptr; - - auto* s = static_cast<PlanWrapper*>(source); - - auto node = std::make_unique<nt::PlanNode>(); - node->op = nt::PlanNode::Op::TAKE; - node->left = s->root; - node->take_limit = limit; - - auto* pw = new PlanWrapper(); - pw->root = node.get(); - pw->nodes.push_back(std::move(node)); - - for (auto& n : s->nodes) pw->nodes.push_back(std::move(n)); - for (auto* c : s->cursors) pw->cursors.push_back(c); - for (auto* h : s->handles) pw->handles.push_back(h); - - delete s; - return pw; -} - -void rnt_plan_free(rnt_plan_t plan) -{ +void rnt_plan_free(rnt_plan_t plan) { free_plan_wrapper(static_cast<PlanWrapper*>(plan)); } -rnt_cursor_t rnt_vm_execute_plan(rnt_plan_t plan) -{ - if (!is_initialized() || !plan) return nullptr; +rnt_cursor_t rnt_vm_execute_plan(rnt_plan_t plan) { + if (!plan) + return nullptr; // VmCursor constructor transfers ownership from PlanWrapper and deletes it. return new VmCursor(*g_rt->cursors, static_cast<PlanWrapper*>(plan)); } -int rnt_vm_cursor_next(rnt_cursor_t vm_cursor, char** tuple_out) -{ - if (!is_initialized() || !vm_cursor || !tuple_out) return -1; +int rnt_vm_cursor_next(rnt_cursor_t vm_cursor, char** tuple_out) { + if (!vm_cursor || !tuple_out) + return -1; auto* vc = static_cast<VmCursor*>(vm_cursor); nt::Tuple* t = vc->vm.Next(vc->root); - if (!t) { *tuple_out = nullptr; return 0; } + if (!t) { + *tuple_out = nullptr; + return 0; + } *tuple_out = heap_str(tuple_to_kv(t)); return 1; } -int rnt_vm_cursor_close(rnt_cursor_t vm_cursor) -{ - if (!is_initialized() || !vm_cursor) return -1; +int rnt_vm_cursor_close(rnt_cursor_t vm_cursor) { + if (!vm_cursor) + return -1; // VmCursor destructor closes all cursors and handles. delete static_cast<VmCursor*>(vm_cursor); return 0; diff --git a/src/RelationalNT.cpp b/src/RelationalNT.cpp index b1302ee..f27179f 100644 --- a/src/RelationalNT.cpp +++ b/src/RelationalNT.cpp @@ -16,50 +16,46 @@ #include <iostream> #endif -namespace nt -{ - bool NT::IsRunning() const - { +namespace nt { + bool NT::IsRunning() const { return true; } - void NT::SimulateEntryCall() - { + void NT::SimulateEntryCall() { } -} +} // namespace nt #ifdef NT_CONSOLE_APP -int main() -{ +int main() { const nt::NT runtime; std::cout << "RNT running: " << (runtime.IsRunning() ? "yes" : "no") << '\n'; // --- Mock: register villager in the object registry --- nt::ObjectManager objects; - std::unique_ptr<nt::ObjectManager::object_type> type = std::make_unique<nt::ObjectManager::object_type>(); + std::unique_ptr<nt::ObjectManager::object_type> type = + std::make_unique<nt::ObjectManager::object_type>(); type->label = RELATION; type->disposable = false; - type->methods = { OPEN, CLOSE }; + type->methods = {OPEN, CLOSE}; - const std::vector<std::string> path = { "multigroups", "sakura", "relations", "villager" }; + const std::vector<std::string> path = {"multigroups", "sakura", "relations", "villager"}; objects.Register(path, std::make_unique<nt::ObjectManager::Relation>(), std::move(type)); - auto* villager_rel = dynamic_cast<nt::ObjectManager::Relation*>( - objects.Find(path)->object.get()); + auto* villager_rel = + dynamic_cast<nt::ObjectManager::Relation*>(objects.Find(path)->object.get()); // --- Populate backend with three tuples via the Merkle tree --- nt::SqliteBackend backend; auto store = [&](std::vector<nt::Attribute> attrs) { auto bytes = nt::TupleCodec::Serialize(attrs); - auto hash = backend.Put(std::move(bytes)); + auto hash = backend.Put(std::move(bytes)); auto hash_bin = nt::hex_to_bin(hash); villager_rel->merkle_root = - nt::Merkle<nt::Hash32>::Insert(backend, villager_rel->merkle_root, - hash_bin, hash_bin); + nt::Merkle<nt::Hash32>::Insert(backend, villager_rel->merkle_root, hash_bin, hash_bin); }; - store({ { "name", "Blathers" }, { "profession", "Museum Curator" } }); - store({ { "name", "Rover" }, { "profession", "Traveller" } }); - store({ { "name", "K.K." }, { "profession", "Artist" } }); + store({{"name", "Blathers"}, {"profession", "Museum Curator"}}); + store({{"name", "Rover"}, {"profession", "Traveller"}}); + store({{"name", "K.K."}, {"profession", "Artist"}}); nt::CursorManager cursors(backend); // --- Open a handle on villager through the full manager pipeline --- @@ -69,18 +65,16 @@ int main() nt::NamespaceReferenceManager references(objects, backend); nt::HandlerManager handler(objects, permissions, identities, lifecycles, references); - int connection = 1; // dummy connection context + int connection = 1; // dummy connection context nt::HandlerManager::handle* handle = handler.Open(path, &connection); - if (handle == nullptr) - { + if (handle == nullptr) { std::cout << "Failed to open handle for villager\n"; return 1; } // --- Open a cursor on the relation --- nt::CursorManager::cursor* cursor = cursors.Open(handle, villager_rel->merkle_root); - if (cursor == nullptr) - { + if (cursor == nullptr) { std::cout << "Failed to open cursor for villager\n"; handler.Close(handle); return 1; @@ -88,17 +82,15 @@ int main() // --- Build a SCAN plan and pull all tuples lazily through the FOL VM --- nt::PlanNode plan; - plan.op = nt::PlanNode::Op::SCAN; + plan.op = nt::FOL_OPERATION_SCAN; plan.scan_cursor = cursor; nt::VM vm(cursors); std::cout << "Tuples in villager:\n"; - while (nt::Tuple* t = vm.Next(&plan)) - { + while (nt::Tuple* t = vm.Next(&plan)) { std::cout << " "; const nt::Attribute* attr = t->Next(); - while (attr != nullptr) - { + while (attr != nullptr) { std::cout << attr->name << "=" << attr->value; attr = t->Next(); if (attr != nullptr) diff --git a/src/SqliteBackend.cpp b/src/SqliteBackend.cpp index 7e9c9d5..3e01058 100644 --- a/src/SqliteBackend.cpp +++ b/src/SqliteBackend.cpp @@ -3,60 +3,48 @@ #include <picosha2.h> #include <stdexcept> -namespace nt -{ - SqliteBackend::SqliteBackend(const std::string& path) - { +namespace nt { + SqliteBackend::SqliteBackend(const std::string& path) { if (sqlite3_open(path.c_str(), &db_) != SQLITE_OK) throw std::runtime_error(sqlite3_errmsg(db_)); - const char* schema = - "CREATE TABLE IF NOT EXISTS kv (" - " hash TEXT PRIMARY KEY," - " value BLOB NOT NULL" - ");"; + const char* schema = "CREATE TABLE IF NOT EXISTS kv (" + " hash TEXT PRIMARY KEY," + " value BLOB NOT NULL" + ");"; char* err = nullptr; - if (sqlite3_exec(db_, schema, nullptr, nullptr, &err) != SQLITE_OK) - { + if (sqlite3_exec(db_, schema, nullptr, nullptr, &err) != SQLITE_OK) { std::string msg(err); sqlite3_free(err); throw std::runtime_error(msg); } } - SqliteBackend::~SqliteBackend() - { + SqliteBackend::~SqliteBackend() { sqlite3_close(db_); } - std::string SqliteBackend::Put(std::vector<uint8_t> value) - { + std::string SqliteBackend::Put(std::vector<uint8_t> value) { const std::string hash = picosha2::hash256_hex_string(value.begin(), value.end()); sqlite3_stmt* stmt = nullptr; - sqlite3_prepare_v2(db_, - "INSERT OR IGNORE INTO kv (hash, value) VALUES (?, ?)", - -1, &stmt, nullptr); + sqlite3_prepare_v2(db_, "INSERT OR IGNORE INTO kv (hash, value) VALUES (?, ?)", -1, &stmt, + nullptr); sqlite3_bind_text(stmt, 1, hash.c_str(), -1, SQLITE_TRANSIENT); - sqlite3_bind_blob(stmt, 2, value.data(), static_cast<int>(value.size()), - SQLITE_TRANSIENT); + sqlite3_bind_blob(stmt, 2, value.data(), static_cast<int>(value.size()), SQLITE_TRANSIENT); sqlite3_step(stmt); sqlite3_finalize(stmt); return hash; } - std::optional<std::vector<uint8_t>> SqliteBackend::Get(const std::string& hash) - { + std::optional<std::vector<uint8_t>> SqliteBackend::Get(const std::string& hash) { sqlite3_stmt* stmt = nullptr; - sqlite3_prepare_v2(db_, - "SELECT value FROM kv WHERE hash = ?", - -1, &stmt, nullptr); + sqlite3_prepare_v2(db_, "SELECT value FROM kv WHERE hash = ?", -1, &stmt, nullptr); sqlite3_bind_text(stmt, 1, hash.c_str(), -1, SQLITE_TRANSIENT); std::optional<std::vector<uint8_t>> result; - if (sqlite3_step(stmt) == SQLITE_ROW) - { + if (sqlite3_step(stmt) == SQLITE_ROW) { const auto* blob = static_cast<const uint8_t*>(sqlite3_column_blob(stmt, 0)); int size = sqlite3_column_bytes(stmt, 0); result = std::vector<uint8_t>(blob, blob + size); @@ -64,4 +52,4 @@ namespace nt sqlite3_finalize(stmt); return result; } -} +} // namespace nt diff --git a/src/TupleCodec.cpp b/src/TupleCodec.cpp index 9b76046..a78ed5b 100644 --- a/src/TupleCodec.cpp +++ b/src/TupleCodec.cpp @@ -7,23 +7,19 @@ #include <cstring> #include <numeric> -namespace nt::TupleCodec -{ - static std::vector<Attribute> Sorted(std::vector<Attribute> attrs) - { +namespace nt::TupleCodec { + static std::vector<Attribute> Sorted(std::vector<Attribute> attrs) { std::sort(attrs.begin(), attrs.end(), [](const Attribute& a, const Attribute& b) { return a.name < b.name; }); return attrs; } - std::string Hash(const std::vector<Attribute>& attrs) - { + std::string Hash(const std::vector<Attribute>& attrs) { auto bytes = Serialize(attrs); return picosha2::hash256_hex_string(bytes.begin(), bytes.end()); } - std::vector<uint8_t> Serialize(const std::vector<Attribute>& attrs) - { + std::vector<uint8_t> Serialize(const std::vector<Attribute>& attrs) { // Format: [uint32_le name_len][name][uint32_le value_len][value] ... // Attributes are stored in sorted name order for determinism. std::vector<uint8_t> out; @@ -34,8 +30,7 @@ namespace nt::TupleCodec out.push_back(static_cast<uint8_t>(n >> 24)); }; - for (const auto& a : Sorted({ attrs.begin(), attrs.end() })) - { + for (const auto& a : Sorted({attrs.begin(), attrs.end()})) { write_u32(static_cast<uint32_t>(a.name.size())); out.insert(out.end(), a.name.begin(), a.name.end()); write_u32(static_cast<uint32_t>(a.value.size())); @@ -44,29 +39,29 @@ namespace nt::TupleCodec return out; } - std::vector<Attribute> Deserialize(const std::vector<uint8_t>& bytes) - { + std::vector<Attribute> Deserialize(const std::vector<uint8_t>& bytes) { auto read_u32 = [&](size_t pos) -> uint32_t { - return static_cast<uint32_t>(bytes[pos]) - | (static_cast<uint32_t>(bytes[pos + 1]) << 8) - | (static_cast<uint32_t>(bytes[pos + 2]) << 16) - | (static_cast<uint32_t>(bytes[pos + 3]) << 24); + return static_cast<uint32_t>(bytes[pos]) | + (static_cast<uint32_t>(bytes[pos + 1]) << 8) | + (static_cast<uint32_t>(bytes[pos + 2]) << 16) | + (static_cast<uint32_t>(bytes[pos + 3]) << 24); }; std::vector<Attribute> result; size_t pos = 0; - while (pos + 8 <= bytes.size()) - { - uint32_t name_len = read_u32(pos); pos += 4; + while (pos + 8 <= bytes.size()) { + uint32_t name_len = read_u32(pos); + pos += 4; std::string name(reinterpret_cast<const char*>(bytes.data() + pos), name_len); pos += name_len; - uint32_t value_len = read_u32(pos); pos += 4; + uint32_t value_len = read_u32(pos); + pos += 4; std::string value(reinterpret_cast<const char*>(bytes.data() + pos), value_len); pos += value_len; - result.push_back({ std::move(name), std::move(value) }); + result.push_back({std::move(name), std::move(value)}); } return result; } -} +} // namespace nt::TupleCodec @@ -1,102 +1,99 @@ #include "VM.h" #include "Types.h" -namespace nt -{ - VM::VM(CursorManager& cursors) : cursors_(cursors) {} +namespace nt { + VM::VM(CursorManager& cursors) : cursors_(cursors) { + } - std::vector<std::string> VM::ResolveArgs(const std::vector<PathArg>& tmpl, Tuple* from) - { + std::vector<std::string> VM::ResolveArgs(const std::vector<PathArg>& tmpl, Tuple* from) { std::vector<std::string> resolved; resolved.reserve(tmpl.size()); - for (const auto& arg : tmpl) - { - if (arg.kind == PathArg::Kind::Const) - { + for (const auto& arg : tmpl) { + if (arg.kind == PathArg::Kind::Const) { resolved.push_back(arg.name); continue; } std::string val; for (const auto& attr : from->attrs()) - if (attr.name == arg.name) { val = attr.value; break; } + if (attr.name == arg.name) { + val = attr.value; + break; + } resolved.push_back(std::move(val)); } return resolved; } - void VM::ResetInner(CursorManager::cursor* c, std::vector<std::string> args) - { - c->args = std::move(args); + void VM::ResetInner(CursorManager::cursor* c, std::vector<std::string> args) { + c->args = std::move(args); c->page.clear(); c->page_position = 0; - c->fetch_offset = 0; - c->exhausted = false; + c->fetch_offset = 0; + c->exhausted = false; } - Tuple* VM::MergeInto(PlanNode* node, Tuple* left, Tuple* right) - { + Tuple* VM::MergeInto(PlanNode* node, Tuple* left, Tuple* right) { std::vector<Attribute> merged; - for (const auto& a : left->attrs()) merged.push_back(a); - for (const auto& a : right->attrs()) merged.push_back(a); + for (const auto& a : left->attrs()) + merged.push_back(a); + for (const auto& a : right->attrs()) + merged.push_back(a); node->join_buffer.emplace(std::move(merged)); return &*node->join_buffer; } - Tuple* VM::Next(PlanNode* node) - { - if (node == nullptr) return nullptr; - - switch (node->op) - { - case PlanNode::Op::SCAN: - return cursors_.Next(node->scan_cursor); + Tuple* VM::Next(PlanNode* node) { + if (node == nullptr) + return nullptr; - case PlanNode::Op::PROJECT: - { - Tuple* next = Next(node->left); - if (next == nullptr) return nullptr; + switch (node->op) { + case Operation::FOL_OPERATION_SCAN: + return cursors_.Next(node->scan_cursor); - std::vector<Attribute> projected; - for (const auto& attr : next->attrs()) - { - if (node->project_attrs.find(attr.name) != node->project_attrs.end()) - projected.push_back(attr); - } + case Operation::FOL_OPERATION_PROJECT: { + Tuple* next = Next(node->left); + if (next == nullptr) + return nullptr; - node->project_buffer.emplace(std::move(projected)); - return &*node->project_buffer; + std::vector<Attribute> projected; + for (const auto& attr : next->attrs()) { + if (node->project_attrs.find(attr.name) != node->project_attrs.end()) + projected.push_back(attr); } - case PlanNode::Op::JOIN: - { - while (true) - { + node->project_buffer.emplace(std::move(projected)); + return &*node->project_buffer; + } + + case Operation::FOL_OPERATION_JOIN: { + while (true) { + if (node->join_left == nullptr) { + node->join_left = Next(node->left); if (node->join_left == nullptr) - { - node->join_left = Next(node->left); - if (node->join_left == nullptr) return nullptr; + return nullptr; - auto args = ResolveArgs(node->right->scan_args, node->join_left); - ResetInner(node->right->scan_cursor, std::move(args)); - } + auto args = ResolveArgs(node->right->scan_args, node->join_left); + ResetInner(node->right->scan_cursor, std::move(args)); + } - Tuple* right = Next(node->right); - if (right != nullptr) - return MergeInto(node, node->join_left, right); + Tuple* right = Next(node->right); + if (right != nullptr) + return MergeInto(node, node->join_left, right); - node->join_left = nullptr; - } + node->join_left = nullptr; } + } - case PlanNode::Op::TAKE: - { - if (node->take_count >= node->take_limit) return nullptr; - Tuple* t = Next(node->left); - if (t) ++node->take_count; - return t; - } + case Operation::FOL_OPERATION_TAKE: { + if (node->take_count >= node->take_limit) + return nullptr; + Tuple* t = Next(node->left); + if (t) + ++node->take_count; + return t; + } } return nullptr; } -} +} // namespace nt |