add nested loop join strategy to VM and tests

4 files changed, 151 insertions, 10 deletions

diff --git a/include/CursorManager.h b/include/CursorManager.h
index 5636d8d..092229c 100644
--- a/include/CursorManager.h
+++ b/include/CursorManager.h
@@ -46,6 +46,12 @@ namespace nt
          */
         struct cursor {
             HandlerManager::handle* handle = nullptr;
+            /**
+             * Bound argument values for EPHEMERAL_RELATION cursors.
+             * Written by the JOIN operator before each probe; ignored for
+             * stored RELATION cursors.
+             */
+            std::vector<std::string> args;
             std::vector<Tuple> page;
             std::size_t page_position = 0;
             std::size_t fetch_offset  = 0;   // next TupleHashes() call starts here
diff --git a/include/ObjectManager.h b/include/ObjectManager.h
index 4b537f7..32b3ae9 100644
--- a/include/ObjectManager.h
+++ b/include/ObjectManager.h
@@ -4,6 +4,7 @@
 #include "Types.h"
 
 #include <cstdint>
+#include <functional>
 #include <memory>
 #include <set>
 #include <string>
@@ -73,6 +74,44 @@ namespace nt
              * @todo Wire into LifecycleManager::Contention.
              */
             bool exclusive = false;
+
+            virtual ~object_type() = default;
+        };
+
+        /**
+         * @brief Object type descriptor for EPHEMERAL_RELATION objects.
+         *
+         * An ephemeral relation has no physical storage. Its tuples are produced
+         * on demand by a generator function. Cardinality may be finite (e.g. a
+         * projected stored relation) or AlephZero (e.g. the eq/lt builtins).
+         *
+         * The generator receives the bound argument values that were written into
+         * the cursor by the JOIN operator before each probe, together with a
+         * pagination offset and limit. It must return at most `limit` tuples
+         * starting at logical position `offset`.
+         *
+         * For membership-probe builtins (all args ground), the generator returns
+         * at most one tuple. For enumeration over AlephZero relations the generator
+         * maps `offset` to the appropriate pair via a bijective enumeration scheme
+         * (e.g. Cantor pairing); callers must bound such scans with a TAKE node.
+         */
+        struct NT_API ephemeral_object_type : object_type
+        {
+            enum class Cardinality { Finite, ConstrainedFinite, AlephZero, Continuum };
+
+            /**
+             * @brief Produces a page of tuples for the given bound arguments.
+             * @param args   Bound argument values written by the JOIN before probing.
+             * @param offset Zero-based logical tuple offset (for pagination).
+             * @param limit  Maximum number of tuples to return.
+             */
+            using Generator = std::function<std::vector<Tuple>(
+                const std::vector<std::string>& args,
+                std::size_t offset,
+                std::size_t limit)>;
+
+            Cardinality cardinality;
+            Generator   generator;
         };
 
         /**
diff --git a/include/Types.h b/include/Types.h
index c6f4b9f..3e38829 100644
--- a/include/Types.h
+++ b/include/Types.h
@@ -12,12 +12,19 @@
 enum OBJECT_TYPE {
     /** A database snapshot grouping relations and tuples. */
     MULTIGROUP,
-    /** A relation object. */
+    /** A relation object backed by physical storage. */
     RELATION,
     /** An attribute object (schema metadata). */
     ATTRIBUTE,
     /** A transaction object. */
-    TRANSACTION
+    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.
+     */
+    EPHEMERAL_RELATION
 };
 
 /** @brief Operations that may be supported by an object type. */
@@ -76,6 +83,9 @@ namespace nt
 
         void Reset() { position_ = 0; }
 
+        /** @brief Direct read-only access to all attributes without affecting position. */
+        const std::vector<Attribute>& attrs() const { return attributes_; }
+
     private:
         std::vector<Attribute> attributes_;
         size_t position_ = 0;
diff --git a/include/VM.h b/include/VM.h
index d6402b3..c560414 100644
--- a/include/VM.h
+++ b/include/VM.h
@@ -4,6 +4,10 @@
 #include "CursorManager.h"
 #include "Types.h"
 
+#include <optional>
+#include <string>
+#include <vector>
+
 /**
  * @file VM.h
  * @brief Declares the logic execution boundary for relational and higher-order workloads.
@@ -47,24 +51,87 @@ namespace nt
      *   snapshots pinned through LifecycleManager::Monitor only for the minimum
      *   time required.
      */
