1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
/********************* */
/*! \file theory_rewrite_eq.cpp
** \verbatim
** Top contributors (to current version):
** Andrew Reynolds
** This file is part of the CVC4 project.
** Copyright (c) 2009-2020 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.\endverbatim
**
** \brief The TheoryRewriteEq preprocessing pass
**/
#include "preprocessing/passes/theory_rewrite_eq.h"
#include "preprocessing/assertion_pipeline.h"
#include "preprocessing/preprocessing_pass_context.h"
#include "theory/theory_engine.h"
using namespace CVC4::theory;
namespace CVC4 {
namespace preprocessing {
namespace passes {
TheoryRewriteEq::TheoryRewriteEq(PreprocessingPassContext* preprocContext)
: PreprocessingPass(preprocContext, "theory-rewrite-eq"){};
PreprocessingPassResult TheoryRewriteEq::applyInternal(
AssertionPipeline* assertions)
{
// apply ppRewrite to all equalities in assertions
for (std::size_t i = 0, size = assertions->size(); i < size; ++i)
{
Node assertion = (*assertions)[i];
TrustNode trn = rewriteAssertion(assertion);
if (!trn.isNull())
{
// replace based on the trust node
assertions->replaceTrusted(i, trn);
}
}
return PreprocessingPassResult::NO_CONFLICT;
}
theory::TrustNode TheoryRewriteEq::rewriteAssertion(TNode n)
{
NodeManager* nm = NodeManager::currentNM();
TheoryEngine* te = d_preprocContext->getTheoryEngine();
std::unordered_map<TNode, Node, TNodeHashFunction> visited;
std::unordered_map<TNode, Node, TNodeHashFunction>::iterator it;
std::vector<TNode> visit;
TNode cur;
visit.push_back(n);
do
{
cur = visit.back();
visit.pop_back();
it = visited.find(cur);
if (it == visited.end())
{
if (cur.getNumChildren()==0)
{
visited[cur] = cur;
}
else
{
visited[cur] = Node::null();
visit.push_back(cur);
visit.insert(visit.end(), cur.begin(), cur.end());
}
}
else if (it->second.isNull())
{
Node ret = cur;
bool childChanged = false;
std::vector<Node> children;
if (cur.getMetaKind() == kind::metakind::PARAMETERIZED)
{
children.push_back(cur.getOperator());
}
for (const Node& cn : cur)
{
it = visited.find(cn);
Assert(it != visited.end());
Assert(!it->second.isNull());
childChanged = childChanged || cn != it->second;
children.push_back(it->second);
}
if (childChanged)
{
ret = nm->mkNode(cur.getKind(), children);
}
if (ret.getKind() == kind::EQUAL && !ret[0].getType().isBoolean())
{
// For example, (= x y) ---> (and (>= x y) (<= x y))
theory::TrustNode trn = te->ppRewriteEquality(ret);
// can make proof producing by using proof generator from trn
ret = trn.isNull() ? Node(ret) : trn.getNode();
}
visited[cur] = ret;
}
} while (!visit.empty());
Assert(visited.find(n) != visited.end());
Assert(!visited.find(n)->second.isNull());
Node ret = visited[n];
if (ret == n)
{
return TrustNode::null();
}
// can make proof producing by providing a term conversion generator here
return TrustNode::mkTrustRewrite(n, ret, nullptr);
}
} // namespace passes
} // namespace preprocessing
} // namespace CVC4
|