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