Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/strings/normal_form.cpp	Lines:	84	84	100.0 %
Date:	2021-09-10	Branches:	149	336	44.3 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Andres Noetzli, Gereon Kremer
 *
 * This file is part of the cvc5 project.
 *
 * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
 * in the top-level source directory and their institutional affiliations.
 * All rights reserved.  See the file COPYING in the top-level source
 * directory for licensing information.
 * ****************************************************************************
 *
 * Implementation of normal form data structure for the theory of strings.
 */

#include "theory/strings/normal_form.h"

#include "options/strings_options.h"
#include "theory/rewriter.h"
#include "theory/strings/theory_strings_utils.h"
#include "theory/strings/word.h"

using namespace std;
using namespace cvc5::kind;

namespace cvc5 {
namespace theory {
namespace strings {

void NormalForm::init(Node base)
{
  Assert(base.getType().isStringLike());
  Assert(base.getKind() != STRING_CONCAT);
  d_base = base;
  d_nf.clear();
  d_isRev = false;
  d_exp.clear();
  d_expDep.clear();

  // add to normal form
  if (!base.isConst() || Word::getLength(base) > 0)
  {
    d_nf.push_back(base);
  }
}

void NormalForm::reverse()
{
  std::reverse(d_nf.begin(), d_nf.end());
  d_isRev = !d_isRev;
}

void NormalForm::splitConstant(unsigned index, Node c1, Node c2)
{
  Assert(Rewriter::rewrite(NodeManager::currentNM()->mkNode(
             STRING_CONCAT, d_isRev ? c2 : c1, d_isRev ? c1 : c2))
         == d_nf[index]);
  d_nf.insert(d_nf.begin() + index + 1, c2);
  d_nf[index] = c1;
  // update the dependency indices
  // notice this is not critical for soundness: not doing the below incrementing
  // will only lead to overapproximating when antecedants are required in
  // explanations
  for (const std::pair<const Node, std::map<bool, unsigned> >& pe : d_expDep)
  {
    for (const auto& pep : pe.second)
    {
      // See if this can be incremented: it can if this literal is not relevant
      // to the current index, and hence it is not relevant for both c1 and c2.
      Assert(pep.second >= 0 && pep.second <= d_nf.size());
      bool increment = (pep.first == d_isRev)
                           ? pep.second > index
                           : (d_nf.size() - 1 - pep.second) < index;
      if (increment)
      {
        d_expDep[pe.first][pep.first] = pep.second + 1;
      }
    }
  }
}

void NormalForm::addToExplanation(Node exp,
                                  unsigned new_val,
                                  unsigned new_rev_val)
{
  Assert(!exp.isConst());
  if (std::find(d_exp.begin(), d_exp.end(), exp) == d_exp.end())
  {
    d_exp.push_back(exp);
  }
  for (unsigned k = 0; k < 2; k++)
  {
    unsigned val = k == 0 ? new_val : new_rev_val;
    std::map<bool, unsigned>::iterator itned = d_expDep[exp].find(k == 1);
    if (itned == d_expDep[exp].end())
    {
      Trace("strings-process-debug")
          << "Deps : set dependency on " << exp << " to " << val
          << " isRev=" << (k == 0) << std::endl;
      d_expDep[exp][k == 1] = val;
    }
    else
    {
      Trace("strings-process-debug")
          << "Deps : Multiple dependencies on " << exp << " : " << itned->second
          << " " << val << " isRev=" << (k == 0) << std::endl;
      // if we already have a dependency (in the case of non-linear string
      // equalities), it is min/max
      bool cmp = val > itned->second;
      if (cmp == (k == 1))
      {
        d_expDep[exp][k == 1] = val;
      }
    }
  }
}

void NormalForm::getExplanation(int index, std::vector<Node>& curr_exp)
{
  if (index == -1 || !options::stringMinPrefixExplain())
  {
    curr_exp.insert(curr_exp.end(), d_exp.begin(), d_exp.end());
    return;
  }
  for (const Node& exp : d_exp)
  {
    int dep = static_cast<int>(d_expDep[exp][d_isRev]);
    if (dep <= index)
    {
      curr_exp.push_back(exp);
      Trace("strings-explain-prefix-debug") << "  include : ";
    }
    else
    {
      Trace("strings-explain-prefix-debug") << "  exclude : ";
    }
    Trace("strings-explain-prefix-debug") << exp << std::endl;
  }
}

Node NormalForm::collectConstantStringAt(size_t& index)
{
  std::vector<Node> c;
  while (d_nf.size() > index && d_nf[index].isConst())
  {
    c.push_back(d_nf[index]);
    index++;
  }
  if (!c.empty())
  {
    if (d_isRev)
    {
      std::reverse(c.begin(), c.end());
    }
    Node cc = Rewriter::rewrite(utils::mkConcat(c, c[0].getType()));
    Assert(cc.isConst());
    return cc;
  }
  else
  {
    return Node::null();
  }
}

void NormalForm::getExplanationForPrefixEq(NormalForm& nfi,
                                           NormalForm& nfj,
                                           int index_i,
                                           int index_j,
                                           std::vector<Node>& curr_exp)
{
  Assert(nfi.d_isRev == nfj.d_isRev);
  Trace("strings-explain-prefix")
      << "Get explanation for prefix " << index_i << ", " << index_j
      << ", reverse = " << nfi.d_isRev << std::endl;
  // get explanations
  nfi.getExplanation(index_i, curr_exp);
  nfj.getExplanation(index_j, curr_exp);
  Trace("strings-explain-prefix")
      << "Included " << curr_exp.size() << " / "
      << (nfi.d_exp.size() + nfj.d_exp.size()) << std::endl;
  // add explanation for why they are equal
  Node eq = nfi.d_base.eqNode(nfj.d_base);
  curr_exp.push_back(eq);
}

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


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andrew Reynolds, Andres Noetzli, Gereon Kremer
4		*
5		* This file is part of the cvc5 project.
6		*
7		* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
8		* in the top-level source directory and their institutional affiliations.
9		* All rights reserved. See the file COPYING in the top-level source
10		* directory for licensing information.
11		* ****************************************************************************
12		*
13		* Implementation of normal form data structure for the theory of strings.
14		*/
15
16		#include "theory/strings/normal_form.h"
17
18		#include "options/strings_options.h"
19		#include "theory/rewriter.h"
20		#include "theory/strings/theory_strings_utils.h"
21		#include "theory/strings/word.h"
22
23		using namespace std;
24		using namespace cvc5::kind;
25
26		namespace cvc5 {
27		namespace theory {
28		namespace strings {
29
30	142584	void NormalForm::init(Node base)
31		{
32	142584	Assert(base.getType().isStringLike());
33	142584	Assert(base.getKind() != STRING_CONCAT);
34	142584	d_base = base;
35	142584	d_nf.clear();
36	142584	d_isRev = false;
37	142584	d_exp.clear();
38	142584	d_expDep.clear();
39
40		// add to normal form
41	142584	if (!base.isConst() \|\| Word::getLength(base) > 0)
42		{
43	127871	d_nf.push_back(base);
44		}
45	142584	}
46
47	53516	void NormalForm::reverse()
48		{
49	53516	std::reverse(d_nf.begin(), d_nf.end());
50	53516	d_isRev = !d_isRev;
51	53516	}
52
53	5225	void NormalForm::splitConstant(unsigned index, Node c1, Node c2)
54		{
55	5225	Assert(Rewriter::rewrite(NodeManager::currentNM()->mkNode(
56		STRING_CONCAT, d_isRev ? c2 : c1, d_isRev ? c1 : c2))
57		== d_nf[index]);
58	5225	d_nf.insert(d_nf.begin() + index + 1, c2);
59	5225	d_nf[index] = c1;
60		// update the dependency indices
61		// notice this is not critical for soundness: not doing the below incrementing
62		// will only lead to overapproximating when antecedants are required in
63		// explanations
64	16456	for (const std::pair<const Node, std::map<bool, unsigned> >& pe : d_expDep)
65		{
66	33693	for (const auto& pep : pe.second)
67		{
68		// See if this can be incremented: it can if this literal is not relevant
69		// to the current index, and hence it is not relevant for both c1 and c2.
70	22462	Assert(pep.second >= 0 && pep.second <= d_nf.size());
71	22462	bool increment = (pep.first == d_isRev)
72	33693	? pep.second > index
73	33693	: (d_nf.size() - 1 - pep.second) < index;
74	22462	if (increment)
75		{
76	9091	d_expDep[pe.first][pep.first] = pep.second + 1;
77		}
78		}
79		}
80	5225	}
81
82	485753	void NormalForm::addToExplanation(Node exp,
83		unsigned new_val,
84		unsigned new_rev_val)
85		{
86	485753	Assert(!exp.isConst());
87	485753	if (std::find(d_exp.begin(), d_exp.end(), exp) == d_exp.end())
88		{
89	482696	d_exp.push_back(exp);
90		}
91	1457259	for (unsigned k = 0; k < 2; k++)
92		{
93	971506	unsigned val = k == 0 ? new_val : new_rev_val;
94	971506	std::map<bool, unsigned>::iterator itned = d_expDep[exp].find(k == 1);
95	971506	if (itned == d_expDep[exp].end())
96		{
97	1930784	Trace("strings-process-debug")
98	965392	<< "Deps : set dependency on " << exp << " to " << val
99	965392	<< " isRev=" << (k == 0) << std::endl;
100	965392	d_expDep[exp][k == 1] = val;
101		}
102		else
103		{
104	12228	Trace("strings-process-debug")
105	6114	<< "Deps : Multiple dependencies on " << exp << " : " << itned->second
106	6114	<< " " << val << " isRev=" << (k == 0) << std::endl;
107		// if we already have a dependency (in the case of non-linear string
108		// equalities), it is min/max
109	6114	bool cmp = val > itned->second;
110	6114	if (cmp == (k == 1))
111		{
112	3057	d_expDep[exp][k == 1] = val;
113		}
114		}
115		}
116	485753	}
117
118	32744	void NormalForm::getExplanation(int index, std::vector<Node>& curr_exp)
119		{
120	32744	if (index == -1 \|\| !options::stringMinPrefixExplain())
121		{
122	4268	curr_exp.insert(curr_exp.end(), d_exp.begin(), d_exp.end());
123	4268	return;
124		}
125	115437	for (const Node& exp : d_exp)
126		{
127	86961	int dep = static_cast<int>(d_expDep[exp][d_isRev]);
128	86961	if (dep <= index)
129		{
130	48803	curr_exp.push_back(exp);
131	48803	Trace("strings-explain-prefix-debug") << " include : ";
132		}
133		else
134		{
135	38158	Trace("strings-explain-prefix-debug") << " exclude : ";
136		}
137	86961	Trace("strings-explain-prefix-debug") << exp << std::endl;
138		}
139		}
140
141	9455	Node NormalForm::collectConstantStringAt(size_t& index)
142		{
143	18910	std::vector<Node> c;
144	24379	while (d_nf.size() > index && d_nf[index].isConst())
145		{
146	7462	c.push_back(d_nf[index]);
147	7462	index++;
148		}
149	9455	if (!c.empty())
150		{
151	6054	if (d_isRev)
152		{
153	3408	std::reverse(c.begin(), c.end());
154		}
155	12108	Node cc = Rewriter::rewrite(utils::mkConcat(c, c[0].getType()));
156	6054	Assert(cc.isConst());
157	6054	return cc;
158		}
159		else
160		{
161	3401	return Node::null();
162		}
163		}
164
165	16372	void NormalForm::getExplanationForPrefixEq(NormalForm& nfi,
166		NormalForm& nfj,
167		int index_i,
168		int index_j,
169		std::vector<Node>& curr_exp)
170		{
171	16372	Assert(nfi.d_isRev == nfj.d_isRev);
172	32744	Trace("strings-explain-prefix")
173	16372	<< "Get explanation for prefix " << index_i << ", " << index_j
174	16372	<< ", reverse = " << nfi.d_isRev << std::endl;
175		// get explanations
176	16372	nfi.getExplanation(index_i, curr_exp);
177	16372	nfj.getExplanation(index_j, curr_exp);
178	32744	Trace("strings-explain-prefix")
179	32744	<< "Included " << curr_exp.size() << " / "
180	16372	<< (nfi.d_exp.size() + nfj.d_exp.size()) << std::endl;
181		// add explanation for why they are equal
182	32744	Node eq = nfi.d_base.eqNode(nfj.d_base);
183	16372	curr_exp.push_back(eq);
184	16372	}
185
186		} // namespace strings
187		} // namespace theory
188	29502	} // namespace cvc5