xlog_logic/hypergraph/ir.rs
1//! Hypergraph IR data types: vertices (variables) and hyperedges (atoms).
2//!
3//! Construction is via [`HypergraphRule::from_rule`]. The resulting
4//! structure preserves the rule's variable identity (no renaming) and
5//! the body atoms' source order. Anonymous wildcards (`_`) are NOT
6//! treated as vertices — each occurrence is a fresh unconstrained
7//! position and contributes nothing to the join graph.
8
9use crate::ast::{Atom, BodyLiteral, Rule, Term};
10use std::collections::HashMap;
11
12/// Stable index into a [`HypergraphRule::vertices`] vector.
13///
14/// Allocated in first-appearance order during construction. Two
15/// [`Vertex`]es with the same logical variable name share one
16/// `VertexId`. Used by [`Hyperedge::vertex_positions`] and
17/// [`crate::hypergraph::var_order::VariableOrder`] implementations.
18#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
19pub struct VertexId(pub usize);
20
21/// A variable in the rule body.
22///
23/// At PR 1 the only carried metadata is the source name. Type
24/// inference results, mode information, and selectivity hints will
25/// attach here in later PRs without changing the surrounding shape.
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct Vertex {
28 /// Logic variable name as it appears in the source rule
29 /// (e.g. `"X"`, `"Path"`).
30 pub name: String,
31}
32
33/// A positive body atom, as a hyperedge over [`VertexId`]s.
34///
35/// `vertex_positions[i] = Some(vid)` means argument position `i` of
36/// the atom is the variable `vid`. `vertex_positions[i] = None`
37/// means position `i` is either a constant or an anonymous wildcard
38/// — both leave the position out of the join graph.
39#[derive(Debug, Clone, PartialEq, Eq)]
40pub struct Hyperedge {
41 /// Predicate name, copied from the source [`Atom`].
42 pub predicate: String,
43 /// Per-argument vertex assignment. `None` for constants and
44 /// anonymous wildcards.
45 pub vertex_positions: Vec<Option<VertexId>>,
46}
47
48impl Hyperedge {
49 /// Arity of the underlying atom.
50 pub fn arity(&self) -> usize {
51 self.vertex_positions.len()
52 }
53
54 /// Distinct variable [`VertexId`]s referenced by this hyperedge,
55 /// in source position order, deduplicated.
56 pub fn vertices(&self) -> Vec<VertexId> {
57 let mut seen = Vec::new();
58 for v in self.vertex_positions.iter().flatten() {
59 if !seen.contains(v) {
60 seen.push(*v);
61 }
62 }
63 seen
64 }
65}
66
67/// A rule body represented as a hypergraph.
68///
69/// Vertices are body variables (named only — anonymous wildcards do
70/// not participate in the graph). Hyperedges are positive body atoms.
71/// `Negated`, `Comparison`, and `IsExpr` body literals are NOT
72/// hyperedges; their presence is recorded in
73/// [`HypergraphRule::has_negation`] / [`HypergraphRule::has_is_expr`]
74/// so the eligibility analyzer can flag them as boundaries without
75/// the IR pretending they're join structure.
76///
77/// Construction is total: every [`Rule`] produces a
78/// [`HypergraphRule`]. Whether the rule is *eligible* for multiway
79/// planning is a separate question handled by
80/// [`crate::hypergraph::eligibility::analyze`].
81#[derive(Debug, Clone, PartialEq, Eq)]
82pub struct HypergraphRule {
83 /// Predicate name of the rule head.
84 pub head_predicate: String,
85 /// Variables in first-appearance order across the body. Empty
86 /// for ground facts and bodies that contain only constants.
87 pub vertices: Vec<Vertex>,
88 /// Positive body atoms in source order.
89 pub hyperedges: Vec<Hyperedge>,
90 /// True if the head contains an [`crate::ast::AggExpr`].
91 pub head_has_aggregation: bool,
92 /// True if any body literal is [`BodyLiteral::Negated`].
93 pub has_negation: bool,
94 /// True if any body literal is [`BodyLiteral::IsExpr`].
95 pub has_is_expr: bool,
96 /// Number of body [`BodyLiteral::Comparison`] literals (filters).
97 /// Comparisons do NOT block multiway eligibility — they are
98 /// applied as filters on top of the join — but the count is
99 /// recorded so the explain output can show them and so future
100 /// PRs can reason about filter selectivity.
101 pub comparison_count: usize,
102 /// True if the rule is a ground fact (`body.is_empty()`).
103 pub is_fact: bool,
104}
105
106impl HypergraphRule {
107 /// Build a [`HypergraphRule`] from an AST [`Rule`]. Total: never
108 /// fails. Anonymous wildcards (`Term::Anonymous`) and constants
109 /// (`Term::Integer` / `Float` / `String` / `Symbol`) leave the
110 /// hyperedge position as `None`. Aggregate terms in body atoms
111 /// are not allowed by the parser (aggregates appear only in rule
112 /// heads), but if one is encountered it is treated as a constant
113 /// position — the head-aggregation flag captures the eligibility
114 /// boundary regardless.
115 pub fn from_rule(rule: &Rule) -> Self {
116 let mut vertices: Vec<Vertex> = Vec::new();
117 let mut name_to_id: HashMap<String, VertexId> = HashMap::new();
118
119 let mut hyperedges = Vec::new();
120 let mut has_negation = false;
121 let mut has_is_expr = false;
122 let mut comparison_count = 0;
123
124 for literal in &rule.body {
125 match literal {
126 BodyLiteral::Positive(atom) => {
127 hyperedges.push(build_hyperedge(atom, &mut vertices, &mut name_to_id));
128 }
129 BodyLiteral::Negated(_) => {
130 has_negation = true;
131 }
132 BodyLiteral::Epistemic(_) => {
133 has_negation = true;
134 }
135 BodyLiteral::Comparison(_) => {
136 comparison_count += 1;
137 }
138 BodyLiteral::IsExpr(_) => {
139 has_is_expr = true;
140 }
141 BodyLiteral::Univ(_) => {
142 comparison_count += 1;
143 }
144 }
145 }
146
147 Self {
148 head_predicate: rule.head.predicate.clone(),
149 vertices,
150 hyperedges,
151 head_has_aggregation: rule.has_aggregation(),
152 has_negation,
153 has_is_expr,
154 comparison_count,
155 is_fact: rule.is_fact(),
156 }
157 }
158
159 /// Number of distinct variables referenced by the body. Equals
160 /// `self.vertices.len()`.
161 pub fn vertex_count(&self) -> usize {
162 self.vertices.len()
163 }
164
165 /// Number of positive body atoms.
166 pub fn hyperedge_count(&self) -> usize {
167 self.hyperedges.len()
168 }
169
170 /// Look up a vertex by id. Panics if `id` is out of range —
171 /// `VertexId`s are only allocated by [`Self::from_rule`], so an
172 /// out-of-range id is a programmer error, not a data error.
173 pub fn vertex(&self, id: VertexId) -> &Vertex {
174 &self.vertices[id.0]
175 }
176
177 /// Iterate over vertex ids in allocation (first-appearance) order.
178 pub fn vertex_ids(&self) -> impl Iterator<Item = VertexId> + '_ {
179 (0..self.vertices.len()).map(VertexId)
180 }
181}
182
183fn build_hyperedge(
184 atom: &Atom,
185 vertices: &mut Vec<Vertex>,
186 name_to_id: &mut HashMap<String, VertexId>,
187) -> Hyperedge {
188 let mut positions = Vec::with_capacity(atom.terms.len());
189 for term in &atom.terms {
190 let pos = match term {
191 Term::Variable(name) => {
192 if let Some(id) = name_to_id.get(name) {
193 Some(*id)
194 } else {
195 let id = VertexId(vertices.len());
196 vertices.push(Vertex { name: name.clone() });
197 name_to_id.insert(name.clone(), id);
198 Some(id)
199 }
200 }
201 // Anonymous wildcards do not participate in the join
202 // graph: each occurrence is a fresh unconstrained
203 // position and `_` shared across atoms is by convention
204 // not the same variable.
205 Term::Anonymous => None,
206 // Constants and aggregate terms in body positions are
207 // treated as fixed values — no vertex.
208 Term::Integer(_)
209 | Term::Float(_)
210 | Term::String(_)
211 | Term::Symbol(_)
212 | Term::Aggregate(_)
213 | Term::List(_)
214 | Term::Cons { .. }
215 | Term::Compound { .. }
216 | Term::PredRef(_) => None,
217 };
218 positions.push(pos);
219 }
220 Hyperedge {
221 predicate: atom.predicate.clone(),
222 vertex_positions: positions,
223 }
224}