Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/smt/sygus_solver.cpp	Lines:	180	204	88.2 %
Date:	2021-08-01	Branches:	328	726	45.2 %


/******************************************************************************
 * 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/skolem_manager.h"
#include "options/base_options.h"
#include "options/option_exception.h"
#include "options/quantifiers_options.h"
#include "options/smt_options.h"
#include "printer/printer.h"
#include "smt/dump.h"
#include "smt/preprocessor.h"
#include "smt/smt_solver.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(SmtSolver& sms,
                         Preprocessor& pp,
                         context::UserContext* u,
                         OutputManager& outMgr)
    : d_smtSolver(sms),
      d_pp(pp),
      d_sygusConjectureStale(u, true),
      d_outMgr(outMgr)
{
}

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);
  }

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

void SygusSolver::assertSygusConstraint(Node constraint)
{
  Trace("smt") << "SygusSolver::assertSygusConstrant: " << constraint << "\n";
  d_sygusConstraints.push_back(constraint);

  // 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
    std::vector<Node> bodyv;
    Trace("smt") << "Sygus : Constructing sygus constraint...\n";
    size_t nconstraints = d_sygusConstraints.size();
    Node body = nconstraints == 0
                    ? nm->mkConst(true)
                    : (nconstraints == 1 ? d_sygusConstraints[0]
                                         : nm->mkNode(AND, d_sygusConstraints));
    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;
    if (Dump.isOn("raw-benchmark"))
    {
      d_outMgr.getPrinter().toStreamCmdCheckSynth(d_outMgr.getDumpOut());
    }

    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, 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);
    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
}

}  // 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/skolem_manager.h"
23		#include "options/base_options.h"
24		#include "options/option_exception.h"
25		#include "options/quantifiers_options.h"
26		#include "options/smt_options.h"
27		#include "printer/printer.h"
28		#include "smt/dump.h"
29		#include "smt/preprocessor.h"
30		#include "smt/smt_solver.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	10480	SygusSolver::SygusSolver(SmtSolver& sms,
45		Preprocessor& pp,
46		context::UserContext* u,
47	10480	OutputManager& outMgr)
48		: d_smtSolver(sms),
49		d_pp(pp),
50		d_sygusConjectureStale(u, true),
51	10480	d_outMgr(outMgr)
52		{
53	10480	}
54
55	10480	SygusSolver::~SygusSolver() {}
56
57	413	void SygusSolver::declareSygusVar(Node var)
58		{
59	826	Trace("smt") << "SygusSolver::declareSygusVar: " << var << " "
60	413	<< var.getType() << "\n";
61	413	d_sygusVars.push_back(var);
62		// don't need to set that the conjecture is stale
63	413	}
64
65	321	void SygusSolver::declareSynthFun(Node fn,
66		TypeNode sygusType,
67		bool isInv,
68		const std::vector<Node>& vars)
69		{
70	321	Trace("smt") << "SygusSolver::declareSynthFun: " << fn << "\n";
71	321	NodeManager* nm = NodeManager::currentNM();
72	321	d_sygusFunSymbols.push_back(fn);
73	321	if (!vars.empty())
74		{
75	538	Node bvl = nm->mkNode(BOUND_VAR_LIST, vars);
76		// use an attribute to mark its bound variable list
77		SygusSynthFunVarListAttribute ssfvla;
78	269	fn.setAttribute(ssfvla, bvl);
79		}
80		// whether sygus type encodes syntax restrictions
81	963	if (!sygusType.isNull() && sygusType.isDatatype()
82	491	&& sygusType.getDType().isSygus())
83		{
84	338	Node sym = nm->mkBoundVar("sfproxy", sygusType);
85		// use an attribute to mark its grammar
86		SygusSynthGrammarAttribute ssfga;
87	169	fn.setAttribute(ssfga, sym);
88		}
89
90		// sygus conjecture is now stale
91	321	setSygusConjectureStale();
92	321	}
93
94	616	void SygusSolver::assertSygusConstraint(Node constraint)
95		{
96	616	Trace("smt") << "SygusSolver::assertSygusConstrant: " << constraint << "\n";
97	616	d_sygusConstraints.push_back(constraint);
98
99		// sygus conjecture is now stale
100	616	setSygusConjectureStale();
101	616	}
102
103	18	void SygusSolver::assertSygusInvConstraint(Node inv,
104		Node pre,
105		Node trans,
106		Node post)
107		{
108	36	Trace("smt") << "SygusSolver::assertSygusInvConstrant: " << inv << " " << pre
109	18	<< " " << trans << " " << post << "\n";
110		// build invariant constraint
111
112		// get variables (regular and their respective primed versions)
113	36	std::vector<Node> terms;
114	36	std::vector<Node> vars;
115	36	std::vector<Node> primed_vars;
116	18	terms.push_back(inv);
117	18	terms.push_back(pre);
118	18	terms.push_back(trans);
119	18	terms.push_back(post);
120		// variables are built based on the invariant type
121	18	NodeManager* nm = NodeManager::currentNM();
122	36	std::vector<TypeNode> argTypes = inv.getType().getArgTypes();
123	115	for (const TypeNode& tn : argTypes)
124		{
125	97	vars.push_back(nm->mkBoundVar(tn));
126	97	d_sygusVars.push_back(vars.back());
127	194	std::stringstream ss;
128	97	ss << vars.back() << "'";
129	97	primed_vars.push_back(nm->mkBoundVar(ss.str(), tn));
130	97	d_sygusVars.push_back(primed_vars.back());
131		}
132
133		// make relevant terms; 0 -> Inv, 1 -> Pre, 2 -> Trans, 3 -> Post
134	90	for (unsigned i = 0; i < 4; ++i)
135		{
136	144	Node op = terms[i];
137	144	Trace("smt-debug") << "Make inv-constraint term #" << i << " : " << op
138	72	<< " with type " << op.getType() << "...\n";
139	144	std::vector<Node> children;
140	72	children.push_back(op);
141		// transition relation applied over both variable lists
142	72	if (i == 2)
143		{
144	18	children.insert(children.end(), vars.begin(), vars.end());
145	18	children.insert(children.end(), primed_vars.begin(), primed_vars.end());
146		}
147		else
148		{
149	54	children.insert(children.end(), vars.begin(), vars.end());
150		}
151	72	terms[i] = nm->mkNode(APPLY_UF, children);
152		// make application of Inv on primed variables
153	72	if (i == 0)
154		{
155	18	children.clear();
156	18	children.push_back(op);
157	18	children.insert(children.end(), primed_vars.begin(), primed_vars.end());
158	18	terms.push_back(nm->mkNode(APPLY_UF, children));
159		}
160		}
161		// make constraints
162	36	std::vector<Node> conj;
163	18	conj.push_back(nm->mkNode(IMPLIES, terms[1], terms[0]));
164	36	Node term0_and_2 = nm->mkNode(AND, terms[0], terms[2]);
165	18	conj.push_back(nm->mkNode(IMPLIES, term0_and_2, terms[4]));
166	18	conj.push_back(nm->mkNode(IMPLIES, terms[0], terms[3]));
167	36	Node constraint = nm->mkNode(AND, conj);
168
169	18	d_sygusConstraints.push_back(constraint);
170
171		// sygus conjecture is now stale
172	18	setSygusConjectureStale();
173	18	}
174
175	206	Result SygusSolver::checkSynth(Assertions& as)
176		{
177	206	if (options::incrementalSolving())
178		{
179		// TODO (project #7)
180		throw ModalException(
181		"Cannot make check-synth commands when incremental solving is enabled");
182		}
183	206	Trace("smt") << "SygusSolver::checkSynth" << std::endl;
184	412	std::vector<Node> query;
185	206	if (d_sygusConjectureStale)
186		{
187	206	NodeManager* nm = NodeManager::currentNM();
188		// build synthesis conjecture from asserted constraints and declared
189		// variables/functions
190	412	std::vector<Node> bodyv;
191	206	Trace("smt") << "Sygus : Constructing sygus constraint...\n";
192	206	size_t nconstraints = d_sygusConstraints.size();
193		Node body = nconstraints == 0
194		? nm->mkConst(true)
195	111	: (nconstraints == 1 ? d_sygusConstraints[0]
196	523	: nm->mkNode(AND, d_sygusConstraints));
197	206	body = body.notNode();
198	206	Trace("smt") << "...constructed sygus constraint " << body << std::endl;
199	206	if (!d_sygusVars.empty())
200		{
201	278	Node boundVars = nm->mkNode(BOUND_VAR_LIST, d_sygusVars);
202	139	body = nm->mkNode(EXISTS, boundVars, body);
203	139	Trace("smt") << "...constructed exists " << body << std::endl;
204		}
205	206	if (!d_sygusFunSymbols.empty())
206		{
207	206	body =
208	412	quantifiers::SygusUtils::mkSygusConjecture(d_sygusFunSymbols, body);
209		}
210	206	Trace("smt") << "...constructed forall " << body << std::endl;
211
212	206	Trace("smt") << "Check synthesis conjecture: " << body << std::endl;
213	206	if (Dump.isOn("raw-benchmark"))
214		{
215		d_outMgr.getPrinter().toStreamCmdCheckSynth(d_outMgr.getDumpOut());
216		}
217
218	206	d_sygusConjectureStale = false;
219
220		// TODO (project #7): if incremental, we should push a context and assert
221	206	query.push_back(body);
222		}
223
224	206	Result r = d_smtSolver.checkSatisfiability(as, query, false, false);
225
226		// Check that synthesis solutions satisfy the conjecture
227	394	if (options::checkSynthSol()
228	394	&& r.asSatisfiabilityResult().isSat() == Result::UNSAT)
229		{
230	171	checkSynthSolution(as);
231		}
232	394	return r;
233		}
234
235	86	bool SygusSolver::getSynthSolutions(std::map<Node, Node>& sol_map)
236		{
237	86	Trace("smt") << "SygusSolver::getSynthSolutions" << std::endl;
238	172	std::map<Node, std::map<Node, Node>> sol_mapn;
239		// fail if the theory engine does not have synthesis solutions
240	86	QuantifiersEngine* qe = d_smtSolver.getQuantifiersEngine();
241	86	if (qe == nullptr \|\| !qe->getSynthSolutions(sol_mapn))
242		{
243		return false;
244		}
245	168	for (std::pair<const Node, std::map<Node, Node>>& cs : sol_mapn)
246		{
247	200	for (std::pair<const Node, Node>& s : cs.second)
248		{
249	118	sol_map[s.first] = s.second;
250		}
251		}
252	86	return true;
253		}
254
255	171	void SygusSolver::checkSynthSolution(Assertions& as)
256		{
257	171	NodeManager* nm = NodeManager::currentNM();
258	171	SkolemManager* sm = nm->getSkolemManager();
259	172	Notice() << "SygusSolver::checkSynthSolution(): checking synthesis solution"
260	1	<< std::endl;
261	342	std::map<Node, std::map<Node, Node>> sol_map;
262		// Get solutions and build auxiliary vectors for substituting
263	171	QuantifiersEngine* qe = d_smtSolver.getQuantifiersEngine();
264	171	if (qe == nullptr \|\| !qe->getSynthSolutions(sol_map))
265		{
266		InternalError()
267		<< "SygusSolver::checkSynthSolution(): No solution to check!";
268		return;
269		}
270	171	if (sol_map.empty())
271		{
272		InternalError() << "SygusSolver::checkSynthSolution(): Got empty solution!";
273		return;
274		}
275	171	Trace("check-synth-sol") << "Got solution map:\n";
276		// the set of synthesis conjectures in our assertions
277	342	std::unordered_set<Node> conjs;
278		// For each of the above conjectures, the functions-to-synthesis and their
279		// solutions. This is used as a substitution below.
280	342	std::map<Node, std::vector<Node>> fvarMap;
281	342	std::map<Node, std::vector<Node>> fsolMap;
282	342	for (const std::pair<const Node, std::map<Node, Node>>& cmap : sol_map)
283		{
284	171	Trace("check-synth-sol") << "For conjecture " << cmap.first << ":\n";
285	171	conjs.insert(cmap.first);
286	171	std::vector<Node>& fvars = fvarMap[cmap.first];
287	171	std::vector<Node>& fsols = fsolMap[cmap.first];
288	432	for (const std::pair<const Node, Node>& pair : cmap.second)
289		{
290	522	Trace("check-synth-sol")
291	261	<< " " << pair.first << " --> " << pair.second << "\n";
292	261	fvars.push_back(pair.first);
293	261	fsols.push_back(pair.second);
294		}
295		}
296	171	Trace("check-synth-sol") << "Starting new SMT Engine\n";
297
298	171	Trace("check-synth-sol") << "Retrieving assertions\n";
299		// Build conjecture from original assertions
300	171	context::CDList<Node>* alist = as.getAssertionList();
301	171	if (alist == nullptr)
302		{
303		Trace("check-synth-sol") << "No assertions to check\n";
304		return;
305		}
306		// auxiliary assertions
307	342	std::vector<Node> auxAssertions;
308		// expand definitions cache
309	342	std::unordered_map<Node, Node> cache;
310	614	for (Node assertion : *alist)
311		{
312	447	Notice() << "SygusSolver::checkSynthSolution(): checking assertion "
313	4	<< assertion << std::endl;
314	443	Trace("check-synth-sol") << "Retrieving assertion " << assertion << "\n";
315		// Apply any define-funs from the problem.
316	886	Node n = d_pp.expandDefinitions(assertion, cache);
317	447	Notice() << "SygusSolver::checkSynthSolution(): -- expands to " << n
318	4	<< std::endl;
319	443	Trace("check-synth-sol") << "Expanded assertion " << n << "\n";
320	443	if (conjs.find(n) == conjs.end())
321		{
322	436	Trace("check-synth-sol") << "It is an auxiliary assertion\n";
323	436	auxAssertions.push_back(n);
324		}
325		else
326		{
327	7	Trace("check-synth-sol") << "It is a synthesis conjecture\n";
328		}
329		}
330		// check all conjectures
331	342	for (Node conj : conjs)
332		{
333		// Start new SMT engine to check solutions
334	342	std::unique_ptr<SmtEngine> solChecker;
335	171	initializeSubsolver(solChecker);
336	171	solChecker->getOptions().smt.checkSynthSol = false;
337	171	solChecker->getOptions().quantifiers.sygusRecFun = false;
338		// get the solution for this conjecture
339	171	std::vector<Node>& fvars = fvarMap[conj];
340	171	std::vector<Node>& fsols = fsolMap[conj];
341		// Apply solution map to conjecture body
342	342	Node conjBody;
343		/* Whether property is quantifier free */
344	171	if (conj[1].getKind() != EXISTS)
345		{
346	171	conjBody = conj[1].substitute(
347		fvars.begin(), fvars.end(), fsols.begin(), fsols.end());
348		}
349		else
350		{
351		conjBody = conj[1][1].substitute(
352		fvars.begin(), fvars.end(), fsols.begin(), fsols.end());
353
354		/* Skolemize property */
355		std::vector<Node> vars, skos;
356		for (unsigned j = 0, size = conj[1][0].getNumChildren(); j < size; ++j)
357		{
358		vars.push_back(conj[1][0][j]);
359		std::stringstream ss;
360		ss << "sk_" << j;
361		skos.push_back(sm->mkDummySkolem(ss.str(), conj[1][0][j].getType()));
362		Trace("check-synth-sol") << "\tSkolemizing " << conj[1][0][j] << " to "
363		<< skos.back() << "\n";
364		}
365		conjBody = conjBody.substitute(
366		vars.begin(), vars.end(), skos.begin(), skos.end());
367		}
368	172	Notice() << "SygusSolver::checkSynthSolution(): -- body substitutes to "
369	1	<< conjBody << std::endl;
370	342	Trace("check-synth-sol")
371	171	<< "Substituted body of assertion to " << conjBody << "\n";
372	171	solChecker->assertFormula(conjBody);
373		// Assert all auxiliary assertions. This may include recursive function
374		// definitions that were added as assertions to the sygus problem.
375	607	for (Node a : auxAssertions)
376		{
377		// We require rewriting here, e.g. so that define-fun from the original
378		// problem are rewritten to true. If this is not the case, then the
379		// assertions module of the subsolver will complain about assertions
380		// with free variables.
381	872	Node ar = theory::Rewriter::rewrite(a);
382	436	solChecker->assertFormula(ar);
383		}
384	342	Result r = solChecker->checkSat();
385	172	Notice() << "SygusSolver::checkSynthSolution(): result is " << r
386	1	<< std::endl;
387	171	Trace("check-synth-sol") << "Satsifiability check: " << r << "\n";
388	171	if (r.asSatisfiabilityResult().isUnknown())
389		{
390		InternalError() << "SygusSolver::checkSynthSolution(): could not check "
391		"solution, result "
392		"unknown.";
393		}
394	171	else if (r.asSatisfiabilityResult().isSat())
395		{
396		InternalError()
397		<< "SygusSolver::checkSynthSolution(): produced solution leads to "
398		"satisfiable negated conjecture.";
399		}
400		}
401		}
402
403	955	void SygusSolver::setSygusConjectureStale()
404		{
405	955	if (d_sygusConjectureStale)
406		{
407		// already stale
408	955	return;
409		}
410		d_sygusConjectureStale = true;
411		// TODO (project #7): if incremental, we should pop a context
412		}
413
414		} // namespace smt
415	29280	} // namespace cvc5