#pragma once
#include "Api.h"
#include "CursorManager.h"
#include "Types.h"
#include <optional>
#include <string>
#include <unordered_set>
#include <vector>
/**
* @file VM.h
* @brief Declares the logic execution boundary for relational and higher-order workloads.
*/
namespace nt {
/**
* @class VM
* @brief Hosts the first-order logic (FOL) and second-order logic (SOL) cores.
*
* This partitioning exists to ensure retrieval terminates when execution is
* constrained to first-order logic.
*
* - Tarski runtime (FOL): a relational engine that implements Tarski's
* relational calculus. It uses a deterministic Volcano-iterator model to
* perform relational algebra operations such as joins, projections, and
* selects directly against the CursorManager and a prepared plan.
*
* - Karuta runtime (SOL): an isolated WAM-based environment for
* higher-order logic programming. It handles recursion, choice points, and
* other programming constructs that do not guarantee termination.
*
* @remark Lazy evaluation and paging strategy
*
* Both the Tarski first-order engine and the Karuta second-order engine are
* strictly pull-based. Data is streamed lazily from the CursorManager to
* preserve a constant memory footprint regardless of relation size.
*
* Pipeline dynamics:
* - Demand-driven: the Karuta WAM requests a fact only when a goal needs
* satisfaction. A request propagates down the algebra tree as a chain of
* Next() calls.
*
* - Short-circuiting: if the Karuta engine finds a solution or reaches a
* failure that invalidates a branch, the Tarski iterator is discarded or
* reset without materializing the remaining tuples.
*
* - Resource stewardship: by maintaining laziness up to the highest logical
* level, the runtime minimizes pressure on ObjectManager and keeps
* snapshots pinned through LifecycleManager::Monitor only for the minimum
* time required.
*/
/**
* @brief One segment of a parameterized relation path in a SCAN node.
*
* Var segments are resolved at runtime from the outer tuple of a JOIN:
* the JOIN writes the bound value into the cursor's args vector before
* each probe. Const segments are ground literals fixed at plan construction.
*
* The resolved args vector is passed to the ephemeral relation's generator
* (for EPHEMERAL_RELATION cursors) or ignored (for stored RELATION cursors,
* which need no per-probe parameterization).
*/
struct PathArg {
enum class Kind { Var, Const };
Kind kind;
std::string name; /**< Attribute name to look up (Var), or literal value (Const). */
static PathArg Var(std::string attr) {
return {Kind::Var, std::move(attr)};
}
static PathArg Const(std::string val) {
return {Kind::Const, std::move(val)};
}
};
enum Operation {
FOL_OPERATION_SCAN = 1,
FOL_OPERATION_JOIN,
FOL_OPERATION_TAKE,
FOL_OPERATION_PROJECT,
FOL_OPERATION_MATERIALIZE,
FOL_OPERATION_RENAME,
FOL_OPERATION_UNION
};
/**
* @brief A node in the Volcano operator tree executed by the Tarski (FOL) runtime.
*
* Each node represents one relational algebra operator. The tree is demand-driven:
* VM::Next() propagates pull requests from root to leaves.
*
* Supported operators:
* - SCAN : pulls tuples from a pre-opened cursor (stored or ephemeral relation).
* - JOIN : nested-loop join. For each outer (left) tuple, resolves scan_args on
* the inner (right) SCAN, resets its cursor, and probes it. Works for
* both stored relations (full re-scan of inner) and ephemeral relations
* (O(1) membership probe when all args are bound).
* - TAKE : passes at most take_limit tuples through, then returns nullptr. Use
* this to bound scans over AlephZero ephemeral relations.
* - PROJECT: filters each input tuple to the named attributes in project_attrs.
* - MATERIALIZE: on its first scan it pulls the whole child and keeps a
* private copy of every tuple. On later scans it replays that copy
* and never reads the child again. Sits on the inner side of a
* nested-loop JOIN so the inner relation is read once instead of
* once per outer tuple. This only works when the child does not
* depend on the outer tuple, meaning it has no Var SCAN leaves that
* the JOIN binds, because the same cached tuples are handed back for
* every outer tuple. Rewind does not pass the outer tuple through
* this node, so it is up to the planner to place it only where the
* child is independent of the outer side.
*/
struct PlanNode {
Operation op;
PlanNode* left = nullptr;
PlanNode* right = nullptr;
/**
* SCAN: pre-opened cursor. For ephemeral relations the JOIN resets it
* (args, offset, exhausted flag) with resolved args before each probe,
* overwriting whatever standalone-scan state it opened with.
*/
CursorManager::cursor* scan_cursor = nullptr;
/**
* SCAN: argument template for parameterized relations.
* Var entries are resolved from the outer JOIN tuple; Const entries
* are used as-is. The resolved values are written into scan_cursor->args
* by the JOIN before it calls Next() on this node.
*/
std::vector<PathArg> scan_args;
/** TAKE: maximum number of tuples to emit before returning nullptr. */
std::size_t take_limit = 0;
std::size_t take_count = 0; /**< Runtime counter; mutable during execution. */
/** PROJECT: unordered set of attribute names to keep. */
std::unordered_set<std::string> project_attrs;
std::optional<Tuple> project_buffer;
/**
* JOIN runtime state.
*
* join_left holds the current outer tuple while probing the inner
* (right) side. The pointer is stable for the lifetime of one outer
* iteration because Next(left) is only called when join_left is reset
* to nullptr, which happens only after the inner side is exhausted.
*
* join_buffer holds the merged output tuple and is overwritten on each
* successful join. Callers must consume the returned pointer before
* calling Next() again — same contract as a cursor page pointer.
*/
Tuple* join_left = nullptr;
std::optional<Tuple> join_buffer;
std::unordered_set<std::string> join_attrs;
/**
* MATERIALIZE runtime state.
*
* mat_buffer holds owned copies of the child's tuples, filled on the
* first scan. mat_done marks the cache complete (child exhausted).
* mat_pos is the replay cursor, reset to 0 by Rewind on each later scan.
*/
std::vector<Tuple> mat_buffer;
std::size_t mat_pos = 0;
bool mat_done = false;
/** RENAME runtime state. */
PlanNode* upstream = nullptr;
std::unordered_map<std::string, std::string> attrs;
/** UNION runtime state. */
std::vector<PlanNode*> nodes;
std::vector<PlanNode*>::iterator current_node;
};
class VM {
public:
// TODO: CursorManager should be injected as a shared runtime instance,
// matching the pattern flagged for HandlerManager and LifecycleManager.
//
// A single CursorManager instance supports multiple simultaneous cursors —
// all iteration state lives in each cursor struct, not in the manager.
// A JOIN plan, for example, holds two independent cursors (one per SCAN leaf)
// and both are driven through the same CursorManager reference.
explicit VM(CursorManager& cursors);
/**
* @brief Pulls the next tuple from the plan tree (Tarski/FOL core).
*
* Propagates a Next() call down the operator tree:
* - SCAN delegates to CursorManager::Next.
* - JOIN drives the nested-loop: for each outer tuple it resolves
* scan_args on the inner SCAN, resets the inner cursor, and
* probes until a match is found or the inner is exhausted.
* - TAKE counts emitted tuples and returns nullptr once the limit
* is reached.
* - PROJECT filters an input tuple to the requested attribute names.
*
* @param node Root of the plan subtree to evaluate.
* @return Next matching tuple, or nullptr when the plan is exhausted.
*/
Tuple* Next(PlanNode* node);
private:
CursorManager& cursors_;
/**
* Resolves a scan_args template against an outer tuple, producing the
* concrete args vector to write into the inner cursor before probing.
*/
static std::vector<std::string> ResolveArgs(const std::vector<PathArg>& tmpl, Tuple* from);
/** Resets the inner cursor state and writes resolved args into it. */
static void ResetInner(CursorManager::cursor* c, std::vector<std::string> args);
/**
* Restarts the inner (right) subtree of a JOIN for a new outer tuple.
* Walks down to every SCAN leaf, rebinds its scan_args to the outer
* tuple, and resets its cursor. On the way it also clears the operator
* state it passes through, such as TAKE counters and nested JOIN buffers.
*/
void Rewind(PlanNode* node, Tuple* outer);
/** Merges left and right tuple attributes into node->join_buffer. */
static Tuple* MergeInto(PlanNode* node, Tuple* left, Tuple* right);
};
} // namespace nt
