Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/smt/sygus_solver.cpp	Lines:	202	226	89.4 %
Date:	2021-09-10	Branches:	369	812	45.4 %


/******************************************************************************
 * 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 "printer/printer.h"
#include "smt/dump.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 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_env.getPrinter().toStreamCmdCheckSynth(d_env.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);

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