xlog_logic/hypergraph/
mod.rs

1//! Hypergraph IR + WCOJ oracle stack (v0.6.2).
2//!
3//! A **parallel structure** to the existing AST-to-RIR lowering pipeline
4//! (see [`crate::lower`]). The executor's consumed plan shape is
5//! untouched — every consumer here is opt-in and pure-Rust.
6//!
7//! ## What this stack ships (PRs 1–9, all on local main)
8//!
9//! * **PR 1 — Foundation.**
10//!   - [`ir::HypergraphRule`] — vertices = body variables, hyperedges =
11//!     positive body atoms.
12//!   - [`eligibility::analyze`] / [`eligibility::analyze_typed`] —
13//!     decide Eligible vs Ineligible for an explicit
14//!     [`eligibility::ExecutorContext`] with a structured
15//!     [`eligibility::Boundary`] list explaining why.
16//!   - [`var_order::VariableOrder`] / [`var_order::AppearanceOrder`] —
17//!     trait + trivial impl. Cost models slot in here later.
18//!   - [`explain::explain`] — stable textual representation.
19//! * **PR 2 — CPU reference evaluator.**
20//!   [`reference::evaluate_rule`] over [`reference::RefRelationStore`];
21//!   the WCOJ correctness oracle for all later kernels.
22//! * **PR 3 — Single-target fixpoint.**
23//!   [`fixpoint::evaluate_fixpoint`] for recursive single-predicate
24//!   rules (transitive closure shape).
25//! * **PR 4 — Multi-predicate SCC fixpoint.**
26//!   [`scc::evaluate_scc_fixpoint`] for mutually-recursive predicate
27//!   groups; correctness oracle for mixed-execution kernels.
28//! * **PR 5 — Typed oracle gate.**
29//!   [`typed::evaluate_rule_typed`] +
30//!   [`typed::evaluate_fixpoint_typed`] +
31//!   [`typed::evaluate_scc_fixpoint_typed`]: schema-driven type
32//!   derivation from [`reference::RefRelationStore`] feeds
33//!   [`eligibility::analyze_typed`] for join-key support gating.
34//! * **PR 6 — Mixed plan contract.**
35//!   [`plan::plan_rule`] / [`plan::plan_rules`] dispatch each rule
36//!   into [`plan::RulePlan::MultiwayCandidate`] (ready for WCOJ) or
37//!   [`plan::RulePlan::BinaryFallback`] (carries every Boundary that
38//!   fired). [`plan::explain_plans`] renders a canonical textual
39//!   summary for mixed rule sets.
40//! * **PR 7 — Certification workloads.** Pure-Rust integration
41//!   tests covering triangle, Same Generation, skewed multiway,
42//!   deep recursive frontier, and mutually-recursive parity SCC
43//!   end-to-end via plan + typed eval + canonical explain.
44//! * **PR 8 — Transitive SCC type inference.**
45//!   [`inference::infer_scc_predicate_schemas`] propagates types
46//!   through the rule graph (body atoms type variables; head
47//!   atoms back-propagate to head-predicate columns; iterate to
48//!   fixpoint). The group-aware typed evaluators
49//!   ([`typed::evaluate_scc_fixpoint_typed`],
50//!   [`typed::evaluate_fixpoint_typed`]) consult the inferred
51//!   schemas alongside `base_relations`. Locked policy narrows to
52//!   "unknowable-after-inference ≠ unsupported."
53//! * **PR 9 — SCC-aware planner + structural-error precedence.**
54//!   [`plan::plan_scc_rules`] runs PR 8 inference before
55//!   per-rule planning, so the planner agrees with
56//!   [`typed::evaluate_scc_fixpoint_typed`] on recursive-only
57//!   join keys. The typed evaluators now pre-flight
58//!   structural head-match checks before running inference, so
59//!   [`SccFixpointError::RuleHeadPredicateMismatch`] /
60//!   [`FixpointError::RuleNotForTarget`] surface correctly even
61//!   when a misgrouped rule's body would also produce inference
62//!   conflicts.
63//!
64//! ## What this stack still does NOT ship
65//!
66//! * No GPU / CUDA kernels — WCOJ kernel work is the next slice.
67//! * No cost model beyond [`var_order::AppearanceOrder`].
68//! * No integration into [`crate::lower`] or the executor — the
69//!   hypergraph stack is constructed on demand from
70//!   [`crate::ast::Rule`] values and consumed in tests, the reference
71//!   oracles, and the planner. Mixed-execution dispatch into the
72//!   existing executor is a separate concern.
73
74pub mod eligibility;
75pub mod explain;
76pub mod fixpoint;
77pub mod inference;
78pub mod ir;
79pub mod plan;
80pub mod reference;
81pub mod scc;
82pub mod typed;
83pub mod var_order;
84
85pub use eligibility::{
86    analyze, analyze_typed, is_eligible, Boundary, Eligibility, ExecutorContext,
87    BINARY_FALLBACK_KEY_LIMIT, WCOJ_ELIGIBLE_KEY_LIMIT, WCOJ_SUPPORTED_KEY_TYPES,
88};
89pub use explain::explain;
90pub use fixpoint::{evaluate_fixpoint, FixpointConfig, FixpointError};
91pub use inference::{infer_scc_predicate_schemas, InferenceError, InferredSchemas};
92pub use ir::{Hyperedge, HypergraphRule, Vertex, VertexId};
93pub use plan::{explain_plans, plan_rule, plan_rules, plan_scc_rules, PlanError, RulePlan};
94pub use reference::{evaluate_rule, RefEvalError, RefRelation, RefRelationStore, RefValue};
95pub use scc::{evaluate_scc_fixpoint, SccFixpointError};
96pub use typed::{evaluate_fixpoint_typed, evaluate_rule_typed, evaluate_scc_fixpoint_typed};
97pub use var_order::{
98    plan_kclique_var_order, AppearanceOrder, CostPredictionRecord, FullVariableOrder, KCliqueEdge,
99    KCliqueShape, PredictedWinner, StatsSource, VariableOrder, VariableShare,
100};
xlog_logic/hypergraph/mod.rs

xlog_logic/hypergraph/
mod.rs