+
+    /**
+     * @brief One segment of a parameterized relation path in a SCAN node.
+     *
+     * Var segments are resolved at runtime from the outer tuple of a JOIN:
+     * the JOIN writes the bound value into the cursor's args vector before
+     * each probe. Const segments are ground literals fixed at plan construction.
+     *
+     * The resolved args vector is passed to the ephemeral relation's generator
+     * (for EPHEMERAL_RELATION cursors) or ignored (for stored RELATION cursors,
+     * which need no per-probe parameterization).
+     */
+    struct NT_API PathArg
+    {
+        enum class Kind { Var, Const };
+
+        Kind        kind;
+        std::string name; /**< Attribute name to look up (Var), or literal value (Const). */
+
+        static PathArg Var(std::string attr)  { return { Kind::Var,   std::move(attr) }; }
+        static PathArg Const(std::string val) { return { Kind::Const, std::move(val) }; }
+    };
+
     /**
      * @brief A node in the Volcano operator tree executed by the Tarski (FOL) runtime.
      *
      * Each node represents one relational algebra operator. The tree is demand-driven:
      * VM::Next() propagates pull requests from root to leaves.
      *
-     * TODO: Add FILTER, PROJECT, and JOIN operators as the query layer grows.
+     * Supported operators:
+     * - SCAN  : pulls tuples from a pre-opened cursor (stored or ephemeral relation).
+     * - JOIN  : nested-loop join. For each outer (left) tuple, resolves scan_args on
+     *           the inner (right) SCAN, resets its cursor, and probes it. Works for
+     *           both stored relations (full re-scan of inner) and ephemeral relations
+     *           (O(1) membership probe when all args are bound).
+     * - TAKE  : passes at most take_limit tuples through, then returns nullptr. Use
+     *           this to bound scans over AlephZero ephemeral relations.
+     *
+     * TODO: Add PROJECT operator as the query layer grows.
      */
     struct NT_API PlanNode
     {
-        enum class Op { SCAN };
+        enum class Op { SCAN, JOIN, TAKE };
 
-        Op op;
-        PlanNode* left  = nullptr;  /**< Left child (binary operators). */
-        PlanNode* right = nullptr;  /**< Right child (binary operators). */
+        Op        op;
+        PlanNode* left  = nullptr;
+        PlanNode* right = nullptr;
 
-        /** Cursor to scan. Set when op == SCAN. */
+        /**
+         * SCAN: pre-opened cursor. For ephemeral relations this cursor is
+         * initially exhausted; the JOIN resets it with resolved args before
+         * each probe.
+         */
         CursorManager::cursor* scan_cursor = nullptr;
+
+        /**
+         * SCAN: argument template for parameterized relations.
+         * Var entries are resolved from the outer JOIN tuple; Const entries
+         * are used as-is. The resolved values are written into scan_cursor->args
+         * by the JOIN before it calls Next() on this node.
+         */
+        std::vector<PathArg> scan_args;
+
+        /** TAKE: maximum number of tuples to emit before returning nullptr. */
+        std::size_t take_limit = 0;
+        std::size_t take_count = 0; /**< Runtime counter; mutable during execution. */
+
+        /**
+         * JOIN runtime state.
+         *
+         * join_left holds the current outer tuple while probing the inner
+         * (right) side. The pointer is stable for the lifetime of one outer
+         * iteration because Next(left) is only called when join_left is reset
+         * to nullptr, which happens only after the inner side is exhausted.
+         *
+         * join_buffer holds the merged output tuple and is overwritten on each
+         * successful join. Callers must consume the returned pointer before
+         * calling Next() again — same contract as a cursor page pointer.
+         */
+        Tuple*               join_left   = nullptr;
+        std::optional<Tuple> join_buffer;
     };
 
     class NT_API VM
@@ -82,8 +149,13 @@ namespace nt
         /**
          * @brief Pulls the next tuple from the plan tree (Tarski/FOL core).
          *
-         * Propagates a Next() call down the operator tree. The call chain
-         * terminates at a SCAN node, which delegates to CursorManager.
+         * Propagates a Next() call down the operator tree:
+         * - SCAN  delegates to CursorManager::Next.
+         * - JOIN  drives the nested-loop: for each outer tuple it resolves
+         *         scan_args on the inner SCAN, resets the inner cursor, and
+         *         probes until a match is found or the inner is exhausted.
+         * - TAKE  counts emitted tuples and returns nullptr once the limit
+         *         is reached.
          *
          * @param node Root of the plan subtree to evaluate.
          * @return Next matching tuple, or nullptr when the plan is exhausted.
@@ -92,5 +164,19 @@ namespace nt
 
     private:
         CursorManager& cursors_;
+
+        /**
+         * Resolves a scan_args template against an outer tuple, producing the
+         * concrete args vector to write into the inner cursor before probing.
+         */
+        static std::vector<std::string> ResolveArgs(const std::vector<PathArg>& tmpl,
+                                                    Tuple* from);
+
+        /** Resets the inner cursor state and writes resolved args into it. */
+        static void ResetInner(CursorManager::cursor* c,
+                               std::vector<std::string> args);
+
+        /** Merges left and right tuple attributes into node->join_buffer. */
+        static Tuple* MergeInto(PlanNode* node, Tuple* left, Tuple* right);
     };
 }