1use crate::NQuin;
2
3pub const MAX_STABLE_MODELS: usize = 8;
4
5pub fn enumerate_stable_models(
8 base: &NQuin,
9 rules: &[NQuin],
10 out_worlds: &mut [u64; MAX_STABLE_MODELS],
11) -> usize {
12 if rules.is_empty() {
13 out_worlds[0] = base.context;
14 return 1;
15 }
16
17 let mut num_worlds = 1;
18 out_worlds[0] = base.context;
19
20 for rule in rules.iter().take(3) {
23 let current_worlds = num_worlds;
25 for w in 0..current_worlds {
26 if num_worlds < MAX_STABLE_MODELS {
27 out_worlds[num_worlds] = out_worlds[w] ^ rule.subject ^ rule.object;
29 num_worlds += 1;
30 }
31 }
32 }
33
34 num_worlds
35}
36
37pub const ASP_MAX_ATOMS: usize = 12; pub const ASP_MAX_BODY: usize = 6;
50
51#[derive(Clone, Copy)]
54pub struct AspRule {
55 pub head: u64,
56 pub pos: [u64; ASP_MAX_BODY],
57 pub pos_len: usize,
58 pub neg: [u64; ASP_MAX_BODY],
59 pub neg_len: usize,
60}
61
62impl AspRule {
63 pub fn new(head: u64, pos: &[u64], neg: &[u64]) -> Self {
66 let mut r = AspRule {
67 head,
68 pos: [0; ASP_MAX_BODY],
69 pos_len: 0,
70 neg: [0; ASP_MAX_BODY],
71 neg_len: 0,
72 };
73 for &a in pos.iter().take(ASP_MAX_BODY) {
74 r.pos[r.pos_len] = a;
75 r.pos_len += 1;
76 }
77 for &a in neg.iter().take(ASP_MAX_BODY) {
78 r.neg[r.neg_len] = a;
79 r.neg_len += 1;
80 }
81 r
82 }
83 pub fn fact(head: u64) -> Self {
85 Self::new(head, &[], &[])
86 }
87 pub fn constraint(pos: &[u64], neg: &[u64]) -> Self {
90 Self::new(0, pos, neg)
91 }
92}
93
94pub fn compute_answer_sets(atoms: &[u64], rules: &[AspRule], out: &mut [u64]) -> usize {
98 let n = atoms.len().min(ASP_MAX_ATOMS);
99 let idx = |a: u64| -> Option<usize> { atoms[..n].iter().position(|&x| x == a) };
100 let removed_by_reduct = |r: &AspRule, cand: u64| -> bool {
101 for &na in &r.neg[..r.neg_len] {
103 if let Some(ni) = idx(na) {
104 if cand & (1u64 << ni) != 0 {
105 return true;
106 }
107 }
108 }
109 false
110 };
111 let body_pos_in = |r: &AspRule, m: u64| -> bool {
112 for &pa in &r.pos[..r.pos_len] {
113 match idx(pa) {
114 Some(pi) if m & (1u64 << pi) != 0 => {}
115 _ => return false,
116 }
117 }
118 true
119 };
120
121 let mut found = 0usize;
122 let total: u64 = 1u64 << n;
123 for cand in 0..total {
124 let mut m: u64 = 0;
126 loop {
127 let mut changed = false;
128 for r in rules {
129 if r.head == 0 || removed_by_reduct(r, cand) {
130 continue;
131 }
132 if body_pos_in(r, m) {
133 if let Some(hi) = idx(r.head) {
134 if m & (1u64 << hi) == 0 {
135 m |= 1u64 << hi;
136 changed = true;
137 }
138 }
139 }
140 }
141 if !changed {
142 break;
143 }
144 }
145 if m != cand {
147 continue;
148 }
149 let mut ok = true;
151 for r in rules {
152 if r.head != 0 || removed_by_reduct(r, cand) {
153 continue;
154 }
155 if body_pos_in(r, m) {
156 ok = false;
157 break;
158 }
159 }
160 if ok {
161 if found >= out.len() {
162 break;
163 }
164 out[found] = m;
165 found += 1;
166 }
167 }
168 found
169}
170
171#[inline]
175pub fn atom_index(atoms: &[u64], a: u64) -> Option<usize> {
176 atoms.iter().take(ASP_MAX_ATOMS).position(|&x| x == a)
177}
178
179#[inline]
183fn body_holds(atoms: &[u64], model: u64, pos: &[u64], neg: &[u64]) -> bool {
184 for &p in pos {
185 match atom_index(atoms, p) {
186 Some(i) if model & (1u64 << i) != 0 => {}
187 _ => return false,
188 }
189 }
190 for &nn in neg {
191 if let Some(i) = atom_index(atoms, nn) {
192 if model & (1u64 << i) != 0 {
193 return false;
194 }
195 }
196 }
197 true
198}
199
200pub fn ground_rule(template: &AspRule, var: u64, domain: &[u64], out: &mut [AspRule]) -> usize {
207 let subst = |a: u64, d: u64| if a == var { d } else { a };
208 let mut n = 0usize;
209 for &d in domain {
210 if n >= out.len() {
211 break;
212 }
213 let mut g = *template;
214 g.head = subst(g.head, d);
215 for i in 0..g.pos_len {
216 g.pos[i] = subst(g.pos[i], d);
217 }
218 for i in 0..g.neg_len {
219 g.neg[i] = subst(g.neg[i], d);
220 }
221 out[n] = g;
222 n += 1;
223 }
224 n
225}
226
227#[derive(Clone, Copy)]
232pub struct WeakConstraint {
233 pub pos: [u64; ASP_MAX_BODY],
234 pub pos_len: usize,
235 pub neg: [u64; ASP_MAX_BODY],
236 pub neg_len: usize,
237 pub weight: i64,
238}
239
240impl WeakConstraint {
241 pub fn new(pos: &[u64], neg: &[u64], weight: i64) -> Self {
245 let mut w = WeakConstraint {
246 pos: [0; ASP_MAX_BODY],
247 pos_len: 0,
248 neg: [0; ASP_MAX_BODY],
249 neg_len: 0,
250 weight,
251 };
252 for &a in pos.iter().take(ASP_MAX_BODY) {
253 w.pos[w.pos_len] = a;
254 w.pos_len += 1;
255 }
256 for &a in neg.iter().take(ASP_MAX_BODY) {
257 w.neg[w.neg_len] = a;
258 w.neg_len += 1;
259 }
260 w
261 }
262}
263
264pub fn model_penalty(atoms: &[u64], model: u64, weak: &[WeakConstraint]) -> i64 {
267 let mut total = 0i64;
268 for w in weak {
269 if body_holds(atoms, model, &w.pos[..w.pos_len], &w.neg[..w.neg_len]) {
270 total += w.weight;
271 }
272 }
273 total
274}
275
276pub fn optimal_answer_set(
280 atoms: &[u64],
281 rules: &[AspRule],
282 weak: &[WeakConstraint],
283 buf: &mut [u64],
284) -> Option<(u64, i64)> {
285 let k = compute_answer_sets(atoms, rules, buf);
286 if k == 0 {
287 return None;
288 }
289 let mut best = (buf[0], model_penalty(atoms, buf[0], weak));
290 for &m in &buf[1..k] {
291 let p = model_penalty(atoms, m, weak);
292 if p < best.1 {
293 best = (m, p);
294 }
295 }
296 Some(best)
297}
298
299pub fn cautious_consequences(models: &[u64]) -> u64 {
304 match models.split_first() {
305 Some((&first, rest)) => rest.iter().fold(first, |acc, &m| acc & m),
306 None => 0,
307 }
308}
309
310pub fn brave_consequences(models: &[u64]) -> u64 {
312 models.iter().fold(0u64, |acc, &m| acc | m)
313}
314
315#[derive(Debug, Clone, Copy, PartialEq, Eq)]
321pub enum AspOutcome {
322 Stable(usize),
324 NoStableModel,
326}
327
328pub fn answer_sets_or_paraconsistent(
332 atoms: &[u64],
333 rules: &[AspRule],
334 out: &mut [u64],
335) -> AspOutcome {
336 let k = compute_answer_sets(atoms, rules, out);
337 if k == 0 {
338 AspOutcome::NoStableModel
339 } else {
340 AspOutcome::Stable(k)
341 }
342}
343
344#[cfg(test)]
345mod tests {
346 use super::*;
347
348 #[test]
350 fn answer_sets_even_loop_and_constraint() {
351 let (p, q) = (101u64, 202u64);
352 let atoms = [p, q];
353 let prog = [AspRule::new(p, &[], &[q]), AspRule::new(q, &[], &[p])];
355 let mut out = [0u64; 8];
356 let k = compute_answer_sets(&atoms, &prog, &mut out);
357 assert_eq!(k, 2, "even loop has exactly two stable models");
358 let bp = 1u64 << 0; let bq = 1u64 << 1; assert!(
361 out[..k].contains(&bp) && out[..k].contains(&bq),
362 "the two answer sets are {{p}} and {{q}}"
363 );
364
365 let prog2 = [
367 AspRule::new(p, &[], &[q]),
368 AspRule::new(q, &[], &[p]),
369 AspRule::constraint(&[q], &[]),
370 ];
371 let mut out2 = [0u64; 8];
372 let k2 = compute_answer_sets(&atoms, &prog2, &mut out2);
373 assert_eq!(k2, 1, "the constraint prunes {{q}}");
374 assert_eq!(out2[0], bp, "only {{p}} remains");
375 }
376
377 #[test]
378 fn test_enumerate_stable_models() {
379 let base = NQuin {
380 subject: 0,
381 predicate: 0,
382 object: 0,
383 context: 42,
384 metadata: 0,
385 parity: 0,
386 };
387 let mut out_worlds = [0; MAX_STABLE_MODELS];
388
389 let count = enumerate_stable_models(&base, &[], &mut out_worlds);
391 assert_eq!(count, 1);
392 assert_eq!(out_worlds[0], 42);
393
394 let rule = NQuin {
396 subject: 10,
397 predicate: 0,
398 object: 20,
399 context: 0,
400 metadata: 0,
401 parity: 0,
402 };
403 let count2 = enumerate_stable_models(&base, &[rule], &mut out_worlds);
404 assert_eq!(count2, 2);
405 assert_eq!(out_worlds[0], 42);
406 assert_eq!(out_worlds[1], 42 ^ 10 ^ 20);
407 }
408
409 #[test]
410 fn grounder_instantiates_a_template_over_a_domain() {
411 let var = crate::q_hash("var:X");
413 let node = |x: u64| x; let template = AspRule::fact(var);
415 let (a, b, c) = (node(11), node(22), node(33));
416 let mut out = [AspRule::fact(0); 8];
417 let n = ground_rule(&template, var, &[a, b, c], &mut out);
418 assert_eq!(n, 3);
419 assert_eq!(out[0].head, a);
420 assert_eq!(out[1].head, b);
421 assert_eq!(out[2].head, c);
422 }
423
424 #[test]
425 fn weak_constraints_select_the_optimal_model() {
426 let (p, q) = (101u64, 202u64);
427 let atoms = [p, q];
428 let prog = [AspRule::new(p, &[], &[q]), AspRule::new(q, &[], &[p])];
430 let weak = [WeakConstraint::new(&[q], &[], 1)];
431 let mut buf = [0u64; 8];
432 let (best, penalty) = optimal_answer_set(&atoms, &prog, &weak, &mut buf).unwrap();
433 assert_eq!(best, 1u64 << 0, "optimal model is {{p}} (no penalty)");
434 assert_eq!(penalty, 0);
435 assert_eq!(model_penalty(&atoms, 1u64 << 1, &weak), 1);
437 }
438
439 #[test]
440 fn cautious_and_brave_consequences() {
441 let (p, q) = (101u64, 202u64);
442 let atoms = [p, q];
443 let prog = [AspRule::new(p, &[], &[q]), AspRule::new(q, &[], &[p])];
444 let mut buf = [0u64; 8];
445 let k = compute_answer_sets(&atoms, &prog, &mut buf);
446 assert_eq!(k, 2);
447 assert_eq!(cautious_consequences(&buf[..k]), 0);
449 assert_eq!(brave_consequences(&buf[..k]), (1u64 << 0) | (1u64 << 1));
450 }
451
452 #[test]
453 fn no_stable_model_routes_to_paraconsistent() {
454 let p = 101u64;
455 let atoms = [p];
456 let prog = [AspRule::new(p, &[], &[p])];
458 let mut out = [0u64; 8];
459 assert_eq!(
460 answer_sets_or_paraconsistent(&atoms, &prog, &mut out),
461 AspOutcome::NoStableModel
462 );
463 let prog2 = [AspRule::fact(p)];
465 assert_eq!(
466 answer_sets_or_paraconsistent(&atoms, &prog2, &mut out),
467 AspOutcome::Stable(1)
468 );
469 }
470}