GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/theory/strings/inference_manager.cpp Lines: 164 180 91.1 %
Date: 2021-08-01 Branches: 359 776 46.3 %

Line Exec Source
1
/******************************************************************************
2
 * Top contributors (to current version):
3
 *   Andrew Reynolds, Gereon Kremer, Mudathir Mohamed
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 the inference manager for the theory of strings.
14
 */
15
16
#include "theory/strings/inference_manager.h"
17
18
#include "options/strings_options.h"
19
#include "theory/ext_theory.h"
20
#include "theory/rewriter.h"
21
#include "theory/strings/theory_strings_utils.h"
22
#include "theory/strings/word.h"
23
#include "util/rational.h"
24
25
using namespace std;
26
using namespace cvc5::context;
27
using namespace cvc5::kind;
28
29
namespace cvc5 {
30
namespace theory {
31
namespace strings {
32
33
9838
InferenceManager::InferenceManager(Theory& t,
34
                                   SolverState& s,
35
                                   TermRegistry& tr,
36
                                   ExtTheory& e,
37
                                   SequencesStatistics& statistics,
38
9838
                                   ProofNodeManager* pnm)
39
    : InferenceManagerBuffered(t, s, pnm, "theory::strings::", false),
40
      d_state(s),
41
      d_termReg(tr),
42
      d_extt(e),
43
      d_statistics(statistics),
44
1241
      d_ipc(pnm ? new InferProofCons(d_state.getSatContext(), pnm, d_statistics)
45
11079
                : nullptr)
46
{
47
9838
  NodeManager* nm = NodeManager::currentNM();
48
9838
  d_zero = nm->mkConst(Rational(0));
49
9838
  d_one = nm->mkConst(Rational(1));
50
9838
  d_true = nm->mkConst(true);
51
9838
  d_false = nm->mkConst(false);
52
9838
}
53
54
33565
void InferenceManager::doPending()
55
{
56
33565
  doPendingFacts();
57
33565
  if (d_state.isInConflict())
58
  {
59
    // just clear the pending vectors, nothing else to do
60
2297
    clearPendingLemmas();
61
2297
    clearPendingPhaseRequirements();
62
2297
    return;
63
  }
64
31268
  doPendingLemmas();
65
31268
  doPendingPhaseRequirements();
66
}
67
68
27032
bool InferenceManager::sendInternalInference(std::vector<Node>& exp,
69
                                             Node conc,
70
                                             InferenceId infer)
71
{
72
54064
  if (conc.getKind() == AND
73
54064
      || (conc.getKind() == NOT && conc[0].getKind() == OR))
74
  {
75
2896
    Node conj = conc.getKind() == AND ? conc : conc[0];
76
1448
    bool pol = conc.getKind() == AND;
77
1448
    bool ret = true;
78
5008
    for (const Node& cc : conj)
79
    {
80
3560
      bool retc = sendInternalInference(exp, pol ? cc : cc.negate(), infer);
81
3560
      ret = ret && retc;
82
    }
83
1448
    return ret;
84
  }
85
25584
  bool pol = conc.getKind() != NOT;
86
51168
  Node lit = pol ? conc : conc[0];
87
25584
  if (lit.getKind() == EQUAL)
88
  {
89
16186
    for (unsigned i = 0; i < 2; i++)
90
    {
91
10884
      if (!lit[i].isConst() && !d_state.hasTerm(lit[i]))
92
      {
93
        // introduces a new non-constant term, do not infer
94
140
        return false;
95
      }
96
    }
97
    // does it already hold?
98
18332
    if (pol ? d_state.areEqual(lit[0], lit[1])
99
13030
            : d_state.areDisequal(lit[0], lit[1]))
100
    {
101
4916
      return true;
102
    }
103
  }
104
20142
  else if (lit.isConst())
105
  {
106
4
    if (lit.getConst<bool>())
107
    {
108
      Assert(pol);
109
      // trivially holds
110
      return true;
111
    }
112
  }
113
20138
  else if (!d_state.hasTerm(lit))
114
  {
115
    // introduces a new non-constant term, do not infer
116
17825
    return false;
117
  }
118
2313
  else if (d_state.areEqual(lit, pol ? d_true : d_false))
119
  {
120
    // already holds
121
2303
    return true;
122
  }
123
400
  sendInference(exp, conc, infer);
124
400
  return true;
125
}
126
127
40444
bool InferenceManager::sendInference(const std::vector<Node>& exp,
128
                                     const std::vector<Node>& noExplain,
129
                                     Node eq,
130
                                     InferenceId infer,
131
                                     bool isRev,
132
                                     bool asLemma)
133
{
134
40444
  if (eq.isNull())
135
  {
136
100
    eq = d_false;
137
  }
138
40344
  else if (Rewriter::rewrite(eq) == d_true)
139
  {
140
    // if trivial, return
141
6
    return false;
142
  }
143
  // wrap in infer info and send below
144
80876
  InferInfo ii(infer);
145
40438
  ii.d_idRev = isRev;
146
40438
  ii.d_conc = eq;
147
40438
  ii.d_premises = exp;
148
40438
  ii.d_noExplain = noExplain;
149
40438
  sendInference(ii, asLemma);
150
40438
  return true;
151
}
152
153
37392
bool InferenceManager::sendInference(const std::vector<Node>& exp,
154
                                     Node eq,
155
                                     InferenceId infer,
156
                                     bool isRev,
157
                                     bool asLemma)
158
{
159
74784
  std::vector<Node> noExplain;
160
74784
  return sendInference(exp, noExplain, eq, infer, isRev, asLemma);
161
}
162
163
42949
void InferenceManager::sendInference(InferInfo& ii, bool asLemma)
164
{
165
42949
  Assert(!ii.isTrivial());
166
  // set that this inference manager will be processing this inference
167
42949
  ii.d_sim = this;
168
85898
  Trace("strings-infer-debug")
169
42949
      << "sendInference: " << ii << ", asLemma = " << asLemma << std::endl;
170
  // check if we should send a conflict, lemma or a fact
171
42949
  if (ii.isConflict())
172
  {
173
1110
    Trace("strings-infer-debug") << "...as conflict" << std::endl;
174
2220
    Trace("strings-lemma") << "Strings::Conflict: " << ii.d_premises << " by "
175
1110
                           << ii.getId() << std::endl;
176
1110
    Trace("strings-conflict") << "CONFLICT: inference conflict " << ii.d_premises << " by " << ii.getId() << std::endl;
177
1110
    ++(d_statistics.d_conflictsInfer);
178
    // process the conflict immediately
179
1110
    processConflict(ii);
180
1110
    return;
181
  }
182
66909
  else if (asLemma || options::stringInferAsLemmas() || !ii.isFact())
183
  {
184
18370
    Trace("strings-infer-debug") << "...as lemma" << std::endl;
185
18370
    addPendingLemma(std::unique_ptr<InferInfo>(new InferInfo(ii)));
186
18370
    return;
187
  }
188
23469
  if (options::stringInferSym())
189
  {
190
46345
    std::vector<Node> unproc;
191
82733
    for (const Node& ac : ii.d_premises)
192
    {
193
59264
      d_termReg.removeProxyEqs(ac, unproc);
194
    }
195
23469
    if (unproc.empty())
196
    {
197
1186
      Node eqs = ii.d_conc;
198
      // keep the same id for now, since we are transforming the form of the
199
      // inference, not the root reason.
200
1186
      InferInfo iiSubsLem(ii.getId());
201
593
      iiSubsLem.d_sim = this;
202
593
      iiSubsLem.d_conc = eqs;
203
593
      if (Trace.isOn("strings-lemma-debug"))
204
      {
205
        Trace("strings-lemma-debug")
206
            << "Strings::Infer " << iiSubsLem << std::endl;
207
        Trace("strings-lemma-debug")
208
            << "Strings::Infer Alternate : " << eqs << std::endl;
209
      }
210
593
      Trace("strings-infer-debug") << "...as symbolic lemma" << std::endl;
211
593
      addPendingLemma(std::unique_ptr<InferInfo>(new InferInfo(iiSubsLem)));
212
593
      return;
213
    }
214
22876
    if (Trace.isOn("strings-lemma-debug"))
215
    {
216
      for (const Node& u : unproc)
217
      {
218
        Trace("strings-lemma-debug")
219
            << "  non-trivial explanation : " << u << std::endl;
220
      }
221
    }
222
  }
223
22876
  Trace("strings-infer-debug") << "...as fact" << std::endl;
224
  // add to pending to be processed as a fact
225
22876
  addPendingFact(std::unique_ptr<InferInfo>(new InferInfo(ii)));
226
}
227
228
533
bool InferenceManager::sendSplit(Node a, Node b, InferenceId infer, bool preq)
229
{
230
1066
  Node eq = a.eqNode(b);
231
533
  eq = Rewriter::rewrite(eq);
232
533
  if (eq.isConst())
233
  {
234
    return false;
235
  }
236
533
  NodeManager* nm = NodeManager::currentNM();
237
1066
  InferInfo iiSplit(infer);
238
533
  iiSplit.d_sim = this;
239
533
  iiSplit.d_conc = nm->mkNode(OR, eq, nm->mkNode(NOT, eq));
240
533
  eq = Rewriter::rewrite(eq);
241
533
  addPendingPhaseRequirement(eq, preq);
242
533
  addPendingLemma(std::unique_ptr<InferInfo>(new InferInfo(iiSplit)));
243
533
  return true;
244
}
245
246
665918
void InferenceManager::addToExplanation(Node a,
247
                                        Node b,
248
                                        std::vector<Node>& exp) const
249
{
250
665918
  if (a != b)
251
  {
252
682816
    Debug("strings-explain")
253
341408
        << "Add to explanation : " << a << " == " << b << std::endl;
254
341408
    Assert(d_state.areEqual(a, b));
255
341408
    exp.push_back(a.eqNode(b));
256
  }
257
665918
}
258
259
void InferenceManager::addToExplanation(Node lit, std::vector<Node>& exp) const
260
{
261
  if (!lit.isNull())
262
  {
263
    Assert(!lit.isConst());
264
    exp.push_back(lit);
265
  }
266
}
267
268
2922774
bool InferenceManager::hasProcessed() const
269
{
270
2922774
  return d_state.isInConflict() || hasPending();
271
}
272
273
211
void InferenceManager::markReduced(Node n, ExtReducedId id, bool contextDepend)
274
{
275
211
  d_extt.markReduced(n, id, contextDepend);
276
211
}
277
278
1510
void InferenceManager::processConflict(const InferInfo& ii)
279
{
280
1510
  Assert(!d_state.isInConflict());
281
  // setup the fact to reproduce the proof in the call below
282
1510
  if (d_ipc != nullptr)
283
  {
284
203
    d_ipc->notifyFact(ii);
285
  }
286
  // make the trust node
287
3020
  TrustNode tconf = mkConflictExp(ii.d_premises, d_ipc.get());
288
1510
  Assert(tconf.getKind() == TrustNodeKind::CONFLICT);
289
3020
  Trace("strings-assert") << "(assert (not " << tconf.getNode()
290
1510
                          << ")) ; conflict " << ii.getId() << std::endl;
291
  // send the trusted conflict
292
1510
  trustedConflict(tconf, ii.getId());
293
1510
}
294
295
22286
void InferenceManager::processFact(InferInfo& ii, ProofGenerator*& pg)
296
{
297
44572
  Trace("strings-assert") << "(assert (=> " << ii.getPremises() << " "
298
22286
                          << ii.d_conc << ")) ; fact " << ii.getId() << std::endl;
299
44572
  Trace("strings-lemma") << "Strings::Fact: " << ii.d_conc << " from "
300
44572
                         << ii.getPremises() << " by " << ii.getId()
301
22286
                         << std::endl;
302
22286
  if (d_ipc != nullptr)
303
  {
304
    // ensure the proof generator is ready to explain this fact in the
305
    // current SAT context
306
2428
    d_ipc->notifyFact(ii);
307
2428
    pg = d_ipc.get();
308
  }
309
22286
}
310
311
19327
TrustNode InferenceManager::processLemma(InferInfo& ii, LemmaProperty& p)
312
{
313
19327
  Assert(!ii.isTrivial());
314
19327
  Assert(!ii.isConflict());
315
  // set up the explanation and no-explanation
316
38654
  std::vector<Node> exp;
317
58311
  for (const Node& ec : ii.d_premises)
318
  {
319
38984
    utils::flattenOp(AND, ec, exp);
320
  }
321
38654
  std::vector<Node> noExplain;
322
38654
  if (!options::stringRExplainLemmas())
323
  {
324
    // if we aren't regressing the explanation, we add all literals to
325
    // noExplain and ignore ii.d_ant.
326
    noExplain.insert(noExplain.end(), exp.begin(), exp.end());
327
  }
328
  else
329
  {
330
    // otherwise, the no-explain literals are those provided
331
22788
    for (const Node& ecn : ii.d_noExplain)
332
    {
333
3461
      utils::flattenOp(AND, ecn, noExplain);
334
    }
335
  }
336
  // ensure that the proof generator is ready to explain the final conclusion
337
  // of the lemma (ii.d_conc).
338
19327
  if (d_ipc != nullptr)
339
  {
340
1845
    d_ipc->notifyFact(ii);
341
  }
342
19327
  TrustNode tlem = mkLemmaExp(ii.d_conc, exp, noExplain, d_ipc.get());
343
38654
  Trace("strings-pending") << "Process pending lemma : " << tlem.getNode()
344
19327
                           << std::endl;
345
346
  // Process the side effects of the inference info.
347
  // Register the new skolems from this inference. We register them here
348
  // (lazily), since this is the moment when we have decided to process the
349
  // inference.
350
1260
  for (const std::pair<const LengthStatus, std::vector<Node> >& sks :
351
19327
       ii.d_skolems)
352
  {
353
2520
    for (const Node& n : sks.second)
354
    {
355
1260
      d_termReg.registerTermAtomic(n, sks.first);
356
    }
357
  }
358
19327
  if (ii.getId() == InferenceId::STRINGS_REDUCTION)
359
  {
360
1887
    p |= LemmaProperty::NEEDS_JUSTIFY;
361
  }
362
38654
  Trace("strings-assert") << "(assert " << tlem.getNode() << ") ; lemma "
363
19327
                          << ii.getId() << std::endl;
364
38654
  Trace("strings-lemma") << "Strings::Lemma: " << tlem.getNode() << " by "
365
19327
                         << ii.getId() << std::endl;
366
38654
  return tlem;
367
}
368
369
}  // namespace strings
370
}  // namespace theory
371
29280
}  // namespace cvc5