Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Andrew Reynolds, Aina Niemetz, Gereon Kremer
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2025 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 sygus_unif.
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "theory/quantifiers/sygus/sygus_unif.h"
      17                 :            : 
      18                 :            : #include "theory/datatypes/sygus_datatype_utils.h"
      19                 :            : #include "theory/quantifiers/sygus/term_database_sygus.h"
      20                 :            : #include "theory/quantifiers/term_util.h"
      21                 :            : #include "util/random.h"
      22                 :            : 
      23                 :            : using namespace std;
      24                 :            : using namespace cvc5::internal::kind;
      25                 :            : 
      26                 :            : namespace cvc5::internal {
      27                 :            : namespace theory {
      28                 :            : namespace quantifiers {
      29                 :            : 
      30                 :       7373 : SygusUnif::SygusUnif(Env& env)
      31                 :       7373 :     : EnvObj(env), d_tds(nullptr), d_enableMinimality(false)
      32                 :            : {
      33                 :       7373 : }
      34                 :            : 
      35                 :       7266 : SygusUnif::~SygusUnif() {}
      36                 :            : 
      37                 :        117 : void SygusUnif::initializeCandidate(
      38                 :            :     TermDbSygus* tds,
      39                 :            :     Node f,
      40                 :            :     std::vector<Node>& enums,
      41                 :            :     std::map<Node, std::vector<Node>>& strategy_lemmas)
      42                 :            : {
      43                 :        117 :   d_tds = tds;
      44                 :        117 :   d_candidates.push_back(f);
      45                 :            :   // initialize the strategy
      46                 :        117 :   d_strategy.emplace(f, SygusUnifStrategy(d_env));
      47                 :        117 :   d_strategy.at(f).initialize(tds, f, enums);
      48                 :        117 : }
      49                 :            : 
      50                 :        434 : Node SygusUnif::getMinimalTerm(const std::vector<Node>& terms)
      51                 :            : {
      52                 :        434 :   unsigned minSize = 0;
      53                 :        434 :   Node minTerm;
      54                 :        434 :   std::map<Node, unsigned>::iterator it;
      55         [ +  + ]:       1116 :   for (const Node& n : terms)
      56                 :            :   {
      57                 :        682 :     it = d_termToSize.find(n);
      58                 :        682 :     unsigned ssize = 0;
      59         [ +  + ]:        682 :     if (it == d_termToSize.end())
      60                 :            :     {
      61                 :        208 :       ssize = datatypes::utils::getSygusTermSize(n);
      62                 :        208 :       d_termToSize[n] = ssize;
      63                 :            :     }
      64                 :            :     else
      65                 :            :     {
      66                 :        474 :       ssize = it->second;
      67                 :            :     }
      68 [ +  + ][ +  + ]:        682 :     if (minTerm.isNull() || ssize < minSize)
                 [ +  + ]
      69                 :            :     {
      70                 :        540 :       minTerm = n;
      71                 :        540 :       minSize = ssize;
      72                 :            :     }
      73                 :            :   }
      74                 :        868 :   return minTerm;
      75                 :            : }
      76                 :            : 
      77                 :        366 : Node SygusUnif::constructBestSolvedTerm(Node e, const std::vector<Node>& solved)
      78                 :            : {
      79 [ -  + ][ -  + ]:        366 :   Assert(!solved.empty());
                 [ -  - ]
      80         [ +  + ]:        366 :   if (d_enableMinimality)
      81                 :            :   {
      82                 :        194 :     return getMinimalTerm(solved);
      83                 :            :   }
      84                 :        172 :   return solved[0];
      85                 :            : }
      86                 :            : 
      87                 :        462 : Node SygusUnif::constructBestConditional(Node ce,
      88                 :            :                                          const std::vector<Node>& conds)
      89                 :            : {
      90 [ -  + ][ -  + ]:        462 :   Assert(!conds.empty());
                 [ -  - ]
      91                 :        462 :   double r = Random::getRandom().pickDouble(0.0, 1.0);
      92                 :        462 :   unsigned cindex = r * conds.size();
      93         [ +  + ]:        462 :   if (cindex > conds.size())
      94                 :            :   {
      95                 :        138 :     cindex = conds.size() - 1;
      96                 :            :   }
      97                 :        462 :   return conds[cindex];
      98                 :            : }
      99                 :            : 
     100                 :       1970 : Node SygusUnif::constructBestStringToConcat(
     101                 :            :     const std::vector<Node>& strs,
     102                 :            :     const std::map<Node, size_t>& total_inc,
     103                 :            :     const std::map<Node, std::vector<size_t>>& incr)
     104                 :            : {
     105 [ -  + ][ -  + ]:       1970 :   Assert(!strs.empty());
                 [ -  - ]
     106                 :       3940 :   std::vector<Node> strs_tmp = strs;
     107                 :       1970 :   std::shuffle(strs_tmp.begin(), strs_tmp.end(), Random::getRandom());
     108                 :            :   // prefer one that has incremented by more than 0
     109         [ +  + ]:       2138 :   for (const Node& ns : strs_tmp)
     110                 :            :   {
     111                 :       2078 :     const std::map<Node, size_t>::const_iterator iti = total_inc.find(ns);
     112 [ +  - ][ +  + ]:       2078 :     if (iti != total_inc.end() && iti->second > 0)
                 [ +  + ]
     113                 :            :     {
     114                 :       1910 :       return ns;
     115                 :            :     }
     116                 :            :   }
     117                 :         60 :   return strs_tmp[0];
     118                 :            : }
     119                 :            : 
     120                 :      46252 : void SygusUnif::indent(const char* c, int ind)
     121                 :            : {
     122         [ -  + ]:      46252 :   if (TraceIsOn(c))
     123                 :            :   {
     124         [ -  - ]:          0 :     for (int i = 0; i < ind; i++)
     125                 :            :     {
     126         [ -  - ]:          0 :       Trace(c) << "  ";
     127                 :            :     }
     128                 :            :   }
     129                 :      46252 : }
     130                 :            : 
     131                 :        164 : void SygusUnif::print_val(const char* c, std::vector<Node>& vals, bool pol)
     132                 :            : {
     133         [ -  + ]:        164 :   if (TraceIsOn(c))
     134                 :            :   {
     135         [ -  - ]:          0 :     for (unsigned i = 0; i < vals.size(); i++)
     136                 :            :     {
     137                 :          0 :       Trace(c) << ((pol ? vals[i].getConst<bool>() : !vals[i].getConst<bool>())
     138                 :            :                        ? "1"
     139         [ -  - ]:          0 :                        : "0");
     140                 :            :     }
     141                 :            :   }
     142                 :        164 : }
     143                 :            : 
     144                 :            : }  // namespace quantifiers
     145                 :            : }  // namespace theory
     146                 :            : }  // namespace cvc5::internal