sqlite backend with actual pagination

5 files changed, 269 insertions, 47 deletions

diff --git a/include/CursorManager.h b/include/CursorManager.h
index 78ea24c..5636d8d 100644
--- a/include/CursorManager.h
+++ b/include/CursorManager.h
@@ -2,10 +2,10 @@
 
 #include "Api.h"
 #include "HandlerManager.h"
+#include "IStorageBackend.h"
 #include "Types.h"
 
-#include <string>
-#include <unordered_map>
+#include <cstddef>
 #include <vector>
 
 /**
@@ -17,55 +17,54 @@ namespace nt
 {
     /**
      * @class CursorManager
-     * @brief Orchestrates data pagination from storage backends to the query executor.
+     * @brief Orchestrates paginated data retrieval from a storage backend.
      *
-     * The cursor manager is the glue between registry objects and the
-     * Volcano-style iterator model. It translates high-level plan requests into
-     * low-level backend operations such as LMDB or etcd reads.
+     * CursorManager depends only on IStorageBackend. The concrete backend
+     * (SqliteBackend, InMemoryBackend, …) is injected at construction time.
      *
-     * Responsibilities:
-     * - Snapshot anchoring and pins: bind retrieval to a multigroup snapshot.
-     *   The snapshot object should hold the reference to the tree containing
-     *   all relations and tuples.
-     *
-     * - State maintenance: track the current iterator or offset inside a
-     *   relation to support sequential Next() calls from the algebra engine.
-     *
-     * - Prefetching and buffering: abstract backend paging. For remote
-     *   backends like etcd, manage local buffers to hide latency from the
-     *   executor. Think of this as a database equivalent of an operating-system
-     *   driver.
-     *
-     * - Boundary enforcement: ensure scans do not cross commit boundaries or
-     *   logical branch definitions unless explicitly requested by the plan.
+     * Tuples are never loaded all at once. Open() fetches the first page;
+     * each subsequent Next() call transparently fetches the next page from
+     * the backend once the current page is exhausted.
      */
     class NT_API CursorManager
     {
     public:
-        /** @brief Active scan state for a single relation. */
+        static constexpr std::size_t PAGE_SIZE = 1;
+
+        /** @brief Constructs a CursorManager that reads from the given backend. */
+        explicit CursorManager(IStorageBackend& backend);
+
+        /**
+         * @brief Active scan state for a single relation.
+         *
+         * Holds one page of deserialized tuples at a time. When page_position
+         * reaches the end of the page, Next() discards the page and fetches
+         * the next one from the backend.
+         *
+         * The pointer returned by Next() is valid only until the next Next()
+         * or Close() call — a page replacement invalidates all prior pointers.
+         */
         struct cursor {
-            /** Handle that authorized this cursor. */
-            HandlerManager::handle* handle;
-            // TODO: Replace with a lazy iterator into the physical storage backend.
-            // Pre-loading all tuples on Open() is a mock simplification.
-            std::vector<Tuple> tuples;
-            size_t position = 0;
+            HandlerManager::handle* handle = nullptr;
+            std::vector<Tuple> page;
+            std::size_t page_position = 0;
+            std::size_t fetch_offset  = 0;   // next TupleHashes() call starts here
+            bool exhausted = false;
         };
 
         /**
          * @brief Opens a cursor on the relation referenced by the handle.
-         * @param handle Authorized handle to a RELATION object.
-         * @return A new cursor, or nullptr if the object is not a RELATION.
+         *
+         * Fetches the first page immediately. Returns nullptr if the relation
+         * has no tuples or the handle does not refer to a RELATION.
          */
         cursor* Open(HandlerManager::handle* handle);
 
         /**
          * @brief Pulls the next tuple from the cursor.
          *
-         * The returned pointer is valid until the next Next() or Close() call.
-         *
-         * @param cursor Active cursor.
-         * @return Pointer to the next tuple, or nullptr when exhausted.
+         * Fetches the next page from the backend transparently when the
+         * current page is exhausted. Returns nullptr when all pages are done.
          */
         Tuple* Next(cursor* cursor);
 
@@ -75,19 +74,11 @@ namespace nt
          */
         void Close(cursor* cursor);
 
-        /**
-         * @brief Inserts one tuple into the mock store for a given relation path.
-         *
-         * TODO: Replace with physical storage writes when the backend is wired up.
-         *
-         * @param path  Logical path of the relation.
-         * @param tuple Attribute values for the tuple to insert.
-         */
-        void MockInsert(std::vector<std::string> path, std::vector<Attribute> tuple);
-
     private:
-        // TODO: Replace with physical storage backend access.
-        // Keyed by the relation path joined as "seg/seg/...".
-        std::unordered_map<std::string, std::vector<std::vector<Attribute>>> mock_store_;
+        IStorageBackend& backend_;
+
+        /** Fetches a page of hashes, resolves each from the KV store, and
+         *  deserializes them into cursor->page. Clears the existing page. */
+        void LoadPage(cursor* c, const std::vector<std::string>& path);
     };
 }
