Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/strings/term_registry.cpp	Lines:	287	325	88.3 %
Date:	2021-09-30	Branches:	694	1482	46.8 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Andres Noetzli, Morgan Deters
 *
 * 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.
 * ****************************************************************************
 *
 * Implementation of term registry for the theory of strings.
 */

#include "theory/strings/term_registry.h"

#include "expr/attribute.h"
#include "options/smt_options.h"
#include "options/strings_options.h"
#include "smt/logic_exception.h"
#include "theory/rewriter.h"
#include "theory/strings/inference_manager.h"
#include "theory/strings/theory_strings_utils.h"
#include "theory/strings/word.h"
#include "util/rational.h"
#include "util/string.h"

using namespace std;
using namespace cvc5::context;
using namespace cvc5::kind;

namespace cvc5 {
namespace theory {
namespace strings {

struct StringsProxyVarAttributeId
{
};
typedef expr::Attribute<StringsProxyVarAttributeId, bool>
    StringsProxyVarAttribute;

TermRegistry::TermRegistry(Env& env,
                           SolverState& s,
                           SequencesStatistics& statistics,
                           ProofNodeManager* pnm)
    : EnvObj(env),
      d_state(s),
      d_im(nullptr),
      d_statistics(statistics),
      d_hasStrCode(false),
      d_aent(env.getRewriter()),
      d_functionsTerms(context()),
      d_inputVars(userContext()),
      d_preregisteredTerms(context()),
      d_registeredTerms(userContext()),
      d_registeredTypes(userContext()),
      d_proxyVar(userContext()),
      d_lengthLemmaTermsCache(userContext()),
      d_epg(
          pnm ? new EagerProofGenerator(
              pnm, userContext(), "strings::TermRegistry::EagerProofGenerator")
              : nullptr)
{
  NodeManager* nm = NodeManager::currentNM();
  d_zero = nm->mkConst(Rational(0));
  d_one = nm->mkConst(Rational(1));
  d_negOne = NodeManager::currentNM()->mkConst(Rational(-1));
  d_cardSize = utils::getAlphabetCardinality();
}

TermRegistry::~TermRegistry() {}

void TermRegistry::finishInit(InferenceManager* im) { d_im = im; }

Node TermRegistry::eagerReduce(Node t, SkolemCache* sc)
{
  NodeManager* nm = NodeManager::currentNM();
  Node lemma;
  Kind tk = t.getKind();
  if (tk == STRING_TO_CODE)
  {
    // ite( str.len(s)==1, 0 <= str.code(s) < |A|, str.code(s)=-1 )
    Node code_len = utils::mkNLength(t[0]).eqNode(nm->mkConst(Rational(1)));
    Node code_eq_neg1 = t.eqNode(nm->mkConst(Rational(-1)));
    Node code_range = nm->mkNode(
        AND,
        nm->mkNode(GEQ, t, nm->mkConst(Rational(0))),
        nm->mkNode(
            LT, t, nm->mkConst(Rational(utils::getAlphabetCardinality()))));
    lemma = nm->mkNode(ITE, code_len, code_range, code_eq_neg1);
  }
  else if (tk == STRING_INDEXOF || tk == STRING_INDEXOF_RE)
  {
    // (and
    //   (or (= (f x y n) (- 1)) (>= (f x y n) n))
    //   (<= (f x y n) (str.len x)))
    //
    // where f in { str.indexof, str.indexof_re }
    Node l = nm->mkNode(STRING_LENGTH, t[0]);
    lemma = nm->mkNode(
        AND,
        nm->mkNode(
            OR, nm->mkConst(Rational(-1)).eqNode(t), nm->mkNode(GEQ, t, t[2])),
        nm->mkNode(LEQ, t, l));
  }
  else if (tk == STRING_STOI)
  {
    // (>= (str.to_int x) (- 1))
    lemma = nm->mkNode(GEQ, t, nm->mkConst(Rational(-1)));
  }
  else if (tk == STRING_CONTAINS)
  {
    // ite( (str.contains s r), (= s (str.++ sk1 r sk2)), (not (= s r)))
    Node sk1 =
        sc->mkSkolemCached(t[0], t[1], SkolemCache::SK_FIRST_CTN_PRE, "sc1");
    Node sk2 =
        sc->mkSkolemCached(t[0], t[1], SkolemCache::SK_FIRST_CTN_POST, "sc2");
    lemma = t[0].eqNode(utils::mkNConcat(sk1, t[1], sk2));
    lemma = nm->mkNode(ITE, t, lemma, t[0].eqNode(t[1]).notNode());
  }
  return lemma;
}

Node TermRegistry::lengthPositive(Node t)
{
  NodeManager* nm = NodeManager::currentNM();
  Node zero = nm->mkConst(Rational(0));
  Node emp = Word::mkEmptyWord(t.getType());
  Node tlen = nm->mkNode(STRING_LENGTH, t);
  Node tlenEqZero = tlen.eqNode(zero);
  Node tEqEmp = t.eqNode(emp);
  Node caseEmpty = nm->mkNode(AND, tlenEqZero, tEqEmp);
  Node caseNEmpty = nm->mkNode(GT, tlen, zero);
  // (or (and (= (str.len t) 0) (= t "")) (> (str.len t) 0))
  return nm->mkNode(OR, caseEmpty, caseNEmpty);
}

void TermRegistry::preRegisterTerm(TNode n)
{
  if (d_preregisteredTerms.find(n) != d_preregisteredTerms.end())
  {
    return;
  }
  eq::EqualityEngine* ee = d_state.getEqualityEngine();
  d_preregisteredTerms.insert(n);
  Trace("strings-preregister")
      << "TheoryString::preregister : " << n << std::endl;
  // check for logic exceptions
  Kind k = n.getKind();
  if (!options::stringExp())
  {
    if (k == STRING_INDEXOF || k == STRING_INDEXOF_RE || k == STRING_ITOS
        || k == STRING_STOI || k == STRING_REPLACE || k == STRING_SUBSTR
        || k == STRING_REPLACE_ALL || k == SEQ_NTH || k == STRING_REPLACE_RE
        || k == STRING_REPLACE_RE_ALL || k == STRING_CONTAINS || k == STRING_LEQ
        || k == STRING_TOLOWER || k == STRING_TOUPPER || k == STRING_REV
        || k == STRING_UPDATE)
    {
      std::stringstream ss;
      ss << "Term of kind " << k
         << " not supported in default mode, try --strings-exp";
      throw LogicException(ss.str());
    }
  }
  if (k == EQUAL)
  {
    if (n[0].getType().isRegExp())
    {
      std::stringstream ss;
      ss << "Equality between regular expressions is not supported";
      throw LogicException(ss.str());
    }
    ee->addTriggerPredicate(n);
    return;
  }
  else if (k == STRING_IN_REGEXP)
  {
    d_im->requirePhase(n, true);
    ee->addTriggerPredicate(n);
    ee->addTerm(n[0]);
    ee->addTerm(n[1]);
    return;
  }
  else if (k == STRING_TO_CODE)
  {
    d_hasStrCode = true;
  }
  else if (k == SEQ_NTH || k == STRING_UPDATE)
  {
    d_hasSeqUpdate = true;
  }
  else if (k == REGEXP_RANGE)
  {
    for (const Node& nc : n)
    {
      if (!nc.isConst())
      {
        throw LogicException(
            "expecting a constant string term in regexp range");
      }
      if (nc.getConst<String>().size() != 1)
      {
        throw LogicException(
            "expecting a single constant string term in regexp range");
      }
    }
  }
  registerTerm(n, 0);
  TypeNode tn = n.getType();
  if (tn.isRegExp() && n.isVar())
  {
    std::stringstream ss;
    ss << "Regular expression variables are not supported.";
    throw LogicException(ss.str());
  }
  if (tn.isString())  // string-only
  {
    // all characters of constants should fall in the alphabet
    if (n.isConst())
    {
      std::vector<unsigned> vec = n.getConst<String>().getVec();
      for (unsigned u : vec)
      {
        if (u >= d_cardSize)
        {
          std::stringstream ss;
          ss << "Characters in string \"" << n
             << "\" are outside of the given alphabet.";
          throw LogicException(ss.str());
        }
      }
    }
    ee->addTerm(n);
  }
  else if (tn.isBoolean())
  {
    // All kinds that we do congruence over that may return a Boolean go here
    if (k == STRING_CONTAINS || k == STRING_LEQ || k == SEQ_NTH)
    {
      // Get triggered for both equal and dis-equal
      ee->addTriggerPredicate(n);
    }
  }
  else
  {
    // Function applications/predicates
    ee->addTerm(n);
  }
  // Set d_functionsTerms stores all function applications that are
  // relevant to theory combination. Notice that this is a subset of
  // the applications whose kinds are function kinds in the equality
  // engine. This means it does not include applications of operators
  // like re.++, which is not a function kind in the equality engine.
  // Concatenation terms do not need to be considered here because
  // their arguments have string type and do not introduce any shared
  // terms.
  if (n.hasOperator() && ee->isFunctionKind(k)
      && kindToTheoryId(k) == THEORY_STRINGS && k != STRING_CONCAT)
  {
    d_functionsTerms.push_back(n);
  }
  if (options::stringFMF())
  {
    if (tn.isStringLike())
    {
      // Our decision strategy will minimize the length of this term if it is a
      // variable but not an internally generated Skolem, or a term that does
      // not belong to this theory.
      if (n.isVar() ? !d_skCache.isSkolem(n)
                    : kindToTheoryId(k) != THEORY_STRINGS)
      {
        d_inputVars.insert(n);
        Trace("strings-preregister") << "input variable: " << n << std::endl;
      }
    }
  }
}

void TermRegistry::registerTerm(Node n, int effort)
{
  Trace("strings-register") << "TheoryStrings::registerTerm() " << n
                            << ", effort = " << effort << std::endl;
  if (d_registeredTerms.find(n) != d_registeredTerms.end())
  {
    Trace("strings-register") << "...already registered" << std::endl;
    return;
  }
  bool do_register = true;
  TypeNode tn = n.getType();
  if (!tn.isStringLike())
  {
    if (options::stringEagerLen())
    {
      do_register = effort == 0;
    }
    else
    {
      do_register = effort > 0 || n.getKind() != STRING_CONCAT;
    }
  }
  if (!do_register)
  {
    Trace("strings-register") << "...do not register" << std::endl;
    return;
  }
  Trace("strings-register") << "...register" << std::endl;
  d_registeredTerms.insert(n);
  // ensure the type is registered
  registerType(tn);
  TrustNode regTermLem;
  if (tn.isStringLike())
  {
    // register length information:
    //  for variables, split on empty vs positive length
    //  for concat/const/replace, introduce proxy var and state length relation
    regTermLem = getRegisterTermLemma(n);
  }
  else if (n.getKind() != STRING_CONTAINS)
  {
    // we don't send out eager reduction lemma for str.contains currently
    Node eagerRedLemma = eagerReduce(n, &d_skCache);
    if (!eagerRedLemma.isNull())
    {
      // if there was an eager reduction, we make the trust node for it
      if (d_epg != nullptr)
      {
        regTermLem = d_epg->mkTrustNode(
            eagerRedLemma, PfRule::STRING_EAGER_REDUCTION, {}, {n});
      }
      else
      {
        regTermLem = TrustNode::mkTrustLemma(eagerRedLemma, nullptr);
      }
    }
  }
  if (!regTermLem.isNull())
  {
    Trace("strings-lemma") << "Strings::Lemma REG-TERM : " << regTermLem
                           << std::endl;
    Trace("strings-assert")
        << "(assert " << regTermLem.getNode() << ")" << std::endl;
    d_im->trustedLemma(regTermLem, InferenceId::STRINGS_REGISTER_TERM);
  }
}

void TermRegistry::registerType(TypeNode tn)
{
  if (d_registeredTypes.find(tn) != d_registeredTypes.end())
  {
    return;
  }
  d_registeredTypes.insert(tn);
  if (tn.isStringLike())
  {
    // preregister the empty word for the type
    Node emp = Word::mkEmptyWord(tn);
    if (!d_state.hasTerm(emp))
    {
      preRegisterTerm(emp);
    }
  }
}

TrustNode TermRegistry::getRegisterTermLemma(Node n)
{
  Assert(n.getType().isStringLike());
  NodeManager* nm = NodeManager::currentNM();
  // register length information:
  //  for variables, split on empty vs positive length
  //  for concat/const/replace, introduce proxy var and state length relation
  Node lsum;
  if (n.getKind() != STRING_CONCAT && !n.isConst())
  {
    Node lsumb = nm->mkNode(STRING_LENGTH, n);
    lsum = Rewriter::rewrite(lsumb);
    // can register length term if it does not rewrite
    if (lsum == lsumb)
    {
      registerTermAtomic(n, LENGTH_SPLIT);
      return TrustNode::null();
    }
  }
  Node sk = d_skCache.mkSkolemCached(n, SkolemCache::SK_PURIFY, "lsym");
  StringsProxyVarAttribute spva;
  sk.setAttribute(spva, true);
  Node eq = Rewriter::rewrite(sk.eqNode(n));
  d_proxyVar[n] = sk;
  // If we are introducing a proxy for a constant or concat term, we do not
  // need to send lemmas about its length, since its length is already
  // implied.
  if (n.isConst() || n.getKind() == STRING_CONCAT)
  {
    // do not send length lemma for sk.
    registerTermAtomic(sk, LENGTH_IGNORE);
  }
  Node skl = nm->mkNode(STRING_LENGTH, sk);
  if (n.getKind() == STRING_CONCAT)
  {
    std::vector<Node> nodeVec;
    for (const Node& nc : n)
    {
      if (nc.getAttribute(StringsProxyVarAttribute()))
      {
        Assert(d_proxyVarToLength.find(nc) != d_proxyVarToLength.end());
        nodeVec.push_back(d_proxyVarToLength[nc]);
      }
      else
      {
        Node lni = nm->mkNode(STRING_LENGTH, nc);
        nodeVec.push_back(lni);
      }
    }
    lsum = nm->mkNode(PLUS, nodeVec);
    lsum = Rewriter::rewrite(lsum);
  }
  else if (n.isConst())
  {
    lsum = nm->mkConst(Rational(Word::getLength(n)));
  }
  Assert(!lsum.isNull());
  d_proxyVarToLength[sk] = lsum;
  Node ceq = Rewriter::rewrite(skl.eqNode(lsum));

  Node ret = nm->mkNode(AND, eq, ceq);

  // it is a simple rewrite to justify this
  if (d_epg != nullptr)
  {
    return d_epg->mkTrustNode(ret, PfRule::MACRO_SR_PRED_INTRO, {}, {ret});
  }
  return TrustNode::mkTrustLemma(ret, nullptr);
}

void TermRegistry::registerTermAtomic(Node n, LengthStatus s)
{
  if (d_lengthLemmaTermsCache.find(n) != d_lengthLemmaTermsCache.end())
  {
    return;
  }
  d_lengthLemmaTermsCache.insert(n);

  if (s == LENGTH_IGNORE)
  {
    // ignore it
    return;
  }
  std::map<Node, bool> reqPhase;
  TrustNode lenLem = getRegisterTermAtomicLemma(n, s, reqPhase);
  if (!lenLem.isNull())
  {
    Trace("strings-lemma") << "Strings::Lemma REGISTER-TERM-ATOMIC : " << lenLem
                           << std::endl;
    Trace("strings-assert")
        << "(assert " << lenLem.getNode() << ")" << std::endl;
    d_im->trustedLemma(lenLem, InferenceId::STRINGS_REGISTER_TERM_ATOMIC);
  }
  for (const std::pair<const Node, bool>& rp : reqPhase)
  {
    d_im->requirePhase(rp.first, rp.second);
  }
}

SkolemCache* TermRegistry::getSkolemCache() { return &d_skCache; }

const context::CDList<TNode>& TermRegistry::getFunctionTerms() const
{
  return d_functionsTerms;
}

const context::CDHashSet<Node>& TermRegistry::getInputVars() const
{
  return d_inputVars;
}

bool TermRegistry::hasStringCode() const { return d_hasStrCode; }

bool TermRegistry::hasSeqUpdate() const { return d_hasSeqUpdate; }

bool TermRegistry::isHandledUpdate(Node n)
{
  Assert(n.getKind() == STRING_UPDATE || n.getKind() == STRING_SUBSTR);
  NodeManager* nm = NodeManager::currentNM();
  Node lenN = n[2];
  if (n.getKind() == STRING_UPDATE)
  {
    lenN = nm->mkNode(STRING_LENGTH, n[2]);
  }
  Node one = nm->mkConst(Rational(1));
  return d_aent.checkEq(lenN, one);
}

Node TermRegistry::getUpdateBase(Node n)
{
  while (n.getKind() == STRING_UPDATE)
  {
    n = n[0];
  }
  return n;
}

TrustNode TermRegistry::getRegisterTermAtomicLemma(
    Node n, LengthStatus s, std::map<Node, bool>& reqPhase)
{
  if (n.isConst())
  {
    // No need to send length for constant terms. This case may be triggered
    // for cases where the skolem cache automatically replaces a skolem by
    // a constant.
    return TrustNode::null();
  }
  Assert(n.getType().isStringLike());
  NodeManager* nm = NodeManager::currentNM();
  Node n_len = nm->mkNode(kind::STRING_LENGTH, n);
  Node emp = Word::mkEmptyWord(n.getType());
  if (s == LENGTH_GEQ_ONE)
  {
    Node neq_empty = n.eqNode(emp).negate();
    Node len_n_gt_z = nm->mkNode(GT, n_len, d_zero);
    Node len_geq_one = nm->mkNode(AND, neq_empty, len_n_gt_z);
    Trace("strings-lemma") << "Strings::Lemma SK-GEQ-ONE : " << len_geq_one
                           << std::endl;
    Trace("strings-assert") << "(assert " << len_geq_one << ")" << std::endl;
    return TrustNode::mkTrustLemma(len_geq_one, nullptr);
  }

  if (s == LENGTH_ONE)
  {
    Node len_one = n_len.eqNode(d_one);
    Trace("strings-lemma") << "Strings::Lemma SK-ONE : " << len_one
                           << std::endl;
    Trace("strings-assert") << "(assert " << len_one << ")" << std::endl;
    return TrustNode::mkTrustLemma(len_one, nullptr);
  }
  Assert(s == LENGTH_SPLIT);

  // get the positive length lemma
  Node lenLemma = lengthPositive(n);
  // split whether the string is empty
  Node n_len_eq_z = n_len.eqNode(d_zero);
  Node n_len_eq_z_2 = n.eqNode(emp);
  Node case_empty = nm->mkNode(AND, n_len_eq_z, n_len_eq_z_2);
  Node case_emptyr = Rewriter::rewrite(case_empty);
  if (!case_emptyr.isConst())
  {
    // prefer trying the empty case first
    // notice that requirePhase must only be called on rewritten literals that
    // occur in the CNF stream.
    n_len_eq_z = Rewriter::rewrite(n_len_eq_z);
    Assert(!n_len_eq_z.isConst());
    reqPhase[n_len_eq_z] = true;
    n_len_eq_z_2 = Rewriter::rewrite(n_len_eq_z_2);
    Assert(!n_len_eq_z_2.isConst());
    reqPhase[n_len_eq_z_2] = true;
  }
  else
  {
    // If n = "" ---> true or len( n ) = 0 ----> true, then we expect that
    // n ---> "". Since this method is only called on non-constants n, it must
    // be that n = "" ^ len( n ) = 0 does not rewrite to true.
    Assert(!case_emptyr.getConst<bool>());
  }

  if (d_epg != nullptr)
  {
    return d_epg->mkTrustNode(lenLemma, PfRule::STRING_LENGTH_POS, {}, {n});
  }
  return TrustNode::mkTrustLemma(lenLemma, nullptr);
}

Node TermRegistry::getSymbolicDefinition(Node n, std::vector<Node>& exp) const
{
  if (n.getNumChildren() == 0)
  {
    Node pn = getProxyVariableFor(n);
    if (pn.isNull())
    {
      return Node::null();
    }
    Node eq = n.eqNode(pn);
    eq = Rewriter::rewrite(eq);
    if (std::find(exp.begin(), exp.end(), eq) == exp.end())
    {
      exp.push_back(eq);
    }
    return pn;
  }
  std::vector<Node> children;
  if (n.getMetaKind() == metakind::PARAMETERIZED)
  {
    children.push_back(n.getOperator());
  }
  for (const Node& nc : n)
  {
    if (n.getType().isRegExp())
    {
      children.push_back(nc);
    }
    else
    {
      Node ns = getSymbolicDefinition(nc, exp);
      if (ns.isNull())
      {
        return Node::null();
      }
      else
      {
        children.push_back(ns);
      }
    }
  }
  return NodeManager::currentNM()->mkNode(n.getKind(), children);
}

Node TermRegistry::getProxyVariableFor(Node n) const
{
  NodeNodeMap::const_iterator it = d_proxyVar.find(n);
  if (it != d_proxyVar.end())
  {
    return (*it).second;
  }
  return Node::null();
}

Node TermRegistry::ensureProxyVariableFor(Node n)
{
  Node proxy = getProxyVariableFor(n);
  if (proxy.isNull())
  {
    registerTerm(n, 0);
    proxy = getProxyVariableFor(n);
  }
  Assert(!proxy.isNull());
  return proxy;
}

void TermRegistry::removeProxyEqs(Node n, std::vector<Node>& unproc) const
{
  if (n.getKind() == AND)
  {
    for (const Node& nc : n)
    {
      removeProxyEqs(nc, unproc);
    }
    return;
  }
  Trace("strings-subs-proxy") << "Input : " << n << std::endl;
  Node ns = Rewriter::rewrite(n);
  if (ns.getKind() == EQUAL)
  {
    for (size_t i = 0; i < 2; i++)
    {
      // determine whether this side has a proxy variable
      if (ns[i].getAttribute(StringsProxyVarAttribute()))
      {
        if (getProxyVariableFor(ns[1 - i]) == ns[i])
        {
          Trace("strings-subs-proxy")
              << "...trivial definition via " << ns[i] << std::endl;
          // it is a trivial equality, e.g. between a proxy variable
          // and its definition
          return;
        }
      }
    }
  }
  if (!n.isConst() || !n.getConst<bool>())
  {
    Trace("strings-subs-proxy") << "...unprocessed" << std::endl;
    unproc.push_back(n);
  }
}

}  // namespace strings
}  // namespace theory
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andrew Reynolds, Andres Noetzli, Morgan Deters
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 term registry for the theory of strings.
14		*/
15
16		#include "theory/strings/term_registry.h"
17
18		#include "expr/attribute.h"
19		#include "options/smt_options.h"
20		#include "options/strings_options.h"
21		#include "smt/logic_exception.h"
22		#include "theory/rewriter.h"
23		#include "theory/strings/inference_manager.h"
24		#include "theory/strings/theory_strings_utils.h"
25		#include "theory/strings/word.h"
26		#include "util/rational.h"
27		#include "util/string.h"
28
29		using namespace std;
30		using namespace cvc5::context;
31		using namespace cvc5::kind;
32
33		namespace cvc5 {
34		namespace theory {
35		namespace strings {
36
37		struct StringsProxyVarAttributeId
38		{
39		};
40		typedef expr::Attribute<StringsProxyVarAttributeId, bool>
41		StringsProxyVarAttribute;
42
43	6278	TermRegistry::TermRegistry(Env& env,
44		SolverState& s,
45		SequencesStatistics& statistics,
46	6278	ProofNodeManager* pnm)
47		: EnvObj(env),
48		d_state(s),
49		d_im(nullptr),
50		d_statistics(statistics),
51		d_hasStrCode(false),
52		d_aent(env.getRewriter()),
53		d_functionsTerms(context()),
54	6278	d_inputVars(userContext()),
55		d_preregisteredTerms(context()),
56	6278	d_registeredTerms(userContext()),
57	6278	d_registeredTypes(userContext()),
58	6278	d_proxyVar(userContext()),
59	6278	d_lengthLemmaTermsCache(userContext()),
60		d_epg(
61		pnm ? new EagerProofGenerator(
62	120	pnm, userContext(), "strings::TermRegistry::EagerProofGenerator")
63	37788	: nullptr)
64		{
65	6278	NodeManager* nm = NodeManager::currentNM();
66	6278	d_zero = nm->mkConst(Rational(0));
67	6278	d_one = nm->mkConst(Rational(1));
68	6278	d_negOne = NodeManager::currentNM()->mkConst(Rational(-1));
69	6278	d_cardSize = utils::getAlphabetCardinality();
70	6278	}
71
72	6275	TermRegistry::~TermRegistry() {}
73
74	6278	void TermRegistry::finishInit(InferenceManager* im) { d_im = im; }
75
76	20197	Node TermRegistry::eagerReduce(Node t, SkolemCache* sc)
77		{
78	20197	NodeManager* nm = NodeManager::currentNM();
79	20197	Node lemma;
80	20197	Kind tk = t.getKind();
81	20197	if (tk == STRING_TO_CODE)
82		{
83		// ite( str.len(s)==1, 0 <= str.code(s) < \|A\|, str.code(s)=-1 )
84	2450	Node code_len = utils::mkNLength(t[0]).eqNode(nm->mkConst(Rational(1)));
85	2450	Node code_eq_neg1 = t.eqNode(nm->mkConst(Rational(-1)));
86		Node code_range = nm->mkNode(
87		AND,
88	2450	nm->mkNode(GEQ, t, nm->mkConst(Rational(0))),
89	2450	nm->mkNode(
90	7350	LT, t, nm->mkConst(Rational(utils::getAlphabetCardinality()))));
91	1225	lemma = nm->mkNode(ITE, code_len, code_range, code_eq_neg1);
92		}
93	18972	else if (tk == STRING_INDEXOF \|\| tk == STRING_INDEXOF_RE)
94		{
95		// (and
96		// (or (= (f x y n) (- 1)) (>= (f x y n) n))
97		// (<= (f x y n) (str.len x)))
98		//
99		// where f in { str.indexof, str.indexof_re }
100	378	Node l = nm->mkNode(STRING_LENGTH, t[0]);
101	567	lemma = nm->mkNode(
102		AND,
103	756	nm->mkNode(
104	756	OR, nm->mkConst(Rational(-1)).eqNode(t), nm->mkNode(GEQ, t, t[2])),
105	567	nm->mkNode(LEQ, t, l));
106		}
107	18783	else if (tk == STRING_STOI)
108		{
109		// (>= (str.to_int x) (- 1))
110	61	lemma = nm->mkNode(GEQ, t, nm->mkConst(Rational(-1)));
111		}
112	18722	else if (tk == STRING_CONTAINS)
113		{
114		// ite( (str.contains s r), (= s (str.++ sk1 r sk2)), (not (= s r)))
115		Node sk1 =
116	4148	sc->mkSkolemCached(t[0], t[1], SkolemCache::SK_FIRST_CTN_PRE, "sc1");
117		Node sk2 =
118	4148	sc->mkSkolemCached(t[0], t[1], SkolemCache::SK_FIRST_CTN_POST, "sc2");
119	2074	lemma = t[0].eqNode(utils::mkNConcat(sk1, t[1], sk2));
120	2074	lemma = nm->mkNode(ITE, t, lemma, t[0].eqNode(t[1]).notNode());
121		}
122	20197	return lemma;
123		}
124
125	7739	Node TermRegistry::lengthPositive(Node t)
126		{
127	7739	NodeManager* nm = NodeManager::currentNM();
128	15478	Node zero = nm->mkConst(Rational(0));
129	15478	Node emp = Word::mkEmptyWord(t.getType());
130	15478	Node tlen = nm->mkNode(STRING_LENGTH, t);
131	15478	Node tlenEqZero = tlen.eqNode(zero);
132	15478	Node tEqEmp = t.eqNode(emp);
133	15478	Node caseEmpty = nm->mkNode(AND, tlenEqZero, tEqEmp);
134	15478	Node caseNEmpty = nm->mkNode(GT, tlen, zero);
135		// (or (and (= (str.len t) 0) (= t "")) (> (str.len t) 0))
136	15478	return nm->mkNode(OR, caseEmpty, caseNEmpty);
137		}
138
139	110699	void TermRegistry::preRegisterTerm(TNode n)
140		{
141	110699	if (d_preregisteredTerms.find(n) != d_preregisteredTerms.end())
142		{
143	45630	return;
144		}
145	110123	eq::EqualityEngine* ee = d_state.getEqualityEngine();
146	110123	d_preregisteredTerms.insert(n);
147	220246	Trace("strings-preregister")
148	110123	<< "TheoryString::preregister : " << n << std::endl;
149		// check for logic exceptions
150	110123	Kind k = n.getKind();
151	110123	if (!options::stringExp())
152		{
153	3057	if (k == STRING_INDEXOF \|\| k == STRING_INDEXOF_RE \|\| k == STRING_ITOS
154	3057	\|\| k == STRING_STOI \|\| k == STRING_REPLACE \|\| k == STRING_SUBSTR
155	3057	\|\| k == STRING_REPLACE_ALL \|\| k == SEQ_NTH \|\| k == STRING_REPLACE_RE
156	3057	\|\| k == STRING_REPLACE_RE_ALL \|\| k == STRING_CONTAINS \|\| k == STRING_LEQ
157	3057	\|\| k == STRING_TOLOWER \|\| k == STRING_TOUPPER \|\| k == STRING_REV
158	3057	\|\| k == STRING_UPDATE)
159		{
160		std::stringstream ss;
161		ss << "Term of kind " << k
162		<< " not supported in default mode, try --strings-exp";
163		throw LogicException(ss.str());
164		}
165		}
166	110123	if (k == EQUAL)
167		{
168	42152	if (n[0].getType().isRegExp())
169		{
170		std::stringstream ss;
171		ss << "Equality between regular expressions is not supported";
172		throw LogicException(ss.str());
173		}
174	42152	ee->addTriggerPredicate(n);
175	42152	return;
176		}
177	67971	else if (k == STRING_IN_REGEXP)
178		{
179	2326	d_im->requirePhase(n, true);
180	2326	ee->addTriggerPredicate(n);
181	2326	ee->addTerm(n[0]);
182	2326	ee->addTerm(n[1]);
183	2326	return;
184		}
185	65645	else if (k == STRING_TO_CODE)
186		{
187	2227	d_hasStrCode = true;
188		}
189	63418	else if (k == SEQ_NTH \|\| k == STRING_UPDATE)
190		{
191	33	d_hasSeqUpdate = true;
192		}
193	63385	else if (k == REGEXP_RANGE)
194		{
195	159	for (const Node& nc : n)
196		{
197	106	if (!nc.isConst())
198		{
199		throw LogicException(
200		"expecting a constant string term in regexp range");
201		}
202	106	if (nc.getConst<String>().size() != 1)
203		{
204		throw LogicException(
205		"expecting a single constant string term in regexp range");
206		}
207		}
208		}
209	65645	registerTerm(n, 0);
210	131290	TypeNode tn = n.getType();
211	65645	if (tn.isRegExp() && n.isVar())
212		{
213		std::stringstream ss;
214		ss << "Regular expression variables are not supported.";
215		throw LogicException(ss.str());
216		}
217	65645	if (tn.isString()) // string-only
218		{
219		// all characters of constants should fall in the alphabet
220	33525	if (n.isConst())
221		{
222	5864	std::vector<unsigned> vec = n.getConst<String>().getVec();
223	14617	for (unsigned u : vec)
224		{
225	11685	if (u >= d_cardSize)
226		{
227		std::stringstream ss;
228		ss << "Characters in string \"" << n
229		<< "\" are outside of the given alphabet.";
230		throw LogicException(ss.str());
231		}
232		}
233		}
234	33525	ee->addTerm(n);
235		}
236	32120	else if (tn.isBoolean())
237		{
238		// All kinds that we do congruence over that may return a Boolean go here
239	1323	if (k == STRING_CONTAINS \|\| k == STRING_LEQ \|\| k == SEQ_NTH)
240		{
241		// Get triggered for both equal and dis-equal
242	1317	ee->addTriggerPredicate(n);
243		}
244		}
245		else
246		{
247		// Function applications/predicates
248	30797	ee->addTerm(n);
249		}
250		// Set d_functionsTerms stores all function applications that are
251		// relevant to theory combination. Notice that this is a subset of
252		// the applications whose kinds are function kinds in the equality
253		// engine. This means it does not include applications of operators
254		// like re.++, which is not a function kind in the equality engine.
255		// Concatenation terms do not need to be considered here because
256		// their arguments have string type and do not introduce any shared
257		// terms.
258	171692	if (n.hasOperator() && ee->isFunctionKind(k)
259	103734	&& kindToTheoryId(k) == THEORY_STRINGS && k != STRING_CONCAT)
260		{
261	30588	d_functionsTerms.push_back(n);
262		}
263	65645	if (options::stringFMF())
264		{
265	13762	if (tn.isStringLike())
266		{
267		// Our decision strategy will minimize the length of this term if it is a
268		// variable but not an internally generated Skolem, or a term that does
269		// not belong to this theory.
270	10014	if (n.isVar() ? !d_skCache.isSkolem(n)
271	2890	: kindToTheoryId(k) != THEORY_STRINGS)
272		{
273	480	d_inputVars.insert(n);
274	480	Trace("strings-preregister") << "input variable: " << n << std::endl;
275		}
276		}
277		}
278		}
279
280	144762	void TermRegistry::registerTerm(Node n, int effort)
281		{
282	289524	Trace("strings-register") << "TheoryStrings::registerTerm() " << n
283	144762	<< ", effort = " << effort << std::endl;
284	144762	if (d_registeredTerms.find(n) != d_registeredTerms.end())
285		{
286	105275	Trace("strings-register") << "...already registered" << std::endl;
287	210550	return;
288		}
289	39487	bool do_register = true;
290	78974	TypeNode tn = n.getType();
291	39487	if (!tn.isStringLike())
292		{
293	18898	if (options::stringEagerLen())
294		{
295	18898	do_register = effort == 0;
296		}
297		else
298		{
299		do_register = effort > 0 \|\| n.getKind() != STRING_CONCAT;
300		}
301		}
302	39487	if (!do_register)
303		{
304		Trace("strings-register") << "...do not register" << std::endl;
305		return;
306		}
307	39487	Trace("strings-register") << "...register" << std::endl;
308	39487	d_registeredTerms.insert(n);
309		// ensure the type is registered
310	39487	registerType(tn);
311	78974	TrustNode regTermLem;
312	39487	if (tn.isStringLike())
313		{
314		// register length information:
315		// for variables, split on empty vs positive length
316		// for concat/const/replace, introduce proxy var and state length relation
317	20589	regTermLem = getRegisterTermLemma(n);
318		}
319	18898	else if (n.getKind() != STRING_CONTAINS)
320		{
321		// we don't send out eager reduction lemma for str.contains currently
322	36246	Node eagerRedLemma = eagerReduce(n, &d_skCache);
323	18123	if (!eagerRedLemma.isNull())
324		{
325		// if there was an eager reduction, we make the trust node for it
326	1475	if (d_epg != nullptr)
327		{
328	232	regTermLem = d_epg->mkTrustNode(
329	116	eagerRedLemma, PfRule::STRING_EAGER_REDUCTION, {}, {n});
330		}
331		else
332		{
333	1359	regTermLem = TrustNode::mkTrustLemma(eagerRedLemma, nullptr);
334		}
335		}
336		}
337	39487	if (!regTermLem.isNull())
338		{
339	15906	Trace("strings-lemma") << "Strings::Lemma REG-TERM : " << regTermLem
340	7953	<< std::endl;
341	15906	Trace("strings-assert")
342	7953	<< "(assert " << regTermLem.getNode() << ")" << std::endl;
343	7953	d_im->trustedLemma(regTermLem, InferenceId::STRINGS_REGISTER_TERM);
344		}
345		}
346
347	39487	void TermRegistry::registerType(TypeNode tn)
348		{
349	39487	if (d_registeredTypes.find(tn) != d_registeredTypes.end())
350		{
351	38058	return;
352		}
353	1429	d_registeredTypes.insert(tn);
354	1429	if (tn.isStringLike())
355		{
356		// preregister the empty word for the type
357	1152	Node emp = Word::mkEmptyWord(tn);
358	576	if (!d_state.hasTerm(emp))
359		{
360	576	preRegisterTerm(emp);
361		}
362		}
363		}
364
365	20589	TrustNode TermRegistry::getRegisterTermLemma(Node n)
366		{
367	20589	Assert(n.getType().isStringLike());
368	20589	NodeManager* nm = NodeManager::currentNM();
369		// register length information:
370		// for variables, split on empty vs positive length
371		// for concat/const/replace, introduce proxy var and state length relation
372	41178	Node lsum;
373	20589	if (n.getKind() != STRING_CONCAT && !n.isConst())
374		{
375	14303	Node lsumb = nm->mkNode(STRING_LENGTH, n);
376	14207	lsum = Rewriter::rewrite(lsumb);
377		// can register length term if it does not rewrite
378	14207	if (lsum == lsumb)
379		{
380	14111	registerTermAtomic(n, LENGTH_SPLIT);
381	14111	return TrustNode::null();
382		}
383		}
384	12956	Node sk = d_skCache.mkSkolemCached(n, SkolemCache::SK_PURIFY, "lsym");
385		StringsProxyVarAttribute spva;
386	6478	sk.setAttribute(spva, true);
387	12956	Node eq = Rewriter::rewrite(sk.eqNode(n));
388	6478	d_proxyVar[n] = sk;
389		// If we are introducing a proxy for a constant or concat term, we do not
390		// need to send lemmas about its length, since its length is already
391		// implied.
392	6478	if (n.isConst() \|\| n.getKind() == STRING_CONCAT)
393		{
394		// do not send length lemma for sk.
395	6382	registerTermAtomic(sk, LENGTH_IGNORE);
396		}
397	12956	Node skl = nm->mkNode(STRING_LENGTH, sk);
398	6478	if (n.getKind() == STRING_CONCAT)
399		{
400	8090	std::vector<Node> nodeVec;
401	13774	for (const Node& nc : n)
402		{
403	9729	if (nc.getAttribute(StringsProxyVarAttribute()))
404		{
405	15	Assert(d_proxyVarToLength.find(nc) != d_proxyVarToLength.end());
406	15	nodeVec.push_back(d_proxyVarToLength[nc]);
407		}
408		else
409		{
410	19428	Node lni = nm->mkNode(STRING_LENGTH, nc);
411	9714	nodeVec.push_back(lni);
412		}
413		}
414	4045	lsum = nm->mkNode(PLUS, nodeVec);
415	4045	lsum = Rewriter::rewrite(lsum);
416		}
417	2433	else if (n.isConst())
418		{
419	2337	lsum = nm->mkConst(Rational(Word::getLength(n)));
420		}
421	6478	Assert(!lsum.isNull());
422	6478	d_proxyVarToLength[sk] = lsum;
423	12956	Node ceq = Rewriter::rewrite(skl.eqNode(lsum));
424
425	12956	Node ret = nm->mkNode(AND, eq, ceq);
426
427		// it is a simple rewrite to justify this
428	6478	if (d_epg != nullptr)
429		{
430	197	return d_epg->mkTrustNode(ret, PfRule::MACRO_SR_PRED_INTRO, {}, {ret});
431		}
432	6281	return TrustNode::mkTrustLemma(ret, nullptr);
433		}
434
435	21562	void TermRegistry::registerTermAtomic(Node n, LengthStatus s)
436		{
437	21562	if (d_lengthLemmaTermsCache.find(n) != d_lengthLemmaTermsCache.end())
438		{
439	21272	return;
440		}
441	14112	d_lengthLemmaTermsCache.insert(n);
442
443	14112	if (s == LENGTH_IGNORE)
444		{
445		// ignore it
446	6372	return;
447		}
448	15480	std::map<Node, bool> reqPhase;
449	15480	TrustNode lenLem = getRegisterTermAtomicLemma(n, s, reqPhase);
450	7740	if (!lenLem.isNull())
451		{
452	15478	Trace("strings-lemma") << "Strings::Lemma REGISTER-TERM-ATOMIC : " << lenLem
453	7739	<< std::endl;
454	15478	Trace("strings-assert")
455	7739	<< "(assert " << lenLem.getNode() << ")" << std::endl;
456	7739	d_im->trustedLemma(lenLem, InferenceId::STRINGS_REGISTER_TERM_ATOMIC);
457		}
458	23210	for (const std::pair<const Node, bool>& rp : reqPhase)
459		{
460	15470	d_im->requirePhase(rp.first, rp.second);
461		}
462		}
463
464	26880	SkolemCache* TermRegistry::getSkolemCache() { return &d_skCache; }
465
466	5721	const context::CDList<TNode>& TermRegistry::getFunctionTerms() const
467		{
468	5721	return d_functionsTerms;
469		}
470
471	55	const context::CDHashSet<Node>& TermRegistry::getInputVars() const
472		{
473	55	return d_inputVars;
474		}
475
476	9218	bool TermRegistry::hasStringCode() const { return d_hasStrCode; }
477
478		bool TermRegistry::hasSeqUpdate() const { return d_hasSeqUpdate; }
479
480		bool TermRegistry::isHandledUpdate(Node n)
481		{
482		Assert(n.getKind() == STRING_UPDATE \|\| n.getKind() == STRING_SUBSTR);
483		NodeManager* nm = NodeManager::currentNM();
484		Node lenN = n[2];
485		if (n.getKind() == STRING_UPDATE)
486		{
487		lenN = nm->mkNode(STRING_LENGTH, n[2]);
488		}
489		Node one = nm->mkConst(Rational(1));
490		return d_aent.checkEq(lenN, one);
491		}
492
493		Node TermRegistry::getUpdateBase(Node n)
494		{
495		while (n.getKind() == STRING_UPDATE)
496		{
497		n = n[0];
498		}
499		return n;
500		}
501
502	7740	TrustNode TermRegistry::getRegisterTermAtomicLemma(
503		Node n, LengthStatus s, std::map<Node, bool>& reqPhase)
504		{
505	7740	if (n.isConst())
506		{
507		// No need to send length for constant terms. This case may be triggered
508		// for cases where the skolem cache automatically replaces a skolem by
509		// a constant.
510	1	return TrustNode::null();
511		}
512	7739	Assert(n.getType().isStringLike());
513	7739	NodeManager* nm = NodeManager::currentNM();
514	15478	Node n_len = nm->mkNode(kind::STRING_LENGTH, n);
515	15478	Node emp = Word::mkEmptyWord(n.getType());
516	7739	if (s == LENGTH_GEQ_ONE)
517		{
518	8	Node neq_empty = n.eqNode(emp).negate();
519	8	Node len_n_gt_z = nm->mkNode(GT, n_len, d_zero);
520	8	Node len_geq_one = nm->mkNode(AND, neq_empty, len_n_gt_z);
521	8	Trace("strings-lemma") << "Strings::Lemma SK-GEQ-ONE : " << len_geq_one
522	4	<< std::endl;
523	4	Trace("strings-assert") << "(assert " << len_geq_one << ")" << std::endl;
524	4	return TrustNode::mkTrustLemma(len_geq_one, nullptr);
525		}
526
527	7735	if (s == LENGTH_ONE)
528		{
529		Node len_one = n_len.eqNode(d_one);
530		Trace("strings-lemma") << "Strings::Lemma SK-ONE : " << len_one
531		<< std::endl;
532		Trace("strings-assert") << "(assert " << len_one << ")" << std::endl;
533		return TrustNode::mkTrustLemma(len_one, nullptr);
534		}
535	7735	Assert(s == LENGTH_SPLIT);
536
537		// get the positive length lemma
538	15470	Node lenLemma = lengthPositive(n);
539		// split whether the string is empty
540	15470	Node n_len_eq_z = n_len.eqNode(d_zero);
541	15470	Node n_len_eq_z_2 = n.eqNode(emp);
542	15470	Node case_empty = nm->mkNode(AND, n_len_eq_z, n_len_eq_z_2);
543	15470	Node case_emptyr = Rewriter::rewrite(case_empty);
544	7735	if (!case_emptyr.isConst())
545		{
546		// prefer trying the empty case first
547		// notice that requirePhase must only be called on rewritten literals that
548		// occur in the CNF stream.
549	7735	n_len_eq_z = Rewriter::rewrite(n_len_eq_z);
550	7735	Assert(!n_len_eq_z.isConst());
551	7735	reqPhase[n_len_eq_z] = true;
552	7735	n_len_eq_z_2 = Rewriter::rewrite(n_len_eq_z_2);
553	7735	Assert(!n_len_eq_z_2.isConst());
554	7735	reqPhase[n_len_eq_z_2] = true;
555		}
556		else
557		{
558		// If n = "" ---> true or len( n ) = 0 ----> true, then we expect that
559		// n ---> "". Since this method is only called on non-constants n, it must
560		// be that n = "" ^ len( n ) = 0 does not rewrite to true.
561		Assert(!case_emptyr.getConst<bool>());
562		}
563
564	7735	if (d_epg != nullptr)
565		{
566	271	return d_epg->mkTrustNode(lenLemma, PfRule::STRING_LENGTH_POS, {}, {n});
567		}
568	7464	return TrustNode::mkTrustLemma(lenLemma, nullptr);
569		}
570
571	325034	Node TermRegistry::getSymbolicDefinition(Node n, std::vector<Node>& exp) const
572		{
573	325034	if (n.getNumChildren() == 0)
574		{
575	280374	Node pn = getProxyVariableFor(n);
576	140187	if (pn.isNull())
577		{
578	16597	return Node::null();
579		}
580	247180	Node eq = n.eqNode(pn);
581	123590	eq = Rewriter::rewrite(eq);
582	123590	if (std::find(exp.begin(), exp.end(), eq) == exp.end())
583		{
584	121295	exp.push_back(eq);
585		}
586	123590	return pn;
587		}
588	369694	std::vector<Node> children;
589	184847	if (n.getMetaKind() == metakind::PARAMETERIZED)
590		{
591	39	children.push_back(n.getOperator());
592		}
593	495277	for (const Node& nc : n)
594		{
595	332824	if (n.getType().isRegExp())
596		{
597	125411	children.push_back(nc);
598		}
599		else
600		{
601	392432	Node ns = getSymbolicDefinition(nc, exp);
602	207413	if (ns.isNull())
603		{
604	22394	return Node::null();
605		}
606		else
607		{
608	185019	children.push_back(ns);
609		}
610		}
611		}
612	162453	return NodeManager::currentNM()->mkNode(n.getKind(), children);
613		}
614
615	146127	Node TermRegistry::getProxyVariableFor(Node n) const
616		{
617	146127	NodeNodeMap::const_iterator it = d_proxyVar.find(n);
618	146127	if (it != d_proxyVar.end())
619		{
620	129277	return (*it).second;
621		}
622	16850	return Node::null();
623		}
624
625	5683	Node TermRegistry::ensureProxyVariableFor(Node n)
626		{
627	5683	Node proxy = getProxyVariableFor(n);
628	5683	if (proxy.isNull())
629		{
630	249	registerTerm(n, 0);
631	249	proxy = getProxyVariableFor(n);
632		}
633	5683	Assert(!proxy.isNull());
634	5683	return proxy;
635		}
636
637	72903	void TermRegistry::removeProxyEqs(Node n, std::vector<Node>& unproc) const
638		{
639	72903	if (n.getKind() == AND)
640		{
641	2196	for (const Node& nc : n)
642		{
643	1754	removeProxyEqs(nc, unproc);
644		}
645	888	return;
646		}
647	72461	Trace("strings-subs-proxy") << "Input : " << n << std::endl;
648	144918	Node ns = Rewriter::rewrite(n);
649	72461	if (ns.getKind() == EQUAL)
650		{
651	216929	for (size_t i = 0; i < 2; i++)
652		{
653		// determine whether this side has a proxy variable
654	144622	if (ns[i].getAttribute(StringsProxyVarAttribute()))
655		{
656	8	if (getProxyVariableFor(ns[1 - i]) == ns[i])
657		{
658	8	Trace("strings-subs-proxy")
659	4	<< "...trivial definition via " << ns[i] << std::endl;
660		// it is a trivial equality, e.g. between a proxy variable
661		// and its definition
662	4	return;
663		}
664		}
665		}
666		}
667	72457	if (!n.isConst() \|\| !n.getConst<bool>())
668		{
669	72455	Trace("strings-subs-proxy") << "...unprocessed" << std::endl;
670	72455	unproc.push_back(n);
671		}
672		}
673
674		} // namespace strings
675		} // namespace theory
676	22755	} // namespace cvc5