Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/bags/inference_generator.cpp	Lines:	139	154	90.3 %
Date:	2021-09-29	Branches:	301	930	32.4 %


/******************************************************************************
 * Top contributors (to current version):
 *   Mudathir Mohamed, Andrew Reynolds, Gereon Kremer
 *
 * This file is part of the cvc5 project.
 *
 * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
 * in the top-level source directory and their institutional affiliations.
 * All rights reserved.  See the file COPYING in the top-level source
 * directory for licensing information.
 * ****************************************************************************
 *
 * Inference generator utility.
 */

#include "inference_generator.h"

#include "expr/attribute.h"
#include "expr/bound_var_manager.h"
#include "expr/skolem_manager.h"
#include "theory/bags/inference_manager.h"
#include "theory/bags/solver_state.h"
#include "theory/uf/equality_engine.h"
#include "util/rational.h"

namespace cvc5 {
namespace theory {
namespace bags {

InferenceGenerator::InferenceGenerator(SolverState* state, InferenceManager* im)
    : d_state(state), d_im(im)
{
  d_nm = NodeManager::currentNM();
  d_sm = d_nm->getSkolemManager();
  d_true = d_nm->mkConst(true);
  d_zero = d_nm->mkConst(Rational(0));
  d_one = d_nm->mkConst(Rational(1));
}

InferInfo InferenceGenerator::nonNegativeCount(Node n, Node e)
{
  Assert(n.getType().isBag());
  Assert(e.getType() == n.getType().getBagElementType());

  InferInfo inferInfo(d_im, InferenceId::BAG_NON_NEGATIVE_COUNT);
  Node count = d_nm->mkNode(kind::BAG_COUNT, e, n);

  Node gte = d_nm->mkNode(kind::GEQ, count, d_zero);
  inferInfo.d_conclusion = gte;
  return inferInfo;
}

InferInfo InferenceGenerator::mkBag(Node n, Node e)
{
  Assert(n.getKind() == kind::MK_BAG);
  Assert(e.getType() == n.getType().getBagElementType());

  if (n[0] == e)
  {
    // TODO issue #78: refactor this with BagRewriter
    // (=> true (= (bag.count e (bag e c)) c))
    InferInfo inferInfo(d_im, InferenceId::BAG_MK_BAG_SAME_ELEMENT);
    Node skolem = getSkolem(n, inferInfo);
    Node count = getMultiplicityTerm(e, skolem);
    inferInfo.d_conclusion = count.eqNode(n[1]);
    return inferInfo;
  }
  else
  {
    // (=>
    //   true
    //   (= (bag.count e (bag x c)) (ite (= e x) c 0)))
    InferInfo inferInfo(d_im, InferenceId::BAG_MK_BAG);
    Node skolem = getSkolem(n, inferInfo);
    Node count = getMultiplicityTerm(e, skolem);
    Node same = d_nm->mkNode(kind::EQUAL, n[0], e);
    Node ite = d_nm->mkNode(kind::ITE, same, n[1], d_zero);
    Node equal = count.eqNode(ite);
    inferInfo.d_conclusion = equal;
    return inferInfo;
  }
}

struct BagsDeqAttributeId
{
};
typedef expr::Attribute<BagsDeqAttributeId, Node> BagsDeqAttribute;

InferInfo InferenceGenerator::bagDisequality(Node n)
{
  Assert(n.getKind() == kind::EQUAL && n[0].getType().isBag());

  Node A = n[0];
  Node B = n[1];

  InferInfo inferInfo(d_im, InferenceId::BAG_DISEQUALITY);

  TypeNode elementType = A.getType().getBagElementType();
  BoundVarManager* bvm = d_nm->getBoundVarManager();
  Node element = bvm->mkBoundVar<BagsDeqAttribute>(n, elementType);
  Node skolem =
      d_sm->mkSkolem(element,
                     n,
                     "bag_disequal",
                     "an extensional lemma for disequality of two bags");

  Node countA = getMultiplicityTerm(skolem, A);
  Node countB = getMultiplicityTerm(skolem, B);

  Node disEqual = countA.eqNode(countB).notNode();

  inferInfo.d_premises.push_back(n.notNode());
  inferInfo.d_conclusion = disEqual;
  return inferInfo;
}

Node InferenceGenerator::getSkolem(Node& n, InferInfo& inferInfo)
{
  Node skolem = d_sm->mkPurifySkolem(n, "skolem_bag", "skolem bag");
  inferInfo.d_skolems[n] = skolem;
  return skolem;
}

InferInfo InferenceGenerator::empty(Node n, Node e)
{
  Assert(n.getKind() == kind::EMPTYBAG);
  Assert(e.getType() == n.getType().getBagElementType());

  InferInfo inferInfo(d_im, InferenceId::BAG_EMPTY);
  Node skolem = getSkolem(n, inferInfo);
  Node count = getMultiplicityTerm(e, skolem);

  Node equal = count.eqNode(d_zero);
  inferInfo.d_conclusion = equal;
  return inferInfo;
}

InferInfo InferenceGenerator::unionDisjoint(Node n, Node e)
{
  Assert(n.getKind() == kind::UNION_DISJOINT && n[0].getType().isBag());
  Assert(e.getType() == n[0].getType().getBagElementType());

  Node A = n[0];
  Node B = n[1];
  InferInfo inferInfo(d_im, InferenceId::BAG_UNION_DISJOINT);

  Node countA = getMultiplicityTerm(e, A);
  Node countB = getMultiplicityTerm(e, B);

  Node skolem = getSkolem(n, inferInfo);
  Node count = getMultiplicityTerm(e, skolem);

  Node sum = d_nm->mkNode(kind::PLUS, countA, countB);
  Node equal = count.eqNode(sum);

  inferInfo.d_conclusion = equal;
  return inferInfo;
}

InferInfo InferenceGenerator::unionMax(Node n, Node e)
{
  Assert(n.getKind() == kind::UNION_MAX && n[0].getType().isBag());
  Assert(e.getType() == n[0].getType().getBagElementType());

  Node A = n[0];
  Node B = n[1];
  InferInfo inferInfo(d_im, InferenceId::BAG_UNION_MAX);

  Node countA = getMultiplicityTerm(e, A);
  Node countB = getMultiplicityTerm(e, B);

  Node skolem = getSkolem(n, inferInfo);
  Node count = getMultiplicityTerm(e, skolem);

  Node gt = d_nm->mkNode(kind::GT, countA, countB);
  Node max = d_nm->mkNode(kind::ITE, gt, countA, countB);
  Node equal = count.eqNode(max);

  inferInfo.d_conclusion = equal;
  return inferInfo;
}

InferInfo InferenceGenerator::intersection(Node n, Node e)
{
  Assert(n.getKind() == kind::INTERSECTION_MIN && n[0].getType().isBag());
  Assert(e.getType() == n[0].getType().getBagElementType());

  Node A = n[0];
  Node B = n[1];
  InferInfo inferInfo(d_im, InferenceId::BAG_INTERSECTION_MIN);

  Node countA = getMultiplicityTerm(e, A);
  Node countB = getMultiplicityTerm(e, B);
  Node skolem = getSkolem(n, inferInfo);
  Node count = getMultiplicityTerm(e, skolem);

  Node lt = d_nm->mkNode(kind::LT, countA, countB);
  Node min = d_nm->mkNode(kind::ITE, lt, countA, countB);
  Node equal = count.eqNode(min);
  inferInfo.d_conclusion = equal;
  return inferInfo;
}

InferInfo InferenceGenerator::differenceSubtract(Node n, Node e)
{
  Assert(n.getKind() == kind::DIFFERENCE_SUBTRACT && n[0].getType().isBag());
  Assert(e.getType() == n[0].getType().getBagElementType());

  Node A = n[0];
  Node B = n[1];
  InferInfo inferInfo(d_im, InferenceId::BAG_DIFFERENCE_SUBTRACT);

  Node countA = getMultiplicityTerm(e, A);
  Node countB = getMultiplicityTerm(e, B);
  Node skolem = getSkolem(n, inferInfo);
  Node count = getMultiplicityTerm(e, skolem);

  Node subtract = d_nm->mkNode(kind::MINUS, countA, countB);
  Node gte = d_nm->mkNode(kind::GEQ, countA, countB);
  Node difference = d_nm->mkNode(kind::ITE, gte, subtract, d_zero);
  Node equal = count.eqNode(difference);
  inferInfo.d_conclusion = equal;
  return inferInfo;
}

InferInfo InferenceGenerator::differenceRemove(Node n, Node e)
{
  Assert(n.getKind() == kind::DIFFERENCE_REMOVE && n[0].getType().isBag());
  Assert(e.getType() == n[0].getType().getBagElementType());

  Node A = n[0];
  Node B = n[1];
  InferInfo inferInfo(d_im, InferenceId::BAG_DIFFERENCE_REMOVE);

  Node countA = getMultiplicityTerm(e, A);
  Node countB = getMultiplicityTerm(e, B);

  Node skolem = getSkolem(n, inferInfo);
  Node count = getMultiplicityTerm(e, skolem);

  Node notInB = d_nm->mkNode(kind::EQUAL, countB, d_zero);
  Node difference = d_nm->mkNode(kind::ITE, notInB, countA, d_zero);
  Node equal = count.eqNode(difference);
  inferInfo.d_conclusion = equal;
  return inferInfo;
}

InferInfo InferenceGenerator::duplicateRemoval(Node n, Node e)
{
  Assert(n.getKind() == kind::DUPLICATE_REMOVAL && n[0].getType().isBag());
  Assert(e.getType() == n[0].getType().getBagElementType());

  Node A = n[0];
  InferInfo inferInfo(d_im, InferenceId::BAG_DUPLICATE_REMOVAL);

  Node countA = getMultiplicityTerm(e, A);
  Node skolem = getSkolem(n, inferInfo);
  Node count = getMultiplicityTerm(e, skolem);

  Node gte = d_nm->mkNode(kind::GEQ, countA, d_one);
  Node ite = d_nm->mkNode(kind::ITE, gte, d_one, d_zero);
  Node equal = count.eqNode(ite);
  inferInfo.d_conclusion = equal;
  return inferInfo;
}

Node InferenceGenerator::getMultiplicityTerm(Node element, Node bag)
{
  Node count = d_nm->mkNode(kind::BAG_COUNT, element, bag);
  return count;
}

}  // namespace bags
}  // namespace theory
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Mudathir Mohamed, Andrew Reynolds, Gereon Kremer
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		* Inference generator utility.
14		*/
15
16		#include "inference_generator.h"
17
18		#include "expr/attribute.h"
19		#include "expr/bound_var_manager.h"
20		#include "expr/skolem_manager.h"
21		#include "theory/bags/inference_manager.h"
22		#include "theory/bags/solver_state.h"
23		#include "theory/uf/equality_engine.h"
24		#include "util/rational.h"
25
26		namespace cvc5 {
27		namespace theory {
28		namespace bags {
29
30	12542	InferenceGenerator::InferenceGenerator(SolverState* state, InferenceManager* im)
31	12542	: d_state(state), d_im(im)
32		{
33	12542	d_nm = NodeManager::currentNM();
34	12542	d_sm = d_nm->getSkolemManager();
35	12542	d_true = d_nm->mkConst(true);
36	12542	d_zero = d_nm->mkConst(Rational(0));
37	12542	d_one = d_nm->mkConst(Rational(1));
38	12542	}
39
40	939	InferInfo InferenceGenerator::nonNegativeCount(Node n, Node e)
41		{
42	939	Assert(n.getType().isBag());
43	939	Assert(e.getType() == n.getType().getBagElementType());
44
45	939	InferInfo inferInfo(d_im, InferenceId::BAG_NON_NEGATIVE_COUNT);
46	1878	Node count = d_nm->mkNode(kind::BAG_COUNT, e, n);
47
48	1878	Node gte = d_nm->mkNode(kind::GEQ, count, d_zero);
49	939	inferInfo.d_conclusion = gte;
50	1878	return inferInfo;
51		}
52
53	211	InferInfo InferenceGenerator::mkBag(Node n, Node e)
54		{
55	211	Assert(n.getKind() == kind::MK_BAG);
56	211	Assert(e.getType() == n.getType().getBagElementType());
57
58	211	if (n[0] == e)
59		{
60		// TODO issue #78: refactor this with BagRewriter
61		// (=> true (= (bag.count e (bag e c)) c))
62	232	InferInfo inferInfo(d_im, InferenceId::BAG_MK_BAG_SAME_ELEMENT);
63	232	Node skolem = getSkolem(n, inferInfo);
64	232	Node count = getMultiplicityTerm(e, skolem);
65	116	inferInfo.d_conclusion = count.eqNode(n[1]);
66	116	return inferInfo;
67		}
68		else
69		{
70		// (=>
71		// true
72		// (= (bag.count e (bag x c)) (ite (= e x) c 0)))
73	190	InferInfo inferInfo(d_im, InferenceId::BAG_MK_BAG);
74	190	Node skolem = getSkolem(n, inferInfo);
75	190	Node count = getMultiplicityTerm(e, skolem);
76	190	Node same = d_nm->mkNode(kind::EQUAL, n[0], e);
77	190	Node ite = d_nm->mkNode(kind::ITE, same, n[1], d_zero);
78	190	Node equal = count.eqNode(ite);
79	95	inferInfo.d_conclusion = equal;
80	95	return inferInfo;
81		}
82		}
83
84		struct BagsDeqAttributeId
85		{
86		};
87		typedef expr::Attribute<BagsDeqAttributeId, Node> BagsDeqAttribute;
88
89	280	InferInfo InferenceGenerator::bagDisequality(Node n)
90		{
91	280	Assert(n.getKind() == kind::EQUAL && n[0].getType().isBag());
92
93	560	Node A = n[0];
94	560	Node B = n[1];
95
96	280	InferInfo inferInfo(d_im, InferenceId::BAG_DISEQUALITY);
97
98	560	TypeNode elementType = A.getType().getBagElementType();
99	280	BoundVarManager* bvm = d_nm->getBoundVarManager();
100	560	Node element = bvm->mkBoundVar<BagsDeqAttribute>(n, elementType);
101		Node skolem =
102	280	d_sm->mkSkolem(element,
103		n,
104		"bag_disequal",
105	560	"an extensional lemma for disequality of two bags");
106
107	560	Node countA = getMultiplicityTerm(skolem, A);
108	560	Node countB = getMultiplicityTerm(skolem, B);
109
110	560	Node disEqual = countA.eqNode(countB).notNode();
111
112	280	inferInfo.d_premises.push_back(n.notNode());
113	280	inferInfo.d_conclusion = disEqual;
114	560	return inferInfo;
115		}
116
117	638	Node InferenceGenerator::getSkolem(Node& n, InferInfo& inferInfo)
118		{
119	638	Node skolem = d_sm->mkPurifySkolem(n, "skolem_bag", "skolem bag");
120	638	inferInfo.d_skolems[n] = skolem;
121	638	return skolem;
122		}
123
124	16	InferInfo InferenceGenerator::empty(Node n, Node e)
125		{
126	16	Assert(n.getKind() == kind::EMPTYBAG);
127	16	Assert(e.getType() == n.getType().getBagElementType());
128
129	16	InferInfo inferInfo(d_im, InferenceId::BAG_EMPTY);
130	32	Node skolem = getSkolem(n, inferInfo);
131	32	Node count = getMultiplicityTerm(e, skolem);
132
133	32	Node equal = count.eqNode(d_zero);
134	16	inferInfo.d_conclusion = equal;
135	32	return inferInfo;
136		}
137
138	192	InferInfo InferenceGenerator::unionDisjoint(Node n, Node e)
139		{
140	192	Assert(n.getKind() == kind::UNION_DISJOINT && n[0].getType().isBag());
141	192	Assert(e.getType() == n[0].getType().getBagElementType());
142
143	384	Node A = n[0];
144	384	Node B = n[1];
145	192	InferInfo inferInfo(d_im, InferenceId::BAG_UNION_DISJOINT);
146
147	384	Node countA = getMultiplicityTerm(e, A);
148	384	Node countB = getMultiplicityTerm(e, B);
149
150	384	Node skolem = getSkolem(n, inferInfo);
151	384	Node count = getMultiplicityTerm(e, skolem);
152
153	384	Node sum = d_nm->mkNode(kind::PLUS, countA, countB);
154	384	Node equal = count.eqNode(sum);
155
156	192	inferInfo.d_conclusion = equal;
157	384	return inferInfo;
158		}
159
160	61	InferInfo InferenceGenerator::unionMax(Node n, Node e)
161		{
162	61	Assert(n.getKind() == kind::UNION_MAX && n[0].getType().isBag());
163	61	Assert(e.getType() == n[0].getType().getBagElementType());
164
165	122	Node A = n[0];
166	122	Node B = n[1];
167	61	InferInfo inferInfo(d_im, InferenceId::BAG_UNION_MAX);
168
169	122	Node countA = getMultiplicityTerm(e, A);
170	122	Node countB = getMultiplicityTerm(e, B);
171
172	122	Node skolem = getSkolem(n, inferInfo);
173	122	Node count = getMultiplicityTerm(e, skolem);
174
175	122	Node gt = d_nm->mkNode(kind::GT, countA, countB);
176	122	Node max = d_nm->mkNode(kind::ITE, gt, countA, countB);
177	122	Node equal = count.eqNode(max);
178
179	61	inferInfo.d_conclusion = equal;
180	122	return inferInfo;
181		}
182
183	105	InferInfo InferenceGenerator::intersection(Node n, Node e)
184		{
185	105	Assert(n.getKind() == kind::INTERSECTION_MIN && n[0].getType().isBag());
186	105	Assert(e.getType() == n[0].getType().getBagElementType());
187
188	210	Node A = n[0];
189	210	Node B = n[1];
190	105	InferInfo inferInfo(d_im, InferenceId::BAG_INTERSECTION_MIN);
191
192	210	Node countA = getMultiplicityTerm(e, A);
193	210	Node countB = getMultiplicityTerm(e, B);
194	210	Node skolem = getSkolem(n, inferInfo);
195	210	Node count = getMultiplicityTerm(e, skolem);
196
197	210	Node lt = d_nm->mkNode(kind::LT, countA, countB);
198	210	Node min = d_nm->mkNode(kind::ITE, lt, countA, countB);
199	210	Node equal = count.eqNode(min);
200	105	inferInfo.d_conclusion = equal;
201	210	return inferInfo;
202		}
203
204	42	InferInfo InferenceGenerator::differenceSubtract(Node n, Node e)
205		{
206	42	Assert(n.getKind() == kind::DIFFERENCE_SUBTRACT && n[0].getType().isBag());
207	42	Assert(e.getType() == n[0].getType().getBagElementType());
208
209	84	Node A = n[0];
210	84	Node B = n[1];
211	42	InferInfo inferInfo(d_im, InferenceId::BAG_DIFFERENCE_SUBTRACT);
212
213	84	Node countA = getMultiplicityTerm(e, A);
214	84	Node countB = getMultiplicityTerm(e, B);
215	84	Node skolem = getSkolem(n, inferInfo);
216	84	Node count = getMultiplicityTerm(e, skolem);
217
218	84	Node subtract = d_nm->mkNode(kind::MINUS, countA, countB);
219	84	Node gte = d_nm->mkNode(kind::GEQ, countA, countB);
220	84	Node difference = d_nm->mkNode(kind::ITE, gte, subtract, d_zero);
221	84	Node equal = count.eqNode(difference);
222	42	inferInfo.d_conclusion = equal;
223	84	return inferInfo;
224		}
225
226		InferInfo InferenceGenerator::differenceRemove(Node n, Node e)
227		{
228		Assert(n.getKind() == kind::DIFFERENCE_REMOVE && n[0].getType().isBag());
229		Assert(e.getType() == n[0].getType().getBagElementType());
230
231		Node A = n[0];
232		Node B = n[1];
233		InferInfo inferInfo(d_im, InferenceId::BAG_DIFFERENCE_REMOVE);
234
235		Node countA = getMultiplicityTerm(e, A);
236		Node countB = getMultiplicityTerm(e, B);
237
238		Node skolem = getSkolem(n, inferInfo);
239		Node count = getMultiplicityTerm(e, skolem);
240
241		Node notInB = d_nm->mkNode(kind::EQUAL, countB, d_zero);
242		Node difference = d_nm->mkNode(kind::ITE, notInB, countA, d_zero);
243		Node equal = count.eqNode(difference);
244		inferInfo.d_conclusion = equal;
245		return inferInfo;
246		}
247
248	11	InferInfo InferenceGenerator::duplicateRemoval(Node n, Node e)
249		{
250	11	Assert(n.getKind() == kind::DUPLICATE_REMOVAL && n[0].getType().isBag());
251	11	Assert(e.getType() == n[0].getType().getBagElementType());
252
253	22	Node A = n[0];
254	11	InferInfo inferInfo(d_im, InferenceId::BAG_DUPLICATE_REMOVAL);
255
256	22	Node countA = getMultiplicityTerm(e, A);
257	22	Node skolem = getSkolem(n, inferInfo);
258	22	Node count = getMultiplicityTerm(e, skolem);
259
260	22	Node gte = d_nm->mkNode(kind::GEQ, countA, d_one);
261	22	Node ite = d_nm->mkNode(kind::ITE, gte, d_one, d_zero);
262	22	Node equal = count.eqNode(ite);
263	11	inferInfo.d_conclusion = equal;
264	22	return inferInfo;
265		}
266
267	2009	Node InferenceGenerator::getMultiplicityTerm(Node element, Node bag)
268		{
269	2009	Node count = d_nm->mkNode(kind::BAG_COUNT, element, bag);
270	2009	return count;
271		}
272
273		} // namespace bags
274		} // namespace theory
275	22746	} // namespace cvc5