xlog_induce/
types.rs

1//! Public types for the exact-induction engine.
2//!
3//! Mirrors the pyxlog `ExactInductionResult` / `ScoredCandidate` dataclasses
4//! but speaks `RelId` instead of relation names — name resolution happens at
5//! the pyxlog boundary in `crates/pyxlog/src/ilp_exact.rs`.
6
7use std::collections::hash_map::DefaultHasher;
8use std::hash::{Hash, Hasher};
9
10use xlog_core::RelId;
11
12/// The four canonical 2-body topologies scored by the engine.
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
14pub enum Topology {
15    /// `H(X,Y) :- L(X,Z), R(Z,Y)` — join on intermediate `Z`.
16    Chain,
17    /// `H(X,Y) :- L(X,Y), R(X,Y)` — shared `X,Y`.
18    Star,
19    /// `H(X,Y) :- L(X,Z), R(X,Y)` — left introduces `Z`.
20    Fanout,
21    /// `H(X,Y) :- L(X,Y), R(Z,Y)` — right introduces `Z`.
22    Fanin,
23}
24
25impl Topology {
26    /// All four topologies, in the scoring order used by the engine.
27    pub const ALL: [Topology; 4] = [
28        Topology::Chain,
29        Topology::Star,
30        Topology::Fanout,
31        Topology::Fanin,
32    ];
33
34    /// Stable string form exposed to pyxlog / Python.
35    pub fn as_str(&self) -> &'static str {
36        match self {
37            Topology::Chain => "chain",
38            Topology::Star => "star",
39            Topology::Fanout => "fanout",
40            Topology::Fanin => "fanin",
41        }
42    }
43}
44
45/// Engine configuration for one exact-induction request.
46#[derive(Debug, Clone, Copy)]
47pub struct ExactInductionConfig {
48    /// Number of top candidates to keep per topology (e.g. `2`).
49    pub k_per_topology: u32,
50    /// Reserved for future use; the native engine is inherently deterministic.
51    pub deterministic: bool,
52}
53
54/// One scored `(left, right)` candidate for a single topology.
55#[derive(Debug, Clone, Copy, PartialEq, Eq)]
56pub struct ScoredCandidate {
57    pub topology: Topology,
58    pub head_rel_idx: RelId,
59    pub left_rel_idx: RelId,
60    pub right_rel_idx: RelId,
61    pub positives_covered: u32,
62    pub negatives_covered: u32,
63    /// 0-indexed within topology, after lexicographic ranking.
64    pub local_rank: u32,
65    /// Positive coverage of the next-ranked candidate in the same topology,
66    /// or `0` if no next candidate exists.
67    pub next_positives_covered: u32,
68    /// Negative coverage of the next-ranked candidate.
69    pub next_negatives_covered: u32,
70    /// Count of candidates sharing the same `(positives_covered, negatives_covered)`.
71    pub tie_class_size: u32,
72}
73
74/// Combined result from one `induce_exact()` call.
75#[derive(Debug, Default, Clone, PartialEq, Eq)]
76pub struct ExactInductionResult {
77    /// Up to `k_per_topology × 4` candidates, grouped by topology then rank.
78    pub candidates: Vec<ScoredCandidate>,
79    /// Total number of `(topology, left, right)` triples scored.
80    pub total_scored: u32,
81    /// Number of body candidates considered (after validation).
82    pub candidate_count: u32,
83    /// Number of positive examples.
84    pub positive_count: u32,
85    /// Number of negative examples.
86    pub negative_count: u32,
87}
88
89/// Origin class for a rule known to the induction/provenance surface.
90#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
91pub enum RuleSourceKind {
92    /// Rule was authored in source text.
93    Source,
94    /// Rule was produced by a native induction or compiler-generation step.
95    Generated,
96    /// Rule was mined by an induction workflow and registered with provenance.
97    Mined,
98    /// Rule came from an imported module.
99    Imported,
100    /// Rule was inserted at runtime through an API.
101    RuntimeInjected,
102}
103
104/// One source row supporting a generated rule candidate.
105#[derive(Debug, Clone, PartialEq, Eq)]
106pub struct InductionSupportRow {
107    /// Supporting relation name.
108    pub relation: String,
109    /// Row index within the supporting relation.
110    pub row_index: u64,
111    /// Stable row hash supplied by the caller or relation loader.
112    pub row_hash: String,
113}
114
115impl InductionSupportRow {
116    /// Create one support-row reference.
117    pub fn new(relation: impl Into<String>, row_index: u64, row_hash: impl Into<String>) -> Self {
118        Self {
119            relation: relation.into(),
120            row_index,
121            row_hash: row_hash.into(),
122        }
123    }
124}
125
126/// Rejected candidate rule with support and falsification counts.
127#[derive(Debug, Clone, PartialEq, Eq)]
128pub struct InductionAlternative {
129    /// Candidate source fragment.
130    pub rule_fragment: String,
131    /// Number of positive examples covered by the rejected alternative.
132    pub support_count: u64,
133    /// Number of falsifying examples covered by the rejected alternative.
134    pub falsification_count: u64,
135}
136
137impl InductionAlternative {
138    /// Create one rejected-alternative record.
139    pub fn new(
140        rule_fragment: impl Into<String>,
141        support_count: u64,
142        falsification_count: u64,
143    ) -> Self {
144        Self {
145            rule_fragment: rule_fragment.into(),
146            support_count,
147            falsification_count,
148        }
149    }
150}
151
152/// Provenance bundle for a generated or induced rule candidate.
153#[derive(Debug, Clone, PartialEq, Eq)]
154pub struct InducedRuleProvenance {
155    /// Stable generated-rule id.
156    pub rule_id: String,
157    /// Rule source fragment.
158    pub rule_fragment: String,
159    /// Origin class for this rule.
160    pub source_kind: RuleSourceKind,
161    /// Deterministic hash over rule text and search metadata.
162    pub generation_trace_hash: String,
163    /// Size of the searched candidate space.
164    pub search_space_size: u64,
165    /// Predicate inventory available to the search.
166    pub predicate_inventory: Vec<String>,
167    /// Rows supporting the accepted candidate.
168    pub support_rows: Vec<InductionSupportRow>,
169    /// Rejected alternatives retained for diagnostics.
170    pub rejected_alternatives: Vec<InductionAlternative>,
171    /// Number of falsifying rows for the accepted candidate.
172    pub falsification_count: u64,
173}
174
175impl InducedRuleProvenance {
176    /// Create provenance for a generated rule candidate.
177    pub fn new(
178        rule_fragment: impl Into<String>,
179        search_space_size: u64,
180        predicate_inventory: Vec<String>,
181    ) -> Self {
182        let rule_fragment = rule_fragment.into();
183        let generation_trace_hash =
184            provenance_hash(&rule_fragment, search_space_size, &predicate_inventory);
185        Self {
186            rule_id: format!("generated:{}", generation_trace_hash),
187            rule_fragment,
188            source_kind: RuleSourceKind::Generated,
189            generation_trace_hash,
190            search_space_size,
191            predicate_inventory,
192            support_rows: Vec::new(),
193            rejected_alternatives: Vec::new(),
194            falsification_count: 0,
195        }
196    }
197
198    /// Attach support rows.
199    pub fn with_support_rows(mut self, support_rows: Vec<InductionSupportRow>) -> Self {
200        self.support_rows = support_rows;
201        self
202    }
203
204    /// Attach rejected alternatives.
205    pub fn with_rejected_alternatives(
206        mut self,
207        rejected_alternatives: Vec<InductionAlternative>,
208    ) -> Self {
209        self.rejected_alternatives = rejected_alternatives;
210        self
211    }
212
213    /// Attach the accepted candidate's falsification count.
214    pub fn with_falsification_count(mut self, falsification_count: u64) -> Self {
215        self.falsification_count = falsification_count;
216        self
217    }
218}
219
220/// In-memory registry for induced rule provenance records.
221#[derive(Debug, Default, Clone, PartialEq, Eq)]
222pub struct InducedRuleRegistry {
223    rules: Vec<InducedRuleProvenance>,
224}
225
226impl InducedRuleRegistry {
227    /// Create an empty induced-rule registry.
228    pub fn new() -> Self {
229        Self::default()
230    }
231
232    /// Register one induced or generated rule and return its stable rule id.
233    pub fn register(&mut self, provenance: InducedRuleProvenance) -> String {
234        let rule_id = provenance.rule_id.clone();
235        self.rules.push(provenance);
236        rule_id
237    }
238
239    /// Number of registered induced rules.
240    pub fn len(&self) -> usize {
241        self.rules.len()
242    }
243
244    /// True when no induced rules have been registered.
245    pub fn is_empty(&self) -> bool {
246        self.rules.is_empty()
247    }
248
249    /// Registered induced rules in insertion order.
250    pub fn rules(&self) -> &[InducedRuleProvenance] {
251        &self.rules
252    }
253}
254
255fn provenance_hash(
256    rule_fragment: &str,
257    search_space_size: u64,
258    predicate_inventory: &[String],
259) -> String {
260    let mut hasher = DefaultHasher::new();
261    rule_fragment.hash(&mut hasher);
262    search_space_size.hash(&mut hasher);
263    predicate_inventory.hash(&mut hasher);
264    format!("{:016x}", hasher.finish())
265}
xlog_induce/types.rs

xlog_induce/
types.rs