diff --git a/include/IStorageBackend.h b/include/IStorageBackend.h
new file mode 100644
index 0000000..884af2d
--- /dev/null
+++ b/include/IStorageBackend.h
@@ -0,0 +1,76 @@
+#pragma once
+
+#include <cstdint>
+#include <optional>
+#include <string>
+#include <vector>
+
+/**
+ * @file IStorageBackend.h
+ * @brief Abstract KV storage backend consumed by CursorManager.
+ *
+ * Storage is strictly content-addressed: every value is stored under its
+ * SHA256 hex digest. This mirrors the Sakura physical layer in which the
+ * key is always `Sha256.to_hex (Sha256.string serialized_bytes)` and the
+ * value is the raw serialized bytes.
+ *
+ * Relation membership (which tuple hashes belong to a given relation) is
+ * tracked via a separate index managed by LinkTuple / TupleHashes. This
+ * corresponds to Sakura's B+ tree of tuple hashes stored under each relation.
+ */
+
+namespace nt
+{
+    /**
+     * @interface IStorageBackend
+     * @brief Contract between CursorManager and a physical (or mock) storage engine.
+     *
+     * Storage is strictly content-addressed: every value lives under its own
+     * SHA256 digest. Relation membership is tracked separately via
+     * LinkTuple / TupleHashes, mirroring Sakura's per-relation B+ tree.
+     */
+    class IStorageBackend
+    {
+    public:
+        virtual ~IStorageBackend() = default;
+
+        /**
+         * @brief Stores a serialized value and returns its SHA256 hex hash.
+         *
+         * Idempotent: storing the same bytes twice does not create a duplicate.
+         * The hash is the only valid key for subsequent Get calls.
+         */
+        virtual std::string Put(std::vector<uint8_t> value) = 0;
+
+        /**
+         * @brief Retrieves bytes by their SHA256 hex hash.
+         * @return The stored bytes, or std::nullopt when the hash is unknown.
+         */
+        virtual std::optional<std::vector<uint8_t>> Get(const std::string& hash) = 0;
+
+        /**
+         * @brief Records that a tuple (by hash) belongs to a relation (by path).
+         *
+         * Idempotent. Corresponds to appending a tuple hash to a relation's
+         * B+ tree in Sakura's physical layer.
+         */
+        virtual void LinkTuple(const std::vector<std::string>& relation_path,
+                               const std::string& tuple_hash) = 0;
+
+        /**
+         * @brief Returns a page of tuple hashes for a relation.
+         *
+         * Pagination is tuple-level: @p offset and @p limit count whole tuples.
+         * Hashes are returned in insertion order.
+         *
+         * @param relation_path Logical relation path.
+         * @param offset        Zero-based index of the first tuple to return.
+         * @param limit         Maximum number of tuple hashes to return.
+         * @return Ordered list of SHA256 hex hashes. Empty when past the end.
+         */
+        virtual std::vector<std::string> TupleHashes(
+            const std::vector<std::string>& relation_path,
+            std::size_t offset,
+            std::size_t limit) = 0;
+    };
+}
diff --git a/include/InMemoryBackend.h b/include/InMemoryBackend.h
new file mode 100644
index 0000000..8f7f50a
--- /dev/null
+++ b/include/InMemoryBackend.h
@@ -0,0 +1,43 @@
+#pragma once
+
+#include "Api.h"
+#include "IStorageBackend.h"
+
+#include <cstdint>
+#include <optional>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+/**
+ * @file InMemoryBackend.h
+ * @brief In-process KV storage backend backed by unordered_maps.
+ */
+
+namespace nt
+{
+    /**
+     * @interface InMemoryBackend
+     * @brief IStorageBackend implementation that keeps all data in process memory.
+     *
+     * Intended for unit tests where SQLite is not appropriate. Data does not
+     * survive process exit and is not thread-safe.
+     */
+    class NT_API InMemoryBackend : public IStorageBackend
+    {
+    public:
+        std::string Put(std::vector<uint8_t> value) override;
+        std::optional<std::vector<uint8_t>> Get(const std::string& hash) override;
+        void LinkTuple(const std::vector<std::string>& relation_path,
+                       const std::string& tuple_hash) override;
+        std::vector<std::string> TupleHashes(const std::vector<std::string>& relation_path,
+                                             std::size_t offset,
+                                             std::size_t limit) override;
+
+    private:
+        std::unordered_map<std::string, std::vector<uint8_t>> kv_;
+        std::unordered_map<std::string, std::vector<std::string>> index_;
+
+        static std::string PathKey(const std::vector<std::string>& path);
+    };
+}
diff --git a/include/SqliteBackend.h b/include/SqliteBackend.h
new file mode 100644
index 0000000..0b21925
--- /dev/null
+++ b/include/SqliteBackend.h
@@ -0,0 +1,60 @@
+#pragma once
+
+#include "Api.h"
+#include "IStorageBackend.h"
+
+#include <sqlite3.h>
+#include <string>
+#include <vector>
+
+/**
+ * @file SqliteBackend.h
+ * @brief IStorageBackend implementation backed by an in-process SQLite database.
+ *
+ * SQLite schema:
+ *
+ *   kv(hash TEXT PRIMARY KEY, value BLOB NOT NULL)
+ *     — content-addressed store; key is the SHA256 hex digest of value.
+ *
+ *   relation_index(path TEXT NOT NULL, tuple_hash TEXT NOT NULL,
+ *                  UNIQUE(path, tuple_hash))
+ *     — maps a relation's logical path to the ordered set of tuple hashes
+ *       it contains. Corresponds to Sakura's per-relation B+ tree of
+ *       tuple hashes stored in the physical layer.
+ */
+
+namespace nt
+{
+    /**
+     * @class SqliteBackend
+     * @brief IStorageBackend that persists data in a SQLite database.
+     *
+     * Constructed with a file path or ":memory:" for an in-process database.
+     * All KV values are opaque blobs; callers are responsible for serialization
+     * (see TupleCodec).
+     */
+    class NT_API SqliteBackend : public IStorageBackend
+    {
+    public:
+        /**
+         * @brief Opens (or creates) a SQLite database at @p path.
+         * @param path File path, or ":memory:" for an in-process database.
+         * @throws std::runtime_error if the database cannot be opened.
+         */
+        explicit SqliteBackend(const std::string& path = ":memory:");
+        ~SqliteBackend() override;
+
+        std::string Put(std::vector<uint8_t> value) override;
+        std::optional<std::vector<uint8_t>> Get(const std::string& hash) override;
+        void LinkTuple(const std::vector<std::string>& relation_path,
+                       const std::string& tuple_hash) override;
+        std::vector<std::string> TupleHashes(const std::vector<std::string>& relation_path,
+                                             std::size_t offset,
+                                             std::size_t limit) override;
+
+    private:
+        sqlite3* db_ = nullptr;
+
+        static std::string PathKey(const std::vector<std::string>& path);
+    };
+}
diff --git a/include/TupleCodec.h b/include/TupleCodec.h
new file mode 100644
index 0000000..18294d4
--- /dev/null
+++ b/include/TupleCodec.h
@@ -0,0 +1,52 @@
+#pragma once
+
+#include "Types.h"
+
+#include <cstdint>
+#include <string>
+#include <vector>
+
+/**
+ * @file TupleCodec.h
+ * @brief Content-addressing utilities for tuples.
+ *
+ * Mirrors Sakura's hashing.ml and physical.ml:
+ *   - Hash()      ≈ hash_tuple: deterministic SHA256 over sorted attribute content
+ *   - Serialize() ≈ Marshal.to_bytes: raw bytes stored as the KV value
+ *   - Deserialize() ≈ Marshal.from_bytes: reconstruct attributes from raw bytes
+ *
+ * The hash input format is:
+ *   "path_seg1/path_seg2/..|name1:value1;name2:value2;"
+ * where attributes are sorted by name for determinism.
+ *
+ * The serialization format is a sequence of length-prefixed UTF-8 pairs:
+ *   [uint32_le name_len][name bytes][uint32_le value_len][value bytes] ...
+ */
+
+namespace nt::TupleCodec
+{
+    /**
+     * @brief Computes the SHA256 hex digest of the serialized tuple.
+     *
+     * Equivalent to SHA256(Serialize(attrs)), so the value returned here
+     * matches the key returned by IStorageBackend::Put(Serialize(attrs)).
+     *
+     * @param attrs Attribute set. Need not be pre-sorted.
+     * @return 64-character lowercase hex string.
+     */
+    std::string Hash(const std::vector<Attribute>& attrs);
+
+    /**
+     * @brief Serializes a tuple's attributes to raw bytes for KV storage.
+     * @param attrs Attribute set. Need not be pre-sorted.
+     * @return Serialized bytes.
+     */
+    std::vector<uint8_t> Serialize(const std::vector<Attribute>& attrs);
+
+    /**
+     * @brief Reconstructs attributes from the bytes returned by Serialize().
+     * @param bytes Bytes produced by Serialize().
+     * @return Reconstructed attribute list in serialization order.
+     */
+    std::vector<Attribute> Deserialize(const std::vector<uint8_t>& bytes);
+}