aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMarcos Magueta <maguetamarcos@gmail.com>2026-05-18 12:50:25 -0300
committerGitHub <noreply@github.com>2026-05-18 12:50:25 -0300
commitaf8759a9c1d965a3220024d1857aea219d62d898 (patch)
tree9cf14af855cac3674f508ec001bd04e262a524ae
parent0fc76b99abbff1d3cef8e2f9fcd56f3ae4f23a7a (diff)
downloadRNT-af8759a9c1d965a3220024d1857aea219d62d898.tar.gz
RNT-af8759a9c1d965a3220024d1857aea219d62d898.zip
Branching and object registry rework (#11)
-rw-r--r--CMakeLists.txt15
-rw-r--r--flake.nix9
-rw-r--r--include/CursorManager.h49
-rw-r--r--include/HandlerManager.h5
-rw-r--r--include/LifecycleManager.h75
-rw-r--r--include/Merkle.h162
-rw-r--r--include/MultigroupCodec.h89
-rw-r--r--include/NamespaceReferenceManager.h70
-rw-r--r--include/ObjectManager.h145
-rw-r--r--include/PermissionsManager.h11
-rw-r--r--include/RNT_C_API.h185
-rw-r--r--include/Types.h73
-rw-r--r--src/CursorManager.cpp68
-rw-r--r--src/HandlerManager.cpp8
-rw-r--r--src/LifecycleManager.cpp121
-rw-r--r--src/Merkle.cpp352
-rw-r--r--src/MultigroupCodec.cpp78
-rw-r--r--src/NamespaceReferenceManager.cpp127
-rw-r--r--src/ObjectManager.cpp15
-rw-r--r--src/RNT_C_API.cpp649
-rw-r--r--src/RelationalNT.cpp10
-rw-r--r--test/C_API.cpp442
-rw-r--r--test/CursorManager.cpp160
-rw-r--r--test/LifecycleManager.cpp185
-rw-r--r--test/MultigroupCodec.cpp145
-rw-r--r--test/NamespaceReferenceManager.cpp203
-rw-r--r--test/ObjectManager.cpp75
-rw-r--r--test/VM.cpp12
28 files changed, 3131 insertions, 407 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 127f1de..d4af6cb 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -26,6 +26,7 @@ add_executable (RelationalNT
"src/CursorManager.cpp"
"src/Merkle.cpp"
"src/TupleCodec.cpp"
+ "src/MultigroupCodec.cpp"
"src/InMemoryBackend.cpp"
"src/SqliteBackend.cpp"
"src/NamespaceReferenceManager.cpp"
@@ -53,6 +54,7 @@ set(RNT_CORE_SOURCES
"src/CursorManager.cpp"
"src/Merkle.cpp"
"src/TupleCodec.cpp"
+ "src/MultigroupCodec.cpp"
"src/InMemoryBackend.cpp"
"src/NamespaceReferenceManager.cpp"
"src/VM.cpp"
@@ -60,6 +62,11 @@ set(RNT_CORE_SOURCES
add_executable(RNT_tests
"test/VM.cpp"
+ "test/MultigroupCodec.cpp"
+ "test/ObjectManager.cpp"
+ "test/NamespaceReferenceManager.cpp"
+ "test/LifecycleManager.cpp"
+ "test/CursorManager.cpp"
${RNT_CORE_SOURCES}
)
target_include_directories(RNT_tests PRIVATE "include")
@@ -81,3 +88,11 @@ 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)
+
+add_executable(RNT_capi_tests
+ "test/C_API.cpp"
+)
+target_include_directories(RNT_capi_tests PRIVATE "include")
+target_link_libraries(RNT_capi_tests PRIVATE RNT Catch2::Catch2WithMain)
+set_property(TARGET RNT_capi_tests PROPERTY CXX_STANDARD 20)
+catch_discover_tests(RNT_capi_tests DISCOVERY_MODE PRE_TEST)
diff --git a/flake.nix b/flake.nix
index 2850520..c45c800 100644
--- a/flake.nix
+++ b/flake.nix
@@ -106,14 +106,6 @@
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 {
@@ -123,7 +115,6 @@
pkgs.cmake
pkgs.lldb
pkgs.ninja
- clangdRnt
picosha2Headers
pkgs.sqlite
unofficialSqlite3Config
diff --git a/include/CursorManager.h b/include/CursorManager.h
index 839bf5e..c2606c3 100644
--- a/include/CursorManager.h
+++ b/include/CursorManager.h
@@ -3,6 +3,8 @@
#include "Api.h"
#include "HandlerManager.h"
#include "IStorageBackend.h"
+#include "LifecycleManager.h"
+#include "ObjectManager.h"
#include "Types.h"
#include <cstddef>
@@ -37,8 +39,19 @@ namespace nt
public:
static constexpr std::size_t PAGE_SIZE = 1;
- /** @brief Constructs a CursorManager that reads from the given backend. */
- explicit CursorManager(IStorageBackend& backend);
+ /**
+ * @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.
@@ -53,9 +66,15 @@ namespace nt
* 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 {
- HandlerManager::handle* handle = nullptr;
/**
* Hex hash of the relation's Merkle B-tree root node.
* Empty string means the relation contains no tuples.
@@ -71,6 +90,26 @@ namespace nt
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;
};
/**
@@ -103,7 +142,9 @@ namespace nt
void Close(cursor* cursor);
private:
- IStorageBackend& backend_;
+ IStorageBackend& backend_;
+ LifecycleManager* lifecycles_ = nullptr;
+ ObjectManager* objects_ = nullptr;
/**
* Fetches a page of hashes via Merkle::Page, resolves each from the
diff --git a/include/HandlerManager.h b/include/HandlerManager.h
index f3d504e..06ed362 100644
--- a/include/HandlerManager.h
+++ b/include/HandlerManager.h
@@ -17,6 +17,7 @@ namespace nt
{
class IdentityManager;
class LifecycleManager;
+ class NamespaceReferenceManager;
class PermissionsManager;
/** @brief Opens and closes authorized handles to registry objects. */
@@ -33,7 +34,8 @@ namespace nt
HandlerManager(ObjectManager& objects,
PermissionsManager& permissions,
IdentityManager& identities,
- LifecycleManager& lifecycles);
+ LifecycleManager& lifecycles,
+ NamespaceReferenceManager& references);
/**
* @brief Represents authorized access to an object in the registry.
@@ -93,5 +95,6 @@ namespace nt
PermissionsManager& permissions_;
IdentityManager& identities_;
LifecycleManager& lifecycles_;
+ NamespaceReferenceManager& references_;
};
}
diff --git a/include/LifecycleManager.h b/include/LifecycleManager.h
index 8126820..5508bc6 100644
--- a/include/LifecycleManager.h
+++ b/include/LifecycleManager.h
@@ -1,6 +1,7 @@
#pragma once
#include "Api.h"
+#include "IStorageBackend.h"
#include "ObjectManager.h"
/**
@@ -15,9 +16,9 @@ namespace nt
*
* 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 views
- * referencing base relations). An object is eligible for GC only when both
- * reach zero.
+ * (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.
@@ -26,6 +27,18 @@ namespace nt
{
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
@@ -53,9 +66,9 @@ namespace nt
* @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 a view is
- * registered against its base relations. Prevents GC of the target object
- * while the dependency is live.
+ * 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.
*
@@ -76,6 +89,15 @@ namespace nt
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,
@@ -97,5 +119,46 @@ namespace nt
* @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_;
};
}
diff --git a/include/Merkle.h b/include/Merkle.h
index 8380093..ba8018a 100644
--- a/include/Merkle.h
+++ b/include/Merkle.h
@@ -5,105 +5,143 @@
#include <array>
#include <cstddef>
#include <cstdint>
+#include <optional>
#include <string>
#include <vector>
/**
* @file Merkle.h
- * @brief Sorted content-addressed B-tree over SHA-256 tuple hash hex strings.
+ * @brief Generic sorted content-addressed B-tree over a templated key type.
*
- * 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.
+ * 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.
*
- * **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).
+ * 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 and Remove produce new nodes only along the modified path; old nodes
+ * Insert / 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 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_hash` (smallest tuple hash in the subtree) is the routing key.
+ * - `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.
- * - 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.
+ * - Leaf entries are sorted ascending by key.
+ * - Internal entries are sorted ascending by min_key.
*
- * @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.
+ * **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 a tuple hash into the tree.
- * @param store KV backend for node serialization.
+ * @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 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.
+ * @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 std::string& hash_hex);
+ const std::string& root_hex,
+ const Key& key,
+ const Hash32& payload);
/**
- * @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.
+ * @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 std::string& hash_hex);
+ 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 tuple hashes in sorted order.
+ * @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 hashes. Only the nodes on the active path are loaded;
+ * most @p limit entries. 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);
+ static std::vector<Entry> Page(IStorageBackend& store,
+ const std::string& root_hex,
+ size_t offset,
+ size_t limit);
private:
- using Hash32 = std::array<uint8_t, 32>;
+ struct LeafEntry {
+ Key key;
+ Hash32 payload;
+ };
struct LeafNode {
- std::vector<Hash32> hashes; // sorted ascending, len ≤ B
+ std::vector<LeafEntry> entries;
};
- // 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
+ uint64_t leaf_count;
+ Key min_key;
+ Hash32 child_hash;
};
struct InternalNode {
- std::vector<ChildEntry> entries; // sorted by min_hash, len ≤ B
+ std::vector<ChildEntry> entries;
};
// Wire format
@@ -113,34 +151,32 @@ private:
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);
+ /** @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);
- // 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 = {};
+ Key split_min_key{};
std::string split_hash;
};
static InsertResult insert_into(IStorageBackend& store,
const std::string& node_hex,
- const Hash32& tuple_hash);
+ const Key& key,
+ const Hash32& payload);
- // Recursive remove result: new node hash (empty = node gone), leaf count.
struct RemoveResult {
std::string new_hash;
uint64_t leaf_count = 0;
@@ -148,17 +184,17 @@ private:
static RemoveResult remove_from(IStorageBackend& store,
const std::string& node_hex,
- const Hash32& tuple_hash);
+ const Key& key);
- // 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);
+ std::vector<Entry>& out);
- // Find which child to route into (rightmost whose min_hash ≤ target).
- static size_t route(const InternalNode& node, const Hash32& target);
+ 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
new file mode 100644
index 0000000..50f7bb8
--- /dev/null
+++ b/include/MultigroupCodec.h
@@ -0,0 +1,89 @@
+#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);
+}
diff --git a/include/NamespaceReferenceManager.h b/include/NamespaceReferenceManager.h
index 0bf00bc..dd91297 100644
--- a/include/NamespaceReferenceManager.h
+++ b/include/NamespaceReferenceManager.h
@@ -1,6 +1,11 @@
#pragma once
#include "Api.h"
+#include "IStorageBackend.h"
+#include "ObjectManager.h"
+
+#include <string>
+#include <vector>
/**
* @file NamespaceReferenceManager.h
@@ -16,8 +21,9 @@ namespace nt
* 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 views to appear as first-class objects
- * in the namespace without exposing their physical storage paths directly.
+ * 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
@@ -27,13 +33,15 @@ namespace nt
* object itself with WRITE access, which is the sole contention point for that
* branch.
*
- * **View resolution.**
- * A view is an ephemeral RELATION whose ParseProcedure reparses to its base
- * relations internally on behalf of the runtime. The caller's handle and access
- * mask remain bound to the view. The base relations are accessed only via the
- * view'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 view boundary, not the base relation boundary.
+ * **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
@@ -43,9 +51,10 @@ namespace nt
* the batch is aborted. This preserves audit consistency.
*
* **Cycle guard.**
- * View definitions may reference other views, 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.
+ * 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
@@ -60,5 +69,42 @@ namespace nt
*/
class NT_API 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_;
};
}
diff --git a/include/ObjectManager.h b/include/ObjectManager.h
index e30ff1b..7531079 100644
--- a/include/ObjectManager.h
+++ b/include/ObjectManager.h
@@ -5,6 +5,7 @@
#include <cstdint>
#include <functional>
+#include <map>
#include <memory>
#include <set>
#include <string>
@@ -33,8 +34,27 @@ namespace nt
virtual ~IObject() = default;
};
- /** @brief Abstract registry object representing a multigroup. */
- class Multigroup : public IObject {};
+ /**
+ * @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.
*
@@ -46,21 +66,107 @@ namespace nt
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 A named mutable reference to a multigroup state.
+ * @brief Registry object representing an active connection's session.
*
- * 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.
+ * `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::vector<uint8_t> payload;
+ 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;
};
/**
@@ -145,8 +251,9 @@ namespace nt
*
* - `handle_count` — open sessions holding a cursor or handle on this object.
* Managed exclusively by LifecycleManager::Monitor / Unmonitor.
- * - `reference_count` — structural dependencies such as a view referencing its
- * base relations, or a cursor pinned to an immutable snapshot version.
+ * - `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
@@ -166,8 +273,8 @@ namespace nt
struct registry_head {
/**
* Structural dependency count. Non-zero while another registry object
- * references this one (e.g. a view depending on a base relation, or a
- * cursor pinned to a snapshot version).
+ * 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;
@@ -216,5 +323,19 @@ namespace nt
* @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);
};
}
diff --git a/include/PermissionsManager.h b/include/PermissionsManager.h
index 2db1784..6718f9f 100644
--- a/include/PermissionsManager.h
+++ b/include/PermissionsManager.h
@@ -58,10 +58,10 @@ namespace nt
* 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 a view (ephemeral relation) is created based on
- * 3 other stored relations, while you can access the view, you cannot directly
- * access the other 3 relations. You need explicit permission to create a handle
- * on the others.
+ * 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
@@ -79,7 +79,8 @@ namespace nt
* /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`.
+ * 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.
diff --git a/include/RNT_C_API.h b/include/RNT_C_API.h
index ddf6a97..e6455ba 100644
--- a/include/RNT_C_API.h
+++ b/include/RNT_C_API.h
@@ -46,15 +46,15 @@ typedef void* rnt_handle_t;
typedef void* rnt_cursor_t;
/* ------------------------------------------------------------------ */
-/* Runtime lifecycle */
+/* Runtime lifecycle */
/* ------------------------------------------------------------------ */
/**
- * @brief Initialises the RNT runtime with the selected storage backend.
+ * @brief Initializes 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
+ * 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".
@@ -83,6 +83,59 @@ int rnt_init(const char* driver, const char* storage_path);
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.
+ */
+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.
+ */
+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.
+ */
+int rnt_session_set_branch(const char* session_hash,
+ const char* branch_name,
+ const char* target_hash);
+
+/* ------------------------------------------------------------------ */
/* Handle lifecycle */
/* ------------------------------------------------------------------ */
@@ -107,41 +160,41 @@ rnt_handle_t rnt_open_handle(const char* path, const char* claims);
int rnt_close_handle(rnt_handle_t handle);
/**
- * @brief Reads the raw payload bytes stored in a BRANCH object.
+ * @brief Reads the current branch-tree root hash from 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).
+ * 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 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.
+ * @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.
*/
-int rnt_branch_payload(rnt_handle_t handle,
- uint8_t** payload_out,
- size_t* len_out);
+int rnt_branch_target(rnt_handle_t handle, char** target_hash_out);
/**
- * @brief Writes new payload bytes into the BRANCH object referenced by handle.
+ * @brief Atomically advances a branch to point at a new branch-tree root.
*
- * Updates the in-memory branch object. Callers are responsible for persisting
- * the multigroup state to the storage backend separately via tuple link
- * operations.
+ * 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 handle Open BRANCH handle.
- * @param payload New serialized multigroup bytes.
- * @param len Number of bytes in payload.
- * @return 0 on success, negative on error.
+ * @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.
*/
-int rnt_branch_set_payload(rnt_handle_t handle,
- const uint8_t* payload,
- size_t len);
+int rnt_branch_advance(const char* branch_path, const char* new_hash);
/* ------------------------------------------------------------------ */
/* Object registration */
@@ -153,24 +206,71 @@ int rnt_branch_set_payload(rnt_handle_t handle,
* 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".
+ * @param path Slash-separated path of the form
+ * "/system/branches/<branch>/multigroups/<mg>/relations/<rel>".
* @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.
+ * @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.
- *
- * @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.
+ * 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.
*/
-int rnt_register_branch(const char* path,
- const uint8_t* payload,
- size_t payload_len);
+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.
+ */
+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.
+ */
+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.
+ */
+int rnt_list_snapshot_relations(const char* snapshot_hash, char** out);
/* ------------------------------------------------------------------ */
/* Tuple storage */
@@ -235,21 +335,6 @@ int rnt_clear_relation(const char* relation_path);
*/
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 */
/* ------------------------------------------------------------------ */
@@ -300,7 +385,7 @@ typedef void* rnt_plan_t;
* 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".
+ * "/system/branches/main/multigroups/warehouse/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);
diff --git a/include/Types.h b/include/Types.h
index f7eadff..edf4297 100644
--- a/include/Types.h
+++ b/include/Types.h
@@ -20,37 +20,74 @@ enum OBJECT_TYPE {
TRANSACTION,
/**
* A relation whose tuples are produced on demand by a generator function
- * rather than read from physical storage. Cardinality may be finite (e.g.
- * a projected stored relation) or AlephZero (e.g. the eq builtin). The
- * object_type for this label must be an ephemeral_object_type.
+ * 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 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.
+ * 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 the payload bytes to
- * reconstruct the multigroup in memory, and holds the handle for the
- * duration of the session.
+ * 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 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.
+ * 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>`.
*
- * @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.
+ * 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.
*/
- VIEW
+ BRANCH_TREE
};
/** @brief Operations that may be supported by an object type. */
diff --git a/src/CursorManager.cpp b/src/CursorManager.cpp
index 219ba2e..d96909b 100644
--- a/src/CursorManager.cpp
+++ b/src/CursorManager.cpp
@@ -5,25 +5,49 @@
namespace nt
{
- CursorManager::CursorManager(IStorageBackend& backend)
+ CursorManager::CursorManager(IStorageBackend& backend,
+ LifecycleManager* lifecycles,
+ ObjectManager* objects)
: backend_(backend)
+ , lifecycles_(lifecycles)
+ , objects_(objects)
{}
+ // Finds the /system/snapshots/<H> entry that owns a handle's relation, or
+ // nullptr when the relation lives outside the snapshot namespace (tests use
+ // synthetic paths like {"relations", "villager"}).
+ static ObjectManager::registry* find_parent_snapshot(
+ ObjectManager& objects,
+ HandlerManager::handle* handle)
+ {
+ if (handle == nullptr || handle->object == nullptr
+ || handle->object->head == nullptr)
+ return nullptr;
+
+ const auto& p = handle->object->head->path;
+ if (p.size() != 5) return nullptr;
+ if (p[0] != "system" || p[1] != "snapshots" || p[3] != "relations")
+ return nullptr;
+
+ return objects.Find({ p[0], p[1], p[2] });
+ }
+
void CursorManager::LoadPage(cursor* c)
{
- auto hashes = Merkle::Page(backend_, c->merkle_root, c->fetch_offset, PAGE_SIZE);
+ auto entries = Merkle<Hash32>::Page(backend_, c->merkle_root,
+ c->fetch_offset, PAGE_SIZE);
c->page.clear();
c->page_position = 0;
- for (const auto& hash : hashes)
+ for (const auto& entry : entries)
{
- auto bytes = backend_.Get(hash);
+ auto bytes = backend_.Get(bin_to_hex(entry.payload));
if (!bytes) continue;
c->page.emplace_back(TupleCodec::Deserialize(*bytes));
}
- c->fetch_offset += hashes.size();
- if (hashes.size() < PAGE_SIZE)
+ c->fetch_offset += entries.size();
+ if (entries.size() < PAGE_SIZE)
c->exhausted = true;
}
@@ -35,13 +59,28 @@ namespace nt
const auto label = handle->object->head->type->label;
+ auto pin_snapshot = [&](cursor* c) {
+ if (lifecycles_ == nullptr || objects_ == nullptr) return;
+ auto* snap = find_parent_snapshot(*objects_, handle);
+ if (snap == nullptr) return;
+ lifecycles_->Pin(snap);
+ c->pinned_snapshot = snap;
+ };
+
if (label == EPHEMERAL_RELATION)
{
// Cursor is created exhausted — the JOIN operator writes args and
- // resets the state before the first probe.
+ // resets the state before the first probe. The generator is copied
+ // off the registry-owned ephemeral_object_type so Next() never has
+ // to dereference the handle again.
+ auto* etype = static_cast<ObjectManager::ephemeral_object_type*>(
+ handle->object->head->type.get());
+
auto* c = new cursor();
- c->handle = handle;
- c->exhausted = true;
+ c->is_ephemeral = true;
+ c->generator = etype->generator;
+ c->exhausted = true;
+ pin_snapshot(c);
return c;
}
@@ -49,8 +88,8 @@ namespace nt
return nullptr;
auto* c = new cursor();
- c->handle = handle;
c->merkle_root = merkle_root;
+ pin_snapshot(c);
if (merkle_root.empty())
{
@@ -72,11 +111,9 @@ namespace nt
if (c->exhausted) return nullptr;
- if (c->handle->object->head->type->label == EPHEMERAL_RELATION)
+ if (c->is_ephemeral)
{
- auto* etype = static_cast<ObjectManager::ephemeral_object_type*>(
- c->handle->object->head->type.get());
- c->page = etype->generator(c->args, c->fetch_offset, PAGE_SIZE);
+ c->page = c->generator(c->args, c->fetch_offset, PAGE_SIZE);
c->page_position = 0;
c->fetch_offset += c->page.size();
if (c->page.size() < PAGE_SIZE)
@@ -92,6 +129,9 @@ namespace nt
void CursorManager::Close(cursor* c)
{
+ if (c == nullptr) { return; }
+ if (lifecycles_ != nullptr && c->pinned_snapshot != nullptr)
+ lifecycles_->Unpin(c->pinned_snapshot);
delete c;
}
}
diff --git a/src/HandlerManager.cpp b/src/HandlerManager.cpp
index 8149ff2..cb3b723 100644
--- a/src/HandlerManager.cpp
+++ b/src/HandlerManager.cpp
@@ -2,6 +2,7 @@
#include "IdentityManager.h"
#include "LifecycleManager.h"
+#include "NamespaceReferenceManager.h"
#include "PermissionsManager.h"
namespace nt
@@ -14,16 +15,19 @@ namespace nt
HandlerManager::HandlerManager(ObjectManager& objects,
PermissionsManager& permissions,
IdentityManager& identities,
- LifecycleManager& lifecycles)
+ LifecycleManager& lifecycles,
+ NamespaceReferenceManager& references)
: objects_(objects)
, permissions_(permissions)
, identities_(identities)
, lifecycles_(lifecycles)
+ , references_(references)
{}
struct HandlerManager::handle* HandlerManager::Open(std::vector<std::string> object_path, void* connection_context)
{
- ObjectManager::registry* retrieved_object = objects_.Find((const std::vector<std::string>)object_path);
+ const auto resolved = references_.Resolve(std::move(object_path));
+ ObjectManager::registry* retrieved_object = objects_.Find(resolved);
if (permissions_.Access(retrieved_object, (const void*)connection_context)
&& identities_.CanOpen(retrieved_object)
&& lifecycles_.Contention(retrieved_object)) {
diff --git a/src/LifecycleManager.cpp b/src/LifecycleManager.cpp
index a83c9e1..78e112d 100644
--- a/src/LifecycleManager.cpp
+++ b/src/LifecycleManager.cpp
@@ -1,21 +1,136 @@
#include "LifecycleManager.h"
+#include "Merkle.h"
+#include "Types.h"
+
+#include <vector>
+
namespace nt
{
+ LifecycleManager::LifecycleManager(ObjectManager& objects,
+ IStorageBackend& storage)
+ : objects_(objects), storage_(storage)
+ {}
+
void LifecycleManager::Monitor(ObjectManager::registry* object)
{
if (object != nullptr)
++object->head->handle_count;
}
+ void LifecycleManager::Unmonitor(ObjectManager::registry* object)
+ {
+ if (object == nullptr || object->head->handle_count == 0) return;
+ --object->head->handle_count;
+ TryCollect(object);
+ }
+
+ void LifecycleManager::Pin(ObjectManager::registry* object)
+ {
+ if (object != nullptr)
+ ++object->head->reference_count;
+ }
+
+ void LifecycleManager::Unpin(ObjectManager::registry* object)
+ {
+ if (object == nullptr || object->head->reference_count == 0) return;
+ --object->head->reference_count;
+ TryCollect(object);
+ }
+
+ bool LifecycleManager::IsEligibleForGC(ObjectManager::registry* object) const
+ {
+ if (object == nullptr || object->head == nullptr) return false;
+ return object->head->handle_count == 0
+ && object->head->reference_count == 0;
+ }
+
const bool LifecycleManager::Contention(ObjectManager::registry* object)
{
return object != nullptr;
}
- void LifecycleManager::Unmonitor(ObjectManager::registry* object)
+ void LifecycleManager::TryCollect(ObjectManager::registry* object)
{
- if (object != nullptr && object->head->handle_count > 0)
- --object->head->handle_count;
+ if (!IsEligibleForGC(object)) return;
+ if (object->head == nullptr || object->head->type == nullptr) return;
+
+ // Named-lifetime types are managed explicitly and must not auto-collect:
+ // BRANCH — named branches persist until a future explicit-delete API
+ // tears them down. Their counters going to zero just means
+ // nobody currently holds them open.
+ // SESSION — rnt_session_close is the sole removal path.
+ // Everything else (MULTIGROUP, BRANCH_TREE, RELATION,
+ // EPHEMERAL_RELATION, TRANSACTION) is purely structurally referenced
+ // and is GC-eligible by counters alone.
+ const auto label = object->head->type->label;
+ if (label == BRANCH || label == SESSION) return;
+
+ if (label == MULTIGROUP) CascadeMultigroup(object);
+ if (label == BRANCH_TREE) CascadeBranchTree(object);
+
+ objects_.Unregister(object->head->path);
+ }
+
+ void LifecycleManager::CascadeMultigroup(ObjectManager::registry* multigroup)
+ {
+ if (multigroup == nullptr || multigroup->head == nullptr) return;
+ const auto& mg_path = multigroup->head->path;
+ if (mg_path.size() < 3) return;
+
+ // /system/snapshots/<hash>/relations/<n> entries are the relation
+ // children pinned by this multigroup. Collect first, mutate after —
+ // Unpin can Unregister the entry we're standing on if its counters
+ // were already zero, and iteration must outlive that mutation.
+ std::vector<ObjectManager::registry*> children;
+ for (auto* cur = objects_.entries.get(); cur != nullptr; cur = cur->next.get())
+ {
+ const auto& p = cur->head->path;
+ if (p.size() != mg_path.size() + 2) continue;
+
+ bool prefix_match = true;
+ for (size_t i = 0; i < mg_path.size(); ++i)
+ if (p[i] != mg_path[i]) { prefix_match = false; break; }
+ if (!prefix_match) continue;
+ if (p[mg_path.size()] != "relations") continue;
+
+ children.push_back(cur);
+ }
+
+ for (auto* child : children) Unpin(child);
+ }
+
+ void LifecycleManager::CascadeBranchTree(ObjectManager::registry* branch_tree)
+ {
+ if (branch_tree == nullptr || branch_tree->head == nullptr) return;
+
+ auto* bt = dynamic_cast<ObjectManager::BranchTree*>(branch_tree->object.get());
+ if (bt == nullptr || bt->merkle_root.empty()) return;
+
+ // Page through the (mg_name, mg_hash) tree and collect each referenced
+ // multigroup before unpinning. Decoupling iteration from mutation
+ // keeps us safe against Unpin cascading further GC under our feet.
+ std::vector<ObjectManager::registry*> mgs;
+ constexpr size_t kPageSize = 1024;
+ size_t offset = 0;
+ while (true)
+ {
+ auto page = Merkle<std::string>::Page(storage_, bt->merkle_root,
+ offset, kPageSize);
+ if (page.empty()) break;
+ for (const auto& entry : page)
+ {
+ static const Hash32 zero{};
+ if (entry.payload == zero) continue;
+ const std::string mg_hash = bin_to_hex(entry.payload);
+ auto* mg_entry = objects_.Find(
+ {"system", "snapshots", mg_hash});
+ if (mg_entry) mgs.push_back(mg_entry);
+ }
+ if (page.size() < kPageSize) break;
+ offset += page.size();
+ }
+
+ for (auto* mg : mgs) Unpin(mg);
}
}
diff --git a/src/Merkle.cpp b/src/Merkle.cpp
index 56ab349..760cfce 100644
--- a/src/Merkle.cpp
+++ b/src/Merkle.cpp
@@ -3,7 +3,6 @@
#include <algorithm>
#include <cassert>
#include <cstring>
-#include <numeric>
#include <stdexcept>
namespace nt {
@@ -49,9 +48,9 @@ static uint64_t read_u64(const uint8_t* p)
| (uint64_t(p[6]) << 8) | uint64_t(p[7]);
}
-// ── Hex / binary conversion ──────────────────────────────────────────────────
+// ── Hex / binary conversion (free, key-agnostic) ─────────────────────────────
-Merkle::Hash32 Merkle::hex_to_bin(const std::string& hex)
+Hash32 hex_to_bin(const std::string& hex)
{
if (hex.size() != 64)
throw std::invalid_argument(
@@ -70,7 +69,7 @@ Merkle::Hash32 Merkle::hex_to_bin(const std::string& hex)
return out;
}
-std::string Merkle::bin_to_hex(const Hash32& bin)
+std::string bin_to_hex(const Hash32& bin)
{
static const char HEX[] = "0123456789abcdef";
std::string out(64, '0');
@@ -82,76 +81,136 @@ std::string Merkle::bin_to_hex(const Hash32& bin)
return out;
}
+// ── Key codec: per-Key serialisation primitives ──────────────────────────────
+
+namespace {
+
+template<typename Key>
+struct KeyCodec; // primary template intentionally undefined
+
+template<>
+struct KeyCodec<Hash32> {
+ static void write(std::vector<uint8_t>& buf, const Hash32& k) {
+ buf.insert(buf.end(), k.begin(), k.end());
+ }
+ // Returns key and advances *p_inout by the number of consumed bytes.
+ static Hash32 read(const uint8_t*& p) {
+ Hash32 k;
+ std::memcpy(k.data(), p, 32);
+ p += 32;
+ return k;
+ }
+ static size_t encoded_size(const Hash32&) { return 32; }
+};
+
+template<>
+struct KeyCodec<std::string> {
+ static void write(std::vector<uint8_t>& buf, const std::string& k) {
+ write_u32(buf, static_cast<uint32_t>(k.size()));
+ buf.insert(buf.end(), k.begin(), k.end());
+ }
+ static std::string read(const uint8_t*& p) {
+ uint32_t len = read_u32(p);
+ p += 4;
+ std::string k(reinterpret_cast<const char*>(p), len);
+ p += len;
+ return k;
+ }
+ static size_t encoded_size(const std::string& k) { return 4 + k.size(); }
+};
+
+} // anonymous namespace
+
// ── Node serialisation ───────────────────────────────────────────────────────
-std::vector<uint8_t> Merkle::encode_leaf(const LeafNode& n)
+template<typename Key>
+std::vector<uint8_t> Merkle<Key>::encode_leaf(const LeafNode& n)
{
std::vector<uint8_t> buf;
- buf.reserve(1 + 4 + n.hashes.size() * 32);
+ size_t payload_size = 0;
+ for (const auto& e : n.entries)
+ payload_size += KeyCodec<Key>::encoded_size(e.key) + 32;
+ buf.reserve(1 + 4 + payload_size);
+
buf.push_back(TAG_LEAF);
- write_u32(buf, static_cast<uint32_t>(n.hashes.size()));
- for (const auto& h : n.hashes)
- buf.insert(buf.end(), h.begin(), h.end());
+ write_u32(buf, static_cast<uint32_t>(n.entries.size()));
+ for (const auto& e : n.entries)
+ {
+ KeyCodec<Key>::write(buf, e.key);
+ buf.insert(buf.end(), e.payload.begin(), e.payload.end());
+ }
return buf;
}
-std::vector<uint8_t> Merkle::encode_internal(const InternalNode& n)
+template<typename Key>
+std::vector<uint8_t> Merkle<Key>::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);
+ size_t payload_size = 0;
+ for (const auto& e : n.entries)
+ payload_size += 8 + KeyCodec<Key>::encoded_size(e.min_key) + 32;
+ buf.reserve(1 + 4 + payload_size);
+
buf.push_back(TAG_INTERNAL);
write_u32(buf, static_cast<uint32_t>(n.entries.size()));
for (const auto& e : n.entries)
{
write_u64(buf, e.leaf_count);
- buf.insert(buf.end(), e.min_hash.begin(), e.min_hash.end());
+ KeyCodec<Key>::write(buf, e.min_key);
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)
+template<typename Key>
+typename Merkle<Key>::LeafNode Merkle<Key>::decode_leaf(const std::vector<uint8_t>& bytes)
{
uint32_t count = read_u32(bytes.data() + 1);
LeafNode n;
- n.hashes.reserve(count);
+ n.entries.reserve(count);
const uint8_t* p = bytes.data() + 5;
- for (uint32_t i = 0; i < count; ++i, p += 32)
+ for (uint32_t i = 0; i < count; ++i)
{
- Hash32 h;
- std::memcpy(h.data(), p, 32);
- n.hashes.push_back(h);
+ LeafEntry e;
+ e.key = KeyCodec<Key>::read(p);
+ std::memcpy(e.payload.data(), p, 32);
+ p += 32;
+ n.entries.push_back(std::move(e));
}
return n;
}
-Merkle::InternalNode Merkle::decode_internal(const std::vector<uint8_t>& bytes)
+template<typename Key>
+typename Merkle<Key>::InternalNode Merkle<Key>::decode_internal(const std::vector<uint8_t>& bytes)
{
uint32_t count = read_u32(bytes.data() + 1);
InternalNode n;
n.entries.reserve(count);
const uint8_t* p = bytes.data() + 5;
- for (uint32_t i = 0; i < count; ++i, p += 72)
+ for (uint32_t i = 0; i < count; ++i)
{
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);
+ p += 8;
+ e.min_key = KeyCodec<Key>::read(p);
+ std::memcpy(e.child_hash.data(), p, 32);
+ p += 32;
+ n.entries.push_back(std::move(e));
}
return n;
}
-bool Merkle::is_leaf_bytes(const std::vector<uint8_t>& bytes)
+template<typename Key>
+bool Merkle<Key>::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)
+template<typename Key>
+std::vector<uint8_t> Merkle<Key>::load_node(IStorageBackend& store,
+ const std::string& hash_hex)
{
auto opt = store.Get(hash_hex);
if (!opt)
@@ -159,46 +218,50 @@ std::vector<uint8_t> Merkle::load_node(IStorageBackend& store,
return std::move(*opt);
}
-std::string Merkle::store_leaf(IStorageBackend& store, const LeafNode& n)
+template<typename Key>
+std::string Merkle<Key>::store_leaf(IStorageBackend& store, const LeafNode& n)
{
return store.Put(encode_leaf(n));
}
-std::string Merkle::store_internal(IStorageBackend& store, const InternalNode& n)
+template<typename Key>
+std::string Merkle<Key>::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)
+template<typename Key>
+Key Merkle<Key>::subtree_min_key(IStorageBackend& store, const std::string& node_hex)
{
auto bytes = load_node(store, node_hex);
if (is_leaf_bytes(bytes))
{
auto leaf = decode_leaf(bytes);
- assert(!leaf.hashes.empty() && "Merkle invariant: leaf node must never be empty");
- return leaf.hashes.front();
+ assert(!leaf.entries.empty() && "Merkle invariant: leaf node must never be empty");
+ return leaf.entries.front().key;
}
auto node = decode_internal(bytes);
assert(!node.entries.empty() && "Merkle invariant: internal node must never be empty");
- return node.entries.front().min_hash;
+ return node.entries.front().min_key;
}
// ── Routing helper ───────────────────────────────────────────────────────────
-size_t Merkle::route(const InternalNode& node, const Hash32& target)
+template<typename Key>
+size_t Merkle<Key>::route(const InternalNode& node, const Key& target)
{
assert(!node.entries.empty() && "Merkle invariant: internal node must never be empty");
assert(std::is_sorted(node.entries.begin(), node.entries.end(),
[](const ChildEntry& a, const ChildEntry& b) {
- return a.min_hash < b.min_hash;
- }) && "Merkle invariant: internal node entries must be sorted by min_hash");
+ return a.min_key < b.min_key;
+ }) && "Merkle invariant: internal node entries must be sorted by min_key");
- // Rightmost child whose min_hash ≤ target.
- // Defaults to 0 (leftmost) when target < all min_hashes.
+ // Rightmost child whose min_key ≤ target.
+ // Defaults to 0 (leftmost) when target < all min_keys.
size_t idx = 0;
for (size_t i = 1; i < node.entries.size(); ++i)
{
- if (node.entries[i].min_hash <= target)
+ if (!(target < node.entries[i].min_key))
idx = i;
else
break;
@@ -208,47 +271,48 @@ size_t Merkle::route(const InternalNode& node, const Hash32& target)
// ── Insert ───────────────────────────────────────────────────────────────────
-std::string Merkle::Insert(IStorageBackend& store,
- const std::string& root_hex,
- const std::string& hash_hex)
+template<typename Key>
+std::string Merkle<Key>::Insert(IStorageBackend& store,
+ const std::string& root_hex,
+ const Key& key,
+ const Hash32& payload)
{
- const Hash32 tuple_hash = hex_to_bin(hash_hex);
-
if (root_hex.empty())
{
LeafNode leaf;
- leaf.hashes.push_back(tuple_hash);
+ leaf.entries.push_back({ key, payload });
return store_leaf(store, leaf);
}
- auto result = insert_into(store, root_hex, tuple_hash);
+ auto result = insert_into(store, root_hex, key, payload);
if (!result.did_split)
return result.new_hash;
// Root split: wrap both halves in a new internal root.
- Hash32 left_min = subtree_min(store, result.new_hash);
- Hash32 right_min = result.split_min_hash;
+ Key left_min = subtree_min_key(store, result.new_hash);
InternalNode new_root;
ChildEntry left;
left.leaf_count = result.leaf_count;
- left.min_hash = left_min;
+ left.min_key = left_min;
left.child_hash = hex_to_bin(result.new_hash);
- new_root.entries.push_back(left);
+ new_root.entries.push_back(std::move(left));
ChildEntry right;
right.leaf_count = result.split_leaf_count;
- right.min_hash = right_min;
+ right.min_key = result.split_min_key;
right.child_hash = hex_to_bin(result.split_hash);
- new_root.entries.push_back(right);
+ new_root.entries.push_back(std::move(right));
return store_internal(store, new_root);
}
-Merkle::InsertResult Merkle::insert_into(IStorageBackend& store,
- const std::string& node_hex,
- const Hash32& tuple_hash)
+template<typename Key>
+typename Merkle<Key>::InsertResult Merkle<Key>::insert_into(IStorageBackend& store,
+ const std::string& node_hex,
+ const Key& key,
+ const Hash32& payload)
{
auto bytes = load_node(store, node_hex);
@@ -257,38 +321,51 @@ Merkle::InsertResult Merkle::insert_into(IStorageBackend& store,
{
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)
+ auto pos = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key,
+ [](const LeafEntry& e, const Key& k) {
+ return e.key < k;
+ });
+ if (pos != leaf.entries.end() && !(key < pos->key))
{
- // Already present — no-op.
+ // Key already present — update payload if it changed, else no-op.
+ if (pos->payload == payload)
+ {
+ InsertResult r;
+ r.new_hash = node_hex;
+ r.leaf_count = leaf.entries.size();
+ return r;
+ }
+ pos->payload = payload;
InsertResult r;
- r.new_hash = node_hex;
- r.leaf_count = leaf.hashes.size();
+ r.new_hash = store_leaf(store, leaf);
+ r.leaf_count = leaf.entries.size();
return r;
}
- leaf.hashes.insert(pos, tuple_hash);
+ leaf.entries.insert(pos, LeafEntry{ key, payload });
- if (leaf.hashes.size() <= B)
+ if (leaf.entries.size() <= B)
{
InsertResult r;
r.new_hash = store_leaf(store, leaf);
- r.leaf_count = leaf.hashes.size();
+ r.leaf_count = leaf.entries.size();
return r;
}
// Split leaf at midpoint.
- size_t mid = leaf.hashes.size() / 2;
+ size_t mid = leaf.entries.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() };
+ left_leaf.entries = { leaf.entries.begin(),
+ leaf.entries.begin() + static_cast<ptrdiff_t>(mid) };
+ right_leaf.entries = { leaf.entries.begin() + static_cast<ptrdiff_t>(mid),
+ leaf.entries.end() };
InsertResult r;
r.new_hash = store_leaf(store, left_leaf);
- r.leaf_count = left_leaf.hashes.size();
+ r.leaf_count = left_leaf.entries.size();
r.did_split = true;
- r.split_leaf_count = right_leaf.hashes.size();
- r.split_min_hash = right_leaf.hashes.front();
+ r.split_leaf_count = right_leaf.entries.size();
+ r.split_min_key = right_leaf.entries.front().key;
r.split_hash = store_leaf(store, right_leaf);
return r;
}
@@ -296,19 +373,20 @@ Merkle::InsertResult Merkle::insert_into(IStorageBackend& store,
// ── Internal node ───────────────────────────────────────────────────────
auto node = decode_internal(bytes);
- size_t child_idx = route(node, tuple_hash);
+ size_t child_idx = route(node, key);
auto child_result = insert_into(store,
bin_to_hex(node.entries[child_idx].child_hash),
- tuple_hash);
+ key,
+ payload);
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).
+ // Update min_key for the modified child — only child 0 can have its min
+ // decrease (routing guarantees min_key[i>0] ≤ inserted key, so inserting
+ // below min_key[i>0] is impossible).
if (child_idx == 0)
- node.entries[0].min_hash = subtree_min(store, child_result.new_hash);
+ node.entries[0].min_key = subtree_min_key(store, child_result.new_hash);
uint64_t total = 0;
for (const auto& e : node.entries) total += e.leaf_count;
@@ -324,9 +402,10 @@ Merkle::InsertResult Merkle::insert_into(IStorageBackend& store,
// 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.min_key = child_result.split_min_key;
sibling.child_hash = hex_to_bin(child_result.split_hash);
- node.entries.insert(node.entries.begin() + static_cast<ptrdiff_t>(child_idx) + 1, sibling);
+ node.entries.insert(node.entries.begin() + static_cast<ptrdiff_t>(child_idx) + 1,
+ std::move(sibling));
total += child_result.split_leaf_count;
if (node.entries.size() <= B)
@@ -340,8 +419,10 @@ Merkle::InsertResult Merkle::insert_into(IStorageBackend& store,
// 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() };
+ 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;
@@ -352,20 +433,20 @@ Merkle::InsertResult Merkle::insert_into(IStorageBackend& store,
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_min_key = right_node.entries.front().min_key;
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)
+template<typename Key>
+std::string Merkle<Key>::Remove(IStorageBackend& store,
+ const std::string& root_hex,
+ const Key& key)
{
if (root_hex.empty()) return "";
- const Hash32 tuple_hash = hex_to_bin(hash_hex);
- auto result = remove_from(store, root_hex, tuple_hash);
+ auto result = remove_from(store, root_hex, key);
if (result.new_hash.empty()) return "";
// Collapse: if the root is an internal node with a single child, skip it.
@@ -379,9 +460,10 @@ std::string Merkle::Remove(IStorageBackend& store,
return result.new_hash;
}
-Merkle::RemoveResult Merkle::remove_from(IStorageBackend& store,
- const std::string& node_hex,
- const Hash32& tuple_hash)
+template<typename Key>
+typename Merkle<Key>::RemoveResult Merkle<Key>::remove_from(IStorageBackend& store,
+ const std::string& node_hex,
+ const Key& key)
{
auto bytes = load_node(store, node_hex);
@@ -389,23 +471,26 @@ Merkle::RemoveResult Merkle::remove_from(IStorageBackend& store,
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())
+ auto it = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key,
+ [](const LeafEntry& e, const Key& k) {
+ return e.key < k;
+ });
+ if (it == leaf.entries.end() || key < it->key)
+ return { node_hex, leaf.entries.size() }; // not found — no change
+
+ leaf.entries.erase(it);
+ if (leaf.entries.empty())
return { "", 0 };
- return { store_leaf(store, leaf), leaf.hashes.size() };
+ return { store_leaf(store, leaf), leaf.entries.size() };
}
// ── Internal node ───────────────────────────────────────────────────────
auto node = decode_internal(bytes);
- size_t child_idx = route(node, tuple_hash);
+ size_t child_idx = route(node, key);
auto child_result = remove_from(store,
bin_to_hex(node.entries[child_idx].child_hash),
- tuple_hash);
+ key);
if (child_result.new_hash.empty())
{
@@ -417,7 +502,7 @@ Merkle::RemoveResult Merkle::remove_from(IStorageBackend& store,
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);
+ node.entries[child_idx].min_key = subtree_min_key(store, child_result.new_hash);
}
uint64_t total = 0;
@@ -425,36 +510,68 @@ Merkle::RemoveResult Merkle::remove_from(IStorageBackend& store,
return { store_internal(store, node), total };
}
+// ── Get ──────────────────────────────────────────────────────────────────────
+
+template<typename Key>
+std::optional<Hash32> Merkle<Key>::Get(IStorageBackend& store,
+ const std::string& root_hex,
+ const Key& key)
+{
+ if (root_hex.empty()) return std::nullopt;
+ return get_from(store, root_hex, key);
+}
+
+template<typename Key>
+std::optional<Hash32> Merkle<Key>::get_from(IStorageBackend& store,
+ const std::string& node_hex,
+ const Key& key)
+{
+ auto bytes = load_node(store, node_hex);
+ if (is_leaf_bytes(bytes))
+ {
+ auto leaf = decode_leaf(bytes);
+ auto it = std::lower_bound(leaf.entries.begin(), leaf.entries.end(), key,
+ [](const LeafEntry& e, const Key& k) {
+ return e.key < k;
+ });
+ if (it == leaf.entries.end() || key < it->key)
+ return std::nullopt;
+ return it->payload;
+ }
+ auto node = decode_internal(bytes);
+ size_t child_idx = route(node, key);
+ return get_from(store, bin_to_hex(node.entries[child_idx].child_hash), key);
+}
+
// ── Page ─────────────────────────────────────────────────────────────────────
-std::vector<std::string> Merkle::Page(IStorageBackend& store,
- const std::string& root_hex,
- size_t offset,
- size_t limit)
+template<typename Key>
+std::vector<typename Merkle<Key>::Entry> Merkle<Key>::Page(IStorageBackend& store,
+ const std::string& root_hex,
+ size_t offset,
+ size_t limit)
{
if (root_hex.empty() || limit == 0) return {};
- std::vector<Hash32> raw;
- raw.reserve(limit);
+ std::vector<Entry> out;
+ out.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));
+ page_from(store, root_hex, skip, limit, out);
return out;
}
-void Merkle::page_from(IStorageBackend& store,
- const std::string& node_hex,
- size_t& offset,
- size_t limit,
- std::vector<Hash32>& out)
+template<typename Key>
+void Merkle<Key>::page_from(IStorageBackend& store,
+ const std::string& node_hex,
+ size_t& offset,
+ size_t limit,
+ std::vector<Entry>& out)
{
auto bytes = load_node(store, node_hex);
if (is_leaf_bytes(bytes))
{
auto leaf = decode_leaf(bytes);
- const size_t available = leaf.hashes.size();
+ const size_t available = leaf.entries.size();
if (offset >= available)
{
@@ -463,7 +580,7 @@ void Merkle::page_from(IStorageBackend& store,
}
for (size_t i = offset; i < available && out.size() < limit; ++i)
- out.push_back(leaf.hashes[i]);
+ out.push_back(Entry{ leaf.entries[i].key, leaf.entries[i].payload });
offset = 0;
return;
@@ -485,4 +602,9 @@ void Merkle::page_from(IStorageBackend& store,
}
}
+// ── Explicit instantiations ──────────────────────────────────────────────────
+
+template class Merkle<Hash32>;
+template class Merkle<std::string>;
+
} // namespace nt
diff --git a/src/MultigroupCodec.cpp b/src/MultigroupCodec.cpp
new file mode 100644
index 0000000..81d305c
--- /dev/null
+++ b/src/MultigroupCodec.cpp
@@ -0,0 +1,78 @@
+#include "MultigroupCodec.h"
+
+#include "Merkle.h"
+
+namespace nt::MultigroupCodec
+{
+ // A relation with zero tuples reports an empty merkle_root externally.
+ // The merkle tree's payload type is fixed-width Hash32, so the codec
+ // maps "" ↔ the all-zero hash. The collision probability with a real
+ // SHA256 hitting all-zero (2^-256) is treated as unreachable.
+ static nt::Hash32 encode_payload(const std::string& hex)
+ {
+ if (hex.empty()) return nt::Hash32{};
+ return nt::hex_to_bin(hex);
+ }
+
+ static std::string decode_payload(const nt::Hash32& bin)
+ {
+ static const nt::Hash32 zero{};
+ if (bin == zero) return "";
+ return nt::bin_to_hex(bin);
+ }
+
+ std::string Build(IStorageBackend& store,
+ const std::vector<RelationEntry>& relations)
+ {
+ std::string root;
+ for (const auto& [name, root_hex] : relations)
+ root = nt::Merkle<std::string>::Insert(store, root, name,
+ encode_payload(root_hex));
+ return root;
+ }
+
+ std::vector<RelationEntry> List(IStorageBackend& store,
+ const std::string& root_hex)
+ {
+ std::vector<RelationEntry> out;
+ constexpr size_t kPageSize = 1024;
+ size_t offset = 0;
+ while (true)
+ {
+ auto page = nt::Merkle<std::string>::Page(store, root_hex,
+ offset, kPageSize);
+ if (page.empty()) break;
+ for (auto& entry : page)
+ out.emplace_back(std::move(entry.key),
+ decode_payload(entry.payload));
+ if (page.size() < kPageSize) break;
+ offset += page.size();
+ }
+ return out;
+ }
+
+ std::string InsertOne(IStorageBackend& store,
+ const std::string& root_hex,
+ const std::string& relation_name,
+ const std::string& relation_root_hex)
+ {
+ return nt::Merkle<std::string>::Insert(store, root_hex, relation_name,
+ encode_payload(relation_root_hex));
+ }
+
+ std::string RemoveOne(IStorageBackend& store,
+ const std::string& root_hex,
+ const std::string& relation_name)
+ {
+ return nt::Merkle<std::string>::Remove(store, root_hex, relation_name);
+ }
+
+ std::string Lookup(IStorageBackend& store,
+ const std::string& root_hex,
+ const std::string& relation_name)
+ {
+ auto found = nt::Merkle<std::string>::Get(store, root_hex, relation_name);
+ if (!found) return "";
+ return decode_payload(*found);
+ }
+}
diff --git a/src/NamespaceReferenceManager.cpp b/src/NamespaceReferenceManager.cpp
index 1d9baac..455d077 100644
--- a/src/NamespaceReferenceManager.cpp
+++ b/src/NamespaceReferenceManager.cpp
@@ -1,5 +1,132 @@
#include "NamespaceReferenceManager.h"
+#include "Merkle.h"
+
namespace nt
{
+ NamespaceReferenceManager::NamespaceReferenceManager(ObjectManager& objects,
+ IStorageBackend& storage)
+ : objects_(objects), storage_(storage)
+ {}
+
+ // Resolves the multigroup hash that `mg_name` currently maps to inside the
+ // branch-tree rooted at `branch_tree_root`. Returns the empty string when
+ // the branch is unborn (empty root) or the multigroup is absent.
+ static std::string lookup_mg_hash(IStorageBackend& storage,
+ const std::string& branch_tree_root,
+ const std::string& mg_name)
+ {
+ if (branch_tree_root.empty()) return "";
+ auto found = Merkle<std::string>::Get(storage, branch_tree_root, mg_name);
+ if (!found) return "";
+ // All-zero payload = "no snapshot bound" sentinel matching MultigroupCodec.
+ static const Hash32 zero{};
+ if (*found == zero) return "";
+ return bin_to_hex(*found);
+ }
+
+ std::vector<std::string> NamespaceReferenceManager::Resolve(
+ std::vector<std::string> path) const
+ {
+ constexpr int kMaxReparseDepth = 30;
+
+ for (int depth = 0; depth < kMaxReparseDepth; ++depth)
+ {
+ // /system/sessions/<X>/branches/<name>/multigroups/<mg>/<sub>...
+ // — per-session override takes precedence; absent override falls
+ // back to the global branch. Requires at minimum the literal
+ // "multigroups" qualifier and an mg name.
+ if (path.size() > 6
+ && path[0] == "system"
+ && path[1] == "sessions"
+ && path[3] == "branches"
+ && path[5] == "multigroups")
+ {
+ const std::vector<std::string> session_path{
+ "system", "sessions", path[2]
+ };
+ auto* session_entry = objects_.Find(session_path);
+
+ std::string branch_tree_root;
+ if (session_entry && session_entry->object)
+ {
+ auto* session = dynamic_cast<ObjectManager::Session*>(
+ session_entry->object.get());
+ if (session)
+ {
+ auto it = session->branch_overrides.find(path[4]);
+ if (it != session->branch_overrides.end())
+ branch_tree_root = it->second;
+ }
+ }
+
+ // No session-level override — defer to the global branch's HEAD.
+ if (branch_tree_root.empty())
+ {
+ const std::vector<std::string> branch_path{
+ "system", "branches", path[4]
+ };
+ auto* bentry = objects_.Find(branch_path);
+ if (bentry && bentry->object)
+ {
+ auto* branch = dynamic_cast<ObjectManager::Branch*>(
+ bentry->object.get());
+ if (branch) branch_tree_root = branch->target_hash;
+ }
+ }
+
+ const std::string mg_hash =
+ lookup_mg_hash(storage_, branch_tree_root, path[6]);
+ if (mg_hash.empty()) return path;
+
+ std::vector<std::string> rewritten{
+ "system", "snapshots", mg_hash
+ };
+ for (size_t i = 7; i < path.size(); ++i)
+ rewritten.push_back(path[i]);
+
+ path = std::move(rewritten);
+ continue;
+ }
+
+ // /system/branches/<name>/multigroups/<mg>/<sub>... →
+ // /system/snapshots/<mg_hash>/<sub>...
+ // Requires the literal "multigroups" qualifier and an mg name. A
+ // bare /system/branches/<name> path opens the branch object itself
+ // and is returned unchanged.
+ if (path.size() > 4
+ && path[0] == "system"
+ && path[1] == "branches"
+ && path[3] == "multigroups")
+ {
+ const std::vector<std::string> branch_path{
+ "system", "branches", path[2]
+ };
+ auto* entry = objects_.Find(branch_path);
+ if (!entry || !entry->object) return path;
+
+ auto* branch =
+ dynamic_cast<ObjectManager::Branch*>(entry->object.get());
+ if (!branch) return path;
+
+ const std::string mg_hash =
+ lookup_mg_hash(storage_, branch->target_hash, path[4]);
+ if (mg_hash.empty()) return path;
+
+ std::vector<std::string> rewritten{
+ "system", "snapshots", mg_hash
+ };
+ for (size_t i = 5; i < path.size(); ++i)
+ rewritten.push_back(path[i]);
+
+ path = std::move(rewritten);
+ continue;
+ }
+
+ return path;
+ }
+
+ // Cycle guard tripped — surface as a lookup miss.
+ return {};
+ }
}
diff --git a/src/ObjectManager.cpp b/src/ObjectManager.cpp
index 19f862d..67504c3 100644
--- a/src/ObjectManager.cpp
+++ b/src/ObjectManager.cpp
@@ -30,4 +30,19 @@ namespace nt
}
return nullptr;
}
+
+ bool ObjectManager::Unregister(const std::vector<std::string>& object_path)
+ {
+ std::unique_ptr<registry>* slot = &entries;
+ while (slot->get() != nullptr)
+ {
+ if ((*slot)->head->path == object_path)
+ {
+ *slot = std::move((*slot)->next);
+ return true;
+ }
+ slot = &(*slot)->next;
+ }
+ return false;
+ }
}
diff --git a/src/RNT_C_API.cpp b/src/RNT_C_API.cpp
index 34bbacc..c92d03b 100644
--- a/src/RNT_C_API.cpp
+++ b/src/RNT_C_API.cpp
@@ -5,6 +5,8 @@
#include "IdentityManager.h"
#include "LifecycleManager.h"
#include "Merkle.h"
+#include "MultigroupCodec.h"
+#include "NamespaceReferenceManager.h"
#include "ObjectManager.h"
#include "PermissionsManager.h"
#include "InMemoryBackend.h"
@@ -12,9 +14,11 @@
#include "TupleCodec.h"
#include "VM.h"
+#include <algorithm>
#include <cstring>
#include <memory>
#include <mutex>
+#include <random>
#include <sstream>
#include <stdexcept>
#include <string>
@@ -38,16 +42,16 @@ namespace
nt::ObjectManager objects;
nt::PermissionsManager permissions;
nt::IdentityManager identities;
- nt::LifecycleManager lifecycles;
+ std::unique_ptr<nt::LifecycleManager> lifecycles;
+ std::unique_ptr<nt::NamespaceReferenceManager> references;
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; }
+ bool is_initialized() { return g_init_done; }
static std::vector<std::string> split_path(const char* path)
{
@@ -121,6 +125,286 @@ namespace
return t;
}
+ static std::unique_ptr<nt::ObjectManager::object_type> make_multigroup_type()
+ {
+ auto t = std::make_unique<nt::ObjectManager::object_type>();
+ t->label = MULTIGROUP;
+ t->disposable = false;
+ t->methods = { OPEN, CLOSE };
+ // Multigroup snapshots are immutable and content-addressed; concurrent
+ // readers never contend. GC is gated by reference_count only.
+ t->exclusive = false;
+ return t;
+ }
+
+ static std::unique_ptr<nt::ObjectManager::object_type> make_branch_tree_type()
+ {
+ auto t = std::make_unique<nt::ObjectManager::object_type>();
+ t->label = BRANCH_TREE;
+ t->disposable = false;
+ t->methods = { OPEN, CLOSE };
+ // Branch-tree blobs are immutable content-addressed merkle roots;
+ // GC is gated by reference_count only.
+ t->exclusive = false;
+ return t;
+ }
+
+ static std::unique_ptr<nt::ObjectManager::object_type> make_session_type()
+ {
+ auto t = std::make_unique<nt::ObjectManager::object_type>();
+ t->label = SESSION;
+ // Sessions live only as long as their connection; rnt_session_close
+ // removes them via ObjectManager::Unregister.
+ t->disposable = true;
+ t->methods = { OPEN, CLOSE };
+ // Multiple readers/writers may consult a session concurrently to read
+ // overrides; contention is only enforced when an exclusive mutator
+ // (set_branch) is wired up. Default to non-exclusive for now.
+ t->exclusive = false;
+ return t;
+ }
+
+ // Generates a random 256-bit hex hash for naming a session. Hashes are
+ // drawn from std::random_device-seeded mt19937_64; we do not need
+ // cryptographic strength here, just enough entropy that two concurrent
+ // rnt_session_open calls cannot collide.
+ static std::string random_session_hash()
+ {
+ static thread_local std::mt19937_64 rng{ std::random_device{}() };
+ static const char hex[] = "0123456789abcdef";
+
+ std::string out;
+ out.reserve(64);
+ for (int i = 0; i < 4; ++i)
+ {
+ uint64_t v = rng();
+ for (int b = 0; b < 8; ++b)
+ {
+ uint8_t byte = static_cast<uint8_t>(v & 0xFF);
+ out.push_back(hex[(byte >> 4) & 0xF]);
+ out.push_back(hex[byte & 0xF]);
+ v >>= 8;
+ }
+ }
+ return out;
+ }
+
+ // Serializes the (name, merkle_root) pairs into the storage backend and
+ // registers the resulting multigroup snapshot under /system/snapshots/<hash>,
+ // with one Relation entry per child at /system/snapshots/<hash>/<name>.
+ // Idempotent: if the snapshot already exists in the registry the existing
+ // entries are reused. Returns the multigroup hash, or empty string on error.
+ //
+ // Each child Relation is Pinned by its parent Multigroup at creation time.
+ // LifecycleManager::CascadeMultigroup releases these pins when the
+ // multigroup itself becomes GC-eligible.
+ static std::string register_snapshot(
+ const std::vector<nt::MultigroupCodec::RelationEntry>& relations)
+ {
+ if (!g_rt) return {};
+
+ const std::string hash = nt::MultigroupCodec::Build(*g_rt->storage, relations);
+ if (hash.empty()) return {};
+ const auto snap_path = split_path(("/system/snapshots/" + hash).c_str());
+
+ if (g_rt->objects.Find(snap_path) != nullptr) return hash;
+
+ auto mg = std::make_unique<nt::ObjectManager::Multigroup>();
+ mg->merkle_root = hash;
+ g_rt->objects.Register(snap_path, std::move(mg), make_multigroup_type());
+
+ for (const auto& [name, root] : relations)
+ {
+ const auto rel_path = split_path(
+ ("/system/snapshots/" + hash + "/relations/" + name).c_str());
+ if (g_rt->objects.Find(rel_path) != nullptr) continue;
+
+ auto rel = std::make_unique<nt::ObjectManager::Relation>();
+ rel->merkle_root = root;
+ g_rt->objects.Register(rel_path, std::move(rel), make_relation_type());
+
+ // Structural pin from the parent Multigroup; released by
+ // LifecycleManager::CascadeMultigroup at GC time.
+ g_rt->lifecycles->Pin(g_rt->objects.Find(rel_path));
+ }
+ return hash;
+ }
+
+ // Enumerates (mg_name, mg_hash) pairs in a branch-tree.
+ static std::vector<std::pair<std::string, std::string>>
+ list_branch_tree(const std::string& branch_tree_root)
+ {
+ std::vector<std::pair<std::string, std::string>> out;
+ if (branch_tree_root.empty()) return out;
+ constexpr size_t kPageSize = 1024;
+ size_t offset = 0;
+ while (true)
+ {
+ auto page = nt::Merkle<std::string>::Page(*g_rt->storage,
+ branch_tree_root,
+ offset, kPageSize);
+ if (page.empty()) break;
+ for (auto& entry : page)
+ out.emplace_back(std::move(entry.key),
+ nt::bin_to_hex(entry.payload));
+ if (page.size() < kPageSize) break;
+ offset += page.size();
+ }
+ return out;
+ }
+
+ // Registers /system/branch_trees/<hash> as a BRANCH_TREE if missing, and
+ // takes one structural pin on each multigroup the tree references. The
+ // pins are mirrored by LifecycleManager::CascadeBranchTree at GC time.
+ // Idempotent: a second call with the same hash returns immediately.
+ static void register_branch_tree(const std::string& tree_root)
+ {
+ if (tree_root.empty()) return;
+ const auto bt_path = split_path(
+ ("/system/branch_trees/" + tree_root).c_str());
+ if (g_rt->objects.Find(bt_path) != nullptr) return;
+
+ auto bt = std::make_unique<nt::ObjectManager::BranchTree>();
+ bt->merkle_root = tree_root;
+ g_rt->objects.Register(bt_path, std::move(bt), make_branch_tree_type());
+
+ for (const auto& [_, mg_hash] : list_branch_tree(tree_root))
+ {
+ if (mg_hash.empty()) continue;
+ const auto p = split_path(("/system/snapshots/" + mg_hash).c_str());
+ g_rt->lifecycles->Pin(g_rt->objects.Find(p));
+ }
+ }
+
+ // Adjusts pins when a branch (or session override) moves its bound
+ // branch-tree root. The new tree is pinned before the old is unpinned so
+ // a no-op advance never sees a pinned BranchTree's ref_count briefly hit
+ // zero and trigger cascade collection of every mg it references.
+ static void rebind_branch_tree_pin(const std::string& old_tree_root,
+ const std::string& new_tree_root)
+ {
+ if (old_tree_root == new_tree_root) return;
+ if (!new_tree_root.empty())
+ {
+ register_branch_tree(new_tree_root);
+ const auto p = split_path(
+ ("/system/branch_trees/" + new_tree_root).c_str());
+ g_rt->lifecycles->Pin(g_rt->objects.Find(p));
+ }
+ if (!old_tree_root.empty())
+ {
+ const auto p = split_path(
+ ("/system/branch_trees/" + old_tree_root).c_str());
+ g_rt->lifecycles->Unpin(g_rt->objects.Find(p));
+ }
+ }
+
+ // Looks up the mg_hash currently bound to `mg_name` in the branch's tree.
+ // Returns empty string when the branch is unborn or the mg is absent.
+ static std::string lookup_branch_mg(const nt::ObjectManager::Branch& branch,
+ const std::string& mg_name)
+ {
+ if (branch.target_hash.empty()) return "";
+ auto found = nt::Merkle<std::string>::Get(*g_rt->storage,
+ branch.target_hash, mg_name);
+ if (!found) return "";
+ static const nt::Hash32 zero{};
+ if (*found == zero) return "";
+ return nt::bin_to_hex(*found);
+ }
+
+ // Reads the (relation_name, root) list of a specific multigroup under a
+ // branch. Returns empty for unborn branches or absent multigroups.
+ static std::vector<nt::MultigroupCodec::RelationEntry> read_mg_relations(
+ const nt::ObjectManager::Branch& branch,
+ const std::string& mg_name)
+ {
+ const std::string mg_hash = lookup_branch_mg(branch, mg_name);
+ if (mg_hash.empty()) return {};
+ return nt::MultigroupCodec::List(*g_rt->storage, mg_hash);
+ }
+
+ // Looks up a branch object by path. Returns nullptr when the path does not
+ // resolve to a BRANCH.
+ static nt::ObjectManager::Branch* find_branch(
+ const std::vector<std::string>& branch_path)
+ {
+ auto* entry = g_rt->objects.Find(branch_path);
+ if (!entry || !entry->object || !entry->head) return nullptr;
+ if (entry->head->type->label != BRANCH) return nullptr;
+ return dynamic_cast<nt::ObjectManager::Branch*>(entry->object.get());
+ }
+
+ // Parses a path of the form
+ // /system/branches/<name>/multigroups/<mg>/relations/<rel>.
+ // Returns true on success; out-parameters are populated with the branch
+ // path, the multigroup name, and the relation name. Returns false for
+ // any other path shape.
+ static bool split_branch_mg_relation(const std::vector<std::string>& parts,
+ std::vector<std::string>& branch_path_out,
+ std::string& mg_name_out,
+ std::string& relation_name_out)
+ {
+ if (parts.size() != 7) return false;
+ if (parts[0] != "system" || parts[1] != "branches"
+ || parts[3] != "multigroups" || parts[5] != "relations") return false;
+ branch_path_out = { "system", "branches", parts[2] };
+ mg_name_out = parts[4];
+ relation_name_out = parts[6];
+ return true;
+ }
+
+ // Applies a per-relation root update with the full two-level cascade:
+ // 1. Read the (rel, root) list of `mg_name` from the branch's current
+ // tree (or empty when the mg is absent / branch is unborn).
+ // 2. Insert/replace (relation_name, new_root) in that list.
+ // 3. register_snapshot → new_mg_hash.
+ // 4. Insert (mg_name → new_mg_hash) into the branch tree → new branch
+ // tree root.
+ // 5. Advance branch.target_hash to the new root and rebind pins.
+ // Returns the new branch tree root on success; empty on error.
+ //
+ // Pin/unpin transitions are applied via rebind_branch_tree_pin: new mgs
+ // are pinned before old mgs are unpinned, so an unchanged advance never
+ // briefly drops a multigroup's ref_count to zero.
+ static std::string commit_relation_update(
+ nt::ObjectManager::Branch& branch,
+ const std::string& mg_name,
+ const std::string& relation_name,
+ const std::string& new_root)
+ {
+ auto relations = read_mg_relations(branch, mg_name);
+ auto it = std::find_if(relations.begin(), relations.end(),
+ [&](const auto& e) { return e.first == relation_name; });
+ if (it != relations.end()) it->second = new_root;
+ else relations.emplace_back(relation_name, new_root);
+
+ const std::string new_mg_hash = register_snapshot(relations);
+ if (new_mg_hash.empty()) return {};
+
+ const nt::Hash32 mg_payload = nt::hex_to_bin(new_mg_hash);
+ const std::string new_tree_root = nt::Merkle<std::string>::Insert(
+ *g_rt->storage, branch.target_hash, mg_name, mg_payload);
+
+ const std::string old_tree_root = branch.target_hash;
+ branch.target_hash = new_tree_root;
+ rebind_branch_tree_pin(old_tree_root, new_tree_root);
+ return new_tree_root;
+ }
+
+ // Returns the merkle_root of a named relation in the specified mg under
+ // the branch's current tree. Empty when the branch is unborn, the mg
+ // doesn't exist, or the relation is absent.
+ static std::string read_relation_root(const nt::ObjectManager::Branch& branch,
+ const std::string& mg_name,
+ const std::string& relation_name)
+ {
+ const auto relations = read_mg_relations(branch, mg_name);
+ auto it = std::find_if(relations.begin(), relations.end(),
+ [&](const auto& e) { return e.first == relation_name; });
+ return (it == relations.end()) ? std::string{} : it->second;
+ }
+
// -----------------------------------------------------------------------
// Plan builder internals
// -----------------------------------------------------------------------
@@ -187,9 +471,6 @@ namespace
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>();
@@ -201,19 +482,25 @@ int rnt_init(const char* driver, const char* storage_path)
rt->storage = std::make_unique<nt::SqliteBackend>(
storage_path ? storage_path : ":memory:");
+ rt->lifecycles = std::make_unique<nt::LifecycleManager>(
+ rt->objects, *rt->storage);
+ rt->references = std::make_unique<nt::NamespaceReferenceManager>(
+ rt->objects, *rt->storage);
rt->handler = std::make_unique<nt::HandlerManager>(
- rt->objects, rt->permissions, rt->identities, rt->lifecycles);
- rt->cursors = std::make_unique<nt::CursorManager>(*rt->storage);
+ rt->objects, rt->permissions, rt->identities, *rt->lifecycles,
+ *rt->references);
+ rt->cursors = std::make_unique<nt::CursorManager>(
+ *rt->storage, rt->lifecycles.get(), &rt->objects);
g_rt = std::move(rt);
// Register the default branch on first boot so that
// rnt_open_handle("/system/branches/master") always succeeds.
- const auto main_path = split_path("/system/branches/master");
- if (g_rt->objects.Find(main_path) == nullptr)
+ const auto master_path = split_path("/system/branches/master");
+ if (g_rt->objects.Find(master_path) == nullptr)
{
auto branch = std::make_unique<nt::ObjectManager::Branch>();
branch->name = "master";
- g_rt->objects.Register(main_path, std::move(branch),
+ g_rt->objects.Register(master_path, std::move(branch),
make_branch_type());
}
@@ -229,28 +516,107 @@ int rnt_init(const char* driver, const char* storage_path)
int rnt_firewall(const char* /*auth_method*/, char** claims_out)
{
- if (!is_init() || !claims_out) return -1;
+ if (!is_initialized() || !claims_out) return -1;
// PermissionsManager::Firewall is stubbed; grant all claims for now.
*claims_out = heap_str("READ WRITE");
return 0;
}
+int rnt_session_open(void* connection_context, char** session_hash_out)
+{
+ if (!is_initialized() || !session_hash_out) return -1;
+
+ // Retry on the astronomically unlikely event of a hash collision against
+ // an already-registered session.
+ std::string hash;
+ for (int attempts = 0; attempts < 8; ++attempts)
+ {
+ hash = random_session_hash();
+ const auto session_path = split_path(("/system/sessions/" + hash).c_str());
+ if (g_rt->objects.Find(session_path) != nullptr) continue;
+
+ auto session = std::make_unique<nt::ObjectManager::Session>();
+ session->connection_context = connection_context;
+ g_rt->objects.Register(session_path, std::move(session), make_session_type());
+ *session_hash_out = heap_str(hash);
+ return 0;
+ }
+ return -1;
+}
+
+int rnt_session_close(const char* session_hash)
+{
+ if (!is_initialized() || !session_hash) return -1;
+ const auto session_path = split_path(
+ ("/system/sessions/" + std::string(session_hash)).c_str());
+
+ auto* entry = g_rt->objects.Find(session_path);
+ if (!entry || !entry->object) return -1;
+ auto* session = dynamic_cast<nt::ObjectManager::Session*>(entry->object.get());
+ if (!session) return -1;
+
+ // Release every pin this session was holding before the entry disappears,
+ // so the dependent multigroups become GC-eligible.
+ for (const auto& [name, hash] : session->branch_overrides)
+ rebind_branch_tree_pin(hash, "");
+ session->branch_overrides.clear();
+
+ return g_rt->objects.Unregister(session_path) ? 0 : -1;
+}
+
+int rnt_session_set_branch(const char* session_hash,
+ const char* branch_name,
+ const char* target_hash)
+{
+ if (!is_initialized() || !session_hash || !branch_name || !target_hash)
+ return -1;
+
+ const auto session_path = split_path(
+ ("/system/sessions/" + std::string(session_hash)).c_str());
+ auto* entry = g_rt->objects.Find(session_path);
+ if (!entry || !entry->object || !entry->head) return -1;
+ if (entry->head->type->label != SESSION) return -1;
+
+ auto* session = dynamic_cast<nt::ObjectManager::Session*>(entry->object.get());
+ if (!session) return -1;
+
+ const std::string hash(target_hash);
+ std::string old_hash;
+ auto it = session->branch_overrides.find(branch_name);
+ if (it != session->branch_overrides.end()) old_hash = it->second;
+
+ if (hash.empty())
+ {
+ session->branch_overrides.erase(branch_name);
+ rebind_branch_tree_pin(old_hash, "");
+ return 0;
+ }
+
+ // target_hash is a branch-tree root — a content-addressed blob produced
+ // by an earlier commit. Reject if unknown.
+ if (!g_rt->storage->Get(hash)) return -1;
+
+ session->branch_overrides[branch_name] = hash;
+ rebind_branch_tree_pin(old_hash, hash);
+ return 0;
+}
+
rnt_handle_t rnt_open_handle(const char* path, const char* /*claims*/)
{
- if (!is_init() || !path) return nullptr;
+ if (!is_initialized() || !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;
+ if (!is_initialized() || !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)
+int rnt_branch_target(rnt_handle_t handle, char** target_hash_out)
{
- if (!is_init() || !handle || !payload_out || !len_out) return -1;
+ if (!is_initialized() || !handle || !target_hash_out) return -1;
auto* h = static_cast<nt::HandlerManager::handle*>(handle);
if (!h->object || !h->object->head) return -1;
@@ -259,127 +625,231 @@ int rnt_branch_payload(rnt_handle_t handle, uint8_t** payload_out, size_t* len_o
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();
+ *target_hash_out = heap_str(branch->target_hash);
return 0;
}
-int rnt_branch_set_payload(rnt_handle_t handle, const uint8_t* payload, size_t len)
+int rnt_branch_advance(const char* branch_path, const char* new_hash)
{
- if (!is_init() || !handle) return -1;
+ if (!is_initialized() || !branch_path || !new_hash) 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* entry = g_rt->objects.Find(split_path(branch_path));
+ if (!entry || !entry->object || !entry->head) return -1;
+ if (entry->head->type->label != BRANCH) return -1;
- auto* branch = dynamic_cast<nt::ObjectManager::Branch*>(h->object->object.get());
+ auto* branch = dynamic_cast<nt::ObjectManager::Branch*>(entry->object.get());
if (!branch) return -1;
- branch->payload.assign(payload, payload + len);
+ const std::string hash(new_hash);
+ // Non-empty branch-tree roots must already exist in the KV store. The
+ // branch tree is a content-addressed blob produced by an earlier mutation
+ // through commit_relation_update; advancing to an unknown root is treated
+ // as a caller bug.
+ if (!hash.empty() && !g_rt->storage->Get(hash)) return -1;
+
+ const std::string old_hash = branch->target_hash;
+ branch->target_hash = hash;
+ rebind_branch_tree_pin(old_hash, hash);
return 0;
}
int rnt_register_relation(const char* path)
{
- if (!is_init() || !path) return -1;
+ if (!is_initialized() || !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;
+
+ std::vector<std::string> branch_path;
+ std::string mg_name, relation_name;
+ if (!split_branch_mg_relation(parts, branch_path, mg_name, relation_name))
+ return -1;
+
+ auto* branch = find_branch(branch_path);
+ if (!branch) return -1;
+
+ // Idempotent: if the relation is already present in the named mg's
+ // current snapshot, the call succeeds without producing a new snapshot.
+ const auto current = read_mg_relations(*branch, mg_name);
+ const bool already_present = std::any_of(
+ current.begin(), current.end(),
+ [&](const auto& e) { return e.first == relation_name; });
+ if (already_present) return 0;
+
+ // Empty merkle_root signals a relation with no tuples.
+ return commit_relation_update(*branch, mg_name, relation_name, "").empty()
+ ? -1 : 0;
}
-int rnt_register_branch(const char* path, const uint8_t* payload, size_t payload_len)
+int rnt_register_branch(const char* path, const char* target_hash)
{
- if (!is_init() || !path) return -1;
+ if (!is_initialized() || !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);
+ const std::string hash = target_hash ? target_hash : "";
+ // Non-empty target_hash is a branch-tree root produced by an earlier
+ // commit; it must already exist as a KV blob.
+ if (!hash.empty() && !g_rt->storage->Get(hash)) return -1;
+
+ auto branch = std::make_unique<nt::ObjectManager::Branch>();
+ branch->name = parts.empty() ? "" : parts.back();
+ branch->target_hash = hash;
g_rt->objects.Register(parts, std::move(branch), make_branch_type());
+ rebind_branch_tree_pin("", hash);
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)
+int rnt_list_relations(const char* branch_mg_path, char** out)
{
- auto* entry = g_rt->objects.Find(parts);
- if (!entry || !entry->object) return nullptr;
- return dynamic_cast<nt::ObjectManager::Relation*>(entry->object.get());
+ if (!is_initialized() || !branch_mg_path || !out) return -1;
+ const auto parts = split_path(branch_mg_path);
+ if (parts.size() != 5) return -1;
+ if (parts[0] != "system" || parts[1] != "branches"
+ || parts[3] != "multigroups") return -1;
+
+ auto* branch = find_branch({ "system", "branches", parts[2] });
+ if (!branch) return -1;
+ const auto relations = read_mg_relations(*branch, parts[4]);
+ std::string result;
+ for (const auto& [name, root] : relations)
+ result += name + "\t" + root + "\n";
+ *out = heap_str(result);
+ return 0;
+}
+
+int rnt_list_branch_multigroups(const char* branch_path, char** out)
+{
+ if (!is_initialized() || !branch_path || !out) return -1;
+ auto* branch = find_branch(split_path(branch_path));
+ if (!branch) return -1;
+ const auto mgs = list_branch_tree(branch->target_hash);
+ std::string result;
+ for (const auto& [name, mg_hash] : mgs)
+ result += name + "\t" + mg_hash + "\n";
+ *out = heap_str(result);
+ return 0;
+}
+
+int rnt_list_snapshot_relations(const char* snapshot_hash, char** out)
+{
+ if (!is_initialized() || !snapshot_hash || !out) return -1;
+ const std::string hash(snapshot_hash);
+ const auto snap_path = split_path(("/system/snapshots/" + hash).c_str());
+ auto* entry = g_rt->objects.Find(snap_path);
+ if (!entry || !entry->object) return -1;
+ auto* mg = dynamic_cast<nt::ObjectManager::Multigroup*>(entry->object.get());
+ if (!mg) return -1;
+ const auto relations = nt::MultigroupCodec::List(*g_rt->storage, mg->merkle_root);
+ std::string result;
+ for (const auto& [name, root] : relations)
+ result += name + "\t" + root + "\n";
+ *out = heap_str(result);
+ return 0;
}
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;
+ if (!is_initialized() || !relation_path || !kv_attrs || !hash_out) return -1;
const auto parts = split_path(relation_path);
- auto* rel = find_relation(parts);
- if (!rel) return -1;
+ std::vector<std::string> branch_path;
+ std::string mg_name, relation_name;
+ if (!split_branch_mg_relation(parts, branch_path, mg_name, relation_name))
+ return -1;
+
+ auto* branch = find_branch(branch_path);
+ if (!branch) return -1;
+
+ const std::string old_root = read_relation_root(*branch, mg_name, relation_name);
- auto bytes = nt::TupleCodec::Serialize(parse_kv(kv_attrs));
- const auto hash = g_rt->storage->Put(std::move(bytes));
+ auto bytes = nt::TupleCodec::Serialize(parse_kv(kv_attrs));
+ const auto tuple_hash = g_rt->storage->Put(std::move(bytes));
+ const auto tuple_bin = nt::hex_to_bin(tuple_hash);
+ const std::string new_root =
+ nt::Merkle<nt::Hash32>::Insert(*g_rt->storage, old_root,
+ tuple_bin, tuple_bin);
- rel->merkle_root = nt::Merkle::Insert(*g_rt->storage, rel->merkle_root, hash);
+ if (commit_relation_update(*branch, mg_name, relation_name, new_root).empty())
+ return -1;
- *hash_out = heap_str(hash);
+ *hash_out = heap_str(tuple_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;
+ if (!is_initialized() || !relation_path || !tuple_hash) return -1;
+ const auto parts = split_path(relation_path);
+
+ std::vector<std::string> branch_path;
+ std::string mg_name, relation_name;
+ if (!split_branch_mg_relation(parts, branch_path, mg_name, relation_name))
+ return -1;
+
+ auto* branch = find_branch(branch_path);
+ if (!branch) return -1;
+
+ const std::string old_root = read_relation_root(*branch, mg_name, relation_name);
+ const std::string new_root =
+ nt::Merkle<nt::Hash32>::Remove(*g_rt->storage, old_root,
+ nt::hex_to_bin(tuple_hash));
+
+ return commit_relation_update(*branch, mg_name, relation_name, new_root).empty()
+ ? -1 : 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;
+ if (!is_initialized() || !relation_path) return -1;
+ const auto parts = split_path(relation_path);
+
+ std::vector<std::string> branch_path;
+ std::string mg_name, relation_name;
+ if (!split_branch_mg_relation(parts, branch_path, mg_name, relation_name))
+ return -1;
+
+ auto* branch = find_branch(branch_path);
+ if (!branch) return -1;
+
+ return commit_relation_update(*branch, mg_name, relation_name, "").empty()
+ ? -1 : 0;
}
int rnt_relation_root(const char* relation_path, char** root_hash_out)
{
- if (!is_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;
-}
+ if (!is_initialized() || !relation_path || !root_hash_out) return -1;
+ const auto parts = split_path(relation_path);
-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 : "";
+ std::vector<std::string> branch_path;
+ std::string mg_name, relation_name;
+ if (!split_branch_mg_relation(parts, branch_path, mg_name, relation_name))
+ return -1;
+
+ auto* branch = find_branch(branch_path);
+ if (!branch) return -1;
+
+ // Distinguish "relation registered but empty" (returns 0 with empty hash)
+ // from "relation not in this multigroup's snapshot" (returns -1). Without
+ // this check an unborn branch would silently report every relation empty.
+ const auto relations = read_mg_relations(*branch, mg_name);
+ auto it = std::find_if(relations.begin(), relations.end(),
+ [&](const auto& e) { return e.first == relation_name; });
+ if (it == relations.end()) return -1;
+
+ *root_hash_out = heap_str(it->second);
return 0;
}
rnt_cursor_t rnt_cursor_open(rnt_handle_t handle)
{
- if (!is_init() || !handle) return nullptr;
+ if (!is_initialized() || !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);
+ auto* rel = dynamic_cast<nt::ObjectManager::Relation*>(h->object->object.get());
if (rel) merkle_root = rel->merkle_root;
}
@@ -388,7 +858,7 @@ rnt_cursor_t rnt_cursor_open(rnt_handle_t handle)
int rnt_cursor_next(rnt_cursor_t cursor, char** tuple_out)
{
- if (!is_init() || !cursor || !tuple_out) return -1;
+ if (!is_initialized() || !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; }
@@ -398,7 +868,7 @@ int rnt_cursor_next(rnt_cursor_t cursor, char** tuple_out)
int rnt_cursor_close(rnt_cursor_t cursor)
{
- if (!is_init() || !cursor) return -1;
+ if (!is_initialized() || !cursor) return -1;
g_rt->cursors->Close(static_cast<nt::CursorManager::cursor*>(cursor));
return 0;
}
@@ -412,17 +882,24 @@ void rnt_free_bytes(uint8_t* p) { delete[] p; }
rnt_plan_t rnt_plan_scan(const char* relation_path)
{
- if (!is_init() || !relation_path) return nullptr;
+ if (!is_initialized() || !relation_path) return nullptr;
// Open a handle to the stored relation through the full manager pipeline.
+ // Open() runs NamespaceReferenceManager::Resolve internally, so the handle
+ // lands on the resolved /system/snapshots/<hash>/relations/<n> entry when
+ // the caller passed a branch-relative path.
const auto parts = split_path(relation_path);
auto* h = g_rt->handler->Open(parts, nullptr);
if (!h) return nullptr;
- // Seed the cursor with the current Merkle root from the ObjectManager.
+ // Read the Merkle root straight from the handle's object — Resolve has
+ // already pointed it at the snapshot-bound Relation entry.
std::string merkle_root;
- auto* rel = find_relation(parts);
- if (rel) merkle_root = rel->merkle_root;
+ if (h->object && h->object->object)
+ {
+ auto* rel = dynamic_cast<nt::ObjectManager::Relation*>(h->object->object.get());
+ if (rel) merkle_root = rel->merkle_root;
+ }
auto* c = g_rt->cursors->Open(h, merkle_root);
if (!c)
@@ -507,14 +984,14 @@ void rnt_plan_free(rnt_plan_t plan)
rnt_cursor_t rnt_vm_execute_plan(rnt_plan_t plan)
{
- if (!is_init() || !plan) return nullptr;
+ if (!is_initialized() || !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;
+ if (!is_initialized() || !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; }
@@ -524,7 +1001,7 @@ int rnt_vm_cursor_next(rnt_cursor_t vm_cursor, char** tuple_out)
int rnt_vm_cursor_close(rnt_cursor_t vm_cursor)
{
- if (!is_init() || !vm_cursor) return -1;
+ if (!is_initialized() || !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 acf7ecb..b1302ee 100644
--- a/src/RelationalNT.cpp
+++ b/src/RelationalNT.cpp
@@ -6,6 +6,7 @@
#include "IdentityManager.h"
#include "LifecycleManager.h"
#include "Merkle.h"
+#include "NamespaceReferenceManager.h"
#include "ObjectManager.h"
#include "PermissionsManager.h"
#include "SqliteBackend.h"
@@ -51,8 +52,10 @@ int main()
auto store = [&](std::vector<nt::Attribute> attrs) {
auto bytes = nt::TupleCodec::Serialize(attrs);
auto hash = backend.Put(std::move(bytes));
+ auto hash_bin = nt::hex_to_bin(hash);
villager_rel->merkle_root =
- nt::Merkle::Insert(backend, villager_rel->merkle_root, hash);
+ nt::Merkle<nt::Hash32>::Insert(backend, villager_rel->merkle_root,
+ hash_bin, hash_bin);
};
store({ { "name", "Blathers" }, { "profession", "Museum Curator" } });
store({ { "name", "Rover" }, { "profession", "Traveller" } });
@@ -62,8 +65,9 @@ int main()
// --- Open a handle on villager through the full manager pipeline ---
nt::PermissionsManager permissions;
nt::IdentityManager identities;
- nt::LifecycleManager lifecycles;
- nt::HandlerManager handler(objects, permissions, identities, lifecycles);
+ nt::LifecycleManager lifecycles(objects, backend);
+ nt::NamespaceReferenceManager references(objects, backend);
+ nt::HandlerManager handler(objects, permissions, identities, lifecycles, references);
int connection = 1; // dummy connection context
nt::HandlerManager::handle* handle = handler.Open(path, &connection);
diff --git a/test/C_API.cpp b/test/C_API.cpp
new file mode 100644
index 0000000..f186374
--- /dev/null
+++ b/test/C_API.cpp
@@ -0,0 +1,442 @@
+#include <catch2/catch_test_macros.hpp>
+
+#include "RNT_C_API.h"
+
+#include <cstring>
+#include <string>
+
+// ---------------------------------------------------------------------------
+// End-to-end C API tests covering step 2 (Branch hash-pointer), step 3+4
+// (copy-on-write writes and resolver wiring through rnt_open_handle), and
+// step 5 (session lifecycle and overrides).
+//
+// The C API holds a single process-global runtime; rnt_init is idempotent.
+// Each test uses unique branch and session identifiers so state from one
+// test does not affect another.
+// ---------------------------------------------------------------------------
+
+namespace
+{
+ struct InitGuard {
+ InitGuard() { REQUIRE(rnt_init("memory", nullptr) == 0); }
+ };
+
+ std::string take_string(char* p)
+ {
+ std::string s = p ? p : "";
+ rnt_free_string(p);
+ return s;
+ }
+}
+
+// ---------------------------------------------------------------------------
+// Step 2 — Branch hash-pointer model
+// ---------------------------------------------------------------------------
+
+TEST_CASE("rnt_register_branch with empty target creates an unborn branch",
+ "[step2][capi][branch]")
+{
+ InitGuard _;
+ const char* path = "/system/branches/test_step2_unborn";
+ REQUIRE(rnt_register_branch(path, "") == 0);
+
+ rnt_handle_t h = rnt_open_handle(path, nullptr);
+ REQUIRE(h != nullptr);
+
+ char* target = nullptr;
+ REQUIRE(rnt_branch_target(h, &target) == 0);
+ REQUIRE(take_string(target) == "");
+
+ REQUIRE(rnt_close_handle(h) == 0);
+}
+
+TEST_CASE("rnt_register_branch rejects an unregistered target hash",
+ "[step2][capi][branch]")
+{
+ InitGuard _;
+ REQUIRE(rnt_register_branch("/system/branches/test_step2_bad_init",
+ "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff")
+ != 0);
+}
+
+TEST_CASE("rnt_branch_advance rejects an unregistered target hash",
+ "[step2][capi][branch]")
+{
+ InitGuard _;
+ const char* bpath = "/system/branches/test_step2_bad_advance";
+ REQUIRE(rnt_register_branch(bpath, "") == 0);
+
+ REQUIRE(rnt_branch_advance(
+ bpath,
+ "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff") != 0);
+
+ // Target unchanged.
+ rnt_handle_t h = rnt_open_handle(bpath, nullptr);
+ REQUIRE(h != nullptr);
+ char* target = nullptr;
+ REQUIRE(rnt_branch_target(h, &target) == 0);
+ REQUIRE(take_string(target) == "");
+ rnt_close_handle(h);
+}
+
+TEST_CASE("Writing a tuple advances the branch to a new snapshot",
+ "[step2][step3][capi][branch]")
+{
+ InitGuard _;
+ const char* bpath = "/system/branches/test_step2_advance";
+ const char* rpath = "/system/branches/test_step2_advance/multigroups/public/relations/items";
+ REQUIRE(rnt_register_branch(bpath, "") == 0);
+ REQUIRE(rnt_register_relation(rpath) == 0);
+
+ // After register_relation, the branch is bound to the first snapshot.
+ rnt_handle_t h = rnt_open_handle(bpath, nullptr);
+ REQUIRE(h != nullptr);
+ char* first = nullptr;
+ REQUIRE(rnt_branch_target(h, &first) == 0);
+ const std::string first_hash = take_string(first);
+ REQUIRE(first_hash.size() == 64);
+ rnt_close_handle(h);
+
+ // A tuple write advances the branch again.
+ char* tuple_hash = nullptr;
+ REQUIRE(rnt_link_tuple(rpath, "id=1\n", &tuple_hash) == 0);
+ rnt_free_string(tuple_hash);
+
+ h = rnt_open_handle(bpath, nullptr);
+ REQUIRE(h != nullptr);
+ char* second = nullptr;
+ REQUIRE(rnt_branch_target(h, &second) == 0);
+ const std::string second_hash = take_string(second);
+ rnt_close_handle(h);
+
+ REQUIRE(second_hash.size() == 64);
+ REQUIRE(second_hash != first_hash);
+}
+
+// ---------------------------------------------------------------------------
+// Step 3+4 — Copy-on-write writes and resolver wiring
+// ---------------------------------------------------------------------------
+
+TEST_CASE("link_tuple commits a new snapshot and relation_root reflects it",
+ "[step3][capi][cow]")
+{
+ InitGuard _;
+ const char* bpath = "/system/branches/test_step3_link";
+ const char* rpath = "/system/branches/test_step3_link/multigroups/public/relations/items";
+ REQUIRE(rnt_register_branch(bpath, "") == 0);
+ REQUIRE(rnt_register_relation(rpath) == 0);
+
+ // Empty relation: root is "".
+ char* root = nullptr;
+ REQUIRE(rnt_relation_root(rpath, &root) == 0);
+ REQUIRE(take_string(root) == "");
+
+ char* tuple_hash = nullptr;
+ REQUIRE(rnt_link_tuple(rpath, "id=1\nname=alpha\n", &tuple_hash) == 0);
+ REQUIRE(tuple_hash != nullptr);
+ rnt_free_string(tuple_hash);
+
+ REQUIRE(rnt_relation_root(rpath, &root) == 0);
+ const std::string new_root = take_string(root);
+ REQUIRE(new_root.size() == 64); // a real Merkle root now
+}
+
+TEST_CASE("unlink_tuple and clear_relation walk back through new snapshots",
+ "[step3][capi][cow]")
+{
+ InitGuard _;
+ const char* bpath = "/system/branches/test_step3_unlink";
+ const char* rpath = "/system/branches/test_step3_unlink/multigroups/public/relations/items";
+ REQUIRE(rnt_register_branch(bpath, "") == 0);
+ REQUIRE(rnt_register_relation(rpath) == 0);
+
+ char* th = nullptr;
+ REQUIRE(rnt_link_tuple(rpath, "id=1\n", &th) == 0);
+ const std::string tuple_hash = take_string(th);
+
+ char* root = nullptr;
+ REQUIRE(rnt_relation_root(rpath, &root) == 0);
+ REQUIRE(take_string(root) != "");
+
+ REQUIRE(rnt_unlink_tuple(rpath, tuple_hash.c_str()) == 0);
+ REQUIRE(rnt_relation_root(rpath, &root) == 0);
+ REQUIRE(take_string(root) == "");
+
+ // After re-link and clear, root is empty again.
+ REQUIRE(rnt_link_tuple(rpath, "id=2\n", &th) == 0);
+ rnt_free_string(th);
+ REQUIRE(rnt_clear_relation(rpath) == 0);
+ REQUIRE(rnt_relation_root(rpath, &root) == 0);
+ REQUIRE(take_string(root) == "");
+}
+
+TEST_CASE("rnt_open_handle resolves branch-relative paths to snapshot relations",
+ "[step4][capi][resolver]")
+{
+ InitGuard _;
+ const char* bpath = "/system/branches/test_step4_resolve";
+ const char* rpath = "/system/branches/test_step4_resolve/multigroups/public/relations/items";
+ REQUIRE(rnt_register_branch(bpath, "") == 0);
+ REQUIRE(rnt_register_relation(rpath) == 0);
+
+ char* tuple_hash = nullptr;
+ REQUIRE(rnt_link_tuple(rpath, "id=1\n", &tuple_hash) == 0);
+ rnt_free_string(tuple_hash);
+
+ // Opening the branch-relative path resolves to the snapshot-bound entry,
+ // and a cursor reads the tuple just written.
+ rnt_handle_t h = rnt_open_handle(rpath, nullptr);
+ REQUIRE(h != nullptr);
+ rnt_cursor_t c = rnt_cursor_open(h);
+ REQUIRE(c != nullptr);
+
+ char* row = nullptr;
+ REQUIRE(rnt_cursor_next(c, &row) == 1);
+ REQUIRE(row != nullptr);
+ rnt_free_string(row);
+
+ // Exhausted on the next call.
+ REQUIRE(rnt_cursor_next(c, &row) == 0);
+ REQUIRE(row == nullptr);
+
+ rnt_cursor_close(c);
+ rnt_close_handle(h);
+}
+
+TEST_CASE("Reading an unborn branch's relation fails cleanly",
+ "[step4][capi][resolver]")
+{
+ InitGuard _;
+ const char* bpath = "/system/branches/test_step4_unborn";
+ REQUIRE(rnt_register_branch(bpath, "") == 0);
+
+ // No relation registered: relation_root miss returns nonzero.
+ char* root = nullptr;
+ REQUIRE(rnt_relation_root(
+ "/system/branches/test_step4_unborn/multigroups/public/relations/missing", &root) != 0);
+}
+
+// ---------------------------------------------------------------------------
+// Step 5 — Session lifecycle and overrides
+// ---------------------------------------------------------------------------
+
+TEST_CASE("Each rnt_session_open returns a distinct 64-char hex hash",
+ "[step5][capi][session]")
+{
+ InitGuard _;
+ char* a = nullptr;
+ char* b = nullptr;
+ REQUIRE(rnt_session_open(nullptr, &a) == 0);
+ REQUIRE(rnt_session_open(nullptr, &b) == 0);
+ const std::string ha = take_string(a);
+ const std::string hb = take_string(b);
+ REQUIRE(ha.size() == 64);
+ REQUIRE(hb.size() == 64);
+ REQUIRE(ha != hb);
+
+ REQUIRE(rnt_session_close(ha.c_str()) == 0);
+ REQUIRE(rnt_session_close(hb.c_str()) == 0);
+}
+
+TEST_CASE("rnt_session_close on an unknown hash fails",
+ "[step5][capi][session]")
+{
+ InitGuard _;
+ REQUIRE(rnt_session_close(
+ "0000000000000000000000000000000000000000000000000000000000000000") != 0);
+}
+
+TEST_CASE("Session override redirects branch-relative reads to a different snapshot",
+ "[step5][capi][session][resolver]")
+{
+ InitGuard _;
+ const char* bpath = "/system/branches/test_step5_override";
+ const char* rpath = "/system/branches/test_step5_override/multigroups/public/relations/items";
+ REQUIRE(rnt_register_branch(bpath, "") == 0);
+ REQUIRE(rnt_register_relation(rpath) == 0);
+
+ // Snapshot S1: one tuple.
+ char* th = nullptr;
+ REQUIRE(rnt_link_tuple(rpath, "id=1\n", &th) == 0);
+ rnt_free_string(th);
+
+ // Capture S1's hash and pin it via a session override before the next
+ // commit — without the override the next link_tuple would cascade-collect
+ // S1 as soon as the branch advances away from it.
+ rnt_handle_t bh = rnt_open_handle(bpath, nullptr);
+ REQUIRE(bh != nullptr);
+ char* target = nullptr;
+ REQUIRE(rnt_branch_target(bh, &target) == 0);
+ const std::string s1 = take_string(target);
+ rnt_close_handle(bh);
+
+ char* sess = nullptr;
+ REQUIRE(rnt_session_open(nullptr, &sess) == 0);
+ const std::string sid = take_string(sess);
+ REQUIRE(rnt_session_set_branch(sid.c_str(),
+ "test_step5_override",
+ s1.c_str()) == 0);
+
+ // Advance the branch to S2 — global HEAD moves on; the session override
+ // keeps S1 resident.
+ REQUIRE(rnt_link_tuple(rpath, "id=2\n", &th) == 0);
+ rnt_free_string(th);
+
+ // Session view: still S1 (one tuple).
+ const std::string spath =
+ "/system/sessions/" + sid +
+ "/branches/test_step5_override/multigroups/public/relations/items";
+
+ rnt_handle_t h_session = rnt_open_handle(spath.c_str(), nullptr);
+ REQUIRE(h_session != nullptr);
+ rnt_cursor_t c_session = rnt_cursor_open(h_session);
+ REQUIRE(c_session != nullptr);
+
+ int rows_under_session = 0;
+ char* row = nullptr;
+ while (rnt_cursor_next(c_session, &row) == 1)
+ {
+ ++rows_under_session;
+ rnt_free_string(row);
+ }
+ REQUIRE(rows_under_session == 1);
+
+ rnt_cursor_close(c_session);
+ rnt_close_handle(h_session);
+
+ // Global view sees both tuples.
+ rnt_handle_t h_global = rnt_open_handle(rpath, nullptr);
+ REQUIRE(h_global != nullptr);
+ rnt_cursor_t c_global = rnt_cursor_open(h_global);
+ REQUIRE(c_global != nullptr);
+ int rows_global = 0;
+ while (rnt_cursor_next(c_global, &row) == 1) { ++rows_global; rnt_free_string(row); }
+ REQUIRE(rows_global == 2);
+ rnt_cursor_close(c_global);
+ rnt_close_handle(h_global);
+
+ REQUIRE(rnt_session_close(sid.c_str()) == 0);
+}
+
+TEST_CASE("Clearing a session override falls back to the global branch HEAD",
+ "[step5][capi][session][resolver]")
+{
+ InitGuard _;
+ const char* bpath = "/system/branches/test_step5_clear";
+ const char* rpath = "/system/branches/test_step5_clear/multigroups/public/relations/items";
+ REQUIRE(rnt_register_branch(bpath, "") == 0);
+ REQUIRE(rnt_register_relation(rpath) == 0);
+
+ char* th = nullptr;
+ REQUIRE(rnt_link_tuple(rpath, "id=1\n", &th) == 0);
+ rnt_free_string(th);
+ rnt_handle_t bh = rnt_open_handle(bpath, nullptr);
+ REQUIRE(bh != nullptr);
+ char* target = nullptr;
+ REQUIRE(rnt_branch_target(bh, &target) == 0);
+ const std::string s1 = take_string(target);
+ rnt_close_handle(bh);
+
+ // Same pattern as above: install the override on S1 before advancing.
+ char* sess = nullptr;
+ REQUIRE(rnt_session_open(nullptr, &sess) == 0);
+ const std::string sid = take_string(sess);
+ REQUIRE(rnt_session_set_branch(sid.c_str(), "test_step5_clear", s1.c_str()) == 0);
+
+ REQUIRE(rnt_link_tuple(rpath, "id=2\n", &th) == 0);
+ rnt_free_string(th);
+
+ // Clear the override.
+ REQUIRE(rnt_session_set_branch(sid.c_str(), "test_step5_clear", "") == 0);
+
+ // Now the session sees the global view (two tuples).
+ const std::string spath =
+ "/system/sessions/" + sid +
+ "/branches/test_step5_clear/multigroups/public/relations/items";
+ rnt_handle_t h = rnt_open_handle(spath.c_str(), nullptr);
+ REQUIRE(h != nullptr);
+ rnt_cursor_t c = rnt_cursor_open(h);
+ REQUIRE(c != nullptr);
+ int rows = 0;
+ char* row = nullptr;
+ while (rnt_cursor_next(c, &row) == 1) { ++rows; rnt_free_string(row); }
+ REQUIRE(rows == 2);
+ rnt_cursor_close(c);
+ rnt_close_handle(h);
+
+ REQUIRE(rnt_session_close(sid.c_str()) == 0);
+}
+
+TEST_CASE("rnt_session_set_branch rejects an unregistered snapshot",
+ "[step5][capi][session]")
+{
+ InitGuard _;
+ char* sess = nullptr;
+ REQUIRE(rnt_session_open(nullptr, &sess) == 0);
+ const std::string sid = take_string(sess);
+
+ REQUIRE(rnt_session_set_branch(
+ sid.c_str(),
+ "anything",
+ "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff") != 0);
+
+ REQUIRE(rnt_session_close(sid.c_str()) == 0);
+}
+
+// ---------------------------------------------------------------------------
+// Multi-mg-per-branch — sibling multigroups under one branch evolve
+// independently. Inserting into one mg must not perturb the other's hash
+// or its enumerable relation set.
+// ---------------------------------------------------------------------------
+
+TEST_CASE("Two multigroups under one branch advance independently",
+ "[capi][multi-mg]")
+{
+ InitGuard _;
+ const std::string bpath = "/system/branches/test_multi_mg";
+ REQUIRE(rnt_register_branch(bpath.c_str(), "") == 0);
+
+ // Register one relation in each of two distinct multigroups.
+ REQUIRE(rnt_register_relation(
+ (bpath + "/multigroups/warehouse/relations/orders").c_str()) == 0);
+ REQUIRE(rnt_register_relation(
+ (bpath + "/multigroups/audit/relations/events").c_str()) == 0);
+
+ char* mgs_raw = nullptr;
+ REQUIRE(rnt_list_branch_multigroups(bpath.c_str(), &mgs_raw) == 0);
+ const std::string mgs = take_string(mgs_raw);
+ REQUIRE(mgs.find("warehouse\t") != std::string::npos);
+ REQUIRE(mgs.find("audit\t") != std::string::npos);
+
+ // Insert into warehouse; record audit's root before/after.
+ char* audit_before = nullptr;
+ REQUIRE(rnt_list_relations(
+ (bpath + "/multigroups/audit").c_str(), &audit_before) == 0);
+ const std::string audit_before_s = take_string(audit_before);
+
+ char* th = nullptr;
+ REQUIRE(rnt_link_tuple((bpath + "/multigroups/warehouse/relations/orders").c_str(),
+ "id=1\n", &th) == 0);
+ rnt_free_string(th);
+
+ char* audit_after = nullptr;
+ REQUIRE(rnt_list_relations(
+ (bpath + "/multigroups/audit").c_str(), &audit_after) == 0);
+ const std::string audit_after_s = take_string(audit_after);
+
+ // audit's relation set is byte-identical: the warehouse-side mutation
+ // touched only the warehouse subtree at the multigroup level.
+ REQUIRE(audit_before_s == audit_after_s);
+
+ // warehouse/orders is now non-empty.
+ char* root = nullptr;
+ REQUIRE(rnt_relation_root(
+ (bpath + "/multigroups/warehouse/relations/orders").c_str(), &root) == 0);
+ REQUIRE(!take_string(root).empty());
+
+ // audit/events still empty.
+ char* root2 = nullptr;
+ REQUIRE(rnt_relation_root(
+ (bpath + "/multigroups/audit/relations/events").c_str(), &root2) == 0);
+ REQUIRE(take_string(root2).empty());
+}
diff --git a/test/CursorManager.cpp b/test/CursorManager.cpp
new file mode 100644
index 0000000..8c7de1a
--- /dev/null
+++ b/test/CursorManager.cpp
@@ -0,0 +1,160 @@
+#include <catch2/catch_test_macros.hpp>
+
+#include "CursorManager.h"
+#include "HandlerManager.h"
+#include "IdentityManager.h"
+#include "InMemoryBackend.h"
+#include "LifecycleManager.h"
+#include "Merkle.h"
+#include "MultigroupCodec.h"
+#include "NamespaceReferenceManager.h"
+#include "ObjectManager.h"
+#include "PermissionsManager.h"
+#include "TupleCodec.h"
+
+#include <memory>
+
+// ---------------------------------------------------------------------------
+// Step 6 / cursor-independence follow-up
+//
+// Two things to verify:
+// 1. A cursor opened on a /system/snapshots/<H>/relations/<n> relation
+// pins the parent Multigroup for its lifetime; releasing the cursor
+// releases the pin.
+// 2. Closing the handle a cursor was opened from no longer dereferences
+// a freed handle pointer inside Next() — the cursor captures the type
+// label and the ephemeral generator at Open time, so iteration after
+// the handle's death is degenerate but safe.
+// ---------------------------------------------------------------------------
+
+namespace
+{
+ std::unique_ptr<nt::ObjectManager::object_type> make_type(OBJECT_TYPE label)
+ {
+ auto t = std::make_unique<nt::ObjectManager::object_type>();
+ t->label = label;
+ t->methods = { OPEN, CLOSE };
+ return t;
+ }
+
+ std::unique_ptr<nt::ObjectManager::ephemeral_object_type>
+ make_constant_eph_type(std::vector<nt::Attribute> attrs)
+ {
+ auto t = std::make_unique<nt::ObjectManager::ephemeral_object_type>();
+ t->label = EPHEMERAL_RELATION;
+ t->methods = { OPEN, CLOSE };
+ t->cardinality = nt::ObjectManager::ephemeral_object_type::Cardinality::Finite;
+ t->generator = [attrs](const std::vector<std::string>&,
+ std::size_t offset, std::size_t limit)
+ -> std::vector<nt::Tuple>
+ {
+ if (offset > 0 || limit == 0) return {};
+ return { nt::Tuple(attrs) };
+ };
+ return t;
+ }
+
+ struct Stack {
+ nt::InMemoryBackend backend;
+ nt::ObjectManager objects;
+ nt::PermissionsManager permissions;
+ nt::IdentityManager identities;
+ nt::LifecycleManager lifecycles { objects, backend };
+ nt::NamespaceReferenceManager references { objects, backend };
+ nt::HandlerManager handler { objects, permissions, identities,
+ lifecycles, references };
+ nt::CursorManager cursors { backend, &lifecycles, &objects };
+ };
+}
+
+TEST_CASE("Cursor pins the parent snapshot and unpins on close",
+ "[step6][cursor][pin]")
+{
+ Stack s;
+
+ // Stand up a minimal snapshot with one relation.
+ auto& om = s.objects;
+ om.Register({"system", "snapshots", "Hcur"},
+ std::make_unique<nt::ObjectManager::Multigroup>(), make_type(MULTIGROUP));
+ om.Register({"system", "snapshots", "Hcur", "relations", "items"},
+ std::make_unique<nt::ObjectManager::Relation>(), make_type(RELATION));
+
+ auto* mg_entry = om.Find({"system", "snapshots", "Hcur"});
+ auto* rel_entry = om.Find({"system", "snapshots", "Hcur", "relations", "items"});
+
+ // Parent's pin on the child Relation (mirrors register_snapshot in the C
+ // API). An external pin on the Multigroup simulates a branch holding the
+ // snapshot — without it, closing the cursor would drop ref_count to 0 and
+ // cascade-collect mg_entry mid-test.
+ s.lifecycles.Pin(rel_entry);
+ s.lifecycles.Pin(mg_entry);
+
+ // Open a handle and a cursor on the child Relation.
+ int conn = 1;
+ auto* h = s.handler.Open({"system", "snapshots", "Hcur", "relations", "items"}, &conn);
+ REQUIRE(h != nullptr);
+ REQUIRE(mg_entry->head->reference_count == 1); // external pin only
+
+ auto* c = s.cursors.Open(h);
+ REQUIRE(c != nullptr);
+ REQUIRE(c->pinned_snapshot == mg_entry);
+ REQUIRE(mg_entry->head->reference_count == 2); // external + cursor pin
+
+ s.cursors.Close(c);
+ REQUIRE(mg_entry->head->reference_count == 1); // back to external only
+
+ s.handler.Close(h);
+ s.lifecycles.Unpin(mg_entry); // releases the external pin; cascade-collects.
+}
+
+TEST_CASE("Closing the handle mid-iteration does not crash an ephemeral cursor",
+ "[step6][cursor][handle-independence]")
+{
+ Stack s;
+ // Register an ephemeral relation; its generator yields one tuple.
+ s.objects.Register({"eph"},
+ std::make_unique<nt::ObjectManager::Relation>(),
+ make_constant_eph_type({{"k", "v"}}));
+
+ int conn = 1;
+ auto* h = s.handler.Open({"eph"}, &conn);
+ REQUIRE(h != nullptr);
+ auto* c = s.cursors.Open(h);
+ REQUIRE(c != nullptr);
+
+ // Ephemeral cursors start exhausted; reset to simulate a JOIN probe.
+ c->exhausted = false;
+ c->args = {};
+
+ // Now violate the documented contract: close the handle BEFORE Next().
+ // The cursor must still produce its tuple from the captured generator
+ // without dereferencing the freed handle.
+ s.handler.Close(h);
+
+ auto* tuple = s.cursors.Next(c);
+ REQUIRE(tuple != nullptr);
+ bool found = false;
+ for (const auto& a : tuple->attrs())
+ if (a.name == "k" && a.value == "v") { found = true; break; }
+ REQUIRE(found);
+
+ s.cursors.Close(c);
+}
+
+TEST_CASE("Cursor opened against a non-snapshot relation does not pin anything",
+ "[step6][cursor][pin]")
+{
+ Stack s;
+ s.objects.Register({"plain", "rel"},
+ std::make_unique<nt::ObjectManager::Relation>(),
+ make_type(RELATION));
+ int conn = 1;
+ auto* h = s.handler.Open({"plain", "rel"}, &conn);
+ REQUIRE(h != nullptr);
+ auto* c = s.cursors.Open(h);
+ REQUIRE(c != nullptr);
+ REQUIRE(c->pinned_snapshot == nullptr);
+
+ s.cursors.Close(c);
+ s.handler.Close(h);
+}
diff --git a/test/LifecycleManager.cpp b/test/LifecycleManager.cpp
new file mode 100644
index 0000000..aa75e14
--- /dev/null
+++ b/test/LifecycleManager.cpp
@@ -0,0 +1,185 @@
+#include <catch2/catch_test_macros.hpp>
+
+#include "InMemoryBackend.h"
+#include "LifecycleManager.h"
+#include "ObjectManager.h"
+
+#include <memory>
+
+// ---------------------------------------------------------------------------
+// Step 6 — Pin/Unpin and the cascade
+//
+// LifecycleManager owns object lifetime. Pin/Unpin adjust reference_count;
+// Monitor/Unmonitor adjust handle_count. Both decrement paths call into
+// TryCollect, which gates GC on the joint condition (both counters zero)
+// and, for MULTIGROUP entries, cascades through CascadeMultigroup to
+// unpin every Relation registered under their snapshot subtree.
+// ---------------------------------------------------------------------------
+
+namespace
+{
+ std::unique_ptr<nt::ObjectManager::object_type> make_type(OBJECT_TYPE label)
+ {
+ auto t = std::make_unique<nt::ObjectManager::object_type>();
+ t->label = label;
+ t->methods = { OPEN, CLOSE };
+ return t;
+ }
+}
+
+TEST_CASE("Pin and Unpin adjust reference_count symmetrically",
+ "[step6][lifecycle][pin]")
+{
+ nt::InMemoryBackend store;
+ nt::ObjectManager om;
+ nt::LifecycleManager lm(om, store);
+ om.Register({"r1"}, std::make_unique<nt::ObjectManager::Relation>(), make_type(RELATION));
+ auto* entry = om.Find({"r1"});
+ REQUIRE(entry->head->reference_count == 0);
+
+ lm.Pin(entry);
+ lm.Pin(entry);
+ REQUIRE(entry->head->reference_count == 2);
+
+ lm.Unpin(entry);
+ REQUIRE(entry->head->reference_count == 1);
+
+ // Still alive at ref_count=1.
+ REQUIRE(om.Find({"r1"}) != nullptr);
+}
+
+TEST_CASE("Pin on nullptr is a no-op", "[step6][lifecycle][pin]")
+{
+ nt::InMemoryBackend store;
+ nt::ObjectManager om;
+ nt::LifecycleManager lm(om, store);
+ REQUIRE_NOTHROW(lm.Pin(nullptr));
+ REQUIRE_NOTHROW(lm.Unpin(nullptr));
+}
+
+TEST_CASE("Unpin below zero does not underflow", "[step6][lifecycle][pin]")
+{
+ nt::InMemoryBackend store;
+ nt::ObjectManager om;
+ nt::LifecycleManager lm(om, store);
+ om.Register({"r1"}, std::make_unique<nt::ObjectManager::Relation>(), make_type(RELATION));
+ auto* entry = om.Find({"r1"});
+
+ lm.Unpin(entry);
+ REQUIRE(entry->head->reference_count == 0);
+}
+
+TEST_CASE("GC is gated on both counters reaching zero", "[step6][lifecycle][gc]")
+{
+ nt::InMemoryBackend store;
+ nt::ObjectManager om;
+ nt::LifecycleManager lm(om, store);
+ om.Register({"r1"}, std::make_unique<nt::ObjectManager::Relation>(), make_type(RELATION));
+ auto* entry = om.Find({"r1"});
+
+ lm.Monitor(entry);
+ lm.Pin(entry);
+
+ // handle_count=1, ref_count=1.
+ lm.Unpin(entry); // ref_count → 0, but handle_count still 1.
+ REQUIRE(om.Find({"r1"}) != nullptr);
+
+ lm.Pin(entry);
+ lm.Unmonitor(entry); // handle_count → 0, but ref_count still 1.
+ REQUIRE(om.Find({"r1"}) != nullptr);
+
+ lm.Unpin(entry); // both zero → GC.
+ REQUIRE(om.Find({"r1"}) == nullptr);
+}
+
+TEST_CASE("Unmonitor that brings both counters to zero collects the entry",
+ "[step6][lifecycle][gc]")
+{
+ nt::InMemoryBackend store;
+ nt::ObjectManager om;
+ nt::LifecycleManager lm(om, store);
+ om.Register({"r1"}, std::make_unique<nt::ObjectManager::Relation>(), make_type(RELATION));
+ auto* entry = om.Find({"r1"});
+
+ lm.Monitor(entry);
+ REQUIRE(entry->head->handle_count == 1);
+ lm.Unmonitor(entry);
+ REQUIRE(om.Find({"r1"}) == nullptr);
+}
+
+TEST_CASE("IsEligibleForGC reflects the joint-zero rule",
+ "[step6][lifecycle][gc]")
+{
+ nt::InMemoryBackend store;
+ nt::ObjectManager om;
+ nt::LifecycleManager lm(om, store);
+ om.Register({"r1"}, std::make_unique<nt::ObjectManager::Relation>(), make_type(RELATION));
+ auto* entry = om.Find({"r1"});
+
+ REQUIRE(lm.IsEligibleForGC(entry));
+ lm.Pin(entry);
+ REQUIRE_FALSE(lm.IsEligibleForGC(entry));
+}
+
+TEST_CASE("CascadeMultigroup unpins child Relations on snapshot collection",
+ "[step6][lifecycle][cascade]")
+{
+ nt::InMemoryBackend store;
+ nt::ObjectManager om;
+ nt::LifecycleManager lm(om, store);
+
+ om.Register({"system", "snapshots", "H1"},
+ std::make_unique<nt::ObjectManager::Multigroup>(), make_type(MULTIGROUP));
+ auto* mg_entry = om.Find({"system", "snapshots", "H1"});
+
+ for (const auto& n : { std::string{"foo"}, std::string{"bar"} })
+ {
+ om.Register({"system", "snapshots", "H1", "relations", n},
+ std::make_unique<nt::ObjectManager::Relation>(),
+ make_type(RELATION));
+ // The parent Multigroup's pin on each child, mirroring what
+ // register_snapshot does in the C API layer.
+ lm.Pin(om.Find({"system", "snapshots", "H1", "relations", n}));
+ }
+ REQUIRE(om.Find({"system", "snapshots", "H1", "relations", "foo"}) != nullptr);
+ REQUIRE(om.Find({"system", "snapshots", "H1", "relations", "bar"}) != nullptr);
+
+ // One external pin on the Multigroup (e.g. a branch). Release it: cascade.
+ lm.Pin(mg_entry);
+ lm.Unpin(mg_entry);
+
+ REQUIRE(om.Find({"system", "snapshots", "H1"}) == nullptr);
+ REQUIRE(om.Find({"system", "snapshots", "H1", "relations", "foo"}) == nullptr);
+ REQUIRE(om.Find({"system", "snapshots", "H1", "relations", "bar"}) == nullptr);
+}
+
+TEST_CASE("Cascade survives a child with an open handle",
+ "[step6][lifecycle][cascade]")
+{
+ nt::InMemoryBackend store;
+ nt::ObjectManager om;
+ nt::LifecycleManager lm(om, store);
+
+ om.Register({"system", "snapshots", "H2"},
+ std::make_unique<nt::ObjectManager::Multigroup>(), make_type(MULTIGROUP));
+ auto* mg_entry = om.Find({"system", "snapshots", "H2"});
+
+ om.Register({"system", "snapshots", "H2", "relations", "live"},
+ std::make_unique<nt::ObjectManager::Relation>(),
+ make_type(RELATION));
+ auto* child = om.Find({"system", "snapshots", "H2", "relations", "live"});
+ lm.Pin(child); // parent's pin
+ lm.Monitor(child); // simulate an open handle on the child
+
+ // Drop the Multigroup's external ref: cascade unpins child (ref → 0),
+ // but handle_count is still 1 — child must survive.
+ lm.Pin(mg_entry);
+ lm.Unpin(mg_entry);
+
+ REQUIRE(om.Find({"system", "snapshots", "H2"}) == nullptr);
+ REQUIRE(om.Find({"system", "snapshots", "H2", "relations", "live"}) != nullptr);
+
+ // Closing the handle now releases the child.
+ lm.Unmonitor(child);
+ REQUIRE(om.Find({"system", "snapshots", "H2", "relations", "live"}) == nullptr);
+}
diff --git a/test/MultigroupCodec.cpp b/test/MultigroupCodec.cpp
new file mode 100644
index 0000000..25c8b53
--- /dev/null
+++ b/test/MultigroupCodec.cpp
@@ -0,0 +1,145 @@
+#include <catch2/catch_test_macros.hpp>
+
+#include "InMemoryBackend.h"
+#include "MultigroupCodec.h"
+
+#include <string>
+#include <vector>
+
+// ---------------------------------------------------------------------------
+// Multigroup snapshot — Merkle<string> tree mapping relation name → relation root.
+//
+// The codec is a thin facade over Merkle<std::string>; these tests confirm
+// the tree is order-independent (it sorts intrinsically), that mutations are
+// path-localised (sibling entries are untouched), and that snapshots can be
+// re-enumerated from a cold backend by hash alone.
+// ---------------------------------------------------------------------------
+
+namespace {
+
+// Pad a short label into a deterministic 64-char hex string so the codec can
+// decode it as a 32-byte payload.
+std::string mk_root(char c, char d = '0')
+{
+ std::string h(64, '0');
+ h[0] = c;
+ h[1] = d;
+ return h;
+}
+
+} // namespace
+
+TEST_CASE("Build is order-independent — tree sorts intrinsically",
+ "[multigroup-codec]")
+{
+ nt::InMemoryBackend a, b;
+
+ std::vector<nt::MultigroupCodec::RelationEntry> in_order = {
+ {"alpha", mk_root('a')},
+ {"bravo", mk_root('b')},
+ {"charlie", mk_root('c')},
+ };
+ std::vector<nt::MultigroupCodec::RelationEntry> shuffled = {
+ {"charlie", mk_root('c')},
+ {"alpha", mk_root('a')},
+ {"bravo", mk_root('b')},
+ };
+
+ REQUIRE(nt::MultigroupCodec::Build(a, in_order)
+ == nt::MultigroupCodec::Build(b, shuffled));
+}
+
+TEST_CASE("Build distinguishes content changes", "[multigroup-codec]")
+{
+ nt::InMemoryBackend backend;
+
+ std::vector<nt::MultigroupCodec::RelationEntry> base = {{"foo", mk_root('a')}};
+ std::vector<nt::MultigroupCodec::RelationEntry> different_root = {{"foo", mk_root('b')}};
+ std::vector<nt::MultigroupCodec::RelationEntry> different_name = {{"bar", mk_root('a')}};
+ std::vector<nt::MultigroupCodec::RelationEntry> extra_member = {
+ {"foo", mk_root('a')}, {"bar", mk_root('b')}
+ };
+
+ const auto h_base = nt::MultigroupCodec::Build(backend, base);
+ REQUIRE(h_base != nt::MultigroupCodec::Build(backend, different_root));
+ REQUIRE(h_base != nt::MultigroupCodec::Build(backend, different_name));
+ REQUIRE(h_base != nt::MultigroupCodec::Build(backend, extra_member));
+}
+
+TEST_CASE("Build then List round-trips entries in key-sorted order",
+ "[multigroup-codec]")
+{
+ nt::InMemoryBackend backend;
+
+ std::vector<nt::MultigroupCodec::RelationEntry> entries = {
+ {"foo", mk_root('a', '1')},
+ {"bar", mk_root('b', '2')},
+ {"baz", mk_root('c', '3')},
+ };
+ const auto root = nt::MultigroupCodec::Build(backend, entries);
+
+ auto listed = nt::MultigroupCodec::List(backend, root);
+ REQUIRE(listed.size() == 3);
+ REQUIRE(listed[0].first == "bar");
+ REQUIRE(listed[1].first == "baz");
+ REQUIRE(listed[2].first == "foo");
+ REQUIRE(listed[0].second == mk_root('b', '2'));
+}
+
+TEST_CASE("Lookup returns payload by name", "[multigroup-codec]")
+{
+ nt::InMemoryBackend backend;
+
+ std::vector<nt::MultigroupCodec::RelationEntry> entries = {
+ {"foo", mk_root('a')},
+ {"bar", mk_root('b')},
+ };
+ const auto root = nt::MultigroupCodec::Build(backend, entries);
+
+ REQUIRE(nt::MultigroupCodec::Lookup(backend, root, "foo") == mk_root('a'));
+ REQUIRE(nt::MultigroupCodec::Lookup(backend, root, "bar") == mk_root('b'));
+ REQUIRE(nt::MultigroupCodec::Lookup(backend, root, "missing").empty());
+}
+
+TEST_CASE("InsertOne mutates one entry; sibling subtree is untouched",
+ "[multigroup-codec]")
+{
+ nt::InMemoryBackend backend;
+
+ std::vector<nt::MultigroupCodec::RelationEntry> entries = {
+ {"foo", mk_root('a')},
+ {"bar", mk_root('b')},
+ };
+ const auto root0 = nt::MultigroupCodec::Build(backend, entries);
+
+ // Mutate foo only; bar's payload must round-trip unchanged.
+ const auto root1 = nt::MultigroupCodec::InsertOne(
+ backend, root0, "foo", mk_root('d'));
+ REQUIRE(root1 != root0);
+ REQUIRE(nt::MultigroupCodec::Lookup(backend, root1, "foo") == mk_root('d'));
+ REQUIRE(nt::MultigroupCodec::Lookup(backend, root1, "bar") == mk_root('b'));
+}
+
+TEST_CASE("RemoveOne deletes one entry; sibling preserved",
+ "[multigroup-codec]")
+{
+ nt::InMemoryBackend backend;
+
+ std::vector<nt::MultigroupCodec::RelationEntry> entries = {
+ {"foo", mk_root('a')},
+ {"bar", mk_root('b')},
+ };
+ const auto root0 = nt::MultigroupCodec::Build(backend, entries);
+
+ const auto root1 = nt::MultigroupCodec::RemoveOne(backend, root0, "foo");
+ REQUIRE(nt::MultigroupCodec::Lookup(backend, root1, "foo").empty());
+ REQUIRE(nt::MultigroupCodec::Lookup(backend, root1, "bar") == mk_root('b'));
+}
+
+TEST_CASE("Empty multigroup builds to an empty root", "[multigroup-codec]")
+{
+ nt::InMemoryBackend backend;
+ std::vector<nt::MultigroupCodec::RelationEntry> empty;
+ REQUIRE(nt::MultigroupCodec::Build(backend, empty).empty());
+ REQUIRE(nt::MultigroupCodec::List(backend, "").empty());
+}
diff --git a/test/NamespaceReferenceManager.cpp b/test/NamespaceReferenceManager.cpp
new file mode 100644
index 0000000..27f0dcd
--- /dev/null
+++ b/test/NamespaceReferenceManager.cpp
@@ -0,0 +1,203 @@
+#include <catch2/catch_test_macros.hpp>
+
+#include "InMemoryBackend.h"
+#include "Merkle.h"
+#include "NamespaceReferenceManager.h"
+#include "ObjectManager.h"
+
+#include <memory>
+
+// ---------------------------------------------------------------------------
+// Resolver — two-level reparse through the branch tree.
+//
+// NamespaceReferenceManager::Resolve rewrites
+// /system/branches/<name>/multigroups/<mg>/<sub>...
+// into
+// /system/snapshots/<mg_hash>/<sub>...
+// by reading branch.target_hash (a Merkle<string> root) from storage and
+// looking up <mg>. Session paths consult the per-session override map first
+// and fall back to the global branch when no override is set.
+// ---------------------------------------------------------------------------
+
+namespace {
+
+using Path = std::vector<std::string>;
+
+// Pad a label into a deterministic 64-char hex string so the merkle codec can
+// decode it as a 32-byte payload.
+std::string mk_hash(char c, char d = '0')
+{
+ std::string h(64, '0');
+ h[0] = c;
+ h[1] = d;
+ return h;
+}
+
+std::unique_ptr<nt::ObjectManager::object_type> make_type(OBJECT_TYPE label)
+{
+ auto t = std::make_unique<nt::ObjectManager::object_type>();
+ t->label = label;
+ t->methods = { OPEN, CLOSE };
+ return t;
+}
+
+void register_branch(nt::ObjectManager& om,
+ const std::string& name,
+ const std::string& target_hash)
+{
+ auto br = std::make_unique<nt::ObjectManager::Branch>();
+ br->name = name;
+ br->target_hash = target_hash;
+ om.Register({"system", "branches", name}, std::move(br), make_type(BRANCH));
+}
+
+void register_session(nt::ObjectManager& om,
+ const std::string& id,
+ std::map<std::string, std::string> overrides = {})
+{
+ auto s = std::make_unique<nt::ObjectManager::Session>();
+ s->branch_overrides = std::move(overrides);
+ om.Register({"system", "sessions", id}, std::move(s), make_type(SESSION));
+}
+
+// Builds a branch tree with a single (mg_name → mg_hash) entry. Returns the
+// branch-tree root hex.
+std::string build_branch_tree(nt::InMemoryBackend& store,
+ const std::string& mg_name,
+ const std::string& mg_hash_hex)
+{
+ return nt::Merkle<std::string>::Insert(store, "", mg_name,
+ nt::hex_to_bin(mg_hash_hex));
+}
+
+} // namespace
+
+TEST_CASE("Branch sub-path rewrites through the branch tree to the mg snapshot",
+ "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+
+ const std::string mg_hash = mk_hash('a');
+ const std::string tree = build_branch_tree(store, "warehouse", mg_hash);
+ register_branch(om, "main", tree);
+
+ nt::NamespaceReferenceManager nrm(om, store);
+ REQUIRE(nrm.Resolve({"system", "branches", "main", "multigroups", "warehouse", "relations", "items"})
+ == Path{"system", "snapshots", mg_hash, "relations", "items"});
+}
+
+TEST_CASE("Resolve on the branch object itself is left unchanged", "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+ const std::string tree = build_branch_tree(store, "warehouse", mk_hash('a'));
+ register_branch(om, "main", tree);
+
+ nt::NamespaceReferenceManager nrm(om, store);
+ const Path p{"system", "branches", "main"};
+ REQUIRE(nrm.Resolve(p) == p);
+}
+
+TEST_CASE("Resolve on an unborn branch leaves the path unchanged", "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+ register_branch(om, "main", ""); // unborn
+
+ nt::NamespaceReferenceManager nrm(om, store);
+ const Path p{"system", "branches", "main", "multigroups", "warehouse", "relations", "items"};
+ REQUIRE(nrm.Resolve(p) == p);
+}
+
+TEST_CASE("Resolve on an absent multigroup leaves the path unchanged", "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+ const std::string tree = build_branch_tree(store, "warehouse", mk_hash('a'));
+ register_branch(om, "main", tree);
+
+ nt::NamespaceReferenceManager nrm(om, store);
+ const Path p{"system", "branches", "main", "multigroups", "audit", "relations", "events"};
+ REQUIRE(nrm.Resolve(p) == p);
+}
+
+TEST_CASE("Resolve on an unknown branch leaves the path unchanged", "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+ nt::NamespaceReferenceManager nrm(om, store);
+ const Path p{"system", "branches", "ghost", "multigroups", "warehouse", "relations", "items"};
+ REQUIRE(nrm.Resolve(p) == p);
+}
+
+TEST_CASE("Non-branch paths pass through unchanged", "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+ nt::NamespaceReferenceManager nrm(om, store);
+ const Path p{"relations", "anywhere"};
+ REQUIRE(nrm.Resolve(p) == p);
+}
+
+TEST_CASE("Session override takes precedence over the global branch HEAD",
+ "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+
+ const std::string mg_global = mk_hash('a');
+ const std::string mg_session = mk_hash('b');
+ const std::string tree_global =
+ build_branch_tree(store, "warehouse", mg_global);
+ const std::string tree_session =
+ build_branch_tree(store, "warehouse", mg_session);
+
+ register_branch(om, "main", tree_global);
+ register_session(om, "sess123", {{"main", tree_session}});
+
+ nt::NamespaceReferenceManager nrm(om, store);
+ REQUIRE(nrm.Resolve({"system", "sessions", "sess123", "branches", "main",
+ "multigroups", "warehouse", "relations", "items"})
+ == Path{"system", "snapshots", mg_session, "relations", "items"});
+}
+
+TEST_CASE("Session resolution falls back to global branch when override is absent",
+ "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+
+ const std::string mg_global = mk_hash('a');
+ const std::string tree_global =
+ build_branch_tree(store, "warehouse", mg_global);
+
+ register_branch(om, "main", tree_global);
+ register_session(om, "sess123"); // no overrides
+
+ nt::NamespaceReferenceManager nrm(om, store);
+ REQUIRE(nrm.Resolve({"system", "sessions", "sess123", "branches", "main",
+ "multigroups", "warehouse", "relations", "items"})
+ == Path{"system", "snapshots", mg_global, "relations", "items"});
+}
+
+TEST_CASE("Session resolution with neither override nor global branch is unchanged",
+ "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+ register_session(om, "sess123");
+
+ nt::NamespaceReferenceManager nrm(om, store);
+ const Path p{"system", "sessions", "sess123", "branches", "main",
+ "multigroups", "warehouse", "relations", "items"};
+ REQUIRE(nrm.Resolve(p) == p);
+}
+
+TEST_CASE("Empty input path is returned unchanged", "[resolve]")
+{
+ nt::ObjectManager om;
+ nt::InMemoryBackend store;
+ nt::NamespaceReferenceManager nrm(om, store);
+ REQUIRE(nrm.Resolve({}).empty());
+}
diff --git a/test/ObjectManager.cpp b/test/ObjectManager.cpp
new file mode 100644
index 0000000..e97bcb2
--- /dev/null
+++ b/test/ObjectManager.cpp
@@ -0,0 +1,75 @@
+#include <catch2/catch_test_macros.hpp>
+
+#include "ObjectManager.h"
+
+#include <memory>
+
+// ---------------------------------------------------------------------------
+// Step 5 — Unregister
+//
+// Sessions are disposable and must be removable from the registry on close.
+// Unregister is the splice-out primitive that rnt_session_close, the
+// LifecycleManager TryCollect path, and any future explicit-delete API all
+// share.
+// ---------------------------------------------------------------------------
+
+namespace
+{
+ std::unique_ptr<nt::ObjectManager::object_type> session_type()
+ {
+ auto t = std::make_unique<nt::ObjectManager::object_type>();
+ t->label = SESSION;
+ t->disposable = true;
+ t->methods = { OPEN, CLOSE };
+ return t;
+ }
+}
+
+TEST_CASE("Unregister removes the entry and Find returns nullptr", "[step5][object-manager]")
+{
+ nt::ObjectManager om;
+ om.Register({"system", "sessions", "alpha"},
+ std::make_unique<nt::ObjectManager::Session>(),
+ session_type());
+ REQUIRE(om.Find({"system", "sessions", "alpha"}) != nullptr);
+
+ REQUIRE(om.Unregister({"system", "sessions", "alpha"}) == true);
+ REQUIRE(om.Find({"system", "sessions", "alpha"}) == nullptr);
+}
+
+TEST_CASE("Unregister returns false for missing paths", "[step5][object-manager]")
+{
+ nt::ObjectManager om;
+ REQUIRE(om.Unregister({"never", "registered"}) == false);
+}
+
+TEST_CASE("Unregister splices a middle entry without disturbing neighbours",
+ "[step5][object-manager]")
+{
+ nt::ObjectManager om;
+ om.Register({"a"}, std::make_unique<nt::ObjectManager::Session>(), session_type());
+ om.Register({"b"}, std::make_unique<nt::ObjectManager::Session>(), session_type());
+ om.Register({"c"}, std::make_unique<nt::ObjectManager::Session>(), session_type());
+
+ REQUIRE(om.Unregister({"b"}) == true);
+
+ REQUIRE(om.Find({"a"}) != nullptr);
+ REQUIRE(om.Find({"b"}) == nullptr);
+ REQUIRE(om.Find({"c"}) != nullptr);
+}
+
+TEST_CASE("Unregister at the head of the list works", "[step5][object-manager]")
+{
+ nt::ObjectManager om;
+ om.Register({"first"}, std::make_unique<nt::ObjectManager::Session>(), session_type());
+ om.Register({"second"}, std::make_unique<nt::ObjectManager::Session>(), session_type());
+
+ // The most recently registered entry is the list head (LIFO).
+ REQUIRE(om.Unregister({"second"}) == true);
+ REQUIRE(om.Find({"second"}) == nullptr);
+ REQUIRE(om.Find({"first"}) != nullptr);
+
+ // And the new head is removable too.
+ REQUIRE(om.Unregister({"first"}) == true);
+ REQUIRE(om.Find({"first"}) == nullptr);
+}
diff --git a/test/VM.cpp b/test/VM.cpp
index 00361cb..b0a602f 100644
--- a/test/VM.cpp
+++ b/test/VM.cpp
@@ -6,6 +6,7 @@
#include "InMemoryBackend.h"
#include "LifecycleManager.h"
#include "Merkle.h"
+#include "NamespaceReferenceManager.h"
#include "ObjectManager.h"
#include "PermissionsManager.h"
#include "TupleCodec.h"
@@ -32,7 +33,9 @@ static void store_tuple(nt::InMemoryBackend& backend,
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);
+ auto hash_bin = nt::hex_to_bin(hash);
+ rel->merkle_root = nt::Merkle<nt::Hash32>::Insert(backend, rel->merkle_root,
+ hash_bin, hash_bin);
}
static std::unique_ptr<nt::ObjectManager::object_type> make_relation_type()
@@ -74,9 +77,10 @@ struct Fixture
nt::ObjectManager objects;
nt::PermissionsManager permissions;
nt::IdentityManager identities;
- nt::LifecycleManager lifecycles;
- nt::HandlerManager handler { objects, permissions, identities, lifecycles };
- nt::CursorManager cursors { backend };
+ nt::LifecycleManager lifecycles { objects, backend };
+ nt::NamespaceReferenceManager references { objects, backend };
+ nt::HandlerManager handler { objects, permissions, identities, lifecycles, references };
+ nt::CursorManager cursors { backend, &lifecycles, &objects };
int conn = 1;
};