Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/smt/sygus_solver.cpp	Lines:	204	227	89.9 %
Date:	2021-09-15	Branches:	376	816	46.1 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Haniel Barbosa, Abdalrhman Mohamed
 *
 * 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.
 * ****************************************************************************
 *
 * The solver for SyGuS queries.
 */

#include "smt/sygus_solver.h"

#include <sstream>

#include "base/modal_exception.h"
#include "expr/dtype.h"
#include "expr/dtype_cons.h"
#include "expr/skolem_manager.h"
#include "options/base_options.h"
#include "options/option_exception.h"
#include "options/quantifiers_options.h"
#include "options/smt_options.h"
#include "smt/preprocessor.h"
#include "smt/smt_solver.h"
#include "theory/datatypes/sygus_datatype_utils.h"
#include "theory/quantifiers/quantifiers_attributes.h"
#include "theory/quantifiers/sygus/sygus_grammar_cons.h"
#include "theory/quantifiers/sygus/sygus_utils.h"
#include "theory/quantifiers_engine.h"
#include "theory/rewriter.h"
#include "theory/smt_engine_subsolver.h"

using namespace cvc5::theory;
using namespace cvc5::kind;

namespace cvc5 {
namespace smt {

SygusSolver::SygusSolver(Env& env, SmtSolver& sms, Preprocessor& pp)
    : d_env(env),
      d_smtSolver(sms),
      d_pp(pp),
      d_sygusConjectureStale(env.getUserContext(), true)
{
}

SygusSolver::~SygusSolver() {}

void SygusSolver::declareSygusVar(Node var)
{
  Trace("smt") << "SygusSolver::declareSygusVar: " << var << " "
               << var.getType() << "\n";
  d_sygusVars.push_back(var);
  // don't need to set that the conjecture is stale
}

void SygusSolver::declareSynthFun(Node fn,
                                  TypeNode sygusType,
                                  bool isInv,
                                  const std::vector<Node>& vars)
{
  Trace("smt") << "SygusSolver::declareSynthFun: " << fn << "\n";
  NodeManager* nm = NodeManager::currentNM();
  d_sygusFunSymbols.push_back(fn);
  if (!vars.empty())
  {
    Node bvl = nm->mkNode(BOUND_VAR_LIST, vars);
    // use an attribute to mark its bound variable list
    SygusSynthFunVarListAttribute ssfvla;
    fn.setAttribute(ssfvla, bvl);
  }
  // whether sygus type encodes syntax restrictions
  if (!sygusType.isNull() && sygusType.isDatatype()
      && sygusType.getDType().isSygus())
  {
    Node sym = nm->mkBoundVar("sfproxy", sygusType);
    // use an attribute to mark its grammar
    SygusSynthGrammarAttribute ssfga;
    fn.setAttribute(ssfga, sym);
    // we must expand definitions for sygus operators in the block
    expandDefinitionsSygusDt(sygusType);
  }

  // sygus conjecture is now stale
  setSygusConjectureStale();
}

void SygusSolver::assertSygusConstraint(Node n, bool isAssume)
{
  Trace("smt") << "SygusSolver::assertSygusConstrant: " << n
               << ", isAssume=" << isAssume << "\n";
  if (isAssume)
  {
    d_sygusAssumps.push_back(n);
  }
  else
  {
    d_sygusConstraints.push_back(n);
  }

  // sygus conjecture is now stale
  setSygusConjectureStale();
}

void SygusSolver::assertSygusInvConstraint(Node inv,
                                           Node pre,
                                           Node trans,
                                           Node post)
{
  Trace("smt") << "SygusSolver::assertSygusInvConstrant: " << inv << " " << pre
               << " " << trans << " " << post << "\n";
  // build invariant constraint

  // get variables (regular and their respective primed versions)
  std::vector<Node> terms;
  std::vector<Node> vars;
  std::vector<Node> primed_vars;
  terms.push_back(inv);
  terms.push_back(pre);
  terms.push_back(trans);
  terms.push_back(post);
  // variables are built based on the invariant type
  NodeManager* nm = NodeManager::currentNM();
  std::vector<TypeNode> argTypes = inv.getType().getArgTypes();
  for (const TypeNode& tn : argTypes)
  {
    vars.push_back(nm->mkBoundVar(tn));
    d_sygusVars.push_back(vars.back());
    std::stringstream ss;
    ss << vars.back() << "'";
    primed_vars.push_back(nm->mkBoundVar(ss.str(), tn));
    d_sygusVars.push_back(primed_vars.back());
  }

  // make relevant terms; 0 -> Inv, 1 -> Pre, 2 -> Trans, 3 -> Post
  for (unsigned i = 0; i < 4; ++i)
  {
    Node op = terms[i];
    Trace("smt-debug") << "Make inv-constraint term #" << i << " : " << op
                       << " with type " << op.getType() << "...\n";
    std::vector<Node> children;
    children.push_back(op);
    // transition relation applied over both variable lists
    if (i == 2)
    {
      children.insert(children.end(), vars.begin(), vars.end());
      children.insert(children.end(), primed_vars.begin(), primed_vars.end());
    }
    else
    {
      children.insert(children.end(), vars.begin(), vars.end());
    }
    terms[i] = nm->mkNode(APPLY_UF, children);
    // make application of Inv on primed variables
    if (i == 0)
    {
      children.clear();
      children.push_back(op);
      children.insert(children.end(), primed_vars.begin(), primed_vars.end());
      terms.push_back(nm->mkNode(APPLY_UF, children));
    }
  }
  // make constraints
  std::vector<Node> conj;
  conj.push_back(nm->mkNode(IMPLIES, terms[1], terms[0]));
  Node term0_and_2 = nm->mkNode(AND, terms[0], terms[2]);
  conj.push_back(nm->mkNode(IMPLIES, term0_and_2, terms[4]));
  conj.push_back(nm->mkNode(IMPLIES, terms[0], terms[3]));
  Node constraint = nm->mkNode(AND, conj);

  d_sygusConstraints.push_back(constraint);

  // sygus conjecture is now stale
  setSygusConjectureStale();
}

Result SygusSolver::checkSynth(Assertions& as)
{
  if (options::incrementalSolving())
  {
    // TODO (project #7)
    throw ModalException(
        "Cannot make check-synth commands when incremental solving is enabled");
  }
  Trace("smt") << "SygusSolver::checkSynth" << std::endl;
  std::vector<Node> query;
  if (d_sygusConjectureStale)
  {
    NodeManager* nm = NodeManager::currentNM();
    // build synthesis conjecture from asserted constraints and declared
    // variables/functions
    Trace("smt") << "Sygus : Constructing sygus constraint...\n";
    Node body = nm->mkAnd(d_sygusConstraints);
    // note that if there are no constraints, then assumptions are irrelevant
    if (!d_sygusConstraints.empty() && !d_sygusAssumps.empty())
    {
      Node bodyAssump = nm->mkAnd(d_sygusAssumps);
      body = nm->mkNode(IMPLIES, bodyAssump, body);
    }
    body = body.notNode();
    Trace("smt") << "...constructed sygus constraint " << body << std::endl;
    if (!d_sygusVars.empty())
    {
      Node boundVars = nm->mkNode(BOUND_VAR_LIST, d_sygusVars);
      body = nm->mkNode(EXISTS, boundVars, body);
      Trace("smt") << "...constructed exists " << body << std::endl;
    }
    if (!d_sygusFunSymbols.empty())
    {
      body =
          quantifiers::SygusUtils::mkSygusConjecture(d_sygusFunSymbols, body);
    }
    Trace("smt") << "...constructed forall " << body << std::endl;

    Trace("smt") << "Check synthesis conjecture: " << body << std::endl;

    d_sygusConjectureStale = false;

    // TODO (project #7): if incremental, we should push a context and assert
    query.push_back(body);
  }

  Result r = d_smtSolver.checkSatisfiability(as, query, false);

  // Check that synthesis solutions satisfy the conjecture
  if (options::checkSynthSol()
      && r.asSatisfiabilityResult().isSat() == Result::UNSAT)
  {
    checkSynthSolution(as);
  }
  return r;
}

bool SygusSolver::getSynthSolutions(std::map<Node, Node>& sol_map)
{
  Trace("smt") << "SygusSolver::getSynthSolutions" << std::endl;
  std::map<Node, std::map<Node, Node>> sol_mapn;
  // fail if the theory engine does not have synthesis solutions
  QuantifiersEngine* qe = d_smtSolver.getQuantifiersEngine();
  if (qe == nullptr || !qe->getSynthSolutions(sol_mapn))
  {
    return false;
  }
  for (std::pair<const Node, std::map<Node, Node>>& cs : sol_mapn)
  {
    for (std::pair<const Node, Node>& s : cs.second)
    {
      sol_map[s.first] = s.second;
    }
  }
  return true;
}

void SygusSolver::checkSynthSolution(Assertions& as)
{
  NodeManager* nm = NodeManager::currentNM();
  SkolemManager* sm = nm->getSkolemManager();
  Notice() << "SygusSolver::checkSynthSolution(): checking synthesis solution"
           << std::endl;
  std::map<Node, std::map<Node, Node>> sol_map;
  // Get solutions and build auxiliary vectors for substituting
  QuantifiersEngine* qe = d_smtSolver.getQuantifiersEngine();
  if (qe == nullptr || !qe->getSynthSolutions(sol_map))
  {
    InternalError()
        << "SygusSolver::checkSynthSolution(): No solution to check!";
    return;
  }
  if (sol_map.empty())
  {
    InternalError() << "SygusSolver::checkSynthSolution(): Got empty solution!";
    return;
  }
  Trace("check-synth-sol") << "Got solution map:\n";
  // the set of synthesis conjectures in our assertions
  std::unordered_set<Node> conjs;
  // For each of the above conjectures, the functions-to-synthesis and their
  // solutions. This is used as a substitution below.
  std::map<Node, std::vector<Node>> fvarMap;
  std::map<Node, std::vector<Node>> fsolMap;
  for (const std::pair<const Node, std::map<Node, Node>>& cmap : sol_map)
  {
    Trace("check-synth-sol") << "For conjecture " << cmap.first << ":\n";
    conjs.insert(cmap.first);
    std::vector<Node>& fvars = fvarMap[cmap.first];
    std::vector<Node>& fsols = fsolMap[cmap.first];
    for (const std::pair<const Node, Node>& pair : cmap.second)
    {
      Trace("check-synth-sol")
          << "  " << pair.first << " --> " << pair.second << "\n";
      fvars.push_back(pair.first);
      fsols.push_back(pair.second);
    }
  }
  Trace("check-synth-sol") << "Starting new SMT Engine\n";

  Trace("check-synth-sol") << "Retrieving assertions\n";
  // Build conjecture from original assertions
  context::CDList<Node>* alist = as.getAssertionList();
  if (alist == nullptr)
  {
    Trace("check-synth-sol") << "No assertions to check\n";
    return;
  }
  // auxiliary assertions
  std::vector<Node> auxAssertions;
  // expand definitions cache
  std::unordered_map<Node, Node> cache;
  for (Node assertion : *alist)
  {
    Notice() << "SygusSolver::checkSynthSolution(): checking assertion "
             << assertion << std::endl;
    Trace("check-synth-sol") << "Retrieving assertion " << assertion << "\n";
    // Apply any define-funs from the problem.
    Node n = d_pp.expandDefinitions(assertion, cache);
    Notice() << "SygusSolver::checkSynthSolution(): -- expands to " << n
             << std::endl;
    Trace("check-synth-sol") << "Expanded assertion " << n << "\n";
    if (conjs.find(n) == conjs.end())
    {
      Trace("check-synth-sol") << "It is an auxiliary assertion\n";
      auxAssertions.push_back(n);
    }
    else
    {
      Trace("check-synth-sol") << "It is a synthesis conjecture\n";
    }
  }
  // check all conjectures
  for (Node conj : conjs)
  {
    // Start new SMT engine to check solutions
    std::unique_ptr<SmtEngine> solChecker;
    initializeSubsolver(solChecker, d_env);
    solChecker->getOptions().smt.checkSynthSol = false;
    solChecker->getOptions().quantifiers.sygusRecFun = false;
    // get the solution for this conjecture
    std::vector<Node>& fvars = fvarMap[conj];
    std::vector<Node>& fsols = fsolMap[conj];
    // Apply solution map to conjecture body
    Node conjBody;
    /* Whether property is quantifier free */
    if (conj[1].getKind() != EXISTS)
    {
      conjBody = conj[1].substitute(
          fvars.begin(), fvars.end(), fsols.begin(), fsols.end());
    }
    else
    {
      conjBody = conj[1][1].substitute(
          fvars.begin(), fvars.end(), fsols.begin(), fsols.end());

      /* Skolemize property */
      std::vector<Node> vars, skos;
      for (unsigned j = 0, size = conj[1][0].getNumChildren(); j < size; ++j)
      {
        vars.push_back(conj[1][0][j]);
        std::stringstream ss;
        ss << "sk_" << j;
        skos.push_back(sm->mkDummySkolem(ss.str(), conj[1][0][j].getType()));
        Trace("check-synth-sol") << "\tSkolemizing " << conj[1][0][j] << " to "
                                 << skos.back() << "\n";
      }
      conjBody = conjBody.substitute(
          vars.begin(), vars.end(), skos.begin(), skos.end());
    }
    Notice() << "SygusSolver::checkSynthSolution(): -- body substitutes to "
             << conjBody << std::endl;
    Trace("check-synth-sol")
        << "Substituted body of assertion to " << conjBody << "\n";
    solChecker->assertFormula(conjBody);
    // Assert all auxiliary assertions. This may include recursive function
    // definitions that were added as assertions to the sygus problem.
    for (Node a : auxAssertions)
    {
      // We require rewriting here, e.g. so that define-fun from the original
      // problem are rewritten to true. If this is not the case, then the
      // assertions module of the subsolver will complain about assertions
      // with free variables.
      Node ar = theory::Rewriter::rewrite(a);
      solChecker->assertFormula(ar);
    }
    Result r = solChecker->checkSat();
    Notice() << "SygusSolver::checkSynthSolution(): result is " << r
             << std::endl;
    Trace("check-synth-sol") << "Satsifiability check: " << r << "\n";
    if (r.asSatisfiabilityResult().isUnknown())
    {
      InternalError() << "SygusSolver::checkSynthSolution(): could not check "
                         "solution, result "
                         "unknown.";
    }
    else if (r.asSatisfiabilityResult().isSat())
    {
      InternalError()
          << "SygusSolver::checkSynthSolution(): produced solution leads to "
             "satisfiable negated conjecture.";
    }
  }
}

void SygusSolver::setSygusConjectureStale()
{
  if (d_sygusConjectureStale)
  {
    // already stale
    return;
  }
  d_sygusConjectureStale = true;
  // TODO (project #7): if incremental, we should pop a context
}

void SygusSolver::expandDefinitionsSygusDt(TypeNode tn) const
{
  std::unordered_set<TypeNode> processed;
  std::vector<TypeNode> toProcess;
  toProcess.push_back(tn);
  size_t index = 0;
  while (index < toProcess.size())
  {
    TypeNode tnp = toProcess[index];
    index++;
    Assert(tnp.isDatatype());
    Assert(tnp.getDType().isSygus());
    const std::vector<std::shared_ptr<DTypeConstructor>>& cons =
        tnp.getDType().getConstructors();
    for (const std::shared_ptr<DTypeConstructor>& c : cons)
    {
      Node op = c->getSygusOp();
      // Only expand definitions if the operator is not constant, since
      // calling expandDefinitions on them should be a no-op. This check
      // ensures we don't try to expand e.g. bitvector extract operators,
      // whose type is undefined, and thus should not be passed to
      // expandDefinitions.
      Node eop = op.isConst() ? op : d_pp.expandDefinitions(op);
      datatypes::utils::setExpandedDefinitionForm(op, eop);
      // also must consider the arguments
      for (unsigned j = 0, nargs = c->getNumArgs(); j < nargs; ++j)
      {
        TypeNode tnc = c->getArgType(j);
        if (tnc.isDatatype() && tnc.getDType().isSygus()
            && processed.find(tnc) == processed.end())
        {
          toProcess.push_back(tnc);
          processed.insert(tnc);
        }
      }
    }
  }
}

}  // namespace smt
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andrew Reynolds, Haniel Barbosa, Abdalrhman 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		* The solver for SyGuS queries.
14		*/
15
16		#include "smt/sygus_solver.h"
17
18		#include <sstream>
19
20		#include "base/modal_exception.h"
21		#include "expr/dtype.h"
22		#include "expr/dtype_cons.h"
23		#include "expr/skolem_manager.h"
24		#include "options/base_options.h"
25		#include "options/option_exception.h"
26		#include "options/quantifiers_options.h"
27		#include "options/smt_options.h"
28		#include "smt/preprocessor.h"
29		#include "smt/smt_solver.h"
30		#include "theory/datatypes/sygus_datatype_utils.h"
31		#include "theory/quantifiers/quantifiers_attributes.h"
32		#include "theory/quantifiers/sygus/sygus_grammar_cons.h"
33		#include "theory/quantifiers/sygus/sygus_utils.h"
34		#include "theory/quantifiers_engine.h"
35		#include "theory/rewriter.h"
36		#include "theory/smt_engine_subsolver.h"
37
38		using namespace cvc5::theory;
39		using namespace cvc5::kind;
40
41		namespace cvc5 {
42		namespace smt {
43
44	13209	SygusSolver::SygusSolver(Env& env, SmtSolver& sms, Preprocessor& pp)
45		: d_env(env),
46		d_smtSolver(sms),
47		d_pp(pp),
48	13209	d_sygusConjectureStale(env.getUserContext(), true)
49		{
50	13209	}
51
52	10562	SygusSolver::~SygusSolver() {}
53
54	422	void SygusSolver::declareSygusVar(Node var)
55		{
56	844	Trace("smt") << "SygusSolver::declareSygusVar: " << var << " "
57	422	<< var.getType() << "\n";
58	422	d_sygusVars.push_back(var);
59		// don't need to set that the conjecture is stale
60	422	}
61
62	384	void SygusSolver::declareSynthFun(Node fn,
63		TypeNode sygusType,
64		bool isInv,
65		const std::vector<Node>& vars)
66		{
67	384	Trace("smt") << "SygusSolver::declareSynthFun: " << fn << "\n";
68	384	NodeManager* nm = NodeManager::currentNM();
69	384	d_sygusFunSymbols.push_back(fn);
70	384	if (!vars.empty())
71		{
72	664	Node bvl = nm->mkNode(BOUND_VAR_LIST, vars);
73		// use an attribute to mark its bound variable list
74		SygusSynthFunVarListAttribute ssfvla;
75	332	fn.setAttribute(ssfvla, bvl);
76		}
77		// whether sygus type encodes syntax restrictions
78	1152	if (!sygusType.isNull() && sygusType.isDatatype()
79	553	&& sygusType.getDType().isSygus())
80		{
81	336	Node sym = nm->mkBoundVar("sfproxy", sygusType);
82		// use an attribute to mark its grammar
83		SygusSynthGrammarAttribute ssfga;
84	168	fn.setAttribute(ssfga, sym);
85		// we must expand definitions for sygus operators in the block
86	168	expandDefinitionsSygusDt(sygusType);
87		}
88
89		// sygus conjecture is now stale
90	384	setSygusConjectureStale();
91	384	}
92
93	652	void SygusSolver::assertSygusConstraint(Node n, bool isAssume)
94		{
95	1304	Trace("smt") << "SygusSolver::assertSygusConstrant: " << n
96	652	<< ", isAssume=" << isAssume << "\n";
97	652	if (isAssume)
98		{
99	4	d_sygusAssumps.push_back(n);
100		}
101		else
102		{
103	648	d_sygusConstraints.push_back(n);
104		}
105
106		// sygus conjecture is now stale
107	652	setSygusConjectureStale();
108	652	}
109
110	18	void SygusSolver::assertSygusInvConstraint(Node inv,
111		Node pre,
112		Node trans,
113		Node post)
114		{
115	36	Trace("smt") << "SygusSolver::assertSygusInvConstrant: " << inv << " " << pre
116	18	<< " " << trans << " " << post << "\n";
117		// build invariant constraint
118
119		// get variables (regular and their respective primed versions)
120	36	std::vector<Node> terms;
121	36	std::vector<Node> vars;
122	36	std::vector<Node> primed_vars;
123	18	terms.push_back(inv);
124	18	terms.push_back(pre);
125	18	terms.push_back(trans);
126	18	terms.push_back(post);
127		// variables are built based on the invariant type
128	18	NodeManager* nm = NodeManager::currentNM();
129	36	std::vector<TypeNode> argTypes = inv.getType().getArgTypes();
130	115	for (const TypeNode& tn : argTypes)
131		{
132	97	vars.push_back(nm->mkBoundVar(tn));
133	97	d_sygusVars.push_back(vars.back());
134	194	std::stringstream ss;
135	97	ss << vars.back() << "'";
136	97	primed_vars.push_back(nm->mkBoundVar(ss.str(), tn));
137	97	d_sygusVars.push_back(primed_vars.back());
138		}
139
140		// make relevant terms; 0 -> Inv, 1 -> Pre, 2 -> Trans, 3 -> Post
141	90	for (unsigned i = 0; i < 4; ++i)
142		{
143	144	Node op = terms[i];
144	144	Trace("smt-debug") << "Make inv-constraint term #" << i << " : " << op
145	72	<< " with type " << op.getType() << "...\n";
146	144	std::vector<Node> children;
147	72	children.push_back(op);
148		// transition relation applied over both variable lists
149	72	if (i == 2)
150		{
151	18	children.insert(children.end(), vars.begin(), vars.end());
152	18	children.insert(children.end(), primed_vars.begin(), primed_vars.end());
153		}
154		else
155		{
156	54	children.insert(children.end(), vars.begin(), vars.end());
157		}
158	72	terms[i] = nm->mkNode(APPLY_UF, children);
159		// make application of Inv on primed variables
160	72	if (i == 0)
161		{
162	18	children.clear();
163	18	children.push_back(op);
164	18	children.insert(children.end(), primed_vars.begin(), primed_vars.end());
165	18	terms.push_back(nm->mkNode(APPLY_UF, children));
166		}
167		}
168		// make constraints
169	36	std::vector<Node> conj;
170	18	conj.push_back(nm->mkNode(IMPLIES, terms[1], terms[0]));
171	36	Node term0_and_2 = nm->mkNode(AND, terms[0], terms[2]);
172	18	conj.push_back(nm->mkNode(IMPLIES, term0_and_2, terms[4]));
173	18	conj.push_back(nm->mkNode(IMPLIES, terms[0], terms[3]));
174	36	Node constraint = nm->mkNode(AND, conj);
175
176	18	d_sygusConstraints.push_back(constraint);
177
178		// sygus conjecture is now stale
179	18	setSygusConjectureStale();
180	18	}
181
182	209	Result SygusSolver::checkSynth(Assertions& as)
183		{
184	209	if (options::incrementalSolving())
185		{
186		// TODO (project #7)
187		throw ModalException(
188		"Cannot make check-synth commands when incremental solving is enabled");
189		}
190	209	Trace("smt") << "SygusSolver::checkSynth" << std::endl;
191	418	std::vector<Node> query;
192	209	if (d_sygusConjectureStale)
193		{
194	209	NodeManager* nm = NodeManager::currentNM();
195		// build synthesis conjecture from asserted constraints and declared
196		// variables/functions
197	209	Trace("smt") << "Sygus : Constructing sygus constraint...\n";
198	418	Node body = nm->mkAnd(d_sygusConstraints);
199		// note that if there are no constraints, then assumptions are irrelevant
200	209	if (!d_sygusConstraints.empty() && !d_sygusAssumps.empty())
201		{
202	4	Node bodyAssump = nm->mkAnd(d_sygusAssumps);
203	2	body = nm->mkNode(IMPLIES, bodyAssump, body);
204		}
205	209	body = body.notNode();
206	209	Trace("smt") << "...constructed sygus constraint " << body << std::endl;
207	209	if (!d_sygusVars.empty())
208		{
209	284	Node boundVars = nm->mkNode(BOUND_VAR_LIST, d_sygusVars);
210	142	body = nm->mkNode(EXISTS, boundVars, body);
211	142	Trace("smt") << "...constructed exists " << body << std::endl;
212		}
213	209	if (!d_sygusFunSymbols.empty())
214		{
215	209	body =
216	418	quantifiers::SygusUtils::mkSygusConjecture(d_sygusFunSymbols, body);
217		}
218	209	Trace("smt") << "...constructed forall " << body << std::endl;
219
220	209	Trace("smt") << "Check synthesis conjecture: " << body << std::endl;
221
222	209	d_sygusConjectureStale = false;
223
224		// TODO (project #7): if incremental, we should push a context and assert
225	209	query.push_back(body);
226		}
227
228	209	Result r = d_smtSolver.checkSatisfiability(as, query, false);
229
230		// Check that synthesis solutions satisfy the conjecture
231	400	if (options::checkSynthSol()
232	400	&& r.asSatisfiabilityResult().isSat() == Result::UNSAT)
233		{
234	174	checkSynthSolution(as);
235		}
236	400	return r;
237		}
238
239	85	bool SygusSolver::getSynthSolutions(std::map<Node, Node>& sol_map)
240		{
241	85	Trace("smt") << "SygusSolver::getSynthSolutions" << std::endl;
242	170	std::map<Node, std::map<Node, Node>> sol_mapn;
243		// fail if the theory engine does not have synthesis solutions
244	85	QuantifiersEngine* qe = d_smtSolver.getQuantifiersEngine();
245	85	if (qe == nullptr \|\| !qe->getSynthSolutions(sol_mapn))
246		{
247		return false;
248		}
249	166	for (std::pair<const Node, std::map<Node, Node>>& cs : sol_mapn)
250		{
251	196	for (std::pair<const Node, Node>& s : cs.second)
252		{
253	115	sol_map[s.first] = s.second;
254		}
255		}
256	85	return true;
257		}
258
259	174	void SygusSolver::checkSynthSolution(Assertions& as)
260		{
261	174	NodeManager* nm = NodeManager::currentNM();
262	174	SkolemManager* sm = nm->getSkolemManager();
263	175	Notice() << "SygusSolver::checkSynthSolution(): checking synthesis solution"
264	1	<< std::endl;
265	348	std::map<Node, std::map<Node, Node>> sol_map;
266		// Get solutions and build auxiliary vectors for substituting
267	174	QuantifiersEngine* qe = d_smtSolver.getQuantifiersEngine();
268	174	if (qe == nullptr \|\| !qe->getSynthSolutions(sol_map))
269		{
270		InternalError()
271		<< "SygusSolver::checkSynthSolution(): No solution to check!";
272		return;
273		}
274	174	if (sol_map.empty())
275		{
276		InternalError() << "SygusSolver::checkSynthSolution(): Got empty solution!";
277		return;
278		}
279	174	Trace("check-synth-sol") << "Got solution map:\n";
280		// the set of synthesis conjectures in our assertions
281	348	std::unordered_set<Node> conjs;
282		// For each of the above conjectures, the functions-to-synthesis and their
283		// solutions. This is used as a substitution below.
284	348	std::map<Node, std::vector<Node>> fvarMap;
285	348	std::map<Node, std::vector<Node>> fsolMap;
286	348	for (const std::pair<const Node, std::map<Node, Node>>& cmap : sol_map)
287		{
288	174	Trace("check-synth-sol") << "For conjecture " << cmap.first << ":\n";
289	174	conjs.insert(cmap.first);
290	174	std::vector<Node>& fvars = fvarMap[cmap.first];
291	174	std::vector<Node>& fsols = fsolMap[cmap.first];
292	498	for (const std::pair<const Node, Node>& pair : cmap.second)
293		{
294	648	Trace("check-synth-sol")
295	324	<< " " << pair.first << " --> " << pair.second << "\n";
296	324	fvars.push_back(pair.first);
297	324	fsols.push_back(pair.second);
298		}
299		}
300	174	Trace("check-synth-sol") << "Starting new SMT Engine\n";
301
302	174	Trace("check-synth-sol") << "Retrieving assertions\n";
303		// Build conjecture from original assertions
304	174	context::CDList<Node>* alist = as.getAssertionList();
305	174	if (alist == nullptr)
306		{
307		Trace("check-synth-sol") << "No assertions to check\n";
308		return;
309		}
310		// auxiliary assertions
311	348	std::vector<Node> auxAssertions;
312		// expand definitions cache
313	348	std::unordered_map<Node, Node> cache;
314	616	for (Node assertion : *alist)
315		{
316	446	Notice() << "SygusSolver::checkSynthSolution(): checking assertion "
317	4	<< assertion << std::endl;
318	442	Trace("check-synth-sol") << "Retrieving assertion " << assertion << "\n";
319		// Apply any define-funs from the problem.
320	884	Node n = d_pp.expandDefinitions(assertion, cache);
321	446	Notice() << "SygusSolver::checkSynthSolution(): -- expands to " << n
322	4	<< std::endl;
323	442	Trace("check-synth-sol") << "Expanded assertion " << n << "\n";
324	442	if (conjs.find(n) == conjs.end())
325		{
326	435	Trace("check-synth-sol") << "It is an auxiliary assertion\n";
327	435	auxAssertions.push_back(n);
328		}
329		else
330		{
331	7	Trace("check-synth-sol") << "It is a synthesis conjecture\n";
332		}
333		}
334		// check all conjectures
335	348	for (Node conj : conjs)
336		{
337		// Start new SMT engine to check solutions
338	348	std::unique_ptr<SmtEngine> solChecker;
339	174	initializeSubsolver(solChecker, d_env);
340	174	solChecker->getOptions().smt.checkSynthSol = false;
341	174	solChecker->getOptions().quantifiers.sygusRecFun = false;
342		// get the solution for this conjecture
343	174	std::vector<Node>& fvars = fvarMap[conj];
344	174	std::vector<Node>& fsols = fsolMap[conj];
345		// Apply solution map to conjecture body
346	348	Node conjBody;
347		/* Whether property is quantifier free */
348	174	if (conj[1].getKind() != EXISTS)
349		{
350	174	conjBody = conj[1].substitute(
351		fvars.begin(), fvars.end(), fsols.begin(), fsols.end());
352		}
353		else
354		{
355		conjBody = conj[1][1].substitute(
356		fvars.begin(), fvars.end(), fsols.begin(), fsols.end());
357
358		/* Skolemize property */
359		std::vector<Node> vars, skos;
360		for (unsigned j = 0, size = conj[1][0].getNumChildren(); j < size; ++j)
361		{
362		vars.push_back(conj[1][0][j]);
363		std::stringstream ss;
364		ss << "sk_" << j;
365		skos.push_back(sm->mkDummySkolem(ss.str(), conj[1][0][j].getType()));
366		Trace("check-synth-sol") << "\tSkolemizing " << conj[1][0][j] << " to "
367		<< skos.back() << "\n";
368		}
369		conjBody = conjBody.substitute(
370		vars.begin(), vars.end(), skos.begin(), skos.end());
371		}
372	175	Notice() << "SygusSolver::checkSynthSolution(): -- body substitutes to "
373	1	<< conjBody << std::endl;
374	348	Trace("check-synth-sol")
375	174	<< "Substituted body of assertion to " << conjBody << "\n";
376	174	solChecker->assertFormula(conjBody);
377		// Assert all auxiliary assertions. This may include recursive function
378		// definitions that were added as assertions to the sygus problem.
379	609	for (Node a : auxAssertions)
380		{
381		// We require rewriting here, e.g. so that define-fun from the original
382		// problem are rewritten to true. If this is not the case, then the
383		// assertions module of the subsolver will complain about assertions
384		// with free variables.
385	870	Node ar = theory::Rewriter::rewrite(a);
386	435	solChecker->assertFormula(ar);
387		}
388	348	Result r = solChecker->checkSat();
389	175	Notice() << "SygusSolver::checkSynthSolution(): result is " << r
390	1	<< std::endl;
391	174	Trace("check-synth-sol") << "Satsifiability check: " << r << "\n";
392	174	if (r.asSatisfiabilityResult().isUnknown())
393		{
394		InternalError() << "SygusSolver::checkSynthSolution(): could not check "
395		"solution, result "
396		"unknown.";
397		}
398	174	else if (r.asSatisfiabilityResult().isSat())
399		{
400		InternalError()
401		<< "SygusSolver::checkSynthSolution(): produced solution leads to "
402		"satisfiable negated conjecture.";
403		}
404		}
405		}
406
407	1054	void SygusSolver::setSygusConjectureStale()
408		{
409	1054	if (d_sygusConjectureStale)
410		{
411		// already stale
412	1054	return;
413		}
414		d_sygusConjectureStale = true;
415		// TODO (project #7): if incremental, we should pop a context
416		}
417
418	168	void SygusSolver::expandDefinitionsSygusDt(TypeNode tn) const
419		{
420	336	std::unordered_set<TypeNode> processed;
421	336	std::vector<TypeNode> toProcess;
422	168	toProcess.push_back(tn);
423	168	size_t index = 0;
424	1116	while (index < toProcess.size())
425		{
426	948	TypeNode tnp = toProcess[index];
427	474	index++;
428	474	Assert(tnp.isDatatype());
429	474	Assert(tnp.getDType().isSygus());
430		const std::vector<std::shared_ptr<DTypeConstructor>>& cons =
431	474	tnp.getDType().getConstructors();
432	2929	for (const std::shared_ptr<DTypeConstructor>& c : cons)
433		{
434	4910	Node op = c->getSygusOp();
435		// Only expand definitions if the operator is not constant, since
436		// calling expandDefinitions on them should be a no-op. This check
437		// ensures we don't try to expand e.g. bitvector extract operators,
438		// whose type is undefined, and thus should not be passed to
439		// expandDefinitions.
440	4910	Node eop = op.isConst() ? op : d_pp.expandDefinitions(op);
441	2455	datatypes::utils::setExpandedDefinitionForm(op, eop);
442		// also must consider the arguments
443	5108	for (unsigned j = 0, nargs = c->getNumArgs(); j < nargs; ++j)
444		{
445	5306	TypeNode tnc = c->getArgType(j);
446	7959	if (tnc.isDatatype() && tnc.getDType().isSygus()
447	5306	&& processed.find(tnc) == processed.end())
448		{
449	306	toProcess.push_back(tnc);
450	306	processed.insert(tnc);
451		}
452		}
453		}
454		}
455	168	}
456
457		} // namespace smt
458	29577	} // namespace cvc5