1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
* This file is part of the source code of the software program
* Vampire. It is protected by applicable
* copyright laws.
*
* This source code is distributed under the licence found here
* https://vprover.github.io/license.html
* and in the source directory
*/
/**
* @file BlockedClauseElimination.hpp
* Defines class BlockedClauseElimination.
*/
#ifndef __BlockedClauseElimination__
#define __BlockedClauseElimination__
#include "Forwards.hpp"
#include "Kernel/Problem.hpp"
#include "Lib/Comparison.hpp"
#include "Lib/Stack.hpp"
#include "Lib/Int.hpp"
namespace Shell {
using namespace Kernel;
/**
* Class for performing first-order BCE.
*/
class BlockedClauseElimination
{
public:
/**
* Equational version of the tautologyhood check is weaker, but has to be used in the presence of positive equalities.
*
* The option forceEquationally forces this even if autodetect would safely not use the equational version.
*/
BlockedClauseElimination(bool forceEquationally = false) : _forceEquationally(forceEquationally) {}
void apply(Kernel::Problem& prb);
private:
bool _forceEquationally;
struct ClWrapper;
struct Candidate {
USE_ALLOCATOR(Candidate);
ClWrapper* clw;
unsigned litIdx; // index of the potentially blocking literal L
unsigned contFrom; // index of the next resolution partner to try in op(L)'s list
unsigned weight; // how many resolution partners still need to be tested -- used to order the priority queue on
};
struct CandidateComparator {
static Comparison compare(Candidate* c1, Candidate* c2) {
return Int::compare(c1->weight,c2->weight);
}
};
struct ClWrapper {
USE_ALLOCATOR(ClWrapper);
Clause* cl; // the actual clause
bool blocked; // if already blocked, don't need to try again
Stack<Candidate*> toResurrect; // when getting block (effectively deleted, all these have a chance again)
ClWrapper(Clause* cl) : cl(cl), blocked(false) {}
};
bool resolvesToTautology(bool equationally, Clause* cl, Literal* lit, Clause* pcl, Literal* plit);
bool resolvesToTautologyUn(Clause* cl, Literal* lit, Clause* pcl, Literal* plit);
bool resolvesToTautologyEq(Clause* cl, Literal* lit, Clause* pcl, Literal* plit);
};
};
#endif /* __BlockedClauseElimination__ */