diff options
Diffstat (limited to '')
| -rw-r--r-- | include/Api.h | 16 | ||||
| -rw-r--r-- | include/CursorManager.h | 153 | ||||
| -rw-r--r-- | include/HandlerManager.h | 96 | ||||
| -rw-r--r-- | include/IStorageBackend.h | 49 | ||||
| -rw-r--r-- | include/IdentityManager.h | 47 | ||||
| -rw-r--r-- | include/InMemoryBackend.h | 31 | ||||
| -rw-r--r-- | include/LifecycleManager.h | 162 | ||||
| -rw-r--r-- | include/Merkle.h | 185 | ||||
| -rw-r--r-- | include/MultigroupCodec.h | 82 | ||||
| -rw-r--r-- | include/NT.h | 17 | ||||
| -rw-r--r-- | include/NamespaceReferenceManager.h | 107 | ||||
| -rw-r--r-- | include/ObjectManager.h | 335 | ||||
| -rw-r--r-- | include/PermissionsManager.h | 88 | ||||
| -rw-r--r-- | include/RNT_C_API.h | 501 | ||||
| -rw-r--r-- | include/Runtime.h | 23 | ||||
| -rw-r--r-- | include/SqliteBackend.h | 41 | ||||
| -rw-r--r-- | include/TupleCodec.h | 51 | ||||
| -rw-r--r-- | include/Types.h | 159 | ||||
| -rw-r--r-- | include/VM.h | 190 |
19 files changed, 0 insertions, 2333 deletions
diff --git a/include/Api.h b/include/Api.h deleted file mode 100644 index 33a7f6d..0000000 --- a/include/Api.h +++ /dev/null @@ -1,16 +0,0 @@ -#pragma once - -/** - * @file Api.h - * @brief Defines symbol visibility for the Relational NT public API. - */ - -#if defined(_WIN32) && defined(NT_CONSOLE_APP) -#define NT_API -#elif defined(_WIN32) && defined(NT_EXPORTS) -#define NT_API __declspec(dllexport) -#elif defined(_WIN32) -#define NT_API __declspec(dllimport) -#else -#define NT_API -#endif diff --git a/include/CursorManager.h b/include/CursorManager.h deleted file mode 100644 index a4c82d7..0000000 --- a/include/CursorManager.h +++ /dev/null @@ -1,153 +0,0 @@ -#pragma once - -#include "Api.h" -#include "HandlerManager.h" -#include "IStorageBackend.h" -#include "LifecycleManager.h" -#include "ObjectManager.h" -#include "Types.h" - -#include <cstddef> -#include <string> -#include <vector> - -/** - * @file CursorManager.h - * @brief Declares paging and cursor orchestration for query execution. - */ - -namespace nt { - /** - * @class CursorManager - * @brief Orchestrates paginated data retrieval from a storage backend. - * - * CursorManager depends only on IStorageBackend. The concrete backend - * (SqliteBackend, InMemoryBackend, …) is injected at construction time. - * - * Tuples are never loaded all at once. Open() fetches the first page; - * each subsequent Next() call transparently fetches the next page from - * the backend once the current page is exhausted. - * - * Pagination is driven by the Merkle B-tree: each cursor carries the hex - * hash of the relation's Merkle root at open time, and LoadPage calls - * Merkle::Page(backend, merkle_root, fetch_offset, PAGE_SIZE) to retrieve - * the next page of tuple hashes without loading sibling subtrees. - */ - class CursorManager { - public: - static constexpr std::size_t PAGE_SIZE = 1; - - /** - * @brief Constructs a CursorManager. - * - * The @p lifecycles and @p objects references are optional: when - * left null the cursor performs no snapshot pinning (this matches the - * test fixtures, which register relations at synthetic paths with no - * /system/snapshots ancestor). When both are provided, Open finds the - * resolved snapshot for the handle's relation and Pins it for the - * cursor's lifetime, releasing the pin in Close. - */ - explicit CursorManager(IStorageBackend& backend, LifecycleManager* lifecycles = nullptr, - ObjectManager* objects = nullptr); - - /** - * @brief Active scan state for a single relation. - * - * Holds one page of deserialized tuples at a time. When page_position - * reaches the end of the page, Next() discards the page and fetches - * the next one from the backend. - * - * The pointer returned by Next() is valid only until the next Next() - * or Close() call — a page replacement invalidates all prior pointers. - * - * merkle_root is seeded from ObjectManager::Relation::merkle_root at - * open time and does not change during iteration; the cursor reads the - * snapshot captured when it was opened. - * - * Notably the cursor does NOT keep a pointer to the HandlerManager - * handle it was opened from. Everything Next() needs — the relation - * type, the merkle_root, and the ephemeral generator function — is - * captured at Open time, so closing the handle before the cursor is - * exhausted is safe (the API contract still says to close the cursor - * first, but a violation no longer dereferences a freed handle). - */ - struct cursor { - /** - * Hex hash of the relation's Merkle B-tree root node. - * Empty string means the relation contains no tuples. - */ - std::string merkle_root; - /** - * Bound argument values for EPHEMERAL_RELATION cursors. - * Written by the JOIN operator before each probe; ignored for - * stored RELATION cursors. - */ - std::vector<std::string> args; - std::vector<Tuple> page; - std::size_t page_position = 0; - std::size_t fetch_offset = 0; // next Merkle::Page() call starts here - bool exhausted = false; - /** - * True for EPHEMERAL_RELATION cursors; selects the generator-driven - * page fetch path instead of Merkle B-tree paging. - */ - bool is_ephemeral = false; - /** - * Generator function for ephemeral cursors. Copied from the - * ephemeral_object_type at Open time, so the cursor remains valid - * even if the source registry entry is later torn down (the - * snapshot pin held in pinned_snapshot prevents that today, but - * the copy makes the cursor independent regardless). - */ - ObjectManager::ephemeral_object_type::Generator generator; - /** - * Borrowed pointer to the snapshot the cursor is pinning. - * Non-null only when a /system/snapshots/<H>/<n> - * ancestor was found at Open time and LifecycleManager was - * available. Close unpins it. - */ - ObjectManager::registry* pinned_snapshot = nullptr; - }; - - /** - * @brief Opens a cursor on the relation referenced by the handle. - * - * Fetches the first page immediately for non-empty relations. Returns - * a valid exhausted cursor when @p merkle_root is empty (empty relation). - * Returns nullptr when the handle does not refer to a RELATION or - * EPHEMERAL_RELATION. - * - * @param handle Open RELATION or EPHEMERAL_RELATION handle. - * @param merkle_root Hex hash of the relation's Merkle root at open - * time. Ignored for EPHEMERAL_RELATION handles. - */ - cursor* Open(HandlerManager::handle* handle, const std::string& merkle_root = ""); - - /** - * @brief Pulls the next tuple from the cursor. - * - * Fetches the next page from the backend transparently when the - * current page is exhausted. Returns nullptr when all pages are done. - */ - Tuple* Next(cursor* cursor); - - /** - * @brief Closes the cursor and releases its resources. - * @param cursor Cursor to close. - */ - void Close(cursor* cursor); - - private: - IStorageBackend& backend_; - LifecycleManager* lifecycles_ = nullptr; - ObjectManager* objects_ = nullptr; - - /** - * Fetches a page of hashes via Merkle::Page, resolves each from the - * KV store, and deserializes them into cursor->page. Clears the - * existing page. Advances fetch_offset by the number of hashes - * returned; sets exhausted when fewer than PAGE_SIZE hashes come back. - */ - void LoadPage(cursor* c); - }; -} // namespace nt diff --git a/include/HandlerManager.h b/include/HandlerManager.h deleted file mode 100644 index b2beb5f..0000000 --- a/include/HandlerManager.h +++ /dev/null @@ -1,96 +0,0 @@ -#pragma once - -#include "Api.h" -#include "ObjectManager.h" -#include "Types.h" - -#include <set> -#include <string> -#include <vector> - -/** - * @file HandlerManager.h - * @brief Declares handle allocation and release for authorized object access. - */ - -namespace nt { - class IdentityManager; - class LifecycleManager; - class NamespaceReferenceManager; - class PermissionsManager; - - /** @brief Opens and closes authorized handles to registry objects. */ - class HandlerManager { - public: - /** - * @brief Constructs a HandlerManager with shared runtime dependencies. - * - * All managers are injected so that state (registry entries, lifecycle - * counters, permission policy) persists across calls rather than being - * rebuilt per open/close. - */ - HandlerManager(ObjectManager& objects, PermissionsManager& permissions, - IdentityManager& identities, LifecycleManager& lifecycles, - NamespaceReferenceManager& references); - - /** - * @brief Represents authorized access to an object in the registry. - * - * The access mask is evaluated once during Open and cached here for the - * lifetime of the handle. Subsequent operations check `granted_access` - * rather than re-evaluating the security descriptor on every call. This - * resolves the performance question in PermissionsManager about when to - * check permissions. - * - * Because storage is append-only, a WRITE claim does not mean mutating an - * existing tuple in-place. It means the session is authorized to commit a - * new snapshot version of the relation. Two sessions holding WRITE handles - * on the same relation always produce independent snapshots — there is no - * data-level conflict. - * - * @todo Populate `granted_access` inside HandlerManager::Open from - * PermissionsManager::Firewall / Access. See docs/reactos-ob-comparison.md §4. - */ - struct handle { - /** Object referenced by this handle. */ - ObjectManager::registry* object = nullptr; - /** Connection metadata associated with the authorized access. */ - void* connection_context = nullptr; - /** - * Access claims granted to this handle at open time. - * Cached here so that per-operation checks read from the handle - * rather than re-evaluating the security descriptor. - * @todo Populate in HandlerManager::Open. - */ - std::set<AUTH_CLAIM> granted_access; - }; - - /** - * @brief Releases a handle allocation. - * @param handle Handle to release. - */ - void DeallocateHandle(struct handle* handle); - - /** - * @brief Opens an object by path for a connection. - * @param object_path Logical object path. - * @param connection_context Connection metadata for the caller. - * @return A valid handle pointer on success, or nullptr on failure. - */ - struct handle* Open(std::vector<std::string> object_path, void* connection_context); - - /** - * @brief Closes a previously opened handle. - * @param handle Handle to close. - * @return True when the handle was closed successfully. - */ - bool Close(struct handle* handle); - - private: - ObjectManager& objects_; - PermissionsManager& permissions_; - IdentityManager& identities_; - LifecycleManager& lifecycles_; - NamespaceReferenceManager& references_; - }; -} // namespace nt diff --git a/include/IStorageBackend.h b/include/IStorageBackend.h deleted file mode 100644 index a7cc782..0000000 --- a/include/IStorageBackend.h +++ /dev/null @@ -1,49 +0,0 @@ -#pragma once - -#include <cstdint> -#include <optional> -#include <string> -#include <vector> - -/** - * @file IStorageBackend.h - * @brief Abstract KV storage backend consumed by CursorManager and Merkle. - * - * Storage is strictly content-addressed: every value is stored under its - * SHA256 hex digest. Relation membership (which tuple hashes belong to a - * given relation) is now tracked via the Merkle B-tree maintained by the - * Merkle class, not by this interface. Only Put and Get are required. - */ - -namespace nt { - /** - * @interface IStorageBackend - * @brief Contract between CursorManager / Merkle and a physical storage engine. - * - * Two primitives are sufficient: - * - Put: store bytes, get back the content-address (SHA256 hex). - * - Get: retrieve bytes by content-address. - * - * Both are idempotent. The Merkle class stores node blobs via Put/Get and - * maintains insertion-order-independent relation membership on top of these - * two primitives. - */ - class IStorageBackend { - public: - virtual ~IStorageBackend() = default; - - /** - * @brief Stores a serialized value and returns its SHA256 hex hash. - * - * Idempotent: storing the same bytes twice does not create a duplicate. - * The returned hash is the only valid key for subsequent Get calls. - */ - virtual std::string Put(std::vector<uint8_t> value) = 0; - - /** - * @brief Retrieves bytes by their SHA256 hex hash. - * @return The stored bytes, or std::nullopt when the hash is unknown. - */ - virtual std::optional<std::vector<uint8_t>> Get(const std::string& hash) = 0; - }; -} // namespace nt diff --git a/include/IdentityManager.h b/include/IdentityManager.h deleted file mode 100644 index 1dd75da..0000000 --- a/include/IdentityManager.h +++ /dev/null @@ -1,47 +0,0 @@ -#pragma once - -#include "Api.h" -#include "ObjectManager.h" - -/** - * @file IdentityManager.h - * @brief Declares object capability checks. - */ - -namespace nt { - /** - * @brief Checks whether an object supports identity-level operations. - * - * @todo Migrate to type callbacks. Once `object_type` holds `OpenProcedure` - * and `CloseProcedure` function pointers, CanOpen / CanClose become - * thin dispatchers that invoke the corresponding procedure — or this - * manager is absorbed into HandlerManager directly. The function pointer - * should be accompanied by a `const char* name` label on `object_type` - * so that error logs identify the type without dereferencing the pointer. - * See docs/reactos-ob-comparison.md §2. - */ - class IdentityManager { - public: - /** - * @brief Returns true when the object's type supports being opened. - * - * Currently checks that the object is non-null (stub). Should invoke - * `object_type::OpenProcedure` once callbacks are defined. - * - * @param object Object to inspect. - * @return True when the object can be opened. - */ - const bool CanOpen(ObjectManager::registry* object); - - /** - * @brief Returns true when the object's type supports being closed. - * - * Currently checks that the object is non-null (stub). Should invoke - * `object_type::CloseProcedure` once callbacks are defined. - * - * @param object Object to inspect. - * @return True when the object can be closed. - */ - const bool CanClose(ObjectManager::registry* object); - }; -} // namespace nt diff --git a/include/InMemoryBackend.h b/include/InMemoryBackend.h deleted file mode 100644 index b66d355..0000000 --- a/include/InMemoryBackend.h +++ /dev/null @@ -1,31 +0,0 @@ -#pragma once - -#include "Api.h" -#include "IStorageBackend.h" - -#include <cstdint> -#include <optional> -#include <string> -#include <unordered_map> -#include <vector> - -/** - * @file InMemoryBackend.h - * @brief In-process KV storage backend backed by an unordered_map. - * - * Intended for unit tests where SQLite is not appropriate. Data does not - * survive process exit and is not thread-safe. - * - * Relation membership is tracked by the Merkle class, not this backend. - */ - -namespace nt { - class InMemoryBackend : public IStorageBackend { - public: - std::string Put(std::vector<uint8_t> value) override; - std::optional<std::vector<uint8_t>> Get(const std::string& hash) override; - - private: - std::unordered_map<std::string, std::vector<uint8_t>> kv_; - }; -} // namespace nt diff --git a/include/LifecycleManager.h b/include/LifecycleManager.h deleted file mode 100644 index c1e63d8..0000000 --- a/include/LifecycleManager.h +++ /dev/null @@ -1,162 +0,0 @@ -#pragma once - -#include "Api.h" -#include "IStorageBackend.h" -#include "ObjectManager.h" - -/** - * @file LifecycleManager.h - * @brief Declares monitoring, pinning, cleanup, and contention operations. - */ - -namespace nt { - /** - * @brief Manages runtime lifecycle concerns for registry objects. - * - * Object lifetime is governed by two independent counters in registry_head: - * `handle_count` (sessions holding an open handle) and `reference_count` - * (structural dependencies such as cursors pinned to a snapshot or - * ephemeral relations referencing their base relations). An object is - * eligible for GC only when both reach zero. - * - * Monitor / Unmonitor manage `handle_count`. Pin / Unpin manage - * `reference_count`. See docs/reactos-ob-comparison.md §1. - */ - class LifecycleManager { - public: - /** - * @brief Constructs a LifecycleManager bound to a registry and store. - * - * Needs the registry to perform GC: Unmonitor and Unpin call - * ObjectManager::Unregister once both counters reach zero. Type-specific - * cleanup (e.g. cascading a Multigroup's pin to its child Relations, - * or a BranchTree's pin to its child Multigroups) runs inside the - * lifecycle manager before the entry is spliced out. The storage - * backend is needed by CascadeBranchTree to page the merkle nodes. - */ - LifecycleManager(ObjectManager& objects, IStorageBackend& storage); - - /** - * @brief Starts monitoring an object's lifecycle. - * - * Increments `handle_count` on the object's registry_head. Should be - * called after all authorization checks pass inside HandlerManager::Open. - * - * @param object Object to monitor. - */ - void Monitor(ObjectManager::registry* object); - - /** - * @brief Stops monitoring an object. - * - * Decrements `handle_count`. When both `handle_count` and - * `reference_count` reach zero, the object becomes eligible for GC. - * - * @todo Gate GC on both counters reaching zero, not just handle_count. - * For deferred compaction, enqueue onto a background GC list rather - * than freeing inline. See docs/reactos-ob-comparison.md §1 and §7. - * - * @param object Object to stop monitoring. - */ - void Unmonitor(ObjectManager::registry* object); - - /** - * @brief Increments the structural dependency count on an object. - * - * Call when one object takes a dependency on another — for example when - * a cursor pins an immutable snapshot version, or when an ephemeral - * relation is registered against its base relations. Prevents GC of the - * target object while the dependency is live. - * - * @todo Implement. See docs/reactos-ob-comparison.md §1. - * - * @param object Object being depended upon. - */ - void Pin(ObjectManager::registry* object); - - /** - * @brief Decrements the structural dependency count on an object. - * - * The inverse of Pin. When both `reference_count` and `handle_count` - * reach zero the object becomes eligible for GC. - * - * @todo Implement. See docs/reactos-ob-comparison.md §1. - * - * @param object Object whose dependency is being released. - */ - void Unpin(ObjectManager::registry* object); - - /** - * @brief Returns true when the object is GC-eligible right now. - * - * Eligibility is the joint condition handle_count == 0 && - * reference_count == 0. Decrement callers (Unmonitor / Unpin) consult - * this and, when true, run type-specific cleanup before unregistering. - */ - bool IsEligibleForGC(ObjectManager::registry* object) const; - - /** - * @brief Serializes contention for changes to mutable reference states. - * - * Immutable objects — relation snapshots, multigroup snapshots, - * transactions — never raise contention. Two sessions opening the same - * immutable snapshot simultaneously is always safe; they will produce - * independent results without conflict. - * - * Contention applies only to mutable reference states: the HEAD of a - * branch and namespace entries targeted by atomic multi-reference updates. - * These are the sole mutable pointers in the system. When a session holds - * a write handle on a HEAD, a second write opener must block or fail. - * - * @todo Implement: read `object_type::exclusive`. Return false immediately - * for non-exclusive objects. For exclusive objects, return false - * (contention detected) when `handle_count > 0` for a write-mode - * opener. See docs/reactos-ob-comparison.md §6. - * - * @param object Object to check for contention. - * @return True when the operation may proceed. - */ - const bool Contention(ObjectManager::registry* object); - - private: - /** - * @brief Joint-counters check + type-specific cascade + Unregister. - * - * Called by Unmonitor and Unpin after their decrement. No-op when the - * object is still referenced. When eligible: - * - MULTIGROUP entries first unpin every Relation registered as a - * direct child of their /system/snapshots/H subtree. - * - BRANCH_TREE entries first unpin every Multigroup their - * content-addressed tree references. - * - The entry is then removed from the registry; its IObject and - * registry_head are freed. - * - * Inline GC for now; the reaper-queue deferred-deletion pattern from - * docs/reactos-ob-comparison.md §7 is a later optimisation. - */ - void TryCollect(ObjectManager::registry* object); - - /** - * @brief Releases pins held by a MULTIGROUP entry on its child Relations. - * - * Iterates the registry once, collects every /system/snapshots/<H>/<n> - * direct child, and calls Unpin on each. Triggered exclusively from - * TryCollect at the moment the parent snapshot becomes eligible for GC. - */ - void CascadeMultigroup(ObjectManager::registry* multigroup); - - /** - * @brief Releases pins held by a BRANCH_TREE entry on its child mgs. - * - * Pages the Merkle<std::string> tree at the BranchTree's merkle_root, - * resolves each (mg_name, mg_hash) entry to its - * /system/snapshots/<mg_hash> Multigroup, and calls Unpin on it. - * Triggered exclusively from TryCollect at the moment the BranchTree - * itself becomes eligible for GC. - */ - void CascadeBranchTree(ObjectManager::registry* branch_tree); - - ObjectManager& objects_; - IStorageBackend& storage_; - }; -} // namespace nt diff --git a/include/Merkle.h b/include/Merkle.h deleted file mode 100644 index 6256ddc..0000000 --- a/include/Merkle.h +++ /dev/null @@ -1,185 +0,0 @@ -#pragma once - -#include "IStorageBackend.h" - -#include <array> -#include <cstddef> -#include <cstdint> -#include <optional> -#include <string> -#include <vector> - -/** - * @file Merkle.h - * @brief Generic sorted content-addressed B-tree over a templated key type. - * - * Maps `Key → Hash32 payload` with `Key` totally ordered. Each tree node is - * stored as an immutable blob in IStorageBackend via Put/Get. All operations - * load only the nodes on the path from root to the target leaf — O(log_B(n)) - * nodes in memory at once, never the whole tree. - * - * Instantiated three times in RNT: - * - * | Level | Key | Payload (Hash32) | - * |---------------|----------------|-------------------------| - * | Branch tree | `std::string` | multigroup snapshot hash| - * | Multigroup | `std::string` | relation merkle root | - * | Relation | `nt::Hash32` | tuple hash (key=payload)| - * - * **Branching factor B = 64**. At 64 children per node and a billion leaves the - * tree is at most 5 levels deep (~20 KB peak working set). - * - * **Immutability**: nodes are never overwritten once written (content-addressed). - * Insert / Remove produce new nodes only along the modified path; old nodes - * remain valid for any snapshot that still holds their root hash. - * - * **Leaf node** stores a sorted-by-key list of `(Key, Hash32 payload)` pairs, - * length ≤ B. For the relation level the key and payload happen to carry the - * same value (the tuple hash); callers pass it twice. Storing both keeps the - * tree shape uniform across the three levels. - * - * **Internal node entry** layout (`leaf_count | min_key | child_hash`): - * - `leaf_count` enables O(log_B(n) + limit) offset navigation for Page() - * without loading sibling subtrees. - * - `min_key` is the smallest key in the subtree — the routing key. - * - `child_hash` is the content-addressed hash of the child node blob. - * - * **Invariants** (asserted in debug builds): - * - No leaf or internal node is ever empty. - * - Leaf entries are sorted ascending by key. - * - Internal entries are sorted ascending by min_key. - * - * **Wire format**: tagged 1-byte node kind ('L' or 'I'), then big-endian u32 - * count, then count repetitions of either a leaf entry or a child entry. - * Key encoding is per-specialisation: `Hash32` is 32 raw bytes; `std::string` - * is `u32_be length | bytes`. Wire format is content-addressed — any change - * here invalidates every existing stored snapshot. - */ - -namespace nt { - - /** @brief 32-byte hash, the universal payload type for all merkle levels. */ - using Hash32 = std::array<uint8_t, 32>; - - /** @brief Decode a 64-character lowercase-hex SHA256 string into raw bytes. - * Throws std::invalid_argument when the string is not exactly 64 hex chars. */ - Hash32 hex_to_bin(const std::string& hex); - - /** @brief Encode raw 32 bytes back into a 64-character lowercase-hex string. */ - std::string bin_to_hex(const Hash32& bin); - - template <typename Key> class Merkle { - public: - static constexpr size_t B = 64; - - /** - * @brief Insert or overwrite a `(key, payload)` mapping. - * @param store KV backend for node serialisation. - * @param root_hex Current root hash (empty string = empty tree). - * @param key Routing/identity key. - * @param payload Hash this key maps to (child root one level down, or - * the key itself at the relation level). - * @return New root hash. Equal to root_hex when an insertion of an - * identical (key, payload) pair would be a no-op. - */ - static std::string Insert(IStorageBackend& store, const std::string& root_hex, - const Key& key, const Hash32& payload); - - /** - * @brief Remove a key from the tree. - * @return New root hash. Empty string when the tree becomes empty. - * Equal to root_hex when the key is absent. - */ - static std::string Remove(IStorageBackend& store, const std::string& root_hex, - const Key& key); - - /** - * @brief Look up the payload for a key. - * @return The payload when present, std::nullopt when absent. - */ - static std::optional<Hash32> Get(IStorageBackend& store, const std::string& root_hex, - const Key& key); - - /** @brief One (key, payload) pair returned by Page(). */ - struct Entry { - Key key; - Hash32 payload; - }; - - /** - * @brief Page through entries in key-sorted order. - * - * Descends to the leaf at logical position @p offset using cumulative - * leaf_counts stored in internal nodes, then walks forward collecting at - * most @p limit entries. Only the nodes on the active path are loaded; - * sibling subtrees are never touched. - */ - static std::vector<Entry> Page(IStorageBackend& store, const std::string& root_hex, - size_t offset, size_t limit); - - private: - struct LeafEntry { - Key key; - Hash32 payload; - }; - - struct LeafNode { - std::vector<LeafEntry> entries; - }; - - struct ChildEntry { - uint64_t leaf_count; - Key min_key; - Hash32 child_hash; - }; - - struct InternalNode { - std::vector<ChildEntry> entries; - }; - - // Wire format - static std::vector<uint8_t> encode_leaf(const LeafNode& n); - static std::vector<uint8_t> encode_internal(const InternalNode& n); - static LeafNode decode_leaf(const std::vector<uint8_t>& bytes); - static InternalNode decode_internal(const std::vector<uint8_t>& bytes); - static bool is_leaf_bytes(const std::vector<uint8_t>& bytes); - - // Storage helpers - static std::vector<uint8_t> load_node(IStorageBackend& store, const std::string& hash_hex); - static std::string store_leaf(IStorageBackend& store, const LeafNode& n); - static std::string store_internal(IStorageBackend& store, const InternalNode& n); - - /** @brief Returns the smallest key in the subtree rooted at @p node_hex. */ - static Key subtree_min_key(IStorageBackend& store, const std::string& node_hex); - - /** @brief Routes a key to the rightmost child whose min_key ≤ target. */ - static size_t route(const InternalNode& node, const Key& target); - - struct InsertResult { - std::string new_hash; - uint64_t leaf_count = 0; - bool did_split = false; - uint64_t split_leaf_count = 0; - Key split_min_key{}; - std::string split_hash; - }; - - static InsertResult insert_into(IStorageBackend& store, const std::string& node_hex, - const Key& key, const Hash32& payload); - - struct RemoveResult { - std::string new_hash; - uint64_t leaf_count = 0; - }; - - static RemoveResult remove_from(IStorageBackend& store, const std::string& node_hex, - const Key& key); - - static void page_from(IStorageBackend& store, const std::string& node_hex, size_t& offset, - size_t limit, std::vector<Entry>& out); - - static std::optional<Hash32> get_from(IStorageBackend& store, const std::string& node_hex, - const Key& key); - }; - -} // namespace nt diff --git a/include/MultigroupCodec.h b/include/MultigroupCodec.h deleted file mode 100644 index 9d003ea..0000000 --- a/include/MultigroupCodec.h +++ /dev/null @@ -1,82 +0,0 @@ -#pragma once - -#include "IStorageBackend.h" - -#include <string> -#include <utility> -#include <vector> - -/** - * @file MultigroupCodec.h - * @brief Thin facade over Merkle<std::string> for multigroup snapshots. - * - * A multigroup snapshot is a `Merkle<std::string>` B-tree mapping each - * relation name to that relation's merkle root. The snapshot identifier is - * the hex hash of the tree's root node — the same path-localised content - * addressing used at the tuple level inside each relation. - * - * Stored relations and ephemeral relations are represented uniformly: only - * the relation's name and its current merkle_root participate in the tree, - * regardless of how that root was derived. - * - * The codec used to be a flat `SHA256(sorted [(name, root)])` over a single - * blob. That collapsed all relations into one rehash on any mutation. With - * the merkle B-tree, a single relation update touches `O(log_B(n_rels))` - * nodes on the way to the new root — sibling subtrees stay byte-identical. - * - * `RelationEntry` is `(relation_name, relation_root_hex)`. Both forms are - * hex strings on the wire; the codec hex-decodes internally before handing - * payloads to `Merkle<std::string>`. - */ - -namespace nt::MultigroupCodec { - /** @brief One entry in a multigroup snapshot: (relation_name, root_hex). */ - using RelationEntry = std::pair<std::string, std::string>; - - /** - * @brief Build a multigroup tree from a list of (name, root) entries. - * - * Each `Insert` advances the root through `O(log_B)` nodes. The final - * root hash is the snapshot identifier. The list need not be pre-sorted — - * the merkle B-tree imposes order intrinsically. - * - * @param store KV backend; receives all node blobs. - * @param relations Entries to load. Duplicates collapse to the last value. - * @return Root node hash (empty string when `relations` is empty). - */ - std::string Build(IStorageBackend& store, const std::vector<RelationEntry>& relations); - - /** - * @brief Enumerate all (name, root_hex) pairs at a multigroup root. - * - * Pages the entire tree (offset 0, no limit). Returned entries are in - * key-sorted order. Empty input root yields an empty list. - */ - std::vector<RelationEntry> List(IStorageBackend& store, const std::string& root_hex); - - /** - * @brief Insert or overwrite one (relation_name → root_hex) entry. - * - * Equivalent to `Merkle<std::string>::Insert` after hex-decoding the - * payload. The caller threads the returned root hash through subsequent - * mutations. Pass an empty `root_hex` for the prior-state argument to - * start from an empty tree. - */ - std::string InsertOne(IStorageBackend& store, const std::string& root_hex, - const std::string& relation_name, const std::string& relation_root_hex); - - /** - * @brief Remove one relation entry from the multigroup tree. - * - * Returns the new root hash; empty when the tree becomes empty. - */ - std::string RemoveOne(IStorageBackend& store, const std::string& root_hex, - const std::string& relation_name); - - /** - * @brief Look up one relation's root hex by name. - * @return Hex root, or empty string when the name is absent. - */ - std::string Lookup(IStorageBackend& store, const std::string& root_hex, - const std::string& relation_name); -} // namespace nt::MultigroupCodec diff --git a/include/NT.h b/include/NT.h deleted file mode 100644 index 041c517..0000000 --- a/include/NT.h +++ /dev/null @@ -1,17 +0,0 @@ -#pragma once - -/** - * @file NT.h - * @brief Includes for the Relational NT public API. - */ - -#include "CursorManager.h" -#include "HandlerManager.h" -#include "IdentityManager.h" -#include "LifecycleManager.h" -#include "NamespaceReferenceManager.h" -#include "ObjectManager.h" -#include "PermissionsManager.h" -#include "Runtime.h" -#include "Types.h" -#include "VM.h" diff --git a/include/NamespaceReferenceManager.h b/include/NamespaceReferenceManager.h deleted file mode 100644 index d09f4d4..0000000 --- a/include/NamespaceReferenceManager.h +++ /dev/null @@ -1,107 +0,0 @@ -#pragma once - -#include "Api.h" -#include "IStorageBackend.h" -#include "ObjectManager.h" - -#include <string> -#include <vector> - -/** - * @file NamespaceReferenceManager.h - * @brief Declares logical reference mapping and namespace isolation. - */ - -namespace nt { - /** - * @class NamespaceReferenceManager - * @brief Handles the logical mapping and isolation of human-readable references. - * - * This manager is the reparse layer of the namespace. Its design mirrors the - * ReactOS ParseProcedure / STATUS_REPARSE mechanism: a namespace entry whose - * type carries a ParseProcedure can redirect name resolution to a different - * path, allowing branch references and ephemeral relations to appear as - * first-class objects in the namespace without exposing their physical - * storage paths directly. - * - * **Branch references.** - * A path such as `/refs/branch/main` is a namespace entry backed by a - * reference object. Its ParseProcedure rewrites the path to the physical - * snapshot path (e.g. `/snapshots/abc123`). The caller's handle lands on the - * snapshot. To advance the HEAD, the caller must explicitly open the reference - * object itself with WRITE access, which is the sole contention point for that - * branch. - * - * **Ephemeral relation resolution.** - * An ephemeral relation produces tuples through a generator function rather - * than physical storage; the generator may query base relations on behalf - * of the runtime to materialise its output. The caller's handle and access - * mask remain bound to the ephemeral relation. Base relations are accessed - * only via the ephemeral relation's own type callbacks; the caller never - * receives a handle on them and does not need explicit permission on them. - * Capability security is enforced at the ephemeral-relation boundary, not - * the base relation boundary. - * - * **Atomic multi-reference updates.** - * Updating multiple references simultaneously (e.g. advancing both `main` and - * `audit_log`) must be all-or-nothing. The implementation should acquire - * exclusive locks on all target namespace entries before modifying any. If - * LifecycleManager::Contention fails on any entry, all locks are released and - * the batch is aborted. This preserves audit consistency. - * - * **Cycle guard.** - * Ephemeral relation definitions may reference other ephemeral relations, - * and branch aliases may chain. Name resolution must track reparse depth - * and return an error after a bounded number of iterations to prevent - * infinite cycles. - * - * **Audit branch.** - * Audit requires global access dissociated from any data branch. It should be - * modelled as an independent branch; its HEAD is the only contention point for - * audit-affecting operations. - * - * @todo Implement `Resolve(path)` with a reparse loop and cycle depth guard. - * @todo Define the reference object type with `object_type::exclusive = true` - * and a ParseProcedure that rewrites the resolution path. - * @todo Define the batch-update API with all-or-nothing contention semantics. - * See docs/reactos-ob-comparison.md §8. - */ - class NamespaceReferenceManager { - public: - /** - * @brief Constructs a NamespaceReferenceManager bound to a registry. - * @param objects Registry used to look up reference objects (branches, - * sessions) during reparse. - * @param storage KV backend; required to read the branch-tree merkle - * nodes when resolving `/system/branches/<n>/<mg>/...` - * paths through to their snapshot. - */ - NamespaceReferenceManager(ObjectManager& objects, IStorageBackend& storage); - - /** - * @brief Rewrites a logical path through reference reparse rules. - * - * Currently handles branch references: - * /system/branches/<name>/<sub>... → /system/snapshots/<target_hash>/<sub>... - * where target_hash is the value stored on the named Branch object. When - * the branch is unborn (target_hash empty) or the rest of the path is - * empty (caller is opening the branch object itself, not something - * under it), the path is returned unchanged. - * - * Session paths (/system/sessions/<X>/branches/<name>/...) will be - * added when SESSION objects exist; for now they are returned as-is. - * - * A 30-iteration cycle guard mirrors the ReactOS reparse cap. If the - * guard trips the returned path is empty, signaling failure to the - * caller (Find will subsequently miss). - * - * @param path Input logical path components. - * @return Resolved path components, or empty vector on cycle/failure. - */ - std::vector<std::string> Resolve(std::vector<std::string> path) const; - - private: - ObjectManager& objects_; - IStorageBackend& storage_; - }; -} // namespace nt diff --git a/include/ObjectManager.h b/include/ObjectManager.h deleted file mode 100644 index 355f4c7..0000000 --- a/include/ObjectManager.h +++ /dev/null @@ -1,335 +0,0 @@ -#pragma once - -#include "Api.h" -#include "Types.h" - -#include <cstdint> -#include <functional> -#include <map> -#include <memory> -#include <set> -#include <string> -#include <vector> - -/** - * @file ObjectManager.h - * @brief Declares the registry responsible for runtime-managed database objects. - */ - -namespace nt { - /** - * @brief Owns the registry used to locate and reference database objects. - * - * The object manager is the central directory for runtime objects. It keeps - * the metadata needed to reason about object type, path, references, and - * handles while the concrete storage model is still being designed. - */ - class ObjectManager { - public: - /** @brief Base type for objects stored in the registry. */ - class IObject { - public: - virtual ~IObject() = default; - }; - - /** - * @brief Registry object representing a multigroup snapshot. - * - * `merkle_root` is the hex hash of the Merkle<std::string> root node - * that maps relation_name → relation_merkle_root for this snapshot. - * Updates are path-localised: inserting one tuple advances the root - * through O(log_B) node rewrites, leaving sibling subtrees byte- - * identical. - * - * Every commit produces a new Multigroup entry under - * /system/snapshots/<merkle_root> with one child Relation per leaf at - * /system/snapshots/<merkle_root>/relations/<relation_name>. Snapshots are - * immutable (disposable=false, exclusive=false); the rest of the - * system refers to them by hash. A Multigroup is eligible for GC - * only when its reference_count drops to zero (no BRANCH_TREE still - * pins it, no pinned cursor still references it). - */ - class Multigroup : public IObject { - public: - std::string merkle_root; - }; - /** - * @brief Registry object representing a stored relation. - * - * merkle_root is the hex hash of the Merkle B-tree root node stored in - * the KV backend. Empty string means the relation contains no tuples. - * Updated atomically by rnt_link_tuple / rnt_unlink_tuple / rnt_clear_relation. - */ - class Relation : public IObject { - public: - std::string merkle_root; - }; - /** - * @brief Registry object representing an ephemeral relation. - * - * Ephemeral relations have no tuple storage of their own; tuples are - * produced on demand by the generator function declared in the - * ephemeral_object_type descriptor. They compose into a multigroup's - * tree on equal footing with stored relations — only `merkle_root` - * participates in the Merkle<std::string> entry for this relation, - * regardless of how that root was derived. - * - * `merkle_root` is the SHA256 hex digest derived from the generator's - * identity, the current schema, and the merkle_roots of the declared - * base relations. Any mutation to structure or rebinding of a base - * produces a new merkle_root, which then propagates into a new - * multigroup snapshot exactly like a tuple insertion in a stored - * relation. - * - * `dependencies` lists the logical paths of base relations this - * ephemeral relation is defined atop of. The lifecycle manager Pins - * each entry while this object is alive, preventing GC of a stored - * relation that still backs an ephemeral one. The dependency list is - * also the foundation for attribute-level provenance tracking added - * later. - * - * @todo Define the merkle_root composition function (hashes the - * generator identity + schema + sorted base merkle_roots). - * Until ephemeral relations are registered through a writer - * path this remains a documentation-only contract. - */ - class EphemeralRelation : public IObject { - public: - std::string merkle_root; - std::vector<std::string> dependencies; - }; - /** @brief Abstract registry object representing a transaction. */ - class Transaction : public IObject {}; - - /** - * @brief Registry object representing an active connection's session. - * - * `connection_context` carries whatever auth/connection metadata the - * caller passed to rnt_session_open. The runtime treats it as an - * opaque pointer; ownership of the pointee is the caller's concern. - * - * `branch_overrides` maps a branch name to the BRANCH_TREE root this - * session should see for that branch, instead of the global HEAD. - * NamespaceReferenceManager::Resolve consults the override first when - * a path of the form /system/sessions/<X>/branches/<name>/<sub>... - * is requested, falling back to the global /system/branches/<name> - * lookup when no override is present. - * - * The session→branch reference direction is intentional: global - * branches do not track viewing sessions, which keeps the hot path - * cheap. GC of a stale snapshot must walk all sessions' override - * maps to discover live references — amortised cost only paid at GC - * time. A reverse index can be added later if session counts make - * the walk hot. - */ - class Session : public IObject { - public: - void* connection_context = nullptr; - std::map<std::string, std::string> branch_overrides; - }; - - /** - * @brief A named mutable reference to a branch-tree root. - * - * `target_hash` is the merkle_root of a BRANCH_TREE — a - * `Merkle<std::string>` root mapping `mg_name -> mg_hash`. Path - * resolution walks the branch tree to translate - * `/system/branches/<n>/multigroups/<mg>/relations/<rel>` into the - * right `/system/snapshots/<mg_hash>/relations/<rel>`. Empty string - * means the branch has no commits yet (unborn). - * - * Branches are the sole mutable pointer in the system; concurrent - * writers serialize through LifecycleManager::Contention because the - * BRANCH object_type carries exclusive=true. Readers never contend — - * they resolve the branch through its tree to the immutable - * Multigroups and operate on those. - */ - class Branch : public IObject { - public: - std::string name; - std::string target_hash; - }; - - /** - * @brief Registry object for a branch-tree blob. - * - * `merkle_root` is the Merkle<std::string> root hash of the (mg_name, - * mg_hash) tree this entry indexes. The same blob is referenced by - * every BRANCH and session override sharing this tip. Lifecycles: - * - * - Pinned once per referencing BRANCH or session override. - * - When its reference count drops to zero, - * LifecycleManager::CascadeBranchTree pages the tree and unpins - * each multigroup it references before unregistering the entry. - */ - class BranchTree : public IObject { - public: - std::string merkle_root; - }; - - /** - * @brief Describes the behavior and capabilities of an object category. - * - * @todo Replace `methods` with typed callback fields: `OpenProcedure`, - * `CloseProcedure`, `DeleteProcedure`, and `ParseProcedure`. - * Store a `const char* name` label alongside each callback so that - * logs and assertions can identify which type fired without having - * to dereference a pointer. `IdentityManager::CanOpen` / `CanClose` - * then become thin dispatchers that invoke the corresponding - * procedure, or are absorbed into `HandlerManager` directly. - * See docs/reactos-ob-comparison.md §2. - * - * @todo Add an `exclusive` flag for mutable reference objects (branch - * HEADs, namespace entries). Non-exclusive objects — immutable - * snapshots, transactions — must skip contention checks entirely. - * See docs/reactos-ob-comparison.md §6. - */ - struct object_type { - /** Object category label. */ - OBJECT_TYPE label; - /** True when the object is not durable. For example: TRANSACTION. */ - bool disposable; - /** - * Methods supported by this object type. - * @todo Replace with typed callback function pointers. See class-level todo. - */ - std::set<METHOD> methods; - /** - * When true, only one write-mode handle may be open at a time. - * Applies to mutable reference states such as branch HEADs. - * Immutable snapshot objects must leave this false. - * @todo Wire into LifecycleManager::Contention. - */ - bool exclusive = false; - - virtual ~object_type() = default; - }; - - /** - * @brief Object type descriptor for EPHEMERAL_RELATION objects. - * - * An ephemeral relation has no physical storage. Its tuples are produced - * on demand by a generator function. Cardinality may be finite (e.g. a - * projected stored relation) or AlephZero (e.g. the eq/lt builtins). - * - * The generator receives the bound argument values that were written into - * the cursor by the JOIN operator before each probe, together with a - * pagination offset and limit. It must return at most `limit` tuples - * starting at logical position `offset`. - * - * For membership-probe builtins (all args ground), the generator returns - * at most one tuple. For enumeration over AlephZero relations the generator - * maps `offset` to the appropriate pair via a bijective enumeration scheme - * (e.g. Cantor pairing); callers must bound such scans with a TAKE node. - */ - struct ephemeral_object_type : object_type { - enum class Cardinality { Finite, ConstrainedFinite, AlephZero, Continuum }; - - /** - * @brief Produces a page of tuples for the given bound arguments. - * @param args Bound argument values written by the JOIN before probing. - * @param offset Zero-based logical tuple offset (for pagination). - * @param limit Maximum number of tuples to return. - */ - using Generator = std::function<std::vector<Tuple>( - const std::vector<std::string>& args, std::size_t offset, std::size_t limit)>; - - Cardinality cardinality; - Generator generator; - }; - - /** - * @brief Shared metadata stored at the head of a registry entry. - * - * Two independent reference counters govern object lifetime. - * An object is eligible for garbage collection only when both reach zero: - * - * - `handle_count` — open sessions holding a cursor or handle on this object. - * Managed exclusively by LifecycleManager::Monitor / Unmonitor. - * - `reference_count` — structural dependencies such as an ephemeral relation - * referencing its base relations, or a cursor pinned to an immutable snapshot - * version. - * Managed by LifecycleManager::Pin / Unpin (not yet implemented). - * - * All snapshot versions are immutable. An insertion or deletion produces a new - * snapshot rather than mutating an existing one. A snapshot's `reference_count` - * is non-zero while any cursor is pinned to it and drops to zero only when all - * such cursors are released. - * - * @todo Implement `reference_count` tracking. Add LifecycleManager::Pin / - * Unpin. Update LifecycleManager::Unmonitor to gate GC on both counters - * reaching zero. See docs/reactos-ob-comparison.md §1. - * - * @todo Define and attach a security_descriptor. When added, store it as a - * pointer into a shared, content-addressed SD cache rather than inline. - * Permissions are strictly capability-based and must never be inherited - * from a parent namespace entry. See docs/reactos-ob-comparison.md §5. - */ - struct registry_head { - /** - * Structural dependency count. Non-zero while another registry object - * references this one (e.g. an ephemeral relation depending on a base - * relation, or a cursor pinned to a snapshot version). - * @todo Implement via LifecycleManager::Pin / Unpin. - */ - uint32_t reference_count = 0; - /** Number of open handles. Maintained by LifecycleManager::Monitor/Unmonitor. */ - uint32_t handle_count = 0; - /** Object type metadata. Owned by this head. */ - std::unique_ptr<object_type> type; - /** Logical object path inside the namespace. */ - std::vector<std::string> path; - }; - - /** @brief Node in the object registry. */ - struct registry { - /** Shared metadata for this object. */ - std::unique_ptr<registry_head> head; - /** Abstract object payload. Owned by this entry. */ - std::unique_ptr<IObject> object; - /** - * Next entry in the registry. Currently a flat linked list. - * @todo Replace with a trie whose nodes are per-path-segment hash maps. - * Each directory level holds a hash map from segment string to - * child registry*. Find() and Register() walk the trie - * component-by-component instead of scanning a flat list. - * Consider pulling a well-tested radix-tree via the Nix flake rather than - * implementing from scratch. See docs/reactos-ob-comparison.md §3. - */ - std::unique_ptr<registry> next; - }; - - /** @brief Head of the registry linked list. Owned by this manager. */ - std::unique_ptr<registry> entries; - - /** - * @brief Registers an object under the given path, taking ownership of it. - * @param path Logical object path. - * @param object Object payload. Ownership is transferred to the registry. - * @param type Object type descriptor. Ownership is transferred to the registry. - */ - void Register(std::vector<std::string> path, std::unique_ptr<IObject> object, - std::unique_ptr<object_type> type); - - /** - * @brief Looks into this registry and attempts to retrieve an entry. - * @param object_path Logical path to search for. - * @return Borrowed pointer to the matching entry, or nullptr when not found. - */ - registry* Find(const std::vector<std::string> object_path); - - /** - * @brief Removes the entry registered at @p object_path, if any. - * - * Splices the matching node out of the registry list and frees its - * owned object and head. No reference-count checks are performed — - * the caller is responsible for releasing handles and pins before - * calling this. Intended for disposable objects (sessions today, - * other disposables once GC lands in step 6). - * - * @param object_path Logical path of the entry to remove. - * @return True when an entry was removed, false when nothing matched. - */ - bool Unregister(const std::vector<std::string>& object_path); - }; -} // namespace nt diff --git a/include/PermissionsManager.h b/include/PermissionsManager.h deleted file mode 100644 index af72154..0000000 --- a/include/PermissionsManager.h +++ /dev/null @@ -1,88 +0,0 @@ -#pragma once - -#include "Api.h" -#include "ObjectManager.h" -#include "Types.h" - -#include <set> - -/** - * @file PermissionsManager.h - * @brief Declares authentication and object-access checks. - */ - -namespace nt { - /** - * @class Capability-based permission manager - * @brief Evaluates connection claims and object permissions. - * - * Permission checks are intentionally separated from lookup. The object - * manager can retrieve a candidate object, while this manager decides - * whether the caller is allowed to use it. - * - * Permissions are strictly capability-based and must be explicitly granted. - * There is no implicit flow of access rights from a parent namespace entry to - * its children (no SD inheritance). A caller who holds READ on a multigroup - * does not thereby hold READ on its constituent relations — that is a separate, - * explicit capability. - * - * @todo Define a security_descriptor structure. Store instances in a shared, - * content-addressed cache (keyed by descriptor content, not by namespace - * ancestry) so that identical ACLs are not duplicated across relations. - * See docs/reactos-ob-comparison.md §5 and §7. - * - * @todo Cache the result of Access() in HandlerManager::handle::granted_access - * at open time. Per-operation checks should then read from the handle - * rather than re-evaluating the descriptor on every call. - * See docs/reactos-ob-comparison.md §4. - */ - class PermissionsManager { - public: - /** - * @brief Validates a connection during login. - * @param method Authentication method used by the connection. - * @return Claims granted to the authenticated connection. - */ - std::set<AUTH_CLAIM> Firewall(AUTH_METHOD method); - - /** - * @brief Validates permission to an object. - * - * Checks the security descriptor on the head of the object found in - * ObjectManager::registry. It should also check connection metadata - * that is still to be defined, such as user group and policy. - * - * It is still undecided whether this should run on every attempt to get - * hold of an object, since that might produce significant overhead. - * - * Note that the permissions systems also rely on objects with capabilities, - * so imagining the case an ephemeral relation is created based on - * 3 other stored relations, while you can access the ephemeral relation, - * you cannot directly access the other 3 relations. You need explicit - * permission to create a handle on the others. - * - * Here's an example tree: - * /system - * /multigroups - * /coffee_shop - * /relations - * /user {type : stored} - * /order {type : stored} - * /user_and_order {type : ephemeral; deps = - * [/system/multigroups/coffee_shop/relations/users, - * /system/multigroups/coffee_shop/relations/orders]} /users /peter /permissions - * /multigroups/coffee_shop/relations/user_and_order {descriptor : [read]} - * /paul - * /permissions - * /multigroups/coffee_shop/relations/user {descriptor : [write, read]} - * - * Meaning that `peter` has access to read the `user_and_order` ephemeral - * relation, but cannot open a handle on `user` and `order`. - * - * @param object Object being accessed. - * @param connection_context Connection metadata for the caller. - * @return True when access is allowed. - */ - const bool Access(const ObjectManager::registry* object, const void* connection_context); - }; -} // namespace nt diff --git a/include/RNT_C_API.h b/include/RNT_C_API.h deleted file mode 100644 index 1a59785..0000000 --- a/include/RNT_C_API.h +++ /dev/null @@ -1,501 +0,0 @@ -#pragma once - -/** - * @file RNT_C_API.h - * @brief C-callable surface over the RNT manager pipeline for OCaml ctypes. - * - * All types are opaque void pointers on the C side; the implementation casts - * them to the appropriate C++ types internally. Callers must never dereference - * handle or cursor pointers directly. - * - * ## Memory contract - * - Strings returned via out-parameters (char**) are heap-allocated by the - * API and must be released with rnt_free_string(). - * - Payloads returned via (uint8_t**, size_t*) are heap-allocated and must - * be released with rnt_free_bytes(). - * - Handles and cursors are owned by the caller and must be closed before - * the program exits. - * - * ## Error convention - * - Functions returning int use 0 for success and a negative value for error. - * - Functions returning a pointer return NULL on failure. - * - * ## Thread safety - * This API is **not thread-safe**. The global runtime (g_rt) is a single - * in-process instance; all callers share the same ObjectManager and storage - * backend. The expected usage model is a single OCaml thread (or domain) - * driving the API at a time. If concurrent access is needed in the future, - * a per-object or per-relation mutex strategy should be introduced. - * - * @todo Implement AUTH_CLAIM::READ/WRITE enforcement in rnt_open_handle once - * PermissionsManager::Access is wired to a real policy engine. Currently - * all handles open with full access regardless of the claims parameter. - */ - -#include <stddef.h> -#include <stdint.h> - -#include "Api.h" -#include "VM.h" - -#ifdef __cplusplus -extern "C" { -#endif - -/** Opaque handle to a registry object opened through HandlerManager. */ -typedef void* rnt_handle_t; - -/** Opaque cursor over a relation, driven by the VM or used directly. */ -typedef void* rnt_cursor_t; - -/* ------------------------------------------------------------------ */ -/* Runtime lifecycle */ -/* ------------------------------------------------------------------ */ - -/** - * @brief Initializes the RNT runtime with the selected storage backend. - * - * Must be called before any other API function. Once the runtime is - * successfully initialized, subsequent calls are no-ops and return 0. - * If initialization fails (returns negative), the call may be retried - * with corrected parameters — the runtime is left in a clean state. - * - * @param driver Storage driver to use: "sqlite" or "memory". - * "sqlite" persists data to @p storage_path. - * "memory" keeps all data in process memory (ignores - * @p storage_path); intended for tests. - * @param storage_path File path for the SQLite database, or ":memory:" for - * an ephemeral SQLite store. Ignored when driver is - * "memory". - * @return 0 on success, negative on error. - */ -NT_API int rnt_init(const char* driver, const char* storage_path); - -/* ------------------------------------------------------------------ */ -/* Authentication */ -/* ------------------------------------------------------------------ */ - -/** - * @brief Runs PermissionsManager::Firewall for a connection. - * - * @param auth_method "plain_text" or "certificate". - * @param claims_out Set to a heap-allocated, newline-separated claim string. - * Release with rnt_free_string(). NULL on error. - * @return 0 on success, negative when authentication is rejected. - */ -NT_API int rnt_firewall(const char* auth_method, char** claims_out); - -/* ------------------------------------------------------------------ */ -/* Session lifecycle */ -/* ------------------------------------------------------------------ */ - -/** - * @brief Opens a session and registers it at /system/sessions/<hash>. - * - * The runtime mints a random 256-bit hex hash for the session; the caller - * has no influence over the value. The returned string is the opaque - * identifier required by every other rnt_session_* call. - * - * @param connection_context Caller-owned pointer carried on the session. - * The runtime treats it as opaque; ownership of - * the pointee remains with the caller. - * @param session_hash_out Set to a heap-allocated 64-char hex string. - * Release with rnt_free_string(). - * @return 0 on success, negative on error. - */ -NT_API int rnt_session_open(void* connection_context, char** session_hash_out); - -/** - * @brief Closes a session, unregistering it from /system/sessions/<hash>. - * - * After this call the session hash is invalid; subsequent rnt_session_* or - * resolver lookups against it will fail. Branch overrides held by the - * session are dropped. - * - * @param session_hash Hash returned by rnt_session_open. - * @return 0 on success, negative when the hash does not match an active session. - */ -NT_API int rnt_session_close(const char* session_hash); - -/** - * @brief Sets a per-session override for a branch. - * - * While the override is in effect, paths resolved through - * /system/sessions/<hash>/branches/<branch_name>/... point at - * /system/snapshots/<target_hash>/... regardless of where the global branch - * HEAD currently sits. Pass an empty string for @p target_hash to remove - * the override and resume falling back to the global branch. - * - * Non-empty target hashes must correspond to an existing - * /system/snapshots/<target_hash> entry; otherwise the call fails. - * - * @param session_hash Session identifier. - * @param branch_name Branch the override applies to (e.g. "main"). - * @param target_hash Snapshot hash to bind, or "" to clear. - * @return 0 on success, negative on error. - */ -NT_API int rnt_session_set_branch(const char* session_hash, const char* branch_name, - const char* target_hash); - -/* ------------------------------------------------------------------ */ -/* Handle lifecycle */ -/* ------------------------------------------------------------------ */ - -/** - * @brief Opens a handle to the object at the given slash-separated path. - * - * Runs the full HandlerManager::Open pipeline: - * ObjectManager::Find → PermissionsManager::Access → - * IdentityManager::CanOpen → LifecycleManager::Contention → - * LifecycleManager::Monitor. - * - * @param path Slash-separated logical path, e.g. "/system/branches/main". - * @param claims Claim string returned by rnt_firewall (may be NULL). - * @return Handle pointer, or NULL when the path is not found or access is denied. - */ -NT_API rnt_handle_t rnt_open_handle(const char* path, const char* claims); - -/** - * @brief Closes a handle, running HandlerManager::Close and Unmonitor. - * @return 0 on success, negative on error. - */ -NT_API int rnt_close_handle(rnt_handle_t handle); - -/** - * @brief Reads the current branch-tree root hash from a BRANCH object. - * - * Only valid for handles opened on BRANCH objects. The returned string is - * the merkle_root of the BRANCH_TREE this branch currently points at — a - * `Merkle<std::string>` root mapping mg_name → mg_hash. An empty string - * indicates an unborn branch with no commits yet. - * - * @param handle Handle to a BRANCH object. - * @param target_hash_out Set to a heap-allocated copy of the target hash - * (possibly empty). Release with rnt_free_string(). - * @return 0 on success, negative when the handle is not a BRANCH. - */ -NT_API int rnt_branch_target(rnt_handle_t handle, char** target_hash_out); - -/** - * @brief Atomically advances a branch to point at a new branch-tree root. - * - * The new hash must already exist as a content-addressed blob in the KV - * store — branch-tree roots are produced by mutating calls (rnt_link_tuple, - * rnt_register_relation, …) and cannot be invented externally. Pass an - * empty string to reset the branch to unborn. - * - * Write exclusion is structural: BRANCH objects carry @c exclusive=true in - * their object_type, so LifecycleManager::Contention prevents a second handle - * from being opened while a writer holds the branch. AUTH_CLAIM::WRITE is not - * checked at the C API boundary. - * - * @param branch_path Slash-separated branch path, e.g. "/system/branches/main". - * @param new_hash Branch-tree root to advance to (64-char lowercase hex), - * or "" to reset to unborn. - * @return 0 on success, negative when the branch is not found, the type is - * not BRANCH, or @p new_hash is non-empty but no matching blob - * exists in the KV store. - */ -NT_API int rnt_branch_advance(const char* branch_path, const char* new_hash); - -/* ------------------------------------------------------------------ */ -/* Object registration */ -/* ------------------------------------------------------------------ */ - -/** - * @brief Registers a RELATION object at the given path. - * - * Idempotent: if an object already exists at the path, the call succeeds - * without re-registering. - * - * @param path Slash-separated path of the form - * "/system/branches/<branch>/multigroups/<mg>/relations/<rel>". - * @return 0 on success, negative on error. - */ -NT_API int rnt_register_relation(const char* path); - -/** - * @brief Registers a BRANCH object at the given path pointing at a branch-tree root. - * - * If a BRANCH already exists at this path, returns 0 without modifying it. - * When @p target_hash is non-NULL and non-empty it must already exist as a - * content-addressed blob in the KV store (produced by an earlier mutation - * through the same runtime); otherwise the call fails. Pass NULL or "" to - * register an unborn branch. - * - * @param path Slash-separated path, e.g. "/system/branches/main". - * @param target_hash Branch-tree root this branch points at (may be NULL - * or "" for unborn). - * @return 0 on success, negative on error. - */ -NT_API int rnt_register_branch(const char* path, const char* target_hash); - -/** - * @brief Lists all relations of a specific multigroup under a branch. - * - * Returns a newline-delimited string of "name\troot_hash" pairs, one per - * relation in the named multigroup at the branch's current tree. An unborn - * branch or an mg absent from the branch tree yields an empty string. The - * caller must release the string with rnt_free_string(). - * - * @param branch_mg_path Slash-separated path of the form - * "/system/branches/<name>/multigroups/<mg>". - * @param out Set to a heap-allocated "name\troot\n" string. - * Release with rnt_free_string(). NULL on error. - * @return 0 on success, negative when the path shape is wrong or the branch - * is not found. - */ -NT_API int rnt_list_relations(const char* branch_mg_path, char** out); - -/** - * @brief Lists all multigroups bound to a branch. - * - * Reads the branch-tree root from `/system/branches/<name>` and pages each - * (mg_name, mg_hash) entry. Returns "name\thash\n" lines. Unborn branches - * yield an empty string. - * - * @param branch_path Slash-separated branch path, e.g. "/system/branches/main". - * @param out Heap-allocated string; release with rnt_free_string(). - * @return 0 on success, negative when the branch is not found. - */ -NT_API int rnt_list_branch_multigroups(const char* branch_path, char** out); - -/** - * @brief Lists all relations stored in a specific snapshot. - * - * Reads the multigroup codec directly from the snapshot at - * /system/snapshots/<snapshot_hash> without following any branch HEAD. - * Use this when the desired snapshot hash is already known (e.g. detached - * checkout). Returns the same "name\troot_hash\n" format as rnt_list_relations. - * - * @param snapshot_hash 64-char hex hash of the snapshot. - * @param out Set to heap-allocated string. Release with rnt_free_string(). - * @return 0 on success, negative when the snapshot is not registered. - */ -NT_API int rnt_list_snapshot_relations(const char* snapshot_hash, char** out); - -/* ------------------------------------------------------------------ */ -/* Tuple storage */ -/* ------------------------------------------------------------------ */ - -/** - * @brief Stores a tuple and links it to the relation at the given path. - * - * Tuples are encoded as a flat key=value string, one attribute per line: - * "name=Blathers\nprofession=Museum Curator\n" - * Attributes are sorted by name before hashing to ensure content-addressing - * is order-independent. - * - * @param relation_path Slash-separated relation path. - * @param kv_attrs Newline-delimited "key=value" attribute string. - * @param hash_out Set to the 64-character hex SHA-256 hash of the tuple. - * Release with rnt_free_string(). NULL on error. - * @return 0 on success, negative on error. - */ -NT_API int rnt_link_tuple(const char* relation_path, const char* kv_attrs, char** hash_out); - -/** - * @brief Removes a tuple from the relation's Merkle tree and tuple store. - * - * Calls Merkle::Remove on the relation's current root and updates - * ObjectManager::Relation::merkle_root atomically. The tuple bytes remain in - * the KV store (they may be referenced by older snapshots); only the - * membership in the current tree is removed. - * - * @param relation_path Slash-separated relation path. - * @param tuple_hash 64-character hex SHA-256 of the tuple to remove. - * @return 0 on success, negative when the relation is not found. - */ -NT_API int rnt_unlink_tuple(const char* relation_path, const char* tuple_hash); - -/** - * @brief Resets a relation's Merkle root to the empty-tree state. - * - * Sets ObjectManager::Relation::merkle_root to the empty string. Existing - * tuple bytes remain in the KV store. After this call the relation contains - * no tuples from the perspective of cursor iteration. - * - * @param relation_path Slash-separated relation path. - * @return 0 on success, negative when the relation is not found. - */ -NT_API int rnt_clear_relation(const char* relation_path); - -/** - * @brief Returns the current Merkle root hash for a relation. - * - * OCaml calls this after rnt_link_tuple or rnt_unlink_tuple to read the - * updated root back and store it in the in-memory multigroup (tree_pointer). - * An empty string is returned for a relation that contains no tuples. - * - * @param relation_path Slash-separated relation path. - * @param root_hash_out Set to the 64-character hex root hash, or to an empty - * heap-allocated string for an empty relation. - * Release with rnt_free_string(). - * @return 0 on success, negative when the relation is not found. - */ -NT_API int rnt_relation_root(const char* relation_path, char** root_hash_out); - -/* ------------------------------------------------------------------ */ -/* Cursor and VM */ -/* ------------------------------------------------------------------ */ - -/** - * @brief Opens a cursor on the relation referenced by handle. - * - * The returned cursor is positioned before the first tuple. Advance it with - * rnt_cursor_next(). The cursor must be closed with rnt_cursor_close() before - * closing the handle. - * - * @param handle Open RELATION handle. - * @return Cursor pointer, or NULL on error. - */ -NT_API rnt_cursor_t rnt_cursor_open(rnt_handle_t handle); - -/** - * @brief Advances the cursor and returns the next tuple as a kv string. - * - * The tuple is encoded as a newline-delimited "key=value" string matching the - * format accepted by rnt_link_tuple: - * "name=Blathers\nprofession=Museum Curator\n" - * - * @param cursor Open cursor. - * @param tuple_out Set to a heap-allocated kv string, or NULL when exhausted. - * Release with rnt_free_string() when non-NULL. - * @return 1 when a tuple was returned, 0 when exhausted, negative on error. - */ -NT_API int rnt_cursor_next(rnt_cursor_t cursor, char** tuple_out); - -/** - * @brief Closes a cursor and releases its resources. - * @return 0 on success, negative on error. - */ -NT_API int rnt_cursor_close(rnt_cursor_t cursor); - -/* ------------------------------------------------------------------ */ -/* VM plan builder */ -/* ------------------------------------------------------------------ */ - -/** Opaque plan node tree, built via rnt_plan_assemble calls. */ -typedef void* rnt_plan_t; - -/** - * SCAN context: reads all tuples from a stored relation. - * - * @param relation_path Absolute slash-separated path, e.g. - * "/system/branches/main/multigroups/warehouse/relations/public:users". - */ -typedef struct { - const char* relation_path; -} PlanArgsScan; - -/** - * JOIN context: nested-loop join of two child plans. - * - * Takes ownership of both children. They are released when the assembled plan - * is freed or executed; on failure both are freed. - */ -typedef struct { - rnt_plan_t left; - rnt_plan_t right; -} PlanArgsJoin; - -/** - * TAKE context: passes at most @p limit tuples from @p source, then stops. - * - * Takes ownership of @p source; on failure @p source is freed. - */ -typedef struct { - rnt_plan_t source; - size_t limit; -} PlanArgsTake; - -/** - * PROJECT context: keeps only the named attributes of @p source. - * - * @p attrs is a NULL-terminated array of attribute names to retain, e.g. - * <tt>{ "name", "profession", NULL }</tt>. Takes ownership of @p source; on - * failure @p source is freed. - */ -typedef struct { - rnt_plan_t source; - const char** attrs; -} PlanArgsProject; - -/** - * A single plan-construction request. @p operation selects which context member - * is read; the others are ignored. The members are laid out side by side rather - * than overlapped in a union so the struct maps cleanly onto OCaml ctypes, which - * has no union support. Only the member matching @p operation need be populated. - */ -typedef struct { - nt::Operation operation; - PlanArgsScan scan; - PlanArgsJoin join; - PlanArgsTake take; - PlanArgsProject project; -} PlanAction; - -/** - * @brief Builds one plan node from @p action and returns the resulting subtree. - * - * Sole entry point for plan construction. Validates runtime state once, then - * dispatches on @p action.op. Child plans for JOIN/TAKE/PROJECT are themselves - * results of prior rnt_plan_assemble calls; ownership transfers per the - * per-operator rules documented on each PlanArgs* struct. - * - * @return Plan node, or NULL when the runtime is uninitialised or construction - * fails (e.g. relation does not exist). - */ -NT_API rnt_plan_t rnt_plan_assemble(PlanAction action); - -/** - * @brief Releases a plan that was built but not yet executed. - * - * Closes any open cursors and handles owned by the plan tree, then frees all - * nodes. Safe to call with NULL. Do NOT call after rnt_vm_execute_plan — - * that function takes ownership. - */ -NT_API void rnt_plan_free(rnt_plan_t plan); - -/** - * @brief Executes a plan tree and returns a streaming VM cursor. - * - * Takes ownership of @p plan; the caller must not call rnt_plan_free after this. - * The returned cursor is advanced with rnt_vm_cursor_next() and must be closed - * with rnt_vm_cursor_close(), which also releases all plan resources. - * - * @return VM cursor, or NULL when the plan is NULL. - */ -NT_API rnt_cursor_t rnt_vm_execute_plan(rnt_plan_t plan); - -/** - * @brief Advances a VM cursor and returns the next merged tuple as a kv string. - * - * Same encoding and return-value semantics as rnt_cursor_next. - * - * @param vm_cursor Cursor returned by rnt_vm_execute_plan. - * @param tuple_out Set to a heap-allocated kv string, or NULL when exhausted. - * Release with rnt_free_string() when non-NULL. - * @return 1 when a tuple was returned, 0 when exhausted, negative on error. - */ -NT_API int rnt_vm_cursor_next(rnt_cursor_t vm_cursor, char** tuple_out); - -/** - * @brief Closes a VM cursor, releases all plan nodes, cursors, and handles. - * @return 0 on success, negative on error. - */ -NT_API int rnt_vm_cursor_close(rnt_cursor_t vm_cursor); - -/* ------------------------------------------------------------------ */ -/* Memory management */ -/* ------------------------------------------------------------------ */ - -/** @brief Releases a string allocated by the API. Safe to call with NULL. */ -NT_API void rnt_free_string(char* s); - -/** @brief Releases a byte buffer allocated by the API. Safe to call with NULL. */ -NT_API void rnt_free_bytes(uint8_t* p); - -#ifdef __cplusplus -} -#endif diff --git a/include/Runtime.h b/include/Runtime.h deleted file mode 100644 index 0fb41a5..0000000 --- a/include/Runtime.h +++ /dev/null @@ -1,23 +0,0 @@ -#pragma once - -#include "Api.h" - -/** - * @file Runtime.h - * @brief Declares the top-level Relational NT runtime facade. - */ - -namespace nt { - /** @brief Top-level runtime object used by applications and the console entry point. */ - class NT { - public: - /** - * @brief Reports whether the runtime is active. - * @return True when the runtime is running. - */ - bool IsRunning() const; - - /** @brief Simulates an external entry call into the runtime. */ - void SimulateEntryCall(); - }; -} // namespace nt diff --git a/include/SqliteBackend.h b/include/SqliteBackend.h deleted file mode 100644 index 037d8e6..0000000 --- a/include/SqliteBackend.h +++ /dev/null @@ -1,41 +0,0 @@ -#pragma once - -#include "Api.h" -#include "IStorageBackend.h" - -#include <sqlite3.h> -#include <string> -#include <vector> - -/** - * @file SqliteBackend.h - * @brief IStorageBackend implementation backed by an in-process SQLite database. - * - * SQLite schema: - * - * kv(hash TEXT PRIMARY KEY, value BLOB NOT NULL) - * — content-addressed store; key is the SHA256 hex digest of value. - * - * Relation membership is tracked by the Merkle B-tree maintained in-process. - * The former relation_index table has been removed; tuple hashes are looked up - * via Merkle::Page which reads only the KV store. - */ - -namespace nt { - class SqliteBackend : public IStorageBackend { - public: - /** - * @brief Opens (or creates) a SQLite database at @p path. - * @param path File path, or ":memory:" for an in-process database. - * @throws std::runtime_error if the database cannot be opened. - */ - explicit SqliteBackend(const std::string& path = ":memory:"); - ~SqliteBackend() override; - - std::string Put(std::vector<uint8_t> value) override; - std::optional<std::vector<uint8_t>> Get(const std::string& hash) override; - - private: - sqlite3* db_ = nullptr; - }; -} // namespace nt diff --git a/include/TupleCodec.h b/include/TupleCodec.h deleted file mode 100644 index 6c74c1e..0000000 --- a/include/TupleCodec.h +++ /dev/null @@ -1,51 +0,0 @@ -#pragma once - -#include "Types.h" - -#include <cstdint> -#include <string> -#include <vector> - -/** - * @file TupleCodec.h - * @brief Content-addressing utilities for tuples. - * - * Mirrors Sakura's hashing.ml and physical.ml: - * - Hash() ≈ hash_tuple: deterministic SHA256 over sorted attribute content - * - Serialize() ≈ Marshal.to_bytes: raw bytes stored as the KV value - * - Deserialize() ≈ Marshal.from_bytes: reconstruct attributes from raw bytes - * - * The hash input format is: - * "path_seg1/path_seg2/..|name1:value1;name2:value2;" - * where attributes are sorted by name for determinism. - * - * The serialization format is a sequence of length-prefixed UTF-8 pairs: - * [uint32_le name_len][name bytes][uint32_le value_len][value bytes] ... - */ - -namespace nt::TupleCodec { - /** - * @brief Computes the SHA256 hex digest of the serialized tuple. - * - * Equivalent to SHA256(Serialize(attrs)), so the value returned here - * matches the key returned by IStorageBackend::Put(Serialize(attrs)). - * - * @param attrs Attribute set. Need not be pre-sorted. - * @return 64-character lowercase hex string. - */ - std::string Hash(const std::vector<Attribute>& attrs); - - /** - * @brief Serializes a tuple's attributes to raw bytes for KV storage. - * @param attrs Attribute set. Need not be pre-sorted. - * @return Serialized bytes. - */ - std::vector<uint8_t> Serialize(const std::vector<Attribute>& attrs); - - /** - * @brief Reconstructs attributes from the bytes returned by Serialize(). - * @param bytes Bytes produced by Serialize(). - * @return Reconstructed attribute list in serialization order. - */ - std::vector<Attribute> Deserialize(const std::vector<uint8_t>& bytes); -} // namespace nt::TupleCodec diff --git a/include/Types.h b/include/Types.h deleted file mode 100644 index 6956e09..0000000 --- a/include/Types.h +++ /dev/null @@ -1,159 +0,0 @@ -#pragma once - -#include <string> -#include <vector> - -/** - * @file Types.h - * @brief Shared enum types and core data types used by the runtime. - */ - -/** @brief Runtime object categories known by the object manager. */ -enum OBJECT_TYPE { - /** A database snapshot grouping relations and tuples. */ - MULTIGROUP, - /** A relation object backed by physical storage. */ - RELATION, - /** An attribute object (schema metadata). */ - ATTRIBUTE, - /** A transaction object. */ - TRANSACTION, - /** - * A relation whose tuples are produced on demand by a generator function - * rather than read from physical storage. Behaves like a RELATION in every - * other respect: owns a `merkle_root`, has mutable schema, composes into its - * multigroup's hash, and may be opened, scanned, and pinned through the - * same handle pipeline. - * - * The generator receives unsigned-int paginators (offset, limit) plus any - * bound argument values written by an upstream JOIN, and yields tuples. - * Cardinality may be finite (e.g. a projection over a stored relation) or - * AlephZero (e.g. the eq builtin). The object_type for this label must be - * an ephemeral_object_type. - * - * Tracked as a distinct label — rather than collapsed into RELATION — - * for three reasons: - * 1. Sakura distinguishes generated relations as a separate subclass at - * the wire layer, even though the runtime treats them uniformly. - * 2. They have no physical tuple-storage backend; reads always go - * through the generator. - * 3. They carry a dependency list of base relation paths they are - * defined atop of. This drives structural reference counting (a - * base relation cannot be GC'd while an ephemeral relation depends - * on it) and is the foundation for attribute-level provenance - * tracking added later. - */ - EPHEMERAL_RELATION, - /** - * A named mutable reference to a multigroup snapshot, analogous to a git - * branch. A BRANCH object carries a `target_hash` — the merkle_root of - * the snapshot it currently points at — and nothing else. - * - * Branch objects are the entry point for database connections: a client - * opens a handle to /system/branches/<name>, reads target_hash, and uses - * that hash to open the snapshot at /system/snapshots/<hash>. Multigroup - * state is reconstructed by walking the content-addressed graph from - * that snapshot, not by deserializing bytes attached to the branch. - * - * The `exclusive` flag on the object_type should be set to true so that - * LifecycleManager::Contention serializes concurrent writers. - */ - BRANCH, - /** - * A per-connection runtime context. SESSION objects own the - * connection_context pointer (auth metadata, etc.) and a map of per-session - * branch overrides: `branch_name -> target_hash`. Overrides let one - * connection observe a different snapshot for a branch than the global - * HEAD without affecting other sessions. - * - * Sessions are identified by random 256-bit hex hashes minted at - * rnt_session_open. The hash is opaque to the caller and is the only - * handle for subsequent rnt_session_* calls. SESSION objects live at - * /system/sessions/<hash>; the resolver consults - * /system/sessions/<hash>/branches/<n> first and falls back to the global - * /system/branches/<n> when there is no override. - */ - SESSION, - /** - * The content-addressed Merkle<string> root of a branch's multigroup map. - * A BRANCH points at a BRANCH_TREE via target_hash; the tree maps - * `mg_name -> mg_hash` and is paged at resolve time to translate - * `/system/branches/<n>/<mg>/<rel>` into `/system/snapshots/<mg_hash>/<rel>`. - * - * BRANCH_TREE objects live at `/system/branch_trees/<hash>`. They are - * immutable (disposable=false, exclusive=false) and pinned by the BRANCH - * objects that reference them; the mgs they reference are in turn pinned - * by the BRANCH_TREE via LifecycleManager::CascadeBranchTree at GC time. - * The same blob is reused across all branches and session overrides - * that share a tip. - */ - BRANCH_TREE -}; - -/** @brief Operations that may be supported by an object type. */ -enum METHOD { - /** Opens an object and creates an authorized handle. */ - OPEN, - /** Closes a previously opened handle. */ - CLOSE, - /** Parses through a secondary namespace. */ - PARSE, - /** Performs security checks. */ - SECURITY -}; - -/** @brief Claims granted to an authenticated connection. */ -enum AUTH_CLAIM { - /** Permission to read object state. */ - READ, - /** Permission to mutate object state. */ - WRITE -}; - -/** @brief Authentication strategies supported by the permissions layer. */ -enum AUTH_METHOD { - /** Certificate-based authentication. */ - CERTIFICATE, - /** Plain-text authentication. */ - PLAIN_TEXT -}; - -namespace nt { - /** @brief A single named value in a tuple, produced by the cursor layer. */ - struct Attribute { - std::string name; - std::string value; - }; - - /** - * @brief A single row of data streamed lazily from the cursor layer. - * - * Follows the Volcano pull model: callers repeatedly call Next() to consume - * one attribute at a time. Returns nullptr when all attributes are exhausted. - */ - class Tuple { - public: - explicit Tuple(std::vector<Attribute> attributes) : attributes_(std::move(attributes)) { - } - - /** @brief Returns the next attribute, or nullptr when exhausted. */ - const Attribute* Next() { - if (position_ < attributes_.size()) - return &attributes_[position_++]; - return nullptr; - } - - void Reset() { - position_ = 0; - } - - /** @brief Direct read-only access to all attributes without affecting position. */ - const std::vector<Attribute>& attrs() const { - return attributes_; - } - - private: - std::vector<Attribute> attributes_; - size_t position_ = 0; - }; -} // namespace nt diff --git a/include/VM.h b/include/VM.h deleted file mode 100644 index 3d97779..0000000 --- a/include/VM.h +++ /dev/null @@ -1,190 +0,0 @@ -#pragma once - -#include "Api.h" -#include "CursorManager.h" -#include "Types.h" - -#include <optional> -#include <string> -#include <unordered_set> -#include <vector> - -/** - * @file VM.h - * @brief Declares the logic execution boundary for relational and higher-order workloads. - */ - -namespace nt { - /** - * @class VM - * @brief Hosts the first-order logic (FOL) and second-order logic (SOL) cores. - * - * This partitioning exists to ensure retrieval terminates when execution is - * constrained to first-order logic. - * - * - Tarski runtime (FOL): a relational engine that implements Tarski's - * relational calculus. It uses a deterministic Volcano-iterator model to - * perform relational algebra operations such as joins, projections, and - * selects directly against the CursorManager and a prepared plan. - * - * - Karuta runtime (SOL): an isolated WAM-based environment for - * higher-order logic programming. It handles recursion, choice points, and - * other programming constructs that do not guarantee termination. - * - * @remark Lazy evaluation and paging strategy - * - * Both the Tarski first-order engine and the Karuta second-order engine are - * strictly pull-based. Data is streamed lazily from the CursorManager to - * preserve a constant memory footprint regardless of relation size. - * - * Pipeline dynamics: - * - Demand-driven: the Karuta WAM requests a fact only when a goal needs - * satisfaction. A request propagates down the algebra tree as a chain of - * Next() calls. - * - * - Short-circuiting: if the Karuta engine finds a solution or reaches a - * failure that invalidates a branch, the Tarski iterator is discarded or - * reset without materializing the remaining tuples. - * - * - Resource stewardship: by maintaining laziness up to the highest logical - * level, the runtime minimizes pressure on ObjectManager and keeps - * snapshots pinned through LifecycleManager::Monitor only for the minimum - * time required. - */ - - /** - * @brief One segment of a parameterized relation path in a SCAN node. - * - * Var segments are resolved at runtime from the outer tuple of a JOIN: - * the JOIN writes the bound value into the cursor's args vector before - * each probe. Const segments are ground literals fixed at plan construction. - * - * The resolved args vector is passed to the ephemeral relation's generator - * (for EPHEMERAL_RELATION cursors) or ignored (for stored RELATION cursors, - * which need no per-probe parameterization). - */ - struct PathArg { - enum class Kind { Var, Const }; - - Kind kind; - std::string name; /**< Attribute name to look up (Var), or literal value (Const). */ - - static PathArg Var(std::string attr) { - return {Kind::Var, std::move(attr)}; - } - static PathArg Const(std::string val) { - return {Kind::Const, std::move(val)}; - } - }; - - enum Operation { - FOL_OPERATION_SCAN = 1, - FOL_OPERATION_JOIN, - FOL_OPERATION_TAKE, - FOL_OPERATION_PROJECT - }; - - /** - * @brief A node in the Volcano operator tree executed by the Tarski (FOL) runtime. - * - * Each node represents one relational algebra operator. The tree is demand-driven: - * VM::Next() propagates pull requests from root to leaves. - * - * Supported operators: - * - SCAN : pulls tuples from a pre-opened cursor (stored or ephemeral relation). - * - JOIN : nested-loop join. For each outer (left) tuple, resolves scan_args on - * the inner (right) SCAN, resets its cursor, and probes it. Works for - * both stored relations (full re-scan of inner) and ephemeral relations - * (O(1) membership probe when all args are bound). - * - TAKE : passes at most take_limit tuples through, then returns nullptr. Use - * this to bound scans over AlephZero ephemeral relations. - * - PROJECT: filters each input tuple to the named attributes in project_attrs. - */ - struct PlanNode { - Operation op; - PlanNode* left = nullptr; - PlanNode* right = nullptr; - - /** - * SCAN: pre-opened cursor. For ephemeral relations this cursor is - * initially exhausted; the JOIN resets it with resolved args before - * each probe. - */ - CursorManager::cursor* scan_cursor = nullptr; - - /** - * SCAN: argument template for parameterized relations. - * Var entries are resolved from the outer JOIN tuple; Const entries - * are used as-is. The resolved values are written into scan_cursor->args - * by the JOIN before it calls Next() on this node. - */ - std::vector<PathArg> scan_args; - - /** TAKE: maximum number of tuples to emit before returning nullptr. */ - std::size_t take_limit = 0; - std::size_t take_count = 0; /**< Runtime counter; mutable during execution. */ - - /** PROJECT: unordered set of attribute names to keep. */ - std::unordered_set<std::string> project_attrs; - std::optional<Tuple> project_buffer; - - /** - * JOIN runtime state. - * - * join_left holds the current outer tuple while probing the inner - * (right) side. The pointer is stable for the lifetime of one outer - * iteration because Next(left) is only called when join_left is reset - * to nullptr, which happens only after the inner side is exhausted. - * - * join_buffer holds the merged output tuple and is overwritten on each - * successful join. Callers must consume the returned pointer before - * calling Next() again — same contract as a cursor page pointer. - */ - Tuple* join_left = nullptr; - std::optional<Tuple> join_buffer; - }; - - class VM { - public: - // TODO: CursorManager should be injected as a shared runtime instance, - // matching the pattern flagged for HandlerManager and LifecycleManager. - // - // A single CursorManager instance supports multiple simultaneous cursors — - // all iteration state lives in each cursor struct, not in the manager. - // A JOIN plan, for example, holds two independent cursors (one per SCAN leaf) - // and both are driven through the same CursorManager reference. - explicit VM(CursorManager& cursors); - - /** - * @brief Pulls the next tuple from the plan tree (Tarski/FOL core). - * - * Propagates a Next() call down the operator tree: - * - SCAN delegates to CursorManager::Next. - * - JOIN drives the nested-loop: for each outer tuple it resolves - * scan_args on the inner SCAN, resets the inner cursor, and - * probes until a match is found or the inner is exhausted. - * - TAKE counts emitted tuples and returns nullptr once the limit - * is reached. - * - PROJECT filters an input tuple to the requested attribute names. - * - * @param node Root of the plan subtree to evaluate. - * @return Next matching tuple, or nullptr when the plan is exhausted. - */ - Tuple* Next(PlanNode* node); - - private: - CursorManager& cursors_; - - /** - * Resolves a scan_args template against an outer tuple, producing the - * concrete args vector to write into the inner cursor before probing. - */ - static std::vector<std::string> ResolveArgs(const std::vector<PathArg>& tmpl, Tuple* from); - - /** Resets the inner cursor state and writes resolved args into it. */ - static void ResetInner(CursorManager::cursor* c, std::vector<std::string> args); - - /** Merges left and right tuple attributes into node->join_buffer. */ - static Tuple* MergeInto(PlanNode* node, Tuple* left, Tuple* right); - }; -} // namespace nt |