1#![allow(missing_docs)] #[allow(unused_imports)]
35use crate::prelude::*;
36
37pub type Lit = i32;
39
40pub type Var = u32;
42
43pub type ClauseId = usize;
45
46#[derive(Debug, Clone, PartialEq, Eq, Hash)]
48pub struct Clause {
49 pub literals: Vec<Lit>,
50}
51
52impl Clause {
53 pub fn new(literals: Vec<Lit>) -> Self {
55 Self { literals }
56 }
57
58 pub fn is_unit(&self) -> bool {
60 self.literals.len() == 1
61 }
62
63 pub fn is_binary(&self) -> bool {
65 self.literals.len() == 2
66 }
67
68 pub fn is_empty(&self) -> bool {
70 self.literals.is_empty()
71 }
72
73 pub fn contains(&self, lit: Lit) -> bool {
75 self.literals.contains(&lit)
76 }
77
78 pub fn size(&self) -> usize {
80 self.literals.len()
81 }
82}
83
84#[derive(Debug, Clone, Default)]
86pub struct PreprocessingStats {
87 pub variables_eliminated: u64,
88 pub clauses_eliminated: u64,
89 pub literals_eliminated: u64,
90 pub subsumptions: u64,
91 pub self_subsuming_resolutions: u64,
92 pub vivifications: u64,
93 pub blocked_clauses: u64,
94 pub equivalent_literals: u64,
95}
96
97#[derive(Debug, Clone)]
99pub struct PreprocessingConfig {
100 pub enable_bve: bool,
102 pub bve_clause_limit: usize,
104 pub enable_subsumption: bool,
106 pub enable_vivification: bool,
108 pub enable_bce: bool,
110 pub enable_equiv_literals: bool,
112 pub max_iterations: usize,
114}
115
116impl Default for PreprocessingConfig {
117 fn default() -> Self {
118 Self {
119 enable_bve: true,
120 bve_clause_limit: 100,
121 enable_subsumption: true,
122 enable_vivification: true,
123 enable_bce: true,
124 enable_equiv_literals: true,
125 max_iterations: 10,
126 }
127 }
128}
129
130pub struct AdvancedPreprocessor {
132 config: PreprocessingConfig,
133 stats: PreprocessingStats,
134 clauses: Vec<Clause>,
136 occurrences: FxHashMap<Lit, Vec<ClauseId>>,
138 elim_order: Vec<Var>,
140 eliminated: FxHashSet<Var>,
142}
143
144impl AdvancedPreprocessor {
145 pub fn new(config: PreprocessingConfig) -> Self {
147 Self {
148 config,
149 stats: PreprocessingStats::default(),
150 clauses: Vec::new(),
151 occurrences: FxHashMap::default(),
152 elim_order: Vec::new(),
153 eliminated: FxHashSet::default(),
154 }
155 }
156
157 pub fn preprocess(&mut self, clauses: Vec<Clause>) -> Result<Vec<Clause>, String> {
159 self.clauses = clauses;
160 self.build_occurrence_lists();
161
162 for _iteration in 0..self.config.max_iterations {
164 let mut changed = false;
165
166 changed |= self.unit_propagation()?;
168
169 if self.config.enable_subsumption {
171 changed |= self.subsumption()?;
172 }
173
174 if self.config.enable_subsumption {
176 changed |= self.self_subsuming_resolution()?;
177 }
178
179 if self.config.enable_vivification {
181 changed |= self.vivification()?;
182 }
183
184 if self.config.enable_bve {
186 changed |= self.bounded_variable_elimination()?;
187 }
188
189 if self.config.enable_bce {
191 changed |= self.blocked_clause_elimination()?;
192 }
193
194 if self.config.enable_equiv_literals {
196 changed |= self.equivalent_literal_substitution()?;
197 }
198
199 if !changed {
201 break;
202 }
203 }
204
205 Ok(self.clauses.clone())
207 }
208
209 fn build_occurrence_lists(&mut self) {
211 self.occurrences.clear();
212
213 for (clause_id, clause) in self.clauses.iter().enumerate() {
214 for &lit in &clause.literals {
215 self.occurrences.entry(lit).or_default().push(clause_id);
216 }
217 }
218 }
219
220 fn unit_propagation(&mut self) -> Result<bool, String> {
222 let mut changed = false;
223
224 loop {
225 let unit_clauses: Vec<_> = self
227 .clauses
228 .iter()
229 .filter(|c| c.is_unit())
230 .cloned()
231 .collect();
232
233 if unit_clauses.is_empty() {
234 break;
235 }
236
237 for unit_clause in unit_clauses {
238 let unit_lit = unit_clause.literals[0];
239
240 self.propagate_literal(unit_lit)?;
242 changed = true;
243 }
244 }
245
246 Ok(changed)
247 }
248
249 fn propagate_literal(&mut self, lit: Lit) -> Result<(), String> {
251 let neg_lit = -lit;
252
253 self.clauses.retain(|c| !c.contains(lit));
255
256 for clause in &mut self.clauses {
258 if clause.contains(neg_lit) {
259 clause.literals.retain(|&l| l != neg_lit);
260 self.stats.literals_eliminated += 1;
261 }
262 }
263
264 if self.clauses.iter().any(|c| c.is_empty()) {
266 return Err("Formula is unsatisfiable".to_string());
267 }
268
269 self.build_occurrence_lists();
270 Ok(())
271 }
272
273 fn subsumption(&mut self) -> Result<bool, String> {
275 let mut changed = false;
276 let mut to_remove = FxHashSet::default();
277
278 for i in 0..self.clauses.len() {
279 if to_remove.contains(&i) {
280 continue;
281 }
282
283 for j in (i + 1)..self.clauses.len() {
284 if to_remove.contains(&j) {
285 continue;
286 }
287
288 if self.subsumes(&self.clauses[i], &self.clauses[j]) {
290 to_remove.insert(j);
291 self.stats.subsumptions += 1;
292 changed = true;
293 }
294 else if self.subsumes(&self.clauses[j], &self.clauses[i]) {
296 to_remove.insert(i);
297 self.stats.subsumptions += 1;
298 changed = true;
299 break;
300 }
301 }
302 }
303
304 let mut new_clauses = Vec::new();
306 for (i, clause) in self.clauses.iter().enumerate() {
307 if !to_remove.contains(&i) {
308 new_clauses.push(clause.clone());
309 }
310 }
311
312 self.clauses = new_clauses;
313 self.stats.clauses_eliminated += to_remove.len() as u64;
314
315 if changed {
316 self.build_occurrence_lists();
317 }
318
319 Ok(changed)
320 }
321
322 fn subsumes(&self, clause1: &Clause, clause2: &Clause) -> bool {
324 if clause1.size() > clause2.size() {
325 return false;
326 }
327
328 clause1.literals.iter().all(|lit| clause2.contains(*lit))
329 }
330
331 fn self_subsuming_resolution(&mut self) -> Result<bool, String> {
333 let mut changed = false;
334
335 for i in 0..self.clauses.len() {
336 for j in (i + 1)..self.clauses.len() {
337 if let Some(resolvent) =
339 self.try_self_subsuming_resolution(&self.clauses[i], &self.clauses[j])
340 {
341 if self.clauses[i].size() > self.clauses[j].size() {
343 self.clauses[i] = resolvent;
344 } else {
345 self.clauses[j] = resolvent;
346 }
347
348 self.stats.self_subsuming_resolutions += 1;
349 changed = true;
350 }
351 }
352 }
353
354 if changed {
355 self.build_occurrence_lists();
356 }
357
358 Ok(changed)
359 }
360
361 fn try_self_subsuming_resolution(&self, c1: &Clause, c2: &Clause) -> Option<Clause> {
363 for &lit in &c1.literals {
365 if c2.contains(-lit) {
366 let c1_without_lit: FxHashSet<_> =
368 c1.literals.iter().filter(|&&l| l != lit).copied().collect();
369
370 if c1_without_lit.iter().all(|l| c2.contains(*l)) {
371 let resolvent_lits: Vec<_> = c2
373 .literals
374 .iter()
375 .filter(|&&l| l != -lit)
376 .copied()
377 .collect();
378
379 return Some(Clause::new(resolvent_lits));
380 }
381 }
382 }
383
384 None
385 }
386
387 fn vivification(&mut self) -> Result<bool, String> {
389 let mut changed = false;
390
391 let indices_to_process: Vec<usize> = self
393 .clauses
394 .iter()
395 .enumerate()
396 .filter(|(_, clause)| clause.size() > 2)
397 .map(|(i, _)| i)
398 .collect();
399
400 for idx in indices_to_process {
401 let clause = &self.clauses[idx];
402 if let Some(strengthened) = self.try_strengthen_clause(clause) {
404 self.clauses[idx] = strengthened;
405 self.stats.vivifications += 1;
406 changed = true;
407 }
408 }
409
410 if changed {
411 self.build_occurrence_lists();
412 }
413
414 Ok(changed)
415 }
416
417 fn try_strengthen_clause(&self, clause: &Clause) -> Option<Clause> {
419 let mut unique_lits: Vec<_> = clause.literals.clone();
422 unique_lits.sort();
423 unique_lits.dedup();
424
425 if unique_lits.len() < clause.literals.len() {
426 Some(Clause::new(unique_lits))
427 } else {
428 None
429 }
430 }
431
432 fn bounded_variable_elimination(&mut self) -> Result<bool, String> {
434 let mut changed = false;
435
436 self.compute_elimination_order();
438
439 for &var in &self.elim_order.clone() {
440 if self.eliminated.contains(&var) {
441 continue;
442 }
443
444 if self.try_eliminate_variable(var)? {
446 self.eliminated.insert(var);
447 self.stats.variables_eliminated += 1;
448 changed = true;
449 }
450 }
451
452 if changed {
453 self.build_occurrence_lists();
454 }
455
456 Ok(changed)
457 }
458
459 fn compute_elimination_order(&mut self) {
461 let mut var_occurrences: FxHashMap<Var, usize> = FxHashMap::default();
462
463 for clause in &self.clauses {
464 for &lit in &clause.literals {
465 let var = lit.unsigned_abs();
466 *var_occurrences.entry(var).or_insert(0) += 1;
467 }
468 }
469
470 let mut vars: Vec<_> = var_occurrences.into_iter().collect();
472 vars.sort_by_key(|(_, count)| *count);
473
474 self.elim_order = vars.into_iter().map(|(var, _)| var).collect();
475 }
476
477 fn try_eliminate_variable(&mut self, var: Var) -> Result<bool, String> {
479 let pos_lit = var as Lit;
480 let neg_lit = -(var as Lit);
481
482 let pos_clauses: Vec<_> = self
484 .clauses
485 .iter()
486 .filter(|c| c.contains(pos_lit))
487 .cloned()
488 .collect();
489
490 let neg_clauses: Vec<_> = self
491 .clauses
492 .iter()
493 .filter(|c| c.contains(neg_lit))
494 .cloned()
495 .collect();
496
497 let mut resolvents = Vec::new();
499
500 for pos_clause in &pos_clauses {
501 for neg_clause in &neg_clauses {
502 if let Some(resolvent) = self.resolve(pos_clause, neg_clause, pos_lit) {
503 resolvents.push(resolvent);
504 }
505 }
506 }
507
508 let old_clause_count = pos_clauses.len() + neg_clauses.len();
510 let new_clause_count = resolvents.len();
511
512 if new_clause_count > self.config.bve_clause_limit
513 || new_clause_count > old_clause_count * 2
514 {
515 return Ok(false);
516 }
517
518 self.clauses
520 .retain(|c| !c.contains(pos_lit) && !c.contains(neg_lit));
521 self.clauses.extend(resolvents);
522
523 self.stats.clauses_eliminated += old_clause_count as u64;
524
525 Ok(true)
526 }
527
528 fn resolve(&self, c1: &Clause, c2: &Clause, pivot: Lit) -> Option<Clause> {
530 let mut resolvent_lits = FxHashSet::default();
531
532 for &lit in &c1.literals {
534 if lit != pivot {
535 resolvent_lits.insert(lit);
536 }
537 }
538
539 for &lit in &c2.literals {
541 if lit != -pivot {
542 if resolvent_lits.contains(&-lit) {
544 return None;
545 }
546 resolvent_lits.insert(lit);
547 }
548 }
549
550 Some(Clause::new(resolvent_lits.into_iter().collect()))
551 }
552
553 fn blocked_clause_elimination(&mut self) -> Result<bool, String> {
555 let mut changed = false;
556 let mut to_remove = FxHashSet::default();
557
558 for (clause_id, clause) in self.clauses.iter().enumerate() {
559 for &lit in &clause.literals {
561 if self.is_blocked(clause, lit) {
562 to_remove.insert(clause_id);
563 self.stats.blocked_clauses += 1;
564 changed = true;
565 break;
566 }
567 }
568 }
569
570 let mut new_clauses = Vec::new();
572 for (i, clause) in self.clauses.iter().enumerate() {
573 if !to_remove.contains(&i) {
574 new_clauses.push(clause.clone());
575 }
576 }
577
578 self.clauses = new_clauses;
579
580 if changed {
581 self.build_occurrence_lists();
582 }
583
584 Ok(changed)
585 }
586
587 fn is_blocked(&self, clause: &Clause, lit: Lit) -> bool {
589 let neg_lit = -lit;
591
592 for other_clause in &self.clauses {
593 if other_clause.contains(neg_lit)
594 && let Some(_resolvent) = self.resolve(clause, other_clause, lit)
595 {
596 return false;
598 }
599 }
600
601 true
602 }
603
604 fn equivalent_literal_substitution(&mut self) -> Result<bool, String> {
606 let mut changed = false;
607
608 let equiv_classes = self.find_equivalent_literals();
610
611 for (representative, equivalents) in equiv_classes {
613 for equiv in equivalents {
614 self.substitute_literal(equiv, representative);
615 self.stats.equivalent_literals += 1;
616 changed = true;
617 }
618 }
619
620 if changed {
621 self.build_occurrence_lists();
622 }
623
624 Ok(changed)
625 }
626
627 fn find_equivalent_literals(&self) -> FxHashMap<Lit, Vec<Lit>> {
629 let mut implications: FxHashMap<Lit, Vec<Lit>> = FxHashMap::default();
630
631 for clause in &self.clauses {
633 if clause.is_binary() {
634 let lit1 = clause.literals[0];
635 let lit2 = clause.literals[1];
636
637 implications.entry(-lit1).or_default().push(lit2);
639 implications.entry(-lit2).or_default().push(lit1);
640 }
641 }
642
643 let mut equiv_classes = FxHashMap::default();
645
646 for (&lit1, targets) in &implications {
649 for &lit2 in targets {
650 if implications.get(&lit2).is_some_and(|t| t.contains(&lit1)) {
651 equiv_classes
653 .entry(lit1.min(lit2))
654 .or_insert_with(Vec::new)
655 .push(lit1.max(lit2));
656 }
657 }
658 }
659
660 equiv_classes
661 }
662
663 fn substitute_literal(&mut self, from: Lit, to: Lit) {
665 for clause in &mut self.clauses {
666 for lit in &mut clause.literals {
667 if *lit == from {
668 *lit = to;
669 } else if *lit == -from {
670 *lit = -to;
671 }
672 }
673 }
674 }
675
676 pub fn stats(&self) -> &PreprocessingStats {
678 &self.stats
679 }
680}
681
682#[cfg(test)]
683mod tests {
684 use super::*;
685
686 #[test]
687 fn test_preprocessor_creation() {
688 let config = PreprocessingConfig::default();
689 let preprocessor = AdvancedPreprocessor::new(config);
690 assert_eq!(preprocessor.stats.variables_eliminated, 0);
691 }
692
693 #[test]
694 fn test_unit_propagation() {
695 let config = PreprocessingConfig::default();
696 let mut preprocessor = AdvancedPreprocessor::new(config);
697
698 let clauses = vec![
699 Clause::new(vec![1]), Clause::new(vec![1, 2]), Clause::new(vec![-1, 3]), ];
703
704 let result = preprocessor.preprocess(clauses);
705 assert!(result.is_ok());
706
707 let preprocessed = result.expect("Preprocessing must succeed");
708 assert!(preprocessed.len() < 3);
709 }
710
711 #[test]
712 fn test_subsumption() {
713 let config = PreprocessingConfig::default();
714 let mut preprocessor = AdvancedPreprocessor::new(config);
715
716 let clauses = vec![
717 Clause::new(vec![1, 2]), Clause::new(vec![1, 2, 3]), ];
720
721 let result = preprocessor.preprocess(clauses);
722 assert!(result.is_ok());
723
724 let preprocessed = result.expect("Preprocessing must succeed");
725 assert!(preprocessed.len() <= 2);
727 }
728
729 #[test]
730 fn test_clause_operations() {
731 let clause = Clause::new(vec![1, 2, 3]);
732
733 assert!(clause.contains(2));
734 assert!(!clause.contains(4));
735 assert_eq!(clause.size(), 3);
736 assert!(!clause.is_unit());
737 assert!(!clause.is_binary());
738 }
739
740 #[test]
741 fn test_subsumes_check() {
742 let preprocessor = AdvancedPreprocessor::new(PreprocessingConfig::default());
743
744 let c1 = Clause::new(vec![1, 2]);
745 let c2 = Clause::new(vec![1, 2, 3]);
746
747 assert!(preprocessor.subsumes(&c1, &c2));
748 assert!(!preprocessor.subsumes(&c2, &c1));
749 }
750
751 #[test]
752 fn test_resolution() {
753 let preprocessor = AdvancedPreprocessor::new(PreprocessingConfig::default());
754
755 let c1 = Clause::new(vec![1, 2]);
756 let c2 = Clause::new(vec![-1, 3]);
757
758 let resolvent = preprocessor.resolve(&c1, &c2, 1);
759 assert!(resolvent.is_some());
760
761 let res = resolvent.expect("Resolution must produce resolvent");
762 assert!(res.contains(2));
763 assert!(res.contains(3));
764 assert!(!res.contains(1));
765 }
766
767 #[test]
768 fn test_tautology_detection() {
769 let preprocessor = AdvancedPreprocessor::new(PreprocessingConfig::default());
770
771 let c1 = Clause::new(vec![1, 2]);
772 let c2 = Clause::new(vec![-1, -2]);
773
774 let resolvent = preprocessor.resolve(&c1, &c2, 1);
776 assert!(resolvent.is_none());
777 }
778
779 #[test]
780 fn test_empty_clause() {
781 let clause = Clause::new(vec![]);
782 assert!(clause.is_empty());
783 }
784}