@spec join([binding()], [ir_term()], [tuple()]) :: [binding()]

Joins a list of binding environments with a collection of tuples using a sequential scan.

For each (binding, tuple) pair, calls match_tuple/3. Collects all successful matches. This is O(bindings × tuples) and suitable for small relations or when no index is available.

Examples

iex> alias ExDatalog.Engine.Join
iex> terms = [{:var, "X"}, {:var, "Y"}]
iex> tuples = [{:alice, :bob}, {:carol, :dave}]
iex> Join.join([%{}], terms, tuples)
[%{"X" => :alice, "Y" => :bob}, %{"X" => :carol, "Y" => :dave}]

iex> terms = [{:var, "X"}, {:var, "Y"}]
iex> tuples = [{:alice, :bob}, {:carol, :dave}]
iex> Join.join([%{"X" => :alice}], terms, tuples)
[%{"X" => :alice, "Y" => :bob}]

@spec match_tuple([ir_term()], tuple(), binding()) :: {:ok, binding()} | :no_match

Matches a storage tuple against a list of IR terms, extending the binding.

For each position i in the terms list:

• {:var, name} — if name is bound, the tuple value at position i must equal the bound value. If unbound, name is bound to the tuple value.
• {:const, ir_value} — the tuple value at position i must equal the native value of ir_value.
• :wildcard — any value matches; no binding change.

Returns {:ok, extended_binding} if all positions match, or :no_match. The terms list and the tuple must have the same length.

Examples

iex> alias ExDatalog.Engine.Join
iex> terms = [{:var, "X"}, {:var, "Y"}]
iex> Join.match_tuple(terms, {:alice, :bob}, %{})
{:ok, %{"X" => :alice, "Y" => :bob}}

iex> terms = [{:var, "X"}, {:const, {:atom, :bob}}]
iex> Join.match_tuple(terms, {:alice, :bob}, %{})
{:ok, %{"X" => :alice}}

iex> terms = [{:var, "X"}, {:const, {:atom, :carol}}]
iex> Join.match_tuple(terms, {:alice, :bob}, %{})
:no_match

iex> terms = [{:var, "X"}, {:var, "X"}]
iex> Join.match_tuple(terms, {:alice, :alice}, %{})
{:ok, %{"X" => :alice}}

iex> terms = [{:var, "X"}, {:var, "X"}]
iex> Join.match_tuple(terms, {:alice, :bob}, %{})
:no_match

@spec project(ExDatalog.IR.Atom.t(), binding()) :: tuple()

Projects a binding environment onto a head atom's IR terms, producing a result tuple.

For each term in the head atom:

• {:var, name} — look up name in the binding and use its value.
• {:const, ir_value} — use the native value of ir_value.
• :wildcard — not valid in rule heads (caught by the validator).

Returns an Elixir tuple suitable for insertion into a storage relation.

Examples

iex> alias ExDatalog.Engine.Join
iex> ir_atom = %ExDatalog.IR.Atom{relation: "ancestor", terms: [{:var, "X"}, {:var, "Y"}]}
iex> Join.project(ir_atom, %{"X" => :alice, "Y" => :bob})
{:alice, :bob}

iex> ir_atom = %ExDatalog.IR.Atom{relation: "result", terms: [{:var, "X"}, {:const, {:atom, :ok}}]}
iex> Join.project(ir_atom, %{"X" => 42})
{42, :ok}