1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Andrew Reynolds, Tianyi Liang, 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 a finite model finding decision strategy for strings. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/strings/strings_fmf.h" |
17 |
|
|
18 |
|
#include "util/rational.h" |
19 |
|
|
20 |
|
using namespace std; |
21 |
|
using namespace cvc5::context; |
22 |
|
using namespace cvc5::kind; |
23 |
|
|
24 |
|
namespace cvc5 { |
25 |
|
namespace theory { |
26 |
|
namespace strings { |
27 |
|
|
28 |
9838 |
StringsFmf::StringsFmf(context::Context* c, |
29 |
|
context::UserContext* u, |
30 |
|
Valuation valuation, |
31 |
9838 |
TermRegistry& tr) |
32 |
|
: d_sslds(nullptr), |
33 |
|
d_satContext(c), |
34 |
|
d_userContext(u), |
35 |
|
d_valuation(valuation), |
36 |
9838 |
d_termReg(tr) |
37 |
|
{ |
38 |
9838 |
} |
39 |
|
|
40 |
9838 |
StringsFmf::~StringsFmf() {} |
41 |
|
|
42 |
78 |
void StringsFmf::presolve() |
43 |
|
{ |
44 |
156 |
d_sslds.reset(new StringSumLengthDecisionStrategy( |
45 |
156 |
d_satContext, d_userContext, d_valuation)); |
46 |
156 |
Trace("strings-dstrat-reg") |
47 |
78 |
<< "presolve: register decision strategy." << std::endl; |
48 |
78 |
const NodeSet& ivars = d_termReg.getInputVars(); |
49 |
156 |
std::vector<Node> inputVars; |
50 |
232 |
for (NodeSet::const_iterator itr = ivars.begin(); itr != ivars.end(); ++itr) |
51 |
|
{ |
52 |
154 |
inputVars.push_back(*itr); |
53 |
|
} |
54 |
78 |
d_sslds->initialize(inputVars); |
55 |
78 |
} |
56 |
|
|
57 |
78 |
DecisionStrategy* StringsFmf::getDecisionStrategy() const |
58 |
|
{ |
59 |
78 |
return d_sslds.get(); |
60 |
|
} |
61 |
|
|
62 |
78 |
StringsFmf::StringSumLengthDecisionStrategy::StringSumLengthDecisionStrategy( |
63 |
78 |
context::Context* c, context::UserContext* u, Valuation valuation) |
64 |
78 |
: DecisionStrategyFmf(c, valuation), d_inputVarLsum(u) |
65 |
|
{ |
66 |
78 |
} |
67 |
|
|
68 |
|
bool StringsFmf::StringSumLengthDecisionStrategy::isInitialized() |
69 |
|
{ |
70 |
|
return !d_inputVarLsum.get().isNull(); |
71 |
|
} |
72 |
|
|
73 |
78 |
void StringsFmf::StringSumLengthDecisionStrategy::initialize( |
74 |
|
const std::vector<Node>& vars) |
75 |
|
{ |
76 |
78 |
if (d_inputVarLsum.get().isNull() && !vars.empty()) |
77 |
|
{ |
78 |
70 |
NodeManager* nm = NodeManager::currentNM(); |
79 |
140 |
std::vector<Node> sum; |
80 |
224 |
for (const Node& v : vars) |
81 |
|
{ |
82 |
154 |
sum.push_back(nm->mkNode(STRING_LENGTH, v)); |
83 |
|
} |
84 |
140 |
Node sumn = sum.size() == 1 ? sum[0] : nm->mkNode(PLUS, sum); |
85 |
70 |
d_inputVarLsum.set(sumn); |
86 |
|
} |
87 |
78 |
} |
88 |
|
|
89 |
302 |
Node StringsFmf::StringSumLengthDecisionStrategy::mkLiteral(unsigned i) |
90 |
|
{ |
91 |
302 |
if (d_inputVarLsum.get().isNull()) |
92 |
|
{ |
93 |
|
return Node::null(); |
94 |
|
} |
95 |
302 |
NodeManager* nm = NodeManager::currentNM(); |
96 |
604 |
Node lit = nm->mkNode(LEQ, d_inputVarLsum.get(), nm->mkConst(Rational(i))); |
97 |
302 |
Trace("strings-fmf") << "StringsFMF::mkLiteral: " << lit << std::endl; |
98 |
302 |
return lit; |
99 |
|
} |
100 |
112078 |
std::string StringsFmf::StringSumLengthDecisionStrategy::identify() const |
101 |
|
{ |
102 |
112078 |
return std::string("string_sum_len"); |
103 |
|
} |
104 |
|
|
105 |
|
} // namespace strings |
106 |
|
} // namespace theory |
107 |
29280 |
} // namespace cvc5 |