Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/strings/normal_form.cpp	Lines:	84	84	100.0 %
Date:	2021-05-24	Branches:	150	342	43.9 %


/******************************************************************************
 * 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	90559	void NormalForm::init(Node base)
31		{
32	90559	Assert(base.getType().isStringLike());
33	90559	Assert(base.getKind() != STRING_CONCAT);
34	90559	d_base = base;
35	90559	d_nf.clear();
36	90559	d_isRev = false;
37	90559	d_exp.clear();
38	90559	d_expDep.clear();
39
40		// add to normal form
41	90559	if (!base.isConst() \|\| Word::getLength(base) > 0)
42		{
43	81601	d_nf.push_back(base);
44		}
45	90559	}
46
47	33664	void NormalForm::reverse()
48		{
49	33664	std::reverse(d_nf.begin(), d_nf.end());
50	33664	d_isRev = !d_isRev;
51	33664	}
52
53	2689	void NormalForm::splitConstant(unsigned index, Node c1, Node c2)
54		{
55	2689	Assert(Rewriter::rewrite(NodeManager::currentNM()->mkNode(
56		STRING_CONCAT, d_isRev ? c2 : c1, d_isRev ? c1 : c2))
57		== d_nf[index]);
58	2689	d_nf.insert(d_nf.begin() + index + 1, c2);
59	2689	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	6829	for (const std::pair<const Node, std::map<bool, unsigned> >& pe : d_expDep)
65		{
66	12420	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	8280	Assert(pep.second >= 0 && pep.second <= d_nf.size());
71	8280	bool increment = (pep.first == d_isRev)
72	12420	? pep.second > index
73	12420	: (d_nf.size() - 1 - pep.second) < index;
74	8280	if (increment)
75		{
76	2636	d_expDep[pe.first][pep.first] = pep.second + 1;
77		}
78		}
79		}
80	2689	}
81
82	277484	void NormalForm::addToExplanation(Node exp,
83		unsigned new_val,
84		unsigned new_rev_val)
85		{
86	277484	Assert(!exp.isConst());
87	277484	if (std::find(d_exp.begin(), d_exp.end(), exp) == d_exp.end())
88		{
89	276286	d_exp.push_back(exp);
90		}
91	832452	for (unsigned k = 0; k < 2; k++)
92		{
93	554968	unsigned val = k == 0 ? new_val : new_rev_val;
94	554968	std::map<bool, unsigned>::iterator itned = d_expDep[exp].find(k == 1);
95	554968	if (itned == d_expDep[exp].end())
96		{
97	1105144	Trace("strings-process-debug")
98	552572	<< "Deps : set dependency on " << exp << " to " << val
99	552572	<< " isRev=" << (k == 0) << std::endl;
100	552572	d_expDep[exp][k == 1] = val;
101		}
102		else
103		{
104	4792	Trace("strings-process-debug")
105	2396	<< "Deps : Multiple dependencies on " << exp << " : " << itned->second
106	2396	<< " " << 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	2396	bool cmp = val > itned->second;
110	2396	if (cmp == (k == 1))
111		{
112	1198	d_expDep[exp][k == 1] = val;
113		}
114		}
115		}
116	277484	}
117
118	19902	void NormalForm::getExplanation(int index, std::vector<Node>& curr_exp)
119		{
120	37404	if (index == -1 \|\| !options::stringMinPrefixExplain())
121		{
122	2400	curr_exp.insert(curr_exp.end(), d_exp.begin(), d_exp.end());
123	2400	return;
124		}
125	75022	for (const Node& exp : d_exp)
126		{
127	57520	int dep = static_cast<int>(d_expDep[exp][d_isRev]);
128	57520	if (dep <= index)
129		{
130	34159	curr_exp.push_back(exp);
131	34159	Trace("strings-explain-prefix-debug") << " include : ";
132		}
133		else
134		{
135	23361	Trace("strings-explain-prefix-debug") << " exclude : ";
136		}
137	57520	Trace("strings-explain-prefix-debug") << exp << std::endl;
138		}
139		}
140
141	6482	Node NormalForm::collectConstantStringAt(size_t& index)
142		{
143	12964	std::vector<Node> c;
144	18578	while (d_nf.size() > index && d_nf[index].isConst())
145		{
146	6048	c.push_back(d_nf[index]);
147	6048	index++;
148		}
149	6482	if (!c.empty())
150		{
151	4924	if (d_isRev)
152		{
153	2748	std::reverse(c.begin(), c.end());
154		}
155	9848	Node cc = Rewriter::rewrite(utils::mkConcat(c, c[0].getType()));
156	4924	Assert(cc.isConst());
157	4924	return cc;
158		}
159		else
160		{
161	1558	return Node::null();
162		}
163		}
164
165	9951	void NormalForm::getExplanationForPrefixEq(NormalForm& nfi,
166		NormalForm& nfj,
167		int index_i,
168		int index_j,
169		std::vector<Node>& curr_exp)
170		{
171	9951	Assert(nfi.d_isRev == nfj.d_isRev);
172	19902	Trace("strings-explain-prefix")
173	9951	<< "Get explanation for prefix " << index_i << ", " << index_j
174	9951	<< ", reverse = " << nfi.d_isRev << std::endl;
175		// get explanations
176	9951	nfi.getExplanation(index_i, curr_exp);
177	9951	nfj.getExplanation(index_j, curr_exp);
178	19902	Trace("strings-explain-prefix")
179	19902	<< "Included " << curr_exp.size() << " / "
180	9951	<< (nfi.d_exp.size() + nfj.d_exp.size()) << std::endl;
181		// add explanation for why they are equal
182	19902	Node eq = nfi.d_base.eqNode(nfj.d_base);
183	9951	curr_exp.push_back(eq);
184	9951	}
185
186		} // namespace strings
187		} // namespace theory
188	45693	} // namespace cvc5