srdatalog.ir.hir.index

HIR Pass 5: Index Selection.

Populates per-stratum required_indices / canonical_index and program-level global_index_map. Required for downstream MIR lowering, which embeds the canonical index columns into RebuildIndex / ComputeDelta / MergeIndex etc.

Mirrors src/srdatalog/hir/index_selection.nim.

Algorithm:

  1. First pass: collect every index used by any variant in any stratum into hir.global_index_map.

  2. Second pass: for each stratum, per SCC member:

    • Recursive: DELTA-version indices first, FULL-version second, global fallback, identity fallback.

    • Non-recursive: local patterns, global fallback, identity fallback.

  3. Canonical index: prefer a full-arity index that is also accessed as FULL in the stratum (so the maintained FULL-version index is actually read; avoids building a dead index).

SCC member iteration is sorted for reproducibility (Python set order is hash-random); Nim relies on its deterministic string hash, but these fields are internal to downstream passes and not emitted, so the order only has to be stable, not byte-matched against Nim.

Module Contents

Classes

IndexSelectionPass

Functions

canonical_index

Pick a full-arity canonical index. Prefer one whose FULL-version is actually read by joins (so the maintained FULL index is actively used).

complete_index

Pad a partial index to full arity by appending missing columns in column order.

default_index

get_arity

select_indices

Pass 5 entry. Mutates and returns the HirProgram.

API

class srdatalog.ir.hir.index.IndexSelectionPass[source]
info

‘PassInfo(…)’

run(hir: srdatalog.ir.hir.types.HirProgram) → srdatalog.ir.hir.types.HirProgram[source]
srdatalog.ir.hir.index.canonical_index(rel_name: str, indices: list[list[int]], decls: list[srdatalog.ir.hir.types.RelationDecl], full_indices: dict[str, set[tuple[int, ...]]] | None = None) → list[int][source]

Pick a full-arity canonical index. Prefer one whose FULL-version is actually read by joins (so the maintained FULL index is actively used).

srdatalog.ir.hir.index.complete_index(idx: list[int], arity: int) → list[int][source]

Pad a partial index to full arity by appending missing columns in column order.

srdatalog.ir.hir.index.default_index(rel_name: str, decls: list[srdatalog.ir.hir.types.RelationDecl]) → list[int][source]
srdatalog.ir.hir.index.get_arity(rel_name: str, decls: list[srdatalog.ir.hir.types.RelationDecl]) → int[source]
srdatalog.ir.hir.index.select_indices(hir: srdatalog.ir.hir.types.HirProgram) → srdatalog.ir.hir.types.HirProgram[source]

Pass 5 entry. Mutates and returns the HirProgram.