1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Andrew Reynolds, Morgan Deters, Aina Niemetz |
4 |
|
* |
5 |
|
* This file is part of the cvc5 project. |
6 |
|
* |
7 |
|
* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS |
8 |
|
* in the top-level source directory and their institutional affiliations. |
9 |
|
* All rights reserved. See the file COPYING in the top-level source |
10 |
|
* directory for licensing information. |
11 |
|
* **************************************************************************** |
12 |
|
* |
13 |
|
* Implementation of quantifier utilities |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/quantifiers/quant_util.h" |
17 |
|
|
18 |
|
#include "theory/quantifiers/term_util.h" |
19 |
|
|
20 |
|
using namespace cvc5::kind; |
21 |
|
|
22 |
|
namespace cvc5 { |
23 |
|
namespace theory { |
24 |
|
|
25 |
49667 |
QuantifiersUtil::QuantifiersUtil(Env& env) : EnvObj(env) {} |
26 |
|
|
27 |
112744 |
QuantPhaseReq::QuantPhaseReq( Node n, bool computeEq ){ |
28 |
112744 |
initialize( n, computeEq ); |
29 |
112744 |
} |
30 |
|
|
31 |
112744 |
void QuantPhaseReq::initialize( Node n, bool computeEq ){ |
32 |
225488 |
std::map< Node, int > phaseReqs2; |
33 |
112744 |
computePhaseReqs( n, false, phaseReqs2 ); |
34 |
308912 |
for( std::map< Node, int >::iterator it = phaseReqs2.begin(); it != phaseReqs2.end(); ++it ){ |
35 |
196168 |
if( it->second==1 ){ |
36 |
88680 |
d_phase_reqs[ it->first ] = true; |
37 |
107488 |
}else if( it->second==-1 ){ |
38 |
107421 |
d_phase_reqs[ it->first ] = false; |
39 |
|
} |
40 |
|
} |
41 |
112744 |
Debug("inst-engine-phase-req") << "Phase requirements for " << n << ":" << std::endl; |
42 |
|
//now, compute if any patterns are equality required |
43 |
112744 |
if( computeEq ){ |
44 |
|
for( std::map< Node, bool >::iterator it = d_phase_reqs.begin(); it != d_phase_reqs.end(); ++it ){ |
45 |
|
Debug("inst-engine-phase-req") << " " << it->first << " -> " << it->second << std::endl; |
46 |
|
if( it->first.getKind()==EQUAL ){ |
47 |
|
if( quantifiers::TermUtil::hasInstConstAttr(it->first[0]) ){ |
48 |
|
if( !quantifiers::TermUtil::hasInstConstAttr(it->first[1]) ){ |
49 |
|
d_phase_reqs_equality_term[ it->first[0] ] = it->first[1]; |
50 |
|
d_phase_reqs_equality[ it->first[0] ] = it->second; |
51 |
|
Debug("inst-engine-phase-req") << " " << it->first[0] << ( it->second ? " == " : " != " ) << it->first[1] << std::endl; |
52 |
|
} |
53 |
|
}else if( quantifiers::TermUtil::hasInstConstAttr(it->first[1]) ){ |
54 |
|
d_phase_reqs_equality_term[ it->first[1] ] = it->first[0]; |
55 |
|
d_phase_reqs_equality[ it->first[1] ] = it->second; |
56 |
|
Debug("inst-engine-phase-req") << " " << it->first[1] << ( it->second ? " == " : " != " ) << it->first[0] << std::endl; |
57 |
|
} |
58 |
|
} |
59 |
|
} |
60 |
|
} |
61 |
112744 |
} |
62 |
|
|
63 |
339922 |
void QuantPhaseReq::computePhaseReqs( Node n, bool polarity, std::map< Node, int >& phaseReqs ){ |
64 |
339922 |
bool newReqPol = false; |
65 |
|
bool newPolarity; |
66 |
339922 |
if( n.getKind()==NOT ){ |
67 |
88749 |
newReqPol = true; |
68 |
88749 |
newPolarity = !polarity; |
69 |
251173 |
}else if( n.getKind()==OR || n.getKind()==IMPLIES ){ |
70 |
45411 |
if( !polarity ){ |
71 |
45411 |
newReqPol = true; |
72 |
45411 |
newPolarity = false; |
73 |
|
} |
74 |
205762 |
}else if( n.getKind()==AND ){ |
75 |
9525 |
if( polarity ){ |
76 |
|
newReqPol = true; |
77 |
|
newPolarity = true; |
78 |
|
} |
79 |
|
}else{ |
80 |
196237 |
int val = polarity ? 1 : -1; |
81 |
196237 |
if( phaseReqs.find( n )==phaseReqs.end() ){ |
82 |
196168 |
phaseReqs[n] = val; |
83 |
69 |
}else if( val!=phaseReqs[n] ){ |
84 |
67 |
phaseReqs[n] = 0; |
85 |
|
} |
86 |
|
} |
87 |
339922 |
if( newReqPol ){ |
88 |
361338 |
for( int i=0; i<(int)n.getNumChildren(); i++ ){ |
89 |
227178 |
if( n.getKind()==IMPLIES && i==0 ){ |
90 |
|
computePhaseReqs( n[i], !newPolarity, phaseReqs ); |
91 |
|
}else{ |
92 |
227178 |
computePhaseReqs( n[i], newPolarity, phaseReqs ); |
93 |
|
} |
94 |
|
} |
95 |
|
} |
96 |
339922 |
} |
97 |
|
|
98 |
1507260 |
void QuantPhaseReq::getPolarity( |
99 |
|
Node n, size_t child, bool hasPol, bool pol, bool& newHasPol, bool& newPol) |
100 |
|
{ |
101 |
1507260 |
if( n.getKind()==AND || n.getKind()==OR || n.getKind()==SEP_STAR ){ |
102 |
347648 |
newHasPol = hasPol; |
103 |
347648 |
newPol = pol; |
104 |
1159612 |
}else if( n.getKind()==IMPLIES ){ |
105 |
8 |
newHasPol = hasPol; |
106 |
8 |
newPol = child==0 ? !pol : pol; |
107 |
1159604 |
}else if( n.getKind()==NOT ){ |
108 |
175469 |
newHasPol = hasPol; |
109 |
175469 |
newPol = !pol; |
110 |
984135 |
}else if( n.getKind()==ITE ){ |
111 |
15861 |
newHasPol = (child!=0) && hasPol; |
112 |
15861 |
newPol = pol; |
113 |
968274 |
}else if( n.getKind()==FORALL ){ |
114 |
152 |
newHasPol = (child==1) && hasPol; |
115 |
152 |
newPol = pol; |
116 |
|
}else{ |
117 |
968122 |
newHasPol = false; |
118 |
968122 |
newPol = false; |
119 |
|
} |
120 |
1507260 |
} |
121 |
|
|
122 |
4003257 |
void QuantPhaseReq::getEntailPolarity( |
123 |
|
Node n, size_t child, bool hasPol, bool pol, bool& newHasPol, bool& newPol) |
124 |
|
{ |
125 |
4003257 |
if( n.getKind()==AND || n.getKind()==OR || n.getKind()==SEP_STAR ){ |
126 |
2001939 |
newHasPol = hasPol && pol!=( n.getKind()==OR ); |
127 |
2001939 |
newPol = pol; |
128 |
2001318 |
}else if( n.getKind()==IMPLIES ){ |
129 |
22940 |
newHasPol = hasPol && !pol; |
130 |
22940 |
newPol = child==0 ? !pol : pol; |
131 |
1978378 |
}else if( n.getKind()==NOT ){ |
132 |
252305 |
newHasPol = hasPol; |
133 |
252305 |
newPol = !pol; |
134 |
|
}else{ |
135 |
1726073 |
newHasPol = false; |
136 |
1726073 |
newPol = false; |
137 |
|
} |
138 |
4003257 |
} |
139 |
|
|
140 |
|
} // namespace theory |
141 |
29502 |
} // namespace cvc5 |