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 |
112466 |
QuantPhaseReq::QuantPhaseReq( Node n, bool computeEq ){ |
26 |
112466 |
initialize( n, computeEq ); |
27 |
112466 |
} |
28 |
|
|
29 |
112466 |
void QuantPhaseReq::initialize( Node n, bool computeEq ){ |
30 |
224932 |
std::map< Node, int > phaseReqs2; |
31 |
112466 |
computePhaseReqs( n, false, phaseReqs2 ); |
32 |
308279 |
for( std::map< Node, int >::iterator it = phaseReqs2.begin(); it != phaseReqs2.end(); ++it ){ |
33 |
195813 |
if( it->second==1 ){ |
34 |
88499 |
d_phase_reqs[ it->first ] = true; |
35 |
107314 |
}else if( it->second==-1 ){ |
36 |
107247 |
d_phase_reqs[ it->first ] = false; |
37 |
|
} |
38 |
|
} |
39 |
112466 |
Debug("inst-engine-phase-req") << "Phase requirements for " << n << ":" << std::endl; |
40 |
|
//now, compute if any patterns are equality required |
41 |
112466 |
if( computeEq ){ |
42 |
|
for( std::map< Node, bool >::iterator it = d_phase_reqs.begin(); it != d_phase_reqs.end(); ++it ){ |
43 |
|
Debug("inst-engine-phase-req") << " " << it->first << " -> " << it->second << std::endl; |
44 |
|
if( it->first.getKind()==EQUAL ){ |
45 |
|
if( quantifiers::TermUtil::hasInstConstAttr(it->first[0]) ){ |
46 |
|
if( !quantifiers::TermUtil::hasInstConstAttr(it->first[1]) ){ |
47 |
|
d_phase_reqs_equality_term[ it->first[0] ] = it->first[1]; |
48 |
|
d_phase_reqs_equality[ it->first[0] ] = it->second; |
49 |
|
Debug("inst-engine-phase-req") << " " << it->first[0] << ( it->second ? " == " : " != " ) << it->first[1] << std::endl; |
50 |
|
} |
51 |
|
}else if( quantifiers::TermUtil::hasInstConstAttr(it->first[1]) ){ |
52 |
|
d_phase_reqs_equality_term[ it->first[1] ] = it->first[0]; |
53 |
|
d_phase_reqs_equality[ it->first[1] ] = it->second; |
54 |
|
Debug("inst-engine-phase-req") << " " << it->first[1] << ( it->second ? " == " : " != " ) << it->first[0] << std::endl; |
55 |
|
} |
56 |
|
} |
57 |
|
} |
58 |
|
} |
59 |
112466 |
} |
60 |
|
|
61 |
339064 |
void QuantPhaseReq::computePhaseReqs( Node n, bool polarity, std::map< Node, int >& phaseReqs ){ |
62 |
339064 |
bool newReqPol = false; |
63 |
|
bool newPolarity; |
64 |
339064 |
if( n.getKind()==NOT ){ |
65 |
88568 |
newReqPol = true; |
66 |
88568 |
newPolarity = !polarity; |
67 |
250496 |
}else if( n.getKind()==OR || n.getKind()==IMPLIES ){ |
68 |
45322 |
if( !polarity ){ |
69 |
45322 |
newReqPol = true; |
70 |
45322 |
newPolarity = false; |
71 |
|
} |
72 |
205174 |
}else if( n.getKind()==AND ){ |
73 |
9292 |
if( polarity ){ |
74 |
|
newReqPol = true; |
75 |
|
newPolarity = true; |
76 |
|
} |
77 |
|
}else{ |
78 |
195882 |
int val = polarity ? 1 : -1; |
79 |
195882 |
if( phaseReqs.find( n )==phaseReqs.end() ){ |
80 |
195813 |
phaseReqs[n] = val; |
81 |
69 |
}else if( val!=phaseReqs[n] ){ |
82 |
67 |
phaseReqs[n] = 0; |
83 |
|
} |
84 |
|
} |
85 |
339064 |
if( newReqPol ){ |
86 |
360488 |
for( int i=0; i<(int)n.getNumChildren(); i++ ){ |
87 |
226598 |
if( n.getKind()==IMPLIES && i==0 ){ |
88 |
|
computePhaseReqs( n[i], !newPolarity, phaseReqs ); |
89 |
|
}else{ |
90 |
226598 |
computePhaseReqs( n[i], newPolarity, phaseReqs ); |
91 |
|
} |
92 |
|
} |
93 |
|
} |
94 |
339064 |
} |
95 |
|
|
96 |
1490812 |
void QuantPhaseReq::getPolarity( Node n, int child, bool hasPol, bool pol, bool& newHasPol, bool& newPol ) { |
97 |
1490812 |
if( n.getKind()==AND || n.getKind()==OR || n.getKind()==SEP_STAR ){ |
98 |
341548 |
newHasPol = hasPol; |
99 |
341548 |
newPol = pol; |
100 |
1149264 |
}else if( n.getKind()==IMPLIES ){ |
101 |
8 |
newHasPol = hasPol; |
102 |
8 |
newPol = child==0 ? !pol : pol; |
103 |
1149256 |
}else if( n.getKind()==NOT ){ |
104 |
173339 |
newHasPol = hasPol; |
105 |
173339 |
newPol = !pol; |
106 |
975917 |
}else if( n.getKind()==ITE ){ |
107 |
15861 |
newHasPol = (child!=0) && hasPol; |
108 |
15861 |
newPol = pol; |
109 |
960056 |
}else if( n.getKind()==FORALL ){ |
110 |
152 |
newHasPol = (child==1) && hasPol; |
111 |
152 |
newPol = pol; |
112 |
|
}else{ |
113 |
959904 |
newHasPol = false; |
114 |
959904 |
newPol = false; |
115 |
|
} |
116 |
1490812 |
} |
117 |
|
|
118 |
4021834 |
void QuantPhaseReq::getEntailPolarity( Node n, int child, bool hasPol, bool pol, bool& newHasPol, bool& newPol ) { |
119 |
4021834 |
if( n.getKind()==AND || n.getKind()==OR || n.getKind()==SEP_STAR ){ |
120 |
2008188 |
newHasPol = hasPol && pol!=( n.getKind()==OR ); |
121 |
2008188 |
newPol = pol; |
122 |
2013646 |
}else if( n.getKind()==IMPLIES ){ |
123 |
22940 |
newHasPol = hasPol && !pol; |
124 |
22940 |
newPol = child==0 ? !pol : pol; |
125 |
1990706 |
}else if( n.getKind()==NOT ){ |
126 |
254314 |
newHasPol = hasPol; |
127 |
254314 |
newPol = !pol; |
128 |
|
}else{ |
129 |
1736392 |
newHasPol = false; |
130 |
1736392 |
newPol = false; |
131 |
|
} |
132 |
4021834 |
} |
133 |
|
|
134 |
|
} // namespace theory |
135 |
29502 |
} // namespace cvc5 |