Branch data Line data Source code
1 : : /******************************************************************************
2 : : * This file is part of the cvc5 project.
3 : : *
4 : : * Copyright (c) 2009-2026 by the authors listed in the file AUTHORS
5 : : * in the top-level source directory and their institutional affiliations.
6 : : * All rights reserved. See the file COPYING in the top-level source
7 : : * directory for licensing information.
8 : : * ****************************************************************************
9 : : *
10 : : * Simple, commonly-used routines for Boolean simplification.
11 : : */
12 : :
13 : : #include "cvc5_private.h"
14 : :
15 : : #ifndef CVC5__BOOLEAN_SIMPLIFICATION_H
16 : : #define CVC5__BOOLEAN_SIMPLIFICATION_H
17 : :
18 : : #include <algorithm>
19 : : #include <vector>
20 : :
21 : : #include "base/check.h"
22 : : #include "expr/node.h"
23 : :
24 : : namespace cvc5::internal {
25 : : namespace preprocessing {
26 : :
27 : : /**
28 : : * A class to contain a number of useful functions for simple
29 : : * simplification of nodes. One never uses it as an object (and
30 : : * it cannot be constructed). It is used as a namespace.
31 : : */
32 : : class BooleanSimplification
33 : : {
34 : : // cannot construct one of these
35 : : BooleanSimplification() = delete;
36 : : BooleanSimplification(const BooleanSimplification&) = delete;
37 : :
38 : : CVC5_WARN_UNUSED_RESULT static bool push_back_associative_commute_recursive(
39 : : Node n, std::vector<Node>& buffer, Kind k, Kind notK, bool negateNode);
40 : :
41 : : public:
42 : : /**
43 : : * The threshold for removing duplicates. (See removeDuplicates().)
44 : : */
45 : : static const uint32_t DUPLICATE_REMOVAL_THRESHOLD = 10;
46 : :
47 : : /**
48 : : * Remove duplicate nodes from a vector, modifying it in-place.
49 : : * If the vector has size >= DUPLICATE_REMOVAL_THRESHOLD, this
50 : : * function is a no-op.
51 : : */
52 : 144 : static void removeDuplicates(std::vector<Node>& buffer)
53 : : {
54 [ + - ]: 144 : if (buffer.size() < DUPLICATE_REMOVAL_THRESHOLD)
55 : : {
56 : 144 : std::sort(buffer.begin(), buffer.end());
57 : : std::vector<Node>::iterator new_end =
58 : 144 : std::unique(buffer.begin(), buffer.end());
59 : 144 : buffer.erase(new_end, buffer.end());
60 : : }
61 : 144 : }
62 : :
63 : : /**
64 : : * Takes a node with kind AND, collapses all AND and (NOT OR)-kinded
65 : : * children of it (as far as possible---see
66 : : * push_back_associative_commute()), removes duplicates, and returns
67 : : * the resulting Node.
68 : : */
69 : 136 : static Node simplifyConflict(Node andNode)
70 : : {
71 [ - + ]: 136 : AssertArgument(!andNode.isNull(), andNode);
72 [ + + ]: 136 : AssertArgument(andNode.getKind() == Kind::AND, andNode);
73 : :
74 : 135 : std::vector<Node> buffer;
75 : 135 : push_back_associative_commute(andNode, buffer, Kind::AND, Kind::OR);
76 : :
77 : 135 : removeDuplicates(buffer);
78 : :
79 [ - + ]: 135 : if (buffer.size() == 1)
80 : : {
81 : 0 : return buffer[0];
82 : : }
83 : :
84 : 135 : NodeBuilder nb(andNode.getNodeManager(), Kind::AND);
85 : 135 : nb.append(buffer);
86 : 135 : return nb;
87 : 135 : }
88 : :
89 : : /**
90 : : * Takes a node with kind OR, collapses all OR and (NOT AND)-kinded
91 : : * children of it (as far as possible---see
92 : : * push_back_associative_commute()), removes duplicates, and returns
93 : : * the resulting Node.
94 : : */
95 : 10 : static Node simplifyClause(Node orNode)
96 : : {
97 [ - + ]: 10 : AssertArgument(!orNode.isNull(), orNode);
98 [ + + ]: 10 : AssertArgument(orNode.getKind() == Kind::OR, orNode);
99 : :
100 : 9 : std::vector<Node> buffer;
101 : 9 : push_back_associative_commute(orNode, buffer, Kind::OR, Kind::AND);
102 : :
103 : 9 : removeDuplicates(buffer);
104 : :
105 [ - + ][ - + ]: 9 : Assert(buffer.size() > 0);
[ - - ]
106 [ - + ]: 9 : if (buffer.size() == 1)
107 : : {
108 : 0 : return buffer[0];
109 : : }
110 : :
111 : 9 : NodeBuilder nb(orNode.getNodeManager(), Kind::OR);
112 : 9 : nb.append(buffer);
113 : 9 : return nb;
114 : 9 : }
115 : :
116 : : /**
117 : : * Takes a node with kind IMPLIES, converts it to an OR, then
118 : : * simplifies the result with simplifyClause().
119 : : *
120 : : * The input doesn't actually have to be Horn, it seems, but that's
121 : : * the common case(?), hence the name.
122 : : */
123 : 5 : static Node simplifyHornClause(Node implication)
124 : : {
125 [ + + ]: 5 : AssertArgument(implication.getKind() == Kind::IMPLIES, implication);
126 : :
127 : 4 : TNode left = implication[0];
128 : 4 : TNode right = implication[1];
129 : :
130 : 4 : Node notLeft = negate(left);
131 : 4 : Node clause = NodeBuilder(implication.getNodeManager(), Kind::OR)
132 : 8 : << notLeft << right;
133 : :
134 : 8 : return simplifyClause(clause);
135 : 4 : }
136 : :
137 : : /**
138 : : * Aids in reforming a node. Takes a node of (N-ary) kind k and
139 : : * copies its children into an output vector, collapsing its k-kinded
140 : : * children into it. Also collapses negations of notK. For example:
141 : : *
142 : : * push_back_associative_commute( [OR [OR a b] [OR b c d] [NOT [AND e f]]],
143 : : * buffer, Kind::OR, Kind::AND )
144 : : * yields a "buffer" vector of [a b b c d e f]
145 : : *
146 : : * @param n the node to operate upon
147 : : * @param buffer the output vector (must be empty on entry)
148 : : * @param k the kind to collapse (should equal the kind of node n)
149 : : * @param notK the "negation" of kind k (e.g. OR's negation is AND),
150 : : * or Kind::UNDEFINED_KIND if none.
151 : : * @param negateChildren true if the children of the resulting node
152 : : * (that is, the elements in buffer) should all be negated; you want
153 : : * this if e.g. you're simplifying the (OR...) in (NOT (OR...)),
154 : : * intending to make the result an AND.
155 : : */
156 : 144 : static inline void push_back_associative_commute(Node n,
157 : : std::vector<Node>& buffer,
158 : : Kind k,
159 : : Kind notK,
160 : : bool negateChildren = false)
161 : : {
162 [ - + ]: 144 : AssertArgument(buffer.empty(), buffer);
163 [ - + ]: 144 : AssertArgument(!n.isNull(), n);
164 [ + - ][ - + ]: 144 : AssertArgument(k != Kind::UNDEFINED_KIND && k != Kind::NULL_EXPR, k);
[ - + ]
165 [ - + ]: 144 : AssertArgument(notK != Kind::NULL_EXPR, notK);
166 [ - + ]: 144 : AssertArgument(n.getKind() == k,
167 : : n,
168 : : "expected node to have kind %s",
169 : : kindToString(k).c_str());
170 : :
171 : : bool b CVC5_UNUSED =
172 : 144 : push_back_associative_commute_recursive(n, buffer, k, notK, false);
173 : :
174 [ - + ]: 144 : if (buffer.size() == 0)
175 : : {
176 : : // all the TRUEs for an AND (resp FALSEs for an OR) were simplified away
177 : 0 : buffer.push_back(
178 : 0 : n.getNodeManager()->mkConst(k == Kind::AND ? true : false));
179 : : }
180 : 144 : } /* push_back_associative_commute() */
181 : :
182 : : /**
183 : : * Negates a node, doing all the double-negation elimination
184 : : * that's possible.
185 : : *
186 : : * @param n the node to negate (cannot be the null node)
187 : : */
188 : 18 : static Node negate(TNode n)
189 : : {
190 [ + + ]: 18 : AssertArgument(!n.isNull(), n);
191 : :
192 : 17 : bool polarity = true;
193 : 17 : TNode base = n;
194 [ + + ]: 23 : while (base.getKind() == Kind::NOT)
195 : : {
196 : 6 : base = base[0];
197 : 6 : polarity = !polarity;
198 : : }
199 [ - + ]: 17 : if (n.isConst())
200 : : {
201 : 0 : return n.getNodeManager()->mkConst(!n.getConst<bool>());
202 : : }
203 [ + + ]: 17 : if (polarity)
204 : : {
205 : 15 : return base.notNode();
206 : : }
207 : : else
208 : : {
209 : 2 : return base;
210 : : }
211 : 17 : }
212 : :
213 : : /**
214 : : * Simplify an OR, AND, or IMPLIES. This function is the identity
215 : : * for all other kinds.
216 : : */
217 : 132 : inline static Node simplify(TNode n)
218 : : {
219 [ + - ][ - - ]: 132 : switch (n.getKind())
220 : : {
221 : 132 : case Kind::AND: return simplifyConflict(n);
222 : :
223 : 0 : case Kind::OR: return simplifyClause(n);
224 : :
225 : 0 : case Kind::IMPLIES: return simplifyHornClause(n);
226 : :
227 : 0 : default: return n;
228 : : }
229 : : }
230 : :
231 : : }; /* class BooleanSimplification */
232 : :
233 : : } // namespace preprocessing
234 : : } // namespace cvc5::internal
235 : :
236 : : #endif /* CVC5__BOOLEAN_SIMPLIFICATION_H */
|
