1 /*++
2 Copyright (c) 2010 Microsoft Corporation
3 
4 Module Name:
5 
6     quant_hoist.cpp
7 
8 Abstract:
9 
10     Quantifier hoisting utility.
11 
12 Author:
13 
14     Nikolaj Bjorner (nbjorner) 2010-02-19
15 
16 Revision History:
17 
18     Hoisted from quant_elim.
19 
20 --*/
21 
22 #include "ast/rewriter/quant_hoist.h"
23 #include "ast/expr_functors.h"
24 #include "ast/ast_smt_pp.h"
25 #include "ast/rewriter/bool_rewriter.h"
26 #include "ast/rewriter/var_subst.h"
27 #include "ast/ast_pp.h"
28 #include "ast/rewriter/ast_counter.h"
29 #include "ast/rewriter/expr_safe_replace.h"
30 
31 //
32 // Bring quantifiers of common type into prenex form.
33 //
34 class quantifier_hoister::impl {
35     ast_manager&        m;
36     bool_rewriter       m_rewriter;
37 
38 public:
impl(ast_manager & m)39     impl(ast_manager& m) :
40         m(m),
41         m_rewriter(m)
42     {}
43 
operator ()(expr * fml,app_ref_vector & vars,bool & is_fa,expr_ref & result,bool use_fresh,bool rewrite_ok)44     void operator()(expr* fml, app_ref_vector& vars, bool& is_fa, expr_ref& result, bool use_fresh, bool rewrite_ok) {
45         quantifier_type qt = Q_none_pos;
46         pull_quantifier(fml, qt, vars, result, use_fresh, rewrite_ok);
47         TRACE("qe_verbose",
48               tout << mk_pp(fml, m) << "\n";
49               tout << mk_pp(result, m) << "\n";);
50         SASSERT(is_positive(qt));
51         is_fa = (Q_forall_pos == qt);
52     }
53 
pull_exists(expr * fml,app_ref_vector & vars,expr_ref & result,bool use_fresh,bool rewrite_ok)54     void pull_exists(expr* fml, app_ref_vector& vars, expr_ref& result, bool use_fresh, bool rewrite_ok) {
55         quantifier_type qt = Q_exists_pos;
56         pull_quantifier(fml, qt, vars, result, use_fresh, rewrite_ok);
57         TRACE("qe_verbose",
58               tout << mk_pp(fml, m) << "\n";
59               tout << mk_pp(result, m) << "\n";);
60     }
61 
pull_quantifier(bool is_forall,expr_ref & fml,app_ref_vector & vars,bool use_fresh,bool rewrite_ok)62     void pull_quantifier(bool is_forall, expr_ref& fml, app_ref_vector& vars, bool use_fresh, bool rewrite_ok) {
63         quantifier_type qt = is_forall?Q_forall_pos:Q_exists_pos;
64         expr_ref result(m);
65         pull_quantifier(fml, qt, vars, result, use_fresh, rewrite_ok);
66         TRACE("qe_verbose",
67               tout << mk_pp(fml, m) << "\n";
68               tout << mk_pp(result, m) << "\n";);
69         fml = std::move(result);
70     }
71 
extract_quantifier(quantifier * q,app_ref_vector & vars,expr_ref & result,bool use_fresh)72     void extract_quantifier(quantifier* q, app_ref_vector& vars, expr_ref& result, bool use_fresh) {
73         unsigned nd = q->get_num_decls();
74         for (unsigned i = 0; i < nd; ++i) {
75             sort* s = q->get_decl_sort(i);
76             symbol const& sym = q->get_decl_name (i);
77             app* a = use_fresh ? m.mk_fresh_const(sym.str ().c_str (), s)
78                                : m.mk_const (sym, s);
79             vars.push_back(a);
80         }
81         expr * const * exprs = (expr* const*) (vars.data() + vars.size()- nd);
82         result = instantiate(m, q, exprs);
83     }
84 
pull_quantifier(bool _is_forall,expr_ref & fml,ptr_vector<sort> * sorts,svector<symbol> * names,bool use_fresh,bool rewrite_ok)85     unsigned pull_quantifier(bool _is_forall, expr_ref& fml, ptr_vector<sort>* sorts, svector<symbol>* names, bool use_fresh, bool rewrite_ok) {
86         unsigned index = var_counter().get_next_var(fml);
87         while (is_quantifier(fml) && _is_forall == is_forall(fml)) {
88             quantifier* q = to_quantifier(fml);
89             index += q->get_num_decls();
90             if (names) {
91                 names->append(q->get_num_decls(), q->get_decl_names());
92             }
93             if (sorts) {
94                 sorts->append(q->get_num_decls(), q->get_decl_sorts());
95             }
96             fml = q->get_expr();
97         }
98         if (!has_quantifiers(fml)) {
99             return index;
100         }
101         app_ref_vector vars(m);
102         pull_quantifier(_is_forall, fml, vars, use_fresh, rewrite_ok);
103         if (vars.empty()) {
104             return index;
105         }
106         // replace vars by de-bruijn indices
107         expr_safe_replace rep(m);
108         svector<symbol> bound_names;
109         ptr_vector<sort> bound_sorts;
110         for (unsigned i = 0; i < vars.size(); ++i) {
111             app* v = vars[i].get();
112             if (names) {
113                 bound_names.push_back(v->get_decl()->get_name());
114             }
115             if (sorts) {
116                 bound_sorts.push_back(v->get_sort());
117             }
118             rep.insert(v, m.mk_var(index++, v->get_sort()));
119         }
120         if (names && !bound_names.empty()) {
121             bound_names.reverse();
122             bound_names.append(*names);
123             names->reset();
124             names->append(bound_names);
125         }
126         if (sorts && !bound_sorts.empty()) {
127             bound_sorts.reverse();
128             bound_sorts.append(*sorts);
129             sorts->reset();
130             sorts->append(bound_sorts);
131         }
132         rep(fml);
133         return index;
134     }
135 
136 private:
137 
138     enum quantifier_type {
139         Q_forall_pos = 0x10,
140         Q_exists_pos = 0x20,
141         Q_none_pos   = 0x40,
142         Q_forall_neg = 0x11,
143         Q_exists_neg = 0x21,
144         Q_none_neg   = 0x41
145     };
146 
display(quantifier_type qt,std::ostream & out)147     void display(quantifier_type qt, std::ostream& out) {
148         switch(qt) {
149         case Q_forall_pos: out << "Forall+"; break;
150         case Q_exists_pos: out << "Exists+"; break;
151         case Q_none_pos:   out << "None+"; break;
152         case Q_forall_neg: out << "Forall-"; break;
153         case Q_exists_neg: out << "Exists-"; break;
154         case Q_none_neg:   out << "None-"; break;
155         }
156     }
157 
negate(quantifier_type & qt)158     quantifier_type& negate(quantifier_type& qt) {
159         qt = static_cast<quantifier_type>(qt ^0x1);
160         return qt;
161     }
162 
is_negative(quantifier_type qt)163     static bool is_negative(quantifier_type qt) {
164         return 0 != (qt & 0x1);
165     }
166 
is_positive(quantifier_type qt)167     static bool is_positive(quantifier_type qt) {
168         return 0 == (qt & 0x1);
169     }
170 
set_quantifier_type(quantifier_type & qt,bool is_forall)171     static void set_quantifier_type(quantifier_type& qt, bool is_forall) {
172         switch(qt) {
173         case Q_forall_pos: SASSERT(is_forall); break;
174         case Q_forall_neg: SASSERT(!is_forall); break;
175         case Q_exists_pos: SASSERT(!is_forall); break;
176         case Q_exists_neg: SASSERT(is_forall); break;
177         case Q_none_pos: qt = is_forall?Q_forall_pos:Q_exists_pos; break;
178         case Q_none_neg: qt = is_forall?Q_exists_neg:Q_forall_neg; break;
179         }
180     }
181 
is_compatible(quantifier_type qt,bool is_forall)182     bool is_compatible(quantifier_type qt, bool is_forall) {
183         switch(qt) {
184         case Q_forall_pos: return is_forall;
185         case Q_forall_neg: return !is_forall;
186         case Q_exists_pos: return !is_forall;
187         case Q_exists_neg: return is_forall;
188         case Q_none_pos: return true;
189         case Q_none_neg: return true;
190         default:
191             UNREACHABLE();
192         }
193         return false;
194     }
195 
196 
pull_quantifier(expr * fml,quantifier_type & qt,app_ref_vector & vars,expr_ref & result,bool use_fresh,bool rewrite_ok)197     void pull_quantifier(expr* fml, quantifier_type& qt, app_ref_vector& vars, expr_ref& result, bool use_fresh, bool rewrite_ok) {
198 
199         if (!has_quantifiers(fml)) {
200             result = fml;
201             return;
202         }
203 
204         switch(fml->get_kind()) {
205         case AST_APP: {
206             expr_ref_vector args(m);
207             expr_ref tmp(m);
208             expr* t1, *t2, *t3;
209             unsigned num_args = 0;
210             app* a = to_app(fml);
211             if (m.is_and(fml)) {
212                 num_args = a->get_num_args();
213                 for (unsigned i = 0; i < num_args; ++i) {
214                     pull_quantifier(a->get_arg(i), qt, vars, tmp, use_fresh, rewrite_ok);
215                     args.push_back(tmp);
216                 }
217                 if (rewrite_ok)
218                     m_rewriter.mk_and(args.size(), args.data(), result);
219                 else
220                     result = m.mk_and (args.size (), args.data ());
221             }
222             else if (m.is_or(fml)) {
223                 num_args = to_app(fml)->get_num_args();
224                 for (unsigned i = 0; i < num_args; ++i) {
225                     pull_quantifier(to_app(fml)->get_arg(i), qt, vars, tmp, use_fresh, rewrite_ok);
226                     args.push_back(tmp);
227                 }
228                 if (rewrite_ok)
229                     m_rewriter.mk_or(args.size(), args.data(), result);
230                 else
231                     result = m.mk_or (args.size (), args.data ());
232             }
233             else if (m.is_not(fml)) {
234                 pull_quantifier(to_app(fml)->get_arg(0), negate(qt), vars, tmp, use_fresh, rewrite_ok);
235                 negate(qt);
236                 result = m.mk_not(tmp);
237             }
238             else if (m.is_implies(fml, t1, t2)) {
239                 pull_quantifier(t1, negate(qt), vars, tmp, use_fresh, rewrite_ok);
240                 negate(qt);
241                 pull_quantifier(t2, qt, vars, result, use_fresh, rewrite_ok);
242                 result = m.mk_implies(tmp, result);
243             }
244             else if (m.is_ite(fml, t1, t2, t3)) {
245                 expr_ref tt1(m), tt2(m), tt3(m), ntt1(m), nt1(m);
246                 pull_quantifier(t2, qt, vars, tt2, use_fresh, rewrite_ok);
247                 pull_quantifier(t3, qt, vars, tt3, use_fresh, rewrite_ok);
248                 if (has_quantifiers(t1)) {
249                     pull_quantifier(t1, qt, vars, tt1, use_fresh, rewrite_ok);
250                     nt1 = m.mk_not(t1);
251                     pull_quantifier(nt1, qt, vars, ntt1, use_fresh, rewrite_ok);
252                     result = m.mk_and(m.mk_or(ntt1, tt2), m.mk_or(tt1, tt3));
253                 }
254                 else {
255                     result = m.mk_ite(t1, tt2, tt3);
256                 }
257             }
258             else if (m.is_eq(fml, t1, t2) && m.is_bool(t1)) {
259                 expr_ref tt1(m), tt2(m), ntt1(m), ntt2(m), nt1(m), nt2(m);
260                 pull_quantifier(t1, qt, vars, tt1, use_fresh, rewrite_ok);
261                 pull_quantifier(t2, qt, vars, tt2, use_fresh, rewrite_ok);
262                 nt1 = m.mk_not(t1);
263                 nt2 = m.mk_not(t2);
264                 pull_quantifier(nt1, qt, vars, ntt1, use_fresh, rewrite_ok);
265                 pull_quantifier(nt2, qt, vars, ntt2, use_fresh, rewrite_ok);
266                 result = m.mk_and(m.mk_or(ntt1, tt2), m.mk_or(ntt2, tt1));
267             }
268             else {
269                 // the formula contains a quantifier, but it is "inaccessible"
270                 result = fml;
271             }
272             break;
273         }
274         case AST_QUANTIFIER: {
275             quantifier* q = to_quantifier(fml);
276             if (is_lambda(q)) {
277                 result = fml;
278                 break;
279             }
280             expr_ref tmp(m);
281             if (!is_compatible(qt, is_forall(q))) {
282                 result = fml;
283                 break;
284             }
285             set_quantifier_type(qt, is_forall(q));
286             extract_quantifier(q, vars, tmp, use_fresh);
287             pull_quantifier(tmp, qt, vars, result, use_fresh, rewrite_ok);
288             break;
289         }
290         case AST_VAR:
291             result = fml;
292             break;
293         default:
294             UNREACHABLE();
295             result = fml;
296             break;
297         }
298     }
299 
300 };
301 
quantifier_hoister(ast_manager & m)302 quantifier_hoister::quantifier_hoister(ast_manager& m) {
303     m_impl = alloc(impl, m);
304 }
305 
~quantifier_hoister()306 quantifier_hoister::~quantifier_hoister() {
307     dealloc(m_impl);
308 }
309 
operator ()(expr * fml,app_ref_vector & vars,bool & is_fa,expr_ref & result,bool use_fresh,bool rewrite_ok)310 void quantifier_hoister::operator()(expr* fml, app_ref_vector& vars, bool& is_fa, expr_ref& result, bool use_fresh, bool rewrite_ok) {
311     (*m_impl)(fml, vars, is_fa, result, use_fresh, rewrite_ok);
312 }
313 
pull_exists(expr * fml,app_ref_vector & vars,expr_ref & result,bool use_fresh,bool rewrite_ok)314 void quantifier_hoister::pull_exists(expr* fml, app_ref_vector& vars, expr_ref& result, bool use_fresh, bool rewrite_ok) {
315     m_impl->pull_exists(fml, vars, result, use_fresh, rewrite_ok);
316 }
317 
pull_quantifier(bool is_forall,expr_ref & fml,app_ref_vector & vars,bool use_fresh,bool rewrite_ok)318 void quantifier_hoister::pull_quantifier(bool is_forall, expr_ref& fml, app_ref_vector& vars, bool use_fresh, bool rewrite_ok) {
319     m_impl->pull_quantifier(is_forall, fml, vars, use_fresh, rewrite_ok);
320 }
321 
pull_quantifier(bool is_forall,expr_ref & fml,ptr_vector<sort> * sorts,svector<symbol> * names,bool use_fresh,bool rewrite_ok)322 unsigned quantifier_hoister::pull_quantifier(bool is_forall, expr_ref& fml, ptr_vector<sort>* sorts, svector<symbol>* names, bool use_fresh, bool rewrite_ok) {
323     return m_impl->pull_quantifier(is_forall, fml, sorts, names, use_fresh, rewrite_ok);
324 }
325