diff options
Diffstat (limited to '')
| -rw-r--r-- | .github/workflows/build.yml | 3 | ||||
| -rw-r--r-- | CMakeLists.txt | 13 | ||||
| -rw-r--r-- | README.org | 18 | ||||
| -rw-r--r-- | flake.lock | 44 | ||||
| -rw-r--r-- | flake.nix | 190 | ||||
| -rw-r--r-- | include/CursorManager.h | 40 | ||||
| -rw-r--r-- | include/IStorageBackend.h | 51 | ||||
| -rw-r--r-- | include/InMemoryBackend.h | 22 | ||||
| -rw-r--r-- | include/Merkle.h | 164 | ||||
| -rw-r--r-- | include/ObjectManager.h | 27 | ||||
| -rw-r--r-- | include/RNT_C_API.h | 378 | ||||
| -rw-r--r-- | include/SqliteBackend.h | 23 | ||||
| -rw-r--r-- | include/Types.h | 28 | ||||
| -rw-r--r-- | src/CursorManager.cpp | 23 | ||||
| -rw-r--r-- | src/InMemoryBackend.cpp | 37 | ||||
| -rw-r--r-- | src/Merkle.cpp | 488 | ||||
| -rw-r--r-- | src/PermissionsManager.cpp | 2 | ||||
| -rw-r--r-- | src/RNT_C_API.cpp | 531 | ||||
| -rw-r--r-- | src/RelationalNT.cpp | 18 | ||||
| -rw-r--r-- | src/SqliteBackend.cpp | 60 | ||||
| -rw-r--r-- | test/VM.cpp | 38 |
21 files changed, 1989 insertions, 209 deletions
diff --git a/.github/workflows/build.yml b/.github/workflows/build.yml index 42ce58d..67b15d2 100644 --- a/.github/workflows/build.yml +++ b/.github/workflows/build.yml @@ -33,3 +33,6 @@ jobs: - name: Build run: cmake --build out/build/${{ matrix.preset }} + + - name: Test + run: ctest --test-dir out/build/${{ matrix.preset }} --output-on-failure diff --git a/CMakeLists.txt b/CMakeLists.txt index 8343a25..127f1de 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -24,6 +24,7 @@ add_executable (RelationalNT "src/LifecycleManager.cpp" "src/HandlerManager.cpp" "src/CursorManager.cpp" + "src/Merkle.cpp" "src/TupleCodec.cpp" "src/InMemoryBackend.cpp" "src/SqliteBackend.cpp" @@ -50,6 +51,7 @@ set(RNT_CORE_SOURCES "src/LifecycleManager.cpp" "src/HandlerManager.cpp" "src/CursorManager.cpp" + "src/Merkle.cpp" "src/TupleCodec.cpp" "src/InMemoryBackend.cpp" "src/NamespaceReferenceManager.cpp" @@ -68,3 +70,14 @@ set_property(TARGET RNT_tests PROPERTY CXX_STANDARD 20) include(Catch) catch_discover_tests(RNT_tests DISCOVERY_MODE PRE_TEST) + +add_library(RNT SHARED + "src/RNT_C_API.cpp" + "src/SqliteBackend.cpp" + ${RNT_CORE_SOURCES} +) +target_include_directories(RNT PUBLIC "include") +target_include_directories(RNT PRIVATE ${PICOSHA2_INCLUDE_DIRS}) +target_compile_definitions(RNT PRIVATE NT_EXPORTS) +target_link_libraries(RNT PRIVATE unofficial::sqlite3::sqlite3) +set_property(TARGET RNT PROPERTY CXX_STANDARD 20) @@ -30,12 +30,28 @@ The NT kernel is a good model for a dedicated database kernel for three reasons. * Current Status -The open-handle pipeline is wired end-to-end and cursors pull tuples lazily from the storage backend one page at a time through the Tarski FOL engine. The active backend (=SqliteBackend=) keeps a =kv(hash, value)= table for content-addressed tuple data and a =relation_index(path, hash)= table for relation membership. =InMemoryBackend= provides the same interface for tests. +The open-handle pipeline is wired end-to-end and cursors pull tuples lazily from the storage backend one page at a time through the Tarski FOL engine. The active backend (=SqliteBackend=) keeps a single =kv(hash, value)= table for content-addressed tuple data. Relation membership is tracked by a sorted Merkle B-tree (=Merkle=) whose nodes are stored in the same KV table; only the root hash per relation is held in memory. =InMemoryBackend= provides the same interface for tests. + +An =extern "C"= API (=RNT_C_API.h=) exposes the full manager pipeline to OCaml via ctypes, enabling Sakura to use this kernel as its storage and query execution layer. Several manager features are still being designed: dual ref counting, type callbacks, trie-based object lookup, and the namespace reparse layer. These are specified in header comments. * Building +** Unix / macOS with Nix + +The easiest Unix path is the Nix development shell. It provides CMake, Ninja, +SQLite, PicoSHA2 headers, Catch2, and debugger tooling. + +#+begin_src shell +nix develop +cmake -S . -B _build -G Ninja -DCMAKE_BUILD_TYPE=Debug +cmake --build _build +ctest --test-dir _build --output-on-failure +#+end_src + +** Windows with Visual Studio / MSVC + Requires MSVC, CMake 3.10 or later, and vcpkg. Dependencies (=sqlite3= and =picosha2=) are fetched and built automatically during CMake configure via the vcpkg manifest. #+begin_src shell diff --git a/flake.lock b/flake.lock new file mode 100644 index 0000000..6307e01 --- /dev/null +++ b/flake.lock @@ -0,0 +1,44 @@ +{ + "nodes": { + "nixpkgs": { + "locked": { + "lastModified": 1777954456, + "narHash": "sha256-hGdgeU2Nk87RAuZyYjyDjFL6LK7dAZN5RE9+hrDTkDU=", + "owner": "NixOS", + "repo": "nixpkgs", + "rev": "549bd84d6279f9852cae6225e372cc67fb91a4c1", + "type": "github" + }, + "original": { + "owner": "NixOS", + "ref": "nixos-unstable", + "repo": "nixpkgs", + "type": "github" + } + }, + "picosha2": { + "flake": false, + "locked": { + "lastModified": 1746328024, + "narHash": "sha256-3psCzbrwR+vO9TyTKOx+gEaWuHDx6pSgLOQ3DqrJsnI=", + "owner": "okdshin", + "repo": "PicoSHA2", + "rev": "161cb3fc4170fa7a3eca9e582cebd27cc4d1fe29", + "type": "github" + }, + "original": { + "owner": "okdshin", + "repo": "PicoSHA2", + "type": "github" + } + }, + "root": { + "inputs": { + "nixpkgs": "nixpkgs", + "picosha2": "picosha2" + } + } + }, + "root": "root", + "version": 7 +} diff --git a/flake.nix b/flake.nix new file mode 100644 index 0000000..2850520 --- /dev/null +++ b/flake.nix @@ -0,0 +1,190 @@ +{ + description = "RelationalNT CMake build"; + + inputs = { + nixpkgs.url = "github:NixOS/nixpkgs/nixos-unstable"; + picosha2 = { + url = "github:okdshin/PicoSHA2"; + flake = false; + }; + }; + + outputs = { self, nixpkgs, picosha2 }: + let + systems = [ + "x86_64-linux" + "aarch64-linux" + "x86_64-darwin" + "aarch64-darwin" + ]; + + forAllSystems = nixpkgs.lib.genAttrs systems; + + # Shared per-system derivations used by both the package and the dev shell. + mkDeps = system: + let + pkgs = import nixpkgs { inherit system; }; + + # Maps the vcpkg-style unofficial::sqlite3::sqlite3 CMake + # target to the system SQLite3 package. Required because CMakeLists.txt + # calls target_link_libraries(... unofficial::sqlite3::sqlite3). + unofficialSqlite3Config = pkgs.writeTextDir + "share/unofficial-sqlite3/unofficial-sqlite3-config.cmake" + '' + include(CMakeFindDependencyMacro) + find_dependency(SQLite3 REQUIRED) + + if(NOT TARGET unofficial::sqlite3::sqlite3) + add_library(unofficial::sqlite3::sqlite3 INTERFACE IMPORTED) + target_link_libraries(unofficial::sqlite3::sqlite3 INTERFACE SQLite::SQLite3) + endif() + ''; + + # PicoSHA2 is a single-header library; extract just the header. + picosha2Headers = pkgs.runCommand "picosha2-headers" { } '' + install -Dm644 ${picosha2}/picosha2.h $out/include/picosha2.h + ''; + + in { inherit pkgs unofficialSqlite3Config picosha2Headers; }; + + in + { + packages = forAllSystems (system: + let + inherit (mkDeps system) pkgs unofficialSqlite3Config picosha2Headers; + in + { + default = pkgs.stdenv.mkDerivation { + pname = "relationalnt"; + version = "0.1.0"; + + src = self; + + nativeBuildInputs = [ + pkgs.cmake + pkgs.ninja + ]; + + buildInputs = [ + pkgs.catch2_3 + picosha2Headers + pkgs.sqlite + unofficialSqlite3Config + ]; + + cmakeFlags = [ + "-DCMAKE_BUILD_TYPE=Release" + ]; + + doCheck = true; + checkPhase = '' + runHook preCheck + ctest --output-on-failure + runHook postCheck + ''; + + installPhase = '' + runHook preInstall + install -Dm755 RelationalNT "$out/bin/RelationalNT" + install -Dm755 RNT_tests "$out/bin/RNT_tests" + for lib in libRNT.so libRNT.dylib; do + if [ -f "$lib" ]; then + install -Dm755 "$lib" "$out/lib/$lib" + fi + done + install -Dm644 ../include/RNT_C_API.h "$out/include/RNT_C_API.h" + runHook postInstall + ''; + + meta = { + description = "Experimental database kernel inspired by the Windows NT object manager"; + mainProgram = "RelationalNT"; + }; + }; + }); + + devShells = forAllSystems (system: + let + inherit (mkDeps system) pkgs unofficialSqlite3Config picosha2Headers; + + # Wrapper that invokes clangd with the Nix toolchain's compiler paths, + # enabling accurate diagnostics in editors that use compile_commands.json. + clangdRnt = pkgs.writeShellScriptBin "clangd-rnt" '' + exec ${pkgs.clang-tools}/bin/clangd \ + --query-driver='${pkgs.stdenv.cc}/bin/*,/usr/bin/clang,/usr/bin/clang++' \ + "$@" + ''; + in + { + default = pkgs.mkShell { + packages = [ + pkgs.catch2_3 + pkgs.clang-tools + pkgs.cmake + pkgs.lldb + pkgs.ninja + clangdRnt + picosha2Headers + pkgs.sqlite + unofficialSqlite3Config + ]; + + CC = "${pkgs.stdenv.cc}/bin/cc"; + CXX = "${pkgs.stdenv.cc}/bin/c++"; + + CMAKE_PREFIX_PATH = pkgs.lib.makeSearchPathOutput "dev" "" [ + picosha2Headers + pkgs.sqlite + unofficialSqlite3Config + ]; + + CMAKE_INCLUDE_PATH = pkgs.lib.makeSearchPathOutput "dev" "include" [ + picosha2Headers + pkgs.sqlite + ]; + + CMAKE_LIBRARY_PATH = pkgs.lib.makeLibraryPath [ + pkgs.sqlite + ]; + + CPATH = pkgs.lib.makeSearchPathOutput "dev" "include" [ + picosha2Headers + pkgs.sqlite + ]; + + C_INCLUDE_PATH = pkgs.lib.makeSearchPathOutput "dev" "include" [ + pkgs.sqlite + ]; + + CPLUS_INCLUDE_PATH = pkgs.lib.makeSearchPathOutput "dev" "include" [ + picosha2Headers + pkgs.sqlite + ]; + + LIBRARY_PATH = pkgs.lib.makeLibraryPath [ + pkgs.sqlite + ]; + + DYLD_LIBRARY_PATH = pkgs.lib.makeLibraryPath [ + pkgs.sqlite + ]; + + PKG_CONFIG_PATH = pkgs.lib.makeSearchPathOutput "dev" "lib/pkgconfig" [ + pkgs.sqlite + ]; + + shellHook = '' + export NIX_CFLAGS_COMPILE="-I${picosha2Headers}/include -I${pkgs.sqlite.dev}/include $NIX_CFLAGS_COMPILE" + export NIX_LDFLAGS="-L${pkgs.sqlite.out}/lib $NIX_LDFLAGS" + ''; + }; + }); + + apps = forAllSystems (system: { + default = { + type = "app"; + program = "${self.packages.${system}.default}/bin/RelationalNT"; + }; + }); + }; +} diff --git a/include/CursorManager.h b/include/CursorManager.h index 092229c..839bf5e 100644 --- a/include/CursorManager.h +++ b/include/CursorManager.h @@ -6,6 +6,7 @@ #include "Types.h" #include <cstddef> +#include <string> #include <vector> /** @@ -25,6 +26,11 @@ namespace nt * 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 NT_API CursorManager { @@ -43,10 +49,19 @@ namespace nt * * 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. */ struct cursor { HandlerManager::handle* handle = nullptr; /** + * 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. @@ -54,17 +69,24 @@ namespace nt std::vector<std::string> args; std::vector<Tuple> page; std::size_t page_position = 0; - std::size_t fetch_offset = 0; // next TupleHashes() call starts here + std::size_t fetch_offset = 0; // next Merkle::Page() call starts here bool exhausted = false; }; /** * @brief Opens a cursor on the relation referenced by the handle. * - * Fetches the first page immediately. Returns nullptr if the relation - * has no tuples or the handle does not refer to a RELATION. + * 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); + cursor* Open(HandlerManager::handle* handle, + const std::string& merkle_root = ""); /** * @brief Pulls the next tuple from the cursor. @@ -83,8 +105,12 @@ namespace nt private: IStorageBackend& backend_; - /** Fetches a page of hashes, resolves each from the KV store, and - * deserializes them into cursor->page. Clears the existing page. */ - void LoadPage(cursor* c, const std::vector<std::string>& path); + /** + * 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); }; } diff --git a/include/IStorageBackend.h b/include/IStorageBackend.h index 884af2d..e408c95 100644 --- a/include/IStorageBackend.h +++ b/include/IStorageBackend.h @@ -7,27 +7,27 @@ /** * @file IStorageBackend.h - * @brief Abstract KV storage backend consumed by CursorManager. + * @brief Abstract KV storage backend consumed by CursorManager and Merkle. * * Storage is strictly content-addressed: every value is stored under its - * SHA256 hex digest. This mirrors the Sakura physical layer in which the - * key is always `Sha256.to_hex (Sha256.string serialized_bytes)` and the - * value is the raw serialized bytes. - * - * Relation membership (which tuple hashes belong to a given relation) is - * tracked via a separate index managed by LinkTuple / TupleHashes. This - * corresponds to Sakura's B+ tree of tuple hashes stored under each relation. + * 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 and a physical (or mock) storage engine. + * @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. * - * Storage is strictly content-addressed: every value lives under its own - * SHA256 digest. Relation membership is tracked separately via - * LinkTuple / TupleHashes, mirroring Sakura's per-relation B+ tree. + * 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 { @@ -38,7 +38,7 @@ namespace nt * @brief Stores a serialized value and returns its SHA256 hex hash. * * Idempotent: storing the same bytes twice does not create a duplicate. - * The hash is the only valid key for subsequent Get calls. + * The returned hash is the only valid key for subsequent Get calls. */ virtual std::string Put(std::vector<uint8_t> value) = 0; @@ -47,30 +47,5 @@ namespace nt * @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; - - /** - * @brief Records that a tuple (by hash) belongs to a relation (by path). - * - * Idempotent. Corresponds to appending a tuple hash to a relation's - * B+ tree in Sakura's physical layer. - */ - virtual void LinkTuple(const std::vector<std::string>& relation_path, - const std::string& tuple_hash) = 0; - - /** - * @brief Returns a page of tuple hashes for a relation. - * - * Pagination is tuple-level: @p offset and @p limit count whole tuples. - * Hashes are returned in insertion order. - * - * @param relation_path Logical relation path. - * @param offset Zero-based index of the first tuple to return. - * @param limit Maximum number of tuple hashes to return. - * @return Ordered list of SHA256 hex hashes. Empty when past the end. - */ - virtual std::vector<std::string> TupleHashes( - const std::vector<std::string>& relation_path, - std::size_t offset, - std::size_t limit) = 0; }; } diff --git a/include/InMemoryBackend.h b/include/InMemoryBackend.h index 8f7f50a..55472a8 100644 --- a/include/InMemoryBackend.h +++ b/include/InMemoryBackend.h @@ -11,33 +11,23 @@ /** * @file InMemoryBackend.h - * @brief In-process KV storage backend backed by unordered_maps. + * @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 { - /** - * @interface InMemoryBackend - * @brief IStorageBackend implementation that keeps all data in process memory. - * - * Intended for unit tests where SQLite is not appropriate. Data does not - * survive process exit and is not thread-safe. - */ class NT_API 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; - void LinkTuple(const std::vector<std::string>& relation_path, - const std::string& tuple_hash) override; - std::vector<std::string> TupleHashes(const std::vector<std::string>& relation_path, - std::size_t offset, - std::size_t limit) override; private: std::unordered_map<std::string, std::vector<uint8_t>> kv_; - std::unordered_map<std::string, std::vector<std::string>> index_; - - static std::string PathKey(const std::vector<std::string>& path); }; } diff --git a/include/Merkle.h b/include/Merkle.h new file mode 100644 index 0000000..8380093 --- /dev/null +++ b/include/Merkle.h @@ -0,0 +1,164 @@ +#pragma once + +#include "IStorageBackend.h" + +#include <array> +#include <cstddef> +#include <cstdint> +#include <string> +#include <vector> + +/** + * @file Merkle.h + * @brief Sorted content-addressed B-tree over SHA-256 tuple hash hex strings. + * + * Each node is stored as an immutable blob in IStorageBackend via Put/Get. + * All three 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. + * + * **Branching factor B = 64**: leaves hold up to 64 hashes; internal nodes hold + * up to 64 child entries. At B=64 and 1 billion tuples the tree is at most + * 5 levels deep (~20 KB peak working set). + * + * **Immutability**: nodes are never overwritten once written (content-addressed). + * Insert and Remove produce new nodes only along the modified path; old nodes + * remain valid for any snapshot that still holds their root hash. + * + * **Internal node entry layout** (leaf_count | min_hash | child_hash): + * - `leaf_count` enables O(log_B(n) + limit) offset navigation for Page() + * without loading sibling subtrees. + * - `min_hash` (smallest tuple hash in the subtree) is 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. + * - Internal node entries are sorted ascending by min_hash. + * - All public entry points that accept a hex hash throw `std::invalid_argument` + * when the string is not exactly 64 lowercase hex characters. + * + * @todo Add bounds checking in decode_leaf / decode_internal: validate that the + * reported entry count does not exceed the actual blob size before reading. + * Currently a truncated or corrupt blob causes out-of-bounds reads. + */ + +namespace nt { + +class Merkle { +public: + static constexpr size_t B = 64; + + /** + * @brief Insert a tuple hash into the tree. + * @param store KV backend for node serialization. + * @param root_hex Current root hash (empty string = empty tree). + * @param hash_hex 64-char hex SHA-256 of the tuple to insert. + * @return New root hash. Equal to root_hex when the hash was already present. + */ + static std::string Insert(IStorageBackend& store, + const std::string& root_hex, + const std::string& hash_hex); + + /** + * @brief Remove a tuple hash from the tree. + * @param store KV backend. + * @param root_hex Current root hash. + * @param hash_hex 64-char hex SHA-256 of the tuple to remove. + * @return New root hash. Empty string when the tree becomes empty. + */ + static std::string Remove(IStorageBackend& store, + const std::string& root_hex, + const std::string& hash_hex); + + /** + * @brief Page through tuple hashes in 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 hashes. Only the nodes on the active path are loaded; + * sibling subtrees are never touched. + * + * @param store KV backend. + * @param root_hex Current root hash. + * @param offset Zero-based logical tuple offset. + * @param limit Maximum number of hashes to return. + * @return Hex hash strings in sorted order. Empty when past the end. + */ + static std::vector<std::string> Page(IStorageBackend& store, + const std::string& root_hex, + size_t offset, + size_t limit); + +private: + using Hash32 = std::array<uint8_t, 32>; + + struct LeafNode { + std::vector<Hash32> hashes; // sorted ascending, len ≤ B + }; + + // Wire: 8-byte leaf_count | 32-byte min_hash | 32-byte child_hash + struct ChildEntry { + uint64_t leaf_count; // number of tuple hashes in this subtree + Hash32 min_hash; // smallest tuple hash in the subtree + Hash32 child_hash; // content-addressed hash of the child node + }; + + struct InternalNode { + std::vector<ChildEntry> entries; // sorted by min_hash, len ≤ B + }; + + // 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); + + // Hex / binary + static Hash32 hex_to_bin(const std::string& hex); + static std::string bin_to_hex(const Hash32& bin); + + // 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); + + // Returns the minimum hash of the subtree rooted at node_hex. + static Hash32 subtree_min(IStorageBackend& store, const std::string& node_hex); + + // Recursive insert result: new node hash, subtree leaf count, optional split. + struct InsertResult { + std::string new_hash; + uint64_t leaf_count = 0; + bool did_split = false; + uint64_t split_leaf_count = 0; + Hash32 split_min_hash = {}; + std::string split_hash; + }; + + static InsertResult insert_into(IStorageBackend& store, + const std::string& node_hex, + const Hash32& tuple_hash); + + // Recursive remove result: new node hash (empty = node gone), leaf count. + struct RemoveResult { + std::string new_hash; + uint64_t leaf_count = 0; + }; + + static RemoveResult remove_from(IStorageBackend& store, + const std::string& node_hex, + const Hash32& tuple_hash); + + // Page collection — offset consumed as we descend. + static void page_from(IStorageBackend& store, + const std::string& node_hex, + size_t& offset, + size_t limit, + std::vector<Hash32>& out); + + // Find which child to route into (rightmost whose min_hash ≤ target). + static size_t route(const InternalNode& node, const Hash32& target); +}; + +} // namespace nt diff --git a/include/ObjectManager.h b/include/ObjectManager.h index 32b3ae9..e30ff1b 100644 --- a/include/ObjectManager.h +++ b/include/ObjectManager.h @@ -35,12 +35,35 @@ namespace nt /** @brief Abstract registry object representing a multigroup. */ class Multigroup : public IObject {}; - /** @brief Abstract registry object representing a relation. */ - class Relation : public IObject {}; + /** + * @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 Abstract registry object representing a transaction. */ class Transaction : public IObject {}; /** + * @brief A named mutable reference to a multigroup state. + * + * The payload field carries the serialized multigroup bytes in whatever + * format the caller registered them with. The C API returns these bytes + * verbatim when a handle to the branch is opened; Sakura is responsible + * for deserializing them into a Multigroup object. + */ + class Branch : public IObject { + public: + std::string name; + std::vector<uint8_t> payload; + }; + + /** * @brief Describes the behavior and capabilities of an object category. * * @todo Replace `methods` with typed callback fields: `OpenProcedure`, diff --git a/include/RNT_C_API.h b/include/RNT_C_API.h new file mode 100644 index 0000000..ddf6a97 --- /dev/null +++ b/include/RNT_C_API.h @@ -0,0 +1,378 @@ +#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> + +#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 Initialises the RNT runtime with the selected storage backend. + * + * Must be called before any other API function. Once the runtime is + * successfully initialised, subsequent calls are no-ops and return 0. + * If initialisation 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. + */ +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. + */ +int rnt_firewall(const char* auth_method, char** claims_out); + +/* ------------------------------------------------------------------ */ +/* 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. + */ +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. + */ +int rnt_close_handle(rnt_handle_t handle); + +/** + * @brief Reads the raw payload bytes stored in a BRANCH object. + * + * Only valid for handles opened on BRANCH objects. The caller uses the bytes + * to reconstruct the in-memory multigroup (e.g. via Sakura's deserializer). + * + * @param handle Handle to a BRANCH object. + * @param payload_out Set to a heap-allocated copy of the payload bytes. + * Release with rnt_free_bytes(). + * @param len_out Set to the number of bytes in payload_out. + * @return 0 on success, negative when the handle is not a BRANCH. + */ +int rnt_branch_payload(rnt_handle_t handle, + uint8_t** payload_out, + size_t* len_out); + +/** + * @brief Writes new payload bytes into the BRANCH object referenced by handle. + * + * Updates the in-memory branch object. Callers are responsible for persisting + * the multigroup state to the storage backend separately via tuple link + * operations. + * + * 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 handle Open BRANCH handle. + * @param payload New serialized multigroup bytes. + * @param len Number of bytes in payload. + * @return 0 on success, negative on error. + */ +int rnt_branch_set_payload(rnt_handle_t handle, + const uint8_t* payload, + size_t len); + +/* ------------------------------------------------------------------ */ +/* 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, e.g. "/system/branches/main/relations/foo". + * @return 0 on success, negative on error. + */ +int rnt_register_relation(const char* path); + +/** + * @brief Registers a BRANCH object at the given path with an initial payload. + * + * If a BRANCH already exists at this path, returns 0 without modifying it. + * + * @param path Slash-separated path, e.g. "/system/branches/main". + * @param payload Initial serialized multigroup bytes (may be NULL for empty). + * @param payload_len Byte count of payload. + * @return 0 on success, negative on error. + */ +int rnt_register_branch(const char* path, + const uint8_t* payload, + size_t payload_len); + +/* ------------------------------------------------------------------ */ +/* 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. + */ +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. + */ +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. + */ +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. + */ +int rnt_relation_root(const char* relation_path, char** root_hash_out); + +/** + * @brief Writes a Merkle root hash into a relation's ObjectManager entry. + * + * Called by Sakura's open_branch during multigroup reconstruction: after + * deserializing the branch payload, OCaml calls this function once per + * relation to restore the persisted Merkle root into the in-memory + * ObjectManager so that subsequent cursors see the correct tuple set. + * + * @param relation_path Slash-separated relation path. + * @param root_hash 64-character hex Merkle root, or empty string to mark + * the relation as empty. + * @return 0 on success, negative when the relation is not found. + */ +int rnt_set_relation_root(const char* relation_path, const char* root_hash); + +/* ------------------------------------------------------------------ */ +/* 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. + */ +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. + */ +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. + */ +int rnt_cursor_close(rnt_cursor_t cursor); + +/* ------------------------------------------------------------------ */ +/* VM plan builder */ +/* ------------------------------------------------------------------ */ + +/** Opaque plan node tree, built incrementally via rnt_plan_* calls. */ +typedef void* rnt_plan_t; + +/** + * @brief Creates a SCAN plan node that reads all tuples from a stored relation. + * + * Opens a RELATION handle and cursor internally. Both are transferred to the + * plan and released when the resulting VM cursor is closed. + * + * @param relation_path Absolute slash-separated path to the relation, e.g. + * "/system/branches/main/relations/public:users". + * @return Plan node, or NULL when the relation does not exist or cannot be opened. + */ +rnt_plan_t rnt_plan_scan(const char* relation_path); + +/** + * @brief Creates a nested-loop JOIN plan node. + * + * Takes ownership of both @p left and @p right. On success the caller must not + * free either child; they are released when the returned plan is freed or + * executed. On failure (NULL return) both children are freed. + * + * @return Plan node, or NULL on error. + */ +rnt_plan_t rnt_plan_join(rnt_plan_t left, rnt_plan_t right); + +/** + * @brief Creates a TAKE plan node that limits output to at most @p limit tuples. + * + * Takes ownership of @p source. On failure @p source is freed. + * + * @return Plan node, or NULL on error. + */ +rnt_plan_t rnt_plan_take(rnt_plan_t source, size_t limit); + +/** + * @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. + */ +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. + */ +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. + */ +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. + */ +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. */ +void rnt_free_string(char* s); + +/** @brief Releases a byte buffer allocated by the API. Safe to call with NULL. */ +void rnt_free_bytes(uint8_t* p); + +#ifdef __cplusplus +} +#endif diff --git a/include/SqliteBackend.h b/include/SqliteBackend.h index 0b21925..ce4e465 100644 --- a/include/SqliteBackend.h +++ b/include/SqliteBackend.h @@ -16,23 +16,13 @@ * kv(hash TEXT PRIMARY KEY, value BLOB NOT NULL) * — content-addressed store; key is the SHA256 hex digest of value. * - * relation_index(path TEXT NOT NULL, tuple_hash TEXT NOT NULL, - * UNIQUE(path, tuple_hash)) - * — maps a relation's logical path to the ordered set of tuple hashes - * it contains. Corresponds to Sakura's per-relation B+ tree of - * tuple hashes stored in the physical layer. + * 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 - * @brief IStorageBackend that persists data in a SQLite database. - * - * Constructed with a file path or ":memory:" for an in-process database. - * All KV values are opaque blobs; callers are responsible for serialization - * (see TupleCodec). - */ class NT_API SqliteBackend : public IStorageBackend { public: @@ -46,15 +36,8 @@ namespace nt std::string Put(std::vector<uint8_t> value) override; std::optional<std::vector<uint8_t>> Get(const std::string& hash) override; - void LinkTuple(const std::vector<std::string>& relation_path, - const std::string& tuple_hash) override; - std::vector<std::string> TupleHashes(const std::vector<std::string>& relation_path, - std::size_t offset, - std::size_t limit) override; private: sqlite3* db_ = nullptr; - - static std::string PathKey(const std::vector<std::string>& path); }; } diff --git a/include/Types.h b/include/Types.h index 3e38829..f7eadff 100644 --- a/include/Types.h +++ b/include/Types.h @@ -24,7 +24,33 @@ enum OBJECT_TYPE { * a projected stored relation) or AlephZero (e.g. the eq builtin). The * object_type for this label must be an ephemeral_object_type. */ - EPHEMERAL_RELATION + EPHEMERAL_RELATION, + /** + * A named mutable reference to a multigroup state, analogous to a git + * branch. A BRANCH object carries an opaque payload (serialized multigroup + * bytes) that the caller — in practice Sakura — deserializes on open. + * + * Branch objects are the entry point for database connections: a client + * opens a handle to /system/branches/<name>, reads the payload bytes to + * reconstruct the multigroup in memory, and holds the handle for the + * duration of the session. + * + * The `exclusive` flag on the object_type should be set to true so that + * LifecycleManager::Contention serializes concurrent writers. + */ + BRANCH, + /** + * A named query plan stored in the object registry. A VIEW object carries + * the serialized plan definition and the multigroup hash at definition time. + * No handles to physical storage are kept open in the VIEW object itself. + * Each time the view is opened, fresh relation handles and cursors are + * created for the duration of that execution, then released on close. + * + * @todo Implement ObjectManager::View, rnt_register_view, and the + * open-view path in HandlerManager. Views are reserved in the type + * system but have no runtime support yet. + */ + VIEW }; /** @brief Operations that may be supported by an object type. */ diff --git a/src/CursorManager.cpp b/src/CursorManager.cpp index 91a0183..219ba2e 100644 --- a/src/CursorManager.cpp +++ b/src/CursorManager.cpp @@ -1,4 +1,5 @@ #include "CursorManager.h" +#include "Merkle.h" #include "ObjectManager.h" #include "TupleCodec.h" @@ -8,9 +9,9 @@ namespace nt : backend_(backend) {} - void CursorManager::LoadPage(cursor* c, const std::vector<std::string>& path) + void CursorManager::LoadPage(cursor* c) { - auto hashes = backend_.TupleHashes(path, c->fetch_offset, PAGE_SIZE); + auto hashes = Merkle::Page(backend_, c->merkle_root, c->fetch_offset, PAGE_SIZE); c->page.clear(); c->page_position = 0; @@ -26,7 +27,8 @@ namespace nt c->exhausted = true; } - CursorManager::cursor* CursorManager::Open(HandlerManager::handle* handle) + CursorManager::cursor* CursorManager::Open(HandlerManager::handle* handle, + const std::string& merkle_root) { if (handle == nullptr || handle->object == nullptr) return nullptr; @@ -47,14 +49,17 @@ namespace nt return nullptr; auto* c = new cursor(); - c->handle = handle; - LoadPage(c, handle->object->head->path); + c->handle = handle; + c->merkle_root = merkle_root; - if (c->page.empty()) + if (merkle_root.empty()) { - delete c; - return nullptr; + // Empty relation: valid but immediately exhausted. + c->exhausted = true; + return c; } + + LoadPage(c); return c; } @@ -80,7 +85,7 @@ namespace nt return &c->page[c->page_position++]; } - LoadPage(c, c->handle->object->head->path); + LoadPage(c); if (c->page.empty()) return nullptr; return &c->page[c->page_position++]; } diff --git a/src/InMemoryBackend.cpp b/src/InMemoryBackend.cpp index 4d637fe..4649da0 100644 --- a/src/InMemoryBackend.cpp +++ b/src/InMemoryBackend.cpp @@ -1,17 +1,9 @@ #include "InMemoryBackend.h" #include <picosha2.h> -#include <numeric> namespace nt { - std::string InMemoryBackend::PathKey(const std::vector<std::string>& path) - { - return std::accumulate( - std::next(path.begin()), path.end(), path.front(), - [](std::string a, const std::string& b) { return std::move(a) + "/" + b; }); - } - std::string InMemoryBackend::Put(std::vector<uint8_t> value) { const std::string hash = picosha2::hash256_hex_string(value.begin(), value.end()); @@ -22,34 +14,7 @@ namespace nt 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; } - - void InMemoryBackend::LinkTuple(const std::vector<std::string>& relation_path, - const std::string& tuple_hash) - { - auto& hashes = index_[PathKey(relation_path)]; - for (const auto& h : hashes) - if (h == tuple_hash) return; - hashes.push_back(tuple_hash); - } - - std::vector<std::string> InMemoryBackend::TupleHashes( - const std::vector<std::string>& relation_path, - std::size_t offset, - std::size_t limit) - { - auto it = index_.find(PathKey(relation_path)); - if (it == index_.end() || offset >= it->second.size()) - return {}; - - const auto& all = it->second; - auto begin = all.begin() + static_cast<ptrdiff_t>(offset); - auto end = (offset + limit <= all.size()) - ? begin + static_cast<ptrdiff_t>(limit) - : all.end(); - return { begin, end }; - } } diff --git a/src/Merkle.cpp b/src/Merkle.cpp new file mode 100644 index 0000000..56ab349 --- /dev/null +++ b/src/Merkle.cpp @@ -0,0 +1,488 @@ +#include "Merkle.h" + +#include <algorithm> +#include <cassert> +#include <cstring> +#include <numeric> +#include <stdexcept> + +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 ────────────────────────────────────────────────── + +Merkle::Hash32 Merkle::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 Merkle::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; +} + +// ── Node serialisation ─────────────────────────────────────────────────────── + +std::vector<uint8_t> Merkle::encode_leaf(const LeafNode& n) +{ + std::vector<uint8_t> buf; + buf.reserve(1 + 4 + n.hashes.size() * 32); + buf.push_back(TAG_LEAF); + write_u32(buf, static_cast<uint32_t>(n.hashes.size())); + for (const auto& h : n.hashes) + buf.insert(buf.end(), h.begin(), h.end()); + return buf; +} + +std::vector<uint8_t> Merkle::encode_internal(const InternalNode& n) +{ + // Each entry: 8 (leaf_count) + 32 (min_hash) + 32 (child_hash) = 72 bytes + std::vector<uint8_t> buf; + buf.reserve(1 + 4 + n.entries.size() * 72); + 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); + buf.insert(buf.end(), e.min_hash.begin(), e.min_hash.end()); + buf.insert(buf.end(), e.child_hash.begin(), e.child_hash.end()); + } + return buf; +} + +Merkle::LeafNode Merkle::decode_leaf(const std::vector<uint8_t>& bytes) +{ + uint32_t count = read_u32(bytes.data() + 1); + LeafNode n; + n.hashes.reserve(count); + const uint8_t* p = bytes.data() + 5; + for (uint32_t i = 0; i < count; ++i, p += 32) + { + Hash32 h; + std::memcpy(h.data(), p, 32); + n.hashes.push_back(h); + } + return n; +} + +Merkle::InternalNode Merkle::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, p += 72) + { + ChildEntry e; + e.leaf_count = read_u64(p); + std::memcpy(e.min_hash.data(), p + 8, 32); + std::memcpy(e.child_hash.data(), p + 40, 32); + n.entries.push_back(e); + } + return n; +} + +bool Merkle::is_leaf_bytes(const std::vector<uint8_t>& bytes) +{ + return !bytes.empty() && bytes[0] == TAG_LEAF; +} + +// ── Storage helpers ────────────────────────────────────────────────────────── + +std::vector<uint8_t> Merkle::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); +} + +std::string Merkle::store_leaf(IStorageBackend& store, const LeafNode& n) +{ + return store.Put(encode_leaf(n)); +} + +std::string Merkle::store_internal(IStorageBackend& store, const InternalNode& n) +{ + return store.Put(encode_internal(n)); +} + +Merkle::Hash32 Merkle::subtree_min(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.hashes.empty() && "Merkle invariant: leaf node must never be empty"); + return leaf.hashes.front(); + } + auto node = decode_internal(bytes); + assert(!node.entries.empty() && "Merkle invariant: internal node must never be empty"); + return node.entries.front().min_hash; +} + +// ── Routing helper ─────────────────────────────────────────────────────────── + +size_t Merkle::route(const InternalNode& node, const Hash32& 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_hash < b.min_hash; + }) && "Merkle invariant: internal node entries must be sorted by min_hash"); + + // Rightmost child whose min_hash ≤ target. + // Defaults to 0 (leftmost) when target < all min_hashes. + size_t idx = 0; + for (size_t i = 1; i < node.entries.size(); ++i) + { + if (node.entries[i].min_hash <= target) + idx = i; + else + break; + } + return idx; +} + +// ── Insert ─────────────────────────────────────────────────────────────────── + +std::string Merkle::Insert(IStorageBackend& store, + const std::string& root_hex, + const std::string& hash_hex) +{ + const Hash32 tuple_hash = hex_to_bin(hash_hex); + + if (root_hex.empty()) + { + LeafNode leaf; + leaf.hashes.push_back(tuple_hash); + return store_leaf(store, leaf); + } + + auto result = insert_into(store, root_hex, tuple_hash); + if (!result.did_split) + return result.new_hash; + + // Root split: wrap both halves in a new internal root. + Hash32 left_min = subtree_min(store, result.new_hash); + Hash32 right_min = result.split_min_hash; + + InternalNode new_root; + + ChildEntry left; + left.leaf_count = result.leaf_count; + left.min_hash = left_min; + left.child_hash = hex_to_bin(result.new_hash); + new_root.entries.push_back(left); + + ChildEntry right; + right.leaf_count = result.split_leaf_count; + right.min_hash = right_min; + right.child_hash = hex_to_bin(result.split_hash); + new_root.entries.push_back(right); + + return store_internal(store, new_root); +} + +Merkle::InsertResult Merkle::insert_into(IStorageBackend& store, + const std::string& node_hex, + const Hash32& tuple_hash) +{ + 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.hashes.begin(), leaf.hashes.end(), tuple_hash); + if (pos != leaf.hashes.end() && *pos == tuple_hash) + { + // Already present — no-op. + InsertResult r; + r.new_hash = node_hex; + r.leaf_count = leaf.hashes.size(); + return r; + } + + leaf.hashes.insert(pos, tuple_hash); + + if (leaf.hashes.size() <= B) + { + InsertResult r; + r.new_hash = store_leaf(store, leaf); + r.leaf_count = leaf.hashes.size(); + return r; + } + + // Split leaf at midpoint. + size_t mid = leaf.hashes.size() / 2; + LeafNode left_leaf, right_leaf; + left_leaf.hashes = { leaf.hashes.begin(), leaf.hashes.begin() + static_cast<ptrdiff_t>(mid) }; + right_leaf.hashes = { leaf.hashes.begin() + static_cast<ptrdiff_t>(mid), leaf.hashes.end() }; + + InsertResult r; + r.new_hash = store_leaf(store, left_leaf); + r.leaf_count = left_leaf.hashes.size(); + r.did_split = true; + r.split_leaf_count = right_leaf.hashes.size(); + r.split_min_hash = right_leaf.hashes.front(); + r.split_hash = store_leaf(store, right_leaf); + return r; + } + + // ── Internal node ─────────────────────────────────────────────────────── + auto node = decode_internal(bytes); + + size_t child_idx = route(node, tuple_hash); + auto child_result = insert_into(store, + bin_to_hex(node.entries[child_idx].child_hash), + tuple_hash); + + 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_hash for the modified child — only child 0 can have its min + // decrease (routing guarantees min_hash[i>0] ≤ inserted hash, so inserting + // below min_hash[i>0] is impossible). + if (child_idx == 0) + node.entries[0].min_hash = subtree_min(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_hash = child_result.split_min_hash; + sibling.child_hash = hex_to_bin(child_result.split_hash); + node.entries.insert(node.entries.begin() + static_cast<ptrdiff_t>(child_idx) + 1, 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; + } + + // 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_hash = right_node.entries.front().min_hash; + r.split_hash = store_internal(store, right_node); + return r; +} + +// ── Remove ─────────────────────────────────────────────────────────────────── + +std::string Merkle::Remove(IStorageBackend& store, + const std::string& root_hex, + const std::string& hash_hex) +{ + if (root_hex.empty()) return ""; + const Hash32 tuple_hash = hex_to_bin(hash_hex); + auto result = remove_from(store, root_hex, tuple_hash); + 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; +} + +Merkle::RemoveResult Merkle::remove_from(IStorageBackend& store, + const std::string& node_hex, + const Hash32& tuple_hash) +{ + 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.hashes.begin(), leaf.hashes.end(), tuple_hash); + if (it == leaf.hashes.end() || *it != tuple_hash) + return { node_hex, leaf.hashes.size() }; // not found — no change + + leaf.hashes.erase(it); + if (leaf.hashes.empty()) + return { "", 0 }; + return { store_leaf(store, leaf), leaf.hashes.size() }; + } + + // ── Internal node ─────────────────────────────────────────────────────── + auto node = decode_internal(bytes); + + size_t child_idx = route(node, tuple_hash); + auto child_result = remove_from(store, + bin_to_hex(node.entries[child_idx].child_hash), + tuple_hash); + + 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_hash = subtree_min(store, child_result.new_hash); + } + + uint64_t total = 0; + for (const auto& e : node.entries) total += e.leaf_count; + return { store_internal(store, node), total }; +} + +// ── Page ───────────────────────────────────────────────────────────────────── + +std::vector<std::string> Merkle::Page(IStorageBackend& store, + const std::string& root_hex, + size_t offset, + size_t limit) +{ + if (root_hex.empty() || limit == 0) return {}; + std::vector<Hash32> raw; + raw.reserve(limit); + size_t skip = offset; + page_from(store, root_hex, skip, limit, raw); + std::vector<std::string> out; + out.reserve(raw.size()); + for (const auto& h : raw) out.push_back(bin_to_hex(h)); + return out; +} + +void Merkle::page_from(IStorageBackend& store, + const std::string& node_hex, + size_t& offset, + size_t limit, + std::vector<Hash32>& out) +{ + auto bytes = load_node(store, node_hex); + + if (is_leaf_bytes(bytes)) + { + auto leaf = decode_leaf(bytes); + const size_t available = leaf.hashes.size(); + + if (offset >= available) + { + offset -= available; + return; + } + + for (size_t i = offset; i < available && out.size() < limit; ++i) + out.push_back(leaf.hashes[i]); + + offset = 0; + return; + } + + auto node = decode_internal(bytes); + + for (const auto& entry : node.entries) + { + if (out.size() >= limit) break; + + if (offset >= entry.leaf_count) + { + offset -= entry.leaf_count; + continue; + } + + page_from(store, bin_to_hex(entry.child_hash), offset, limit, out); + } +} + +} // namespace nt diff --git a/src/PermissionsManager.cpp b/src/PermissionsManager.cpp index 228dd2d..ddd49eb 100644 --- a/src/PermissionsManager.cpp +++ b/src/PermissionsManager.cpp @@ -14,6 +14,6 @@ namespace nt // 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 && connection_context != nullptr; + return object != nullptr; } } diff --git a/src/RNT_C_API.cpp b/src/RNT_C_API.cpp new file mode 100644 index 0000000..34bbacc --- /dev/null +++ b/src/RNT_C_API.cpp @@ -0,0 +1,531 @@ +#include "RNT_C_API.h" + +#include "CursorManager.h" +#include "HandlerManager.h" +#include "IdentityManager.h" +#include "LifecycleManager.h" +#include "Merkle.h" +#include "ObjectManager.h" +#include "PermissionsManager.h" +#include "InMemoryBackend.h" +#include "SqliteBackend.h" +#include "TupleCodec.h" +#include "VM.h" + +#include <cstring> +#include <memory> +#include <mutex> +#include <sstream> +#include <stdexcept> +#include <string> +#include <vector> + +// --------------------------------------------------------------------------- +// Global runtime state +// +// A single Runtime instance is created per process on the first successful +// rnt_init call. All managers share this instance; they do not hold their +// own state. Initialisation is protected by g_init_mutex so that concurrent +// first-callers are safe; once g_init_done is true the mutex is never +// contended again. +// --------------------------------------------------------------------------- + +namespace +{ + struct Runtime + { + std::unique_ptr<nt::IStorageBackend> storage; + nt::ObjectManager objects; + nt::PermissionsManager permissions; + nt::IdentityManager identities; + nt::LifecycleManager lifecycles; + std::unique_ptr<nt::HandlerManager> handler; + std::unique_ptr<nt::CursorManager> cursors; + }; + + static std::unique_ptr<Runtime> g_rt; + static std::mutex g_init_mutex; + static bool g_init_done = false; + + bool is_init() { return g_init_done; } + + static std::vector<std::string> split_path(const char* path) + { + std::vector<std::string> parts; + if (!path) return parts; + std::string s(path); + 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); + return parts; + } + + static std::vector<nt::Attribute> parse_kv(const char* kv) + { + std::vector<nt::Attribute> attrs; + if (!kv) return attrs; + std::stringstream ss(kv); + std::string line; + 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) }); + } + return attrs; + } + + static std::string tuple_to_kv(nt::Tuple* t) + { + std::string out; + t->Reset(); + const nt::Attribute* a = t->Next(); + while (a) + { + out += a->name + "=" + a->value + "\n"; + a = t->Next(); + } + return out; + } + + 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; + t->disposable = false; + 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; + t->disposable = false; + t->methods = { OPEN, CLOSE }; + // Branches are mutable reference heads: serialize writers through + // LifecycleManager::Contention. + t->exclusive = true; + return t; + } + + // ----------------------------------------------------------------------- + // Plan builder internals + // ----------------------------------------------------------------------- + + /** + * Wraps an entire plan subtree. All PlanNode allocations and all + * CursorManager::cursor* / HandlerManager::handle* opened by SCAN nodes + * 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 + }; + + 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; + } + + /** + * A VM cursor owns the materialised plan tree and all resources opened + * 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); + cursors = std::move(pw->cursors); + handles = std::move(pw->handles); + 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); + } + }; +} + +// --------------------------------------------------------------------------- +// Public C API +// +// Section order mirrors the NT open-handle pipeline: +// Runtime lifecycle → Authentication → Handle lifecycle → +// Object registration → Tuple storage → Cursor / VM plan builder +// --------------------------------------------------------------------------- + +int rnt_init(const char* driver, const char* storage_path) +{ + std::lock_guard<std::mutex> lock(g_init_mutex); + if (g_init_done) return 0; + + 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->handler = std::make_unique<nt::HandlerManager>( + rt->objects, rt->permissions, rt->identities, rt->lifecycles); + rt->cursors = std::make_unique<nt::CursorManager>(*rt->storage); + g_rt = std::move(rt); + + // Register the default branch on first boot so that + // rnt_open_handle("/system/branches/master") always succeeds. + const auto main_path = split_path("/system/branches/master"); + if (g_rt->objects.Find(main_path) == nullptr) + { + auto branch = std::make_unique<nt::ObjectManager::Branch>(); + branch->name = "master"; + g_rt->objects.Register(main_path, std::move(branch), + make_branch_type()); + } + + g_init_done = true; + return 0; + } + catch (...) + { + g_rt.reset(); + return -1; + } +} + +int rnt_firewall(const char* /*auth_method*/, char** claims_out) +{ + if (!is_init() || !claims_out) return -1; + // PermissionsManager::Firewall is stubbed; grant all claims for now. + *claims_out = heap_str("READ WRITE"); + return 0; +} + +rnt_handle_t rnt_open_handle(const char* path, const char* /*claims*/) +{ + if (!is_init() || !path) return nullptr; + return g_rt->handler->Open(split_path(path), nullptr); +} + +int rnt_close_handle(rnt_handle_t handle) +{ + if (!is_init() || !handle) return -1; + auto* h = static_cast<nt::HandlerManager::handle*>(handle); + return g_rt->handler->Close(h) ? 0 : -1; +} + +int rnt_branch_payload(rnt_handle_t handle, uint8_t** payload_out, size_t* len_out) +{ + if (!is_init() || !handle || !payload_out || !len_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; + + auto* branch = dynamic_cast<nt::ObjectManager::Branch*>(h->object->object.get()); + if (!branch) return -1; + + const auto& src = branch->payload; + auto* buf = new uint8_t[src.size()]; + std::memcpy(buf, src.data(), src.size()); + *payload_out = buf; + *len_out = src.size(); + return 0; +} + +int rnt_branch_set_payload(rnt_handle_t handle, const uint8_t* payload, size_t len) +{ + if (!is_init() || !handle) 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; + + auto* branch = dynamic_cast<nt::ObjectManager::Branch*>(h->object->object.get()); + if (!branch) return -1; + + branch->payload.assign(payload, payload + len); + return 0; +} + +int rnt_register_relation(const char* path) +{ + if (!is_init() || !path) return -1; + const auto parts = split_path(path); + if (g_rt->objects.Find(parts) != nullptr) return 0; + g_rt->objects.Register( + parts, + std::make_unique<nt::ObjectManager::Relation>(), + make_relation_type()); + return 0; +} + +int rnt_register_branch(const char* path, const uint8_t* payload, size_t payload_len) +{ + if (!is_init() || !path) return -1; + const auto parts = split_path(path); + if (g_rt->objects.Find(parts) != nullptr) return 0; + + auto branch = std::make_unique<nt::ObjectManager::Branch>(); + branch->name = parts.empty() ? "" : parts.back(); + if (payload && payload_len > 0) + branch->payload.assign(payload, payload + payload_len); + + g_rt->objects.Register(parts, std::move(branch), make_branch_type()); + return 0; +} + +// Looks up the Relation object for a path; returns nullptr when not found or wrong type. +static nt::ObjectManager::Relation* find_relation(const std::vector<std::string>& parts) +{ + auto* entry = g_rt->objects.Find(parts); + if (!entry || !entry->object) return nullptr; + return dynamic_cast<nt::ObjectManager::Relation*>(entry->object.get()); +} + +int rnt_link_tuple(const char* relation_path, const char* kv_attrs, char** hash_out) +{ + if (!is_init() || !relation_path || !kv_attrs || !hash_out) return -1; + const auto parts = split_path(relation_path); + + auto* rel = find_relation(parts); + if (!rel) return -1; + + auto bytes = nt::TupleCodec::Serialize(parse_kv(kv_attrs)); + const auto hash = g_rt->storage->Put(std::move(bytes)); + + rel->merkle_root = nt::Merkle::Insert(*g_rt->storage, rel->merkle_root, hash); + + *hash_out = heap_str(hash); + return 0; +} + +int rnt_unlink_tuple(const char* relation_path, const char* tuple_hash) +{ + if (!is_init() || !relation_path || !tuple_hash) return -1; + auto* rel = find_relation(split_path(relation_path)); + if (!rel) return -1; + rel->merkle_root = nt::Merkle::Remove(*g_rt->storage, rel->merkle_root, tuple_hash); + return 0; +} + +int rnt_clear_relation(const char* relation_path) +{ + if (!is_init() || !relation_path) return -1; + auto* rel = find_relation(split_path(relation_path)); + if (!rel) return -1; + rel->merkle_root.clear(); + return 0; +} + +int rnt_relation_root(const char* relation_path, char** root_hash_out) +{ + if (!is_init() || !relation_path || !root_hash_out) return -1; + auto* rel = find_relation(split_path(relation_path)); + if (!rel) return -1; + *root_hash_out = heap_str(rel->merkle_root); + return 0; +} + +int rnt_set_relation_root(const char* relation_path, const char* root_hash) +{ + if (!is_init() || !relation_path) return -1; + auto* rel = find_relation(split_path(relation_path)); + if (!rel) return -1; + rel->merkle_root = root_hash ? root_hash : ""; + return 0; +} + +rnt_cursor_t rnt_cursor_open(rnt_handle_t handle) +{ + if (!is_init() || !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) + { + auto* rel = find_relation(h->object->head->path); + 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_init() || !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; } + *tuple_out = heap_str(tuple_to_kv(t)); + return 1; +} + +int rnt_cursor_close(rnt_cursor_t cursor) +{ + if (!is_init() || !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; } + +// --------------------------------------------------------------------------- +// VM plan builder +// --------------------------------------------------------------------------- + +rnt_plan_t rnt_plan_scan(const char* relation_path) +{ + if (!is_init() || !relation_path) return nullptr; + + // Open a handle to the stored relation through the full manager pipeline. + const auto parts = split_path(relation_path); + auto* h = g_rt->handler->Open(parts, nullptr); + if (!h) return nullptr; + + // Seed the cursor with the current Merkle root from the ObjectManager. + std::string merkle_root; + auto* rel = find_relation(parts); + 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::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; +} + +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) +{ + free_plan_wrapper(static_cast<PlanWrapper*>(plan)); +} + +rnt_cursor_t rnt_vm_execute_plan(rnt_plan_t plan) +{ + if (!is_init() || !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_init() || !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; } + *tuple_out = heap_str(tuple_to_kv(t)); + return 1; +} + +int rnt_vm_cursor_close(rnt_cursor_t vm_cursor) +{ + if (!is_init() || !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 e82b8c9..acf7ecb 100644 --- a/src/RelationalNT.cpp +++ b/src/RelationalNT.cpp @@ -5,6 +5,7 @@ #include "HandlerManager.h" #include "IdentityManager.h" #include "LifecycleManager.h" +#include "Merkle.h" #include "ObjectManager.h" #include "PermissionsManager.h" #include "SqliteBackend.h" @@ -40,15 +41,18 @@ int main() type->disposable = false; type->methods = { OPEN, CLOSE }; - objects.Register({ "multigroups", "sakura", "relations", "villager" }, std::make_unique<nt::ObjectManager::Relation>(), std::move(type)); + 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()); - // --- Populate SQLite backend with three tuples --- + // --- Populate backend with three tuples via the Merkle tree --- nt::SqliteBackend backend; - const std::vector<std::string> path = { "multigroups", "sakura", "relations", "villager" }; auto store = [&](std::vector<nt::Attribute> attrs) { auto bytes = nt::TupleCodec::Serialize(attrs); - auto hash = backend.Put(bytes); - backend.LinkTuple(path, hash); + auto hash = backend.Put(std::move(bytes)); + villager_rel->merkle_root = + nt::Merkle::Insert(backend, villager_rel->merkle_root, hash); }; store({ { "name", "Blathers" }, { "profession", "Museum Curator" } }); store({ { "name", "Rover" }, { "profession", "Traveller" } }); @@ -62,7 +66,7 @@ int main() nt::HandlerManager handler(objects, permissions, identities, lifecycles); int connection = 1; // dummy connection context - nt::HandlerManager::handle* handle = handler.Open({ "multigroups", "sakura", "relations", "villager" }, &connection); + nt::HandlerManager::handle* handle = handler.Open(path, &connection); if (handle == nullptr) { std::cout << "Failed to open handle for villager\n"; @@ -70,7 +74,7 @@ int main() } // --- Open a cursor on the relation --- - nt::CursorManager::cursor* cursor = cursors.Open(handle); + nt::CursorManager::cursor* cursor = cursors.Open(handle, villager_rel->merkle_root); if (cursor == nullptr) { std::cout << "Failed to open cursor for villager\n"; diff --git a/src/SqliteBackend.cpp b/src/SqliteBackend.cpp index 4741033..7e9c9d5 100644 --- a/src/SqliteBackend.cpp +++ b/src/SqliteBackend.cpp @@ -1,18 +1,10 @@ #include "SqliteBackend.h" #include <picosha2.h> -#include <numeric> #include <stdexcept> namespace nt { - static std::string JoinPath(const std::vector<std::string>& path) - { - return std::accumulate( - std::next(path.begin()), path.end(), path.front(), - [](std::string a, const std::string& b) { return std::move(a) + "/" + b; }); - } - SqliteBackend::SqliteBackend(const std::string& path) { if (sqlite3_open(path.c_str(), &db_) != SQLITE_OK) @@ -22,11 +14,6 @@ namespace nt "CREATE TABLE IF NOT EXISTS kv (" " hash TEXT PRIMARY KEY," " value BLOB NOT NULL" - ");" - "CREATE TABLE IF NOT EXISTS relation_index (" - " path TEXT NOT NULL," - " tuple_hash TEXT NOT NULL," - " UNIQUE(path, tuple_hash)" ");"; char* err = nullptr; @@ -43,11 +30,6 @@ namespace nt sqlite3_close(db_); } - std::string SqliteBackend::PathKey(const std::vector<std::string>& path) - { - return JoinPath(path); - } - std::string SqliteBackend::Put(std::vector<uint8_t> value) { const std::string hash = picosha2::hash256_hex_string(value.begin(), value.end()); @@ -57,10 +39,10 @@ namespace nt "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; } @@ -82,42 +64,4 @@ namespace nt sqlite3_finalize(stmt); return result; } - - void SqliteBackend::LinkTuple(const std::vector<std::string>& relation_path, - const std::string& tuple_hash) - { - const std::string path_key = PathKey(relation_path); - - sqlite3_stmt* stmt = nullptr; - sqlite3_prepare_v2(db_, - "INSERT OR IGNORE INTO relation_index (path, tuple_hash) VALUES (?, ?)", - -1, &stmt, nullptr); - sqlite3_bind_text(stmt, 1, path_key.c_str(), -1, SQLITE_TRANSIENT); - sqlite3_bind_text(stmt, 2, tuple_hash.c_str(), -1, SQLITE_TRANSIENT); - sqlite3_step(stmt); - sqlite3_finalize(stmt); - } - - std::vector<std::string> SqliteBackend::TupleHashes( - const std::vector<std::string>& relation_path, - std::size_t offset, - std::size_t limit) - { - const std::string path_key = PathKey(relation_path); - - sqlite3_stmt* stmt = nullptr; - sqlite3_prepare_v2(db_, - "SELECT tuple_hash FROM relation_index" - " WHERE path = ? ORDER BY rowid LIMIT ? OFFSET ?", - -1, &stmt, nullptr); - sqlite3_bind_text(stmt, 1, path_key.c_str(), -1, SQLITE_TRANSIENT); - sqlite3_bind_int64(stmt, 2, static_cast<sqlite3_int64>(limit)); - sqlite3_bind_int64(stmt, 3, static_cast<sqlite3_int64>(offset)); - - std::vector<std::string> hashes; - while (sqlite3_step(stmt) == SQLITE_ROW) - hashes.emplace_back(reinterpret_cast<const char*>(sqlite3_column_text(stmt, 0))); - sqlite3_finalize(stmt); - return hashes; - } } diff --git a/test/VM.cpp b/test/VM.cpp index ed98be0..00361cb 100644 --- a/test/VM.cpp +++ b/test/VM.cpp @@ -5,6 +5,7 @@ #include "IdentityManager.h" #include "InMemoryBackend.h" #include "LifecycleManager.h" +#include "Merkle.h" #include "ObjectManager.h" #include "PermissionsManager.h" #include "TupleCodec.h" @@ -18,13 +19,20 @@ // Helpers // --------------------------------------------------------------------------- +// Stores a tuple in the backend and updates the Relation object's Merkle root. static void store_tuple(nt::InMemoryBackend& backend, + nt::ObjectManager& objects, const std::vector<std::string>& path, std::vector<nt::Attribute> attrs) { auto bytes = nt::TupleCodec::Serialize(attrs); auto hash = backend.Put(std::move(bytes)); - backend.LinkTuple(path, hash); + + auto* entry = objects.Find(path); + if (!entry) return; + auto* rel = dynamic_cast<nt::ObjectManager::Relation*>(entry->object.get()); + if (!rel) return; + rel->merkle_root = nt::Merkle::Insert(backend, rel->merkle_root, hash); } static std::unique_ptr<nt::ObjectManager::object_type> make_relation_type() @@ -82,12 +90,13 @@ TEST_CASE("SCAN returns all tuples from a stored relation", "[scan]") const std::vector<std::string> path = { "relations", "villager" }; f.objects.Register(path, std::make_unique<nt::ObjectManager::Relation>(), make_relation_type()); - store_tuple(f.backend, path, { { "name", "John" }, { "age", "30" } }); - store_tuple(f.backend, path, { { "name", "Peter" }, { "age", "25" } }); + store_tuple(f.backend, f.objects, path, { { "name", "John" }, { "age", "30" } }); + store_tuple(f.backend, f.objects, path, { { "name", "Peter" }, { "age", "25" } }); auto* handle = f.handler.Open(path, &f.conn); REQUIRE(handle != nullptr); - auto* cursor = f.cursors.Open(handle); + auto* rel = dynamic_cast<nt::ObjectManager::Relation*>(f.objects.Find(path)->object.get()); + auto* cursor = f.cursors.Open(handle, rel->merkle_root); REQUIRE(cursor != nullptr); nt::PlanNode plan; @@ -115,9 +124,9 @@ TEST_CASE("JOIN filters a stored relation with eq ephemeral", "[join]") std::make_unique<nt::ObjectManager::Relation>(), make_relation_type()); - store_tuple(f.backend, people_path, { { "name", "John" }, { "age", "30" } }); - store_tuple(f.backend, people_path, { { "name", "Peter" }, { "age", "25" } }); - store_tuple(f.backend, people_path, { { "name", "Jude" }, { "age", "25" } }); + store_tuple(f.backend, f.objects, people_path, { { "name", "John" }, { "age", "30" } }); + store_tuple(f.backend, f.objects, people_path, { { "name", "Peter" }, { "age", "25" } }); + store_tuple(f.backend, f.objects, people_path, { { "name", "Jude" }, { "age", "25" } }); // Register ephemeral eq relation f.objects.Register(eq_path, @@ -130,9 +139,11 @@ TEST_CASE("JOIN filters a stored relation with eq ephemeral", "[join]") auto* eq_handle = f.handler.Open(eq_path, &f.conn); REQUIRE(eq_handle != nullptr); - auto* people_cursor = f.cursors.Open(people_handle); + auto* people_rel = dynamic_cast<nt::ObjectManager::Relation*>( + f.objects.Find(people_path)->object.get()); + auto* people_cursor = f.cursors.Open(people_handle, people_rel->merkle_root); REQUIRE(people_cursor != nullptr); - auto* eq_cursor = f.cursors.Open(eq_handle); // starts exhausted — JOIN resets it + auto* eq_cursor = f.cursors.Open(eq_handle); // EPHEMERAL: starts exhausted, JOIN resets REQUIRE(eq_cursor != nullptr); // Plan: JOIN( SCAN(people), SCAN(eq[ Var("age"), Const("25") ]) ) @@ -178,13 +189,14 @@ TEST_CASE("TAKE limits tuples emitted from a SCAN", "[take]") const std::vector<std::string> path = { "relations", "items" }; f.objects.Register(path, std::make_unique<nt::ObjectManager::Relation>(), make_relation_type()); - store_tuple(f.backend, path, { { "id", "1" } }); - store_tuple(f.backend, path, { { "id", "2" } }); - store_tuple(f.backend, path, { { "id", "3" } }); + store_tuple(f.backend, f.objects, path, { { "id", "1" } }); + store_tuple(f.backend, f.objects, path, { { "id", "2" } }); + store_tuple(f.backend, f.objects, path, { { "id", "3" } }); auto* handle = f.handler.Open(path, &f.conn); REQUIRE(handle != nullptr); - auto* cursor = f.cursors.Open(handle); + auto* rel = dynamic_cast<nt::ObjectManager::Relation*>(f.objects.Find(path)->object.get()); + auto* cursor = f.cursors.Open(handle, rel->merkle_root); REQUIRE(cursor != nullptr); nt::PlanNode scan; |