Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/quantifiers/ematching/inst_match_generator_multi.cpp	Lines:	132	140	94.3 %
Date:	2021-09-09	Branches:	207	392	52.8 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Morgan Deters, Tim King
 *
 * 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.
 * ****************************************************************************
 *
 * Multi inst match generator class.
 */

#include "theory/quantifiers/ematching/inst_match_generator_multi.h"

#include "theory/quantifiers/quantifiers_state.h"
#include "theory/quantifiers/term_util.h"
#include "theory/uf/equality_engine_iterator.h"

using namespace cvc5::kind;

namespace cvc5 {
namespace theory {
namespace quantifiers {
namespace inst {

InstMatchGeneratorMulti::InstMatchGeneratorMulti(Trigger* tparent,
                                                 Node q,
                                                 std::vector<Node>& pats)
    : IMGenerator(tparent), d_quant(q)
{
  Trace("multi-trigger-cache")
      << "Making smart multi-trigger for " << q << std::endl;
  std::map<Node, std::vector<Node> > var_contains;
  for (const Node& pat : pats)
  {
    TermUtil::computeInstConstContainsForQuant(q, pat, var_contains[pat]);
  }
  // convert to indicies
  for (std::pair<const Node, std::vector<Node> >& vc : var_contains)
  {
    Trace("multi-trigger-cache") << "Pattern " << vc.first << " contains: ";
    for (const Node& vcn : vc.second)
    {
      Trace("multi-trigger-cache") << vcn << " ";
      uint64_t index = vcn.getAttribute(InstVarNumAttribute());
      d_var_contains[vc.first].push_back(index);
      d_var_to_node[index].push_back(vc.first);
    }
    Trace("multi-trigger-cache") << std::endl;
  }
  size_t patsSize = pats.size();
  for (size_t i = 0; i < patsSize; i++)
  {
    Node n = pats[i];
    // make the match generator
    InstMatchGenerator* img =
        InstMatchGenerator::mkInstMatchGenerator(tparent, q, n);
    img->setActiveAdd(false);
    d_children.push_back(img);
    // compute unique/shared variables
    std::vector<uint64_t> unique_vars;
    std::map<uint64_t, bool> shared_vars;
    unsigned numSharedVars = 0;
    std::vector<uint64_t>& vctn = d_var_contains[n];
    for (size_t j = 0, vctnSize = vctn.size(); j < vctnSize; j++)
    {
      if (d_var_to_node[vctn[j]].size() == 1)
      {
        Trace("multi-trigger-cache")
            << "Var " << vctn[j] << " is unique to " << pats[i] << std::endl;
        unique_vars.push_back(vctn[j]);
      }
      else
      {
        shared_vars[vctn[j]] = true;
        numSharedVars++;
      }
    }
    // we use the latest shared variables, then unique variables
    std::vector<uint64_t> vars;
    size_t index = i == 0 ? pats.size() - 1 : (i - 1);
    while (numSharedVars > 0 && index != i)
    {
      for (std::pair<const uint64_t, bool>& sv : shared_vars)
      {
        if (sv.second)
        {
          std::vector<uint64_t>& vctni = d_var_contains[pats[index]];
          if (std::find(vctni.begin(), vctni.end(), sv.first) != vctni.end())
          {
            vars.push_back(sv.first);
            shared_vars[sv.first] = false;
            numSharedVars--;
          }
        }
      }
      index = index == 0 ? patsSize - 1 : (index - 1);
    }
    vars.insert(vars.end(), unique_vars.begin(), unique_vars.end());
    if (Trace.isOn("multi-trigger-cache"))
    {
      Trace("multi-trigger-cache") << "   Index[" << i << "]: ";
      for (uint64_t v : vars)
      {
        Trace("multi-trigger-cache") << v << " ";
      }
      Trace("multi-trigger-cache") << std::endl;
    }
    // make ordered inst match trie
    d_imtio[i] = new InstMatchTrie::ImtIndexOrder;
    d_imtio[i]->d_order.insert(
        d_imtio[i]->d_order.begin(), vars.begin(), vars.end());
    d_children_trie.push_back(InstMatchTrieOrdered(d_imtio[i]));
  }
}

InstMatchGeneratorMulti::~InstMatchGeneratorMulti()
{
  for (size_t i = 0, csize = d_children.size(); i < csize; i++)
  {
    delete d_children[i];
  }
  for (std::pair<const size_t, InstMatchTrie::ImtIndexOrder*>& i : d_imtio)
  {
    delete i.second;
  }
}

/** reset instantiation round (call this whenever equivalence classes have
 * changed) */
void InstMatchGeneratorMulti::resetInstantiationRound()
{
  for (InstMatchGenerator* c : d_children)
  {
    c->resetInstantiationRound();
  }
}

/** reset, eqc is the equivalence class to search in (any if eqc=null) */
bool InstMatchGeneratorMulti::reset(Node eqc)
{
  for (InstMatchGenerator* c : d_children)
  {
    if (!c->reset(eqc))
    {
      // do not return false here
    }
  }
  return true;
}

uint64_t InstMatchGeneratorMulti::addInstantiations(Node q)
{
  uint64_t addedLemmas = 0;
  Trace("multi-trigger-cache") << "Process smart multi trigger" << std::endl;
  for (size_t i = 0, csize = d_children.size(); i < csize; i++)
  {
    Trace("multi-trigger-cache") << "Calculate matches " << i << std::endl;
    std::vector<InstMatch> newMatches;
    InstMatch m(q);
    while (d_children[i]->getNextMatch(q, m) > 0)
    {
      // m.makeRepresentative( qe );
      newMatches.push_back(InstMatch(&m));
      m.clear();
    }
    Trace("multi-trigger-cache") << "Made " << newMatches.size()
                                 << " new matches for index " << i << std::endl;
    for (size_t j = 0, nmatches = newMatches.size(); j < nmatches; j++)
    {
      Trace("multi-trigger-cache2")
          << "...processing " << j << " / " << newMatches.size()
          << ", #lemmas = " << addedLemmas << std::endl;
      processNewMatch(newMatches[j], i, addedLemmas);
      if (d_qstate.isInConflict())
      {
        return addedLemmas;
      }
    }
  }
  return addedLemmas;
}

void InstMatchGeneratorMulti::processNewMatch(InstMatch& m,
                                              size_t fromChildIndex,
                                              uint64_t& addedLemmas)
{
  // see if these produce new matches
  d_children_trie[fromChildIndex].addInstMatch(d_qstate, d_quant, m.d_vals);
  // possibly only do the following if we know that new matches will be
  // produced? the issue is that instantiations are filtered in quantifiers
  // engine, and so there is no guarentee that
  // we can safely skip the following lines, even when we have already produced
  // this match.
  Trace("multi-trigger-cache-debug")
      << "Child " << fromChildIndex << " produced match " << m << std::endl;
  // process new instantiations
  size_t childIndex = (fromChildIndex + 1) % d_children.size();
  processNewInstantiations(m,
                           addedLemmas,
                           d_children_trie[childIndex].getTrie(),
                           0,
                           childIndex,
                           fromChildIndex,
                           true);
}

void InstMatchGeneratorMulti::processNewInstantiations(InstMatch& m,
                                                       uint64_t& addedLemmas,
                                                       InstMatchTrie* tr,
                                                       size_t trieIndex,
                                                       size_t childIndex,
                                                       size_t endChildIndex,
                                                       bool modEq)
{
  Assert(!d_qstate.isInConflict());
  if (childIndex == endChildIndex)
  {
    // m is an instantiation
    if (sendInstantiation(m, InferenceId::QUANTIFIERS_INST_E_MATCHING_MT))
    {
      addedLemmas++;
      Trace("multi-trigger-cache-debug")
          << "-> Produced instantiation " << m << std::endl;
    }
    return;
  }
  InstMatchTrie::ImtIndexOrder* iio = d_children_trie[childIndex].getOrdering();
  if (trieIndex < iio->d_order.size())
  {
    size_t curr_index = iio->d_order[trieIndex];
    Node n = m.get(curr_index);
    if (n.isNull())
    {
      // add to InstMatch
      for (std::pair<const Node, InstMatchTrie>& d : tr->d_data)
      {
        InstMatch mn(&m);
        mn.setValue(curr_index, d.first);
        processNewInstantiations(mn,
                                 addedLemmas,
                                 &(d.second),
                                 trieIndex + 1,
                                 childIndex,
                                 endChildIndex,
                                 modEq);
        if (d_qstate.isInConflict())
        {
          break;
        }
      }
    }
    // shared and set variable, try to merge
    std::map<Node, InstMatchTrie>::iterator it = tr->d_data.find(n);
    if (it != tr->d_data.end())
    {
      processNewInstantiations(m,
                               addedLemmas,
                               &(it->second),
                               trieIndex + 1,
                               childIndex,
                               endChildIndex,
                               modEq);
    }
    if (!modEq)
    {
      return;
    }
    QuantifiersState& qs = d_qstate;
    // check modulo equality for other possible instantiations
    if (!qs.hasTerm(n))
    {
      return;
    }
    eq::EqClassIterator eqc(qs.getRepresentative(n), qs.getEqualityEngine());
    while (!eqc.isFinished())
    {
      Node en = (*eqc);
      if (en != n)
      {
        std::map<Node, InstMatchTrie>::iterator itc = tr->d_data.find(en);
        if (itc != tr->d_data.end())
        {
          processNewInstantiations(m,
                                   addedLemmas,
                                   &(itc->second),
                                   trieIndex + 1,
                                   childIndex,
                                   endChildIndex,
                                   modEq);
          if (d_qstate.isInConflict())
          {
            break;
          }
        }
      }
      ++eqc;
    }
  }
  else
  {
    size_t newChildIndex = (childIndex + 1) % d_children.size();
    processNewInstantiations(m,
                             addedLemmas,
                             d_children_trie[newChildIndex].getTrie(),
                             0,
                             newChildIndex,
                             endChildIndex,
                             modEq);
  }
}

}  // namespace inst
}  // namespace quantifiers
}  // namespace theory
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andrew Reynolds, Morgan Deters, Tim King
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		* Multi inst match generator class.
14		*/
15
16		#include "theory/quantifiers/ematching/inst_match_generator_multi.h"
17
18		#include "theory/quantifiers/quantifiers_state.h"
19		#include "theory/quantifiers/term_util.h"
20		#include "theory/uf/equality_engine_iterator.h"
21
22		using namespace cvc5::kind;
23
24		namespace cvc5 {
25		namespace theory {
26		namespace quantifiers {
27		namespace inst {
28
29	10	InstMatchGeneratorMulti::InstMatchGeneratorMulti(Trigger* tparent,
30		Node q,
31	10	std::vector<Node>& pats)
32	10	: IMGenerator(tparent), d_quant(q)
33		{
34	20	Trace("multi-trigger-cache")
35	10	<< "Making smart multi-trigger for " << q << std::endl;
36	20	std::map<Node, std::vector<Node> > var_contains;
37	33	for (const Node& pat : pats)
38		{
39	23	TermUtil::computeInstConstContainsForQuant(q, pat, var_contains[pat]);
40		}
41		// convert to indicies
42	33	for (std::pair<const Node, std::vector<Node> >& vc : var_contains)
43		{
44	23	Trace("multi-trigger-cache") << "Pattern " << vc.first << " contains: ";
45	111	for (const Node& vcn : vc.second)
46		{
47	88	Trace("multi-trigger-cache") << vcn << " ";
48	88	uint64_t index = vcn.getAttribute(InstVarNumAttribute());
49	88	d_var_contains[vc.first].push_back(index);
50	88	d_var_to_node[index].push_back(vc.first);
51		}
52	23	Trace("multi-trigger-cache") << std::endl;
53		}
54	10	size_t patsSize = pats.size();
55	33	for (size_t i = 0; i < patsSize; i++)
56		{
57	46	Node n = pats[i];
58		// make the match generator
59		InstMatchGenerator* img =
60	23	InstMatchGenerator::mkInstMatchGenerator(tparent, q, n);
61	23	img->setActiveAdd(false);
62	23	d_children.push_back(img);
63		// compute unique/shared variables
64	46	std::vector<uint64_t> unique_vars;
65	46	std::map<uint64_t, bool> shared_vars;
66	23	unsigned numSharedVars = 0;
67	23	std::vector<uint64_t>& vctn = d_var_contains[n];
68	111	for (size_t j = 0, vctnSize = vctn.size(); j < vctnSize; j++)
69		{
70	88	if (d_var_to_node[vctn[j]].size() == 1)
71		{
72	118	Trace("multi-trigger-cache")
73	59	<< "Var " << vctn[j] << " is unique to " << pats[i] << std::endl;
74	59	unique_vars.push_back(vctn[j]);
75		}
76		else
77		{
78	29	shared_vars[vctn[j]] = true;
79	29	numSharedVars++;
80		}
81		}
82		// we use the latest shared variables, then unique variables
83	46	std::vector<uint64_t> vars;
84	23	size_t index = i == 0 ? pats.size() - 1 : (i - 1);
85	75	while (numSharedVars > 0 && index != i)
86		{
87	61	for (std::pair<const uint64_t, bool>& sv : shared_vars)
88		{
89	35	if (sv.second)
90		{
91	32	std::vector<uint64_t>& vctni = d_var_contains[pats[index]];
92	32	if (std::find(vctni.begin(), vctni.end(), sv.first) != vctni.end())
93		{
94	29	vars.push_back(sv.first);
95	29	shared_vars[sv.first] = false;
96	29	numSharedVars--;
97		}
98		}
99		}
100	26	index = index == 0 ? patsSize - 1 : (index - 1);
101		}
102	23	vars.insert(vars.end(), unique_vars.begin(), unique_vars.end());
103	23	if (Trace.isOn("multi-trigger-cache"))
104		{
105		Trace("multi-trigger-cache") << " Index[" << i << "]: ";
106		for (uint64_t v : vars)
107		{
108		Trace("multi-trigger-cache") << v << " ";
109		}
110		Trace("multi-trigger-cache") << std::endl;
111		}
112		// make ordered inst match trie
113	23	d_imtio[i] = new InstMatchTrie::ImtIndexOrder;
114	46	d_imtio[i]->d_order.insert(
115	46	d_imtio[i]->d_order.begin(), vars.begin(), vars.end());
116	23	d_children_trie.push_back(InstMatchTrieOrdered(d_imtio[i]));
117		}
118	10	}
119
120	30	InstMatchGeneratorMulti::~InstMatchGeneratorMulti()
121		{
122	33	for (size_t i = 0, csize = d_children.size(); i < csize; i++)
123		{
124	23	delete d_children[i];
125		}
126	33	for (std::pair<const size_t, InstMatchTrie::ImtIndexOrder*>& i : d_imtio)
127		{
128	23	delete i.second;
129		}
130	20	}
131
132		/** reset instantiation round (call this whenever equivalence classes have
133		* changed) */
134	54	void InstMatchGeneratorMulti::resetInstantiationRound()
135		{
136	171	for (InstMatchGenerator* c : d_children)
137		{
138	117	c->resetInstantiationRound();
139		}
140	54	}
141
142		/** reset, eqc is the equivalence class to search in (any if eqc=null) */
143	54	bool InstMatchGeneratorMulti::reset(Node eqc)
144		{
145	171	for (InstMatchGenerator* c : d_children)
146		{
147	117	if (!c->reset(eqc))
148		{
149		// do not return false here
150		}
151		}
152	54	return true;
153		}
154
155	32	uint64_t InstMatchGeneratorMulti::addInstantiations(Node q)
156		{
157	32	uint64_t addedLemmas = 0;
158	32	Trace("multi-trigger-cache") << "Process smart multi trigger" << std::endl;
159	102	for (size_t i = 0, csize = d_children.size(); i < csize; i++)
160		{
161	70	Trace("multi-trigger-cache") << "Calculate matches " << i << std::endl;
162	140	std::vector<InstMatch> newMatches;
163	140	InstMatch m(q);
164	686	while (d_children[i]->getNextMatch(q, m) > 0)
165		{
166		// m.makeRepresentative( qe );
167	308	newMatches.push_back(InstMatch(&m));
168	308	m.clear();
169		}
170	140	Trace("multi-trigger-cache") << "Made " << newMatches.size()
171	70	<< " new matches for index " << i << std::endl;
172	378	for (size_t j = 0, nmatches = newMatches.size(); j < nmatches; j++)
173		{
174	616	Trace("multi-trigger-cache2")
175	616	<< "...processing " << j << " / " << newMatches.size()
176	308	<< ", #lemmas = " << addedLemmas << std::endl;
177	308	processNewMatch(newMatches[j], i, addedLemmas);
178	308	if (d_qstate.isInConflict())
179		{
180		return addedLemmas;
181		}
182		}
183		}
184	32	return addedLemmas;
185		}
186
187	308	void InstMatchGeneratorMulti::processNewMatch(InstMatch& m,
188		size_t fromChildIndex,
189		uint64_t& addedLemmas)
190		{
191		// see if these produce new matches
192	308	d_children_trie[fromChildIndex].addInstMatch(d_qstate, d_quant, m.d_vals);
193		// possibly only do the following if we know that new matches will be
194		// produced? the issue is that instantiations are filtered in quantifiers
195		// engine, and so there is no guarentee that
196		// we can safely skip the following lines, even when we have already produced
197		// this match.
198	616	Trace("multi-trigger-cache-debug")
199	308	<< "Child " << fromChildIndex << " produced match " << m << std::endl;
200		// process new instantiations
201	308	size_t childIndex = (fromChildIndex + 1) % d_children.size();
202	616	processNewInstantiations(m,
203		addedLemmas,
204	308	d_children_trie[childIndex].getTrie(),
205		0,
206		childIndex,
207		fromChildIndex,
208		true);
209	308	}
210
211	3236	void InstMatchGeneratorMulti::processNewInstantiations(InstMatch& m,
212		uint64_t& addedLemmas,
213		InstMatchTrie* tr,
214		size_t trieIndex,
215		size_t childIndex,
216		size_t endChildIndex,
217		bool modEq)
218		{
219	3236	Assert(!d_qstate.isInConflict());
220	3236	if (childIndex == endChildIndex)
221		{
222		// m is an instantiation
223	953	if (sendInstantiation(m, InferenceId::QUANTIFIERS_INST_E_MATCHING_MT))
224		{
225	404	addedLemmas++;
226	808	Trace("multi-trigger-cache-debug")
227	404	<< "-> Produced instantiation " << m << std::endl;
228		}
229	953	return;
230		}
231	2283	InstMatchTrie::ImtIndexOrder* iio = d_children_trie[childIndex].getOrdering();
232	2283	if (trieIndex < iio->d_order.size())
233		{
234	1165	size_t curr_index = iio->d_order[trieIndex];
235	1803	Node n = m.get(curr_index);
236	1165	if (n.isNull())
237		{
238		// add to InstMatch
239	1916	for (std::pair<const Node, InstMatchTrie>& d : tr->d_data)
240		{
241	2778	InstMatch mn(&m);
242	1389	mn.setValue(curr_index, d.first);
243	1389	processNewInstantiations(mn,
244		addedLemmas,
245		&(d.second),
246		trieIndex + 1,
247		childIndex,
248		endChildIndex,
249		modEq);
250	1389	if (d_qstate.isInConflict())
251		{
252		break;
253		}
254		}
255		}
256		// shared and set variable, try to merge
257	1165	std::map<Node, InstMatchTrie>::iterator it = tr->d_data.find(n);
258	1165	if (it != tr->d_data.end())
259		{
260	722	processNewInstantiations(m,
261		addedLemmas,
262	361	&(it->second),
263		trieIndex + 1,
264		childIndex,
265		endChildIndex,
266		modEq);
267		}
268	1165	if (!modEq)
269		{
270		return;
271		}
272	1165	QuantifiersState& qs = d_qstate;
273		// check modulo equality for other possible instantiations
274	1165	if (!qs.hasTerm(n))
275		{
276	527	return;
277		}
278	638	eq::EqClassIterator eqc(qs.getRepresentative(n), qs.getEqualityEngine());
279	2834	while (!eqc.isFinished())
280		{
281	2196	Node en = (*eqc);
282	1098	if (en != n)
283		{
284	460	std::map<Node, InstMatchTrie>::iterator itc = tr->d_data.find(en);
285	460	if (itc != tr->d_data.end())
286		{
287	120	processNewInstantiations(m,
288		addedLemmas,
289	60	&(itc->second),
290		trieIndex + 1,
291		childIndex,
292		endChildIndex,
293		modEq);
294	60	if (d_qstate.isInConflict())
295		{
296		break;
297		}
298		}
299		}
300	1098	++eqc;
301		}
302		}
303		else
304		{
305	1118	size_t newChildIndex = (childIndex + 1) % d_children.size();
306	2236	processNewInstantiations(m,
307		addedLemmas,
308	1118	d_children_trie[newChildIndex].getTrie(),
309		0,
310		newChildIndex,
311		endChildIndex,
312		modEq);
313		}
314		}
315
316		} // namespace inst
317		} // namespace quantifiers
318		} // namespace theory
319	29505	} // namespace cvc5