Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * This file is part of the cvc5 project.
       3                 :            :  *
       4                 :            :  * Copyright (c) 2009-2026 by the authors listed in the file AUTHORS
       5                 :            :  * in the top-level source directory and their institutional affiliations.
       6                 :            :  * All rights reserved.  See the file COPYING in the top-level source
       7                 :            :  * directory for licensing information.
       8                 :            :  * ****************************************************************************
       9                 :            :  *
      10                 :            :  * Skolem definition manager.
      11                 :            :  */
      12                 :            : 
      13                 :            : #include "prop/skolem_def_manager.h"
      14                 :            : 
      15                 :            : namespace cvc5::internal {
      16                 :            : namespace prop {
      17                 :            : 
      18                 :      28895 : SkolemDefManager::SkolemDefManager(context::Context* context,
      19                 :      28895 :                                    context::UserContext* userContext)
      20                 :      28895 :     : d_skDefs(userContext), d_skActive(context), d_hasSkolems(userContext)
      21                 :            : {
      22                 :      28895 : }
      23                 :            : 
      24                 :      28882 : SkolemDefManager::~SkolemDefManager() {}
      25                 :            : 
      26                 :      65486 : void SkolemDefManager::notifySkolemDefinition(TNode skolem, Node def)
      27                 :            : {
      28                 :            :   // Notice that skolem should have kind SKOLEM
      29         [ +  - ]:     130972 :   Trace("sk-defs") << "notifySkolemDefinition: " << def << " for " << skolem
      30                 :      65486 :                    << std::endl;
      31                 :            :   // in very rare cases, a skolem may be generated twice for terms that are
      32                 :            :   // equivalent up to purification
      33         [ +  + ]:      65486 :   if (d_skDefs.find(skolem) == d_skDefs.end())
      34                 :            :   {
      35                 :            :     // should not have already computed whether the skolem has skolems or
      36                 :            :     // otherwise we should have marked that we have skolems, or else
      37                 :            :     // our computation of hasSkolems is wrong after adding this definition
      38                 :      62022 :     Assert(d_hasSkolems.find(skolem) == d_hasSkolems.end()
      39                 :            :            || d_hasSkolems[skolem]);
      40                 :      62022 :     d_skDefs.insert(skolem, def);
      41                 :            :   }
      42                 :      65486 : }
      43                 :            : 
      44                 :       4142 : TNode SkolemDefManager::getDefinitionForSkolem(TNode skolem) const
      45                 :            : {
      46                 :       4142 :   NodeNodeMap::const_iterator it = d_skDefs.find(skolem);
      47                 :       4142 :   Assert(it != d_skDefs.end()) << "No skolem def for " << skolem;
      48                 :       8284 :   return it->second;
      49                 :            : }
      50                 :            : 
      51                 :   12017638 : void SkolemDefManager::notifyAsserted(TNode literal,
      52                 :            :                                       std::vector<TNode>& activatedSkolems)
      53                 :            : {
      54         [ +  + ]:   12017638 :   if (d_skActive.size() == d_skDefs.size())
      55                 :            :   {
      56                 :            :     // already activated all skolems
      57                 :    6826705 :     return;
      58                 :            :   }
      59                 :    5190933 :   std::unordered_set<Node> defs;
      60                 :    5190933 :   getSkolems(literal, defs, true);
      61         [ +  - ]:   10381866 :   Trace("sk-defs") << "notifyAsserted: " << literal << " has skolems " << defs
      62                 :    5190933 :                    << std::endl;
      63         [ +  + ]:   12758726 :   for (const Node& d : defs)
      64                 :            :   {
      65         [ +  + ]:    7567793 :     if (d_skActive.find(d) != d_skActive.end())
      66                 :            :     {
      67                 :            :       // already active
      68                 :    6759319 :       continue;
      69                 :            :     }
      70                 :     808474 :     d_skActive.insert(d);
      71         [ +  - ]:     808474 :     Trace("sk-defs") << "...activate " << d << std::endl;
      72                 :            :     // add its definition to the activated list
      73                 :     808474 :     activatedSkolems.push_back(d);
      74                 :            :   }
      75                 :    5190933 : }
      76                 :            : 
      77                 :   37406479 : bool SkolemDefManager::hasSkolems(TNode n)
      78                 :            : {
      79         [ +  - ]:   37406479 :   Trace("sk-defs-debug") << "Compute has skolems for " << n << std::endl;
      80                 :   37406479 :   std::unordered_set<TNode> visited;
      81                 :   37406479 :   std::unordered_set<TNode>::iterator it;
      82                 :   37406479 :   NodeBoolMap::const_iterator itn;
      83                 :   37406479 :   std::vector<TNode> visit;
      84                 :   37406479 :   TNode cur;
      85                 :   37406479 :   visit.push_back(n);
      86                 :            :   do
      87                 :            :   {
      88                 :   38884342 :     cur = visit.back();
      89                 :   38884342 :     itn = d_hasSkolems.find(cur);
      90         [ +  + ]:   38884342 :     if (itn != d_hasSkolems.end())
      91                 :            :     {
      92                 :   37771358 :       visit.pop_back();
      93                 :            :       // already computed
      94                 :   37771358 :       continue;
      95                 :            :     }
      96                 :    1112984 :     it = visited.find(cur);
      97         [ +  + ]:    1112984 :     if (it == visited.end())
      98                 :            :     {
      99                 :     615959 :       visited.insert(cur);
     100         [ +  + ]:     615959 :       if (cur.getNumChildren() == 0)
     101                 :            :       {
     102                 :     118934 :         visit.pop_back();
     103                 :     118934 :         Kind ck = cur.getKind();
     104                 :            :         // We have skolems if we are a skolem that has a definition, or
     105                 :            :         // we are a Boolean term variable. For Boolean term variables, we do
     106                 :            :         // not make this test depend on whether the skolem has a definition,
     107                 :            :         // since that is prone to change if the Boolean term variable was
     108                 :            :         // introduced in a lemma prior to its definition being introduced.
     109                 :            :         // This is for example the case in strings reduction for Booleans,
     110                 :            :         // ground term purification for E-matching, etc.
     111                 :     237868 :         d_hasSkolems[cur] = (ck == Kind::SKOLEM
     112 [ +  + ][ +  + ]:     248869 :                              && (d_skDefs.find(cur) != d_skDefs.end()
                 [ -  - ]
     113 [ +  + ][ +  + ]:     248869 :                                  || cur.getType().isBoolean()));
         [ +  + ][ -  - ]
     114                 :            :       }
     115                 :            :       else
     116                 :            :       {
     117         [ +  + ]:     497025 :         if (cur.getMetaKind() == kind::metakind::PARAMETERIZED)
     118                 :            :         {
     119                 :      97408 :           visit.push_back(cur.getOperator());
     120                 :            :         }
     121                 :     497025 :         visit.insert(visit.end(), cur.begin(), cur.end());
     122                 :            :       }
     123                 :            :     }
     124                 :            :     else
     125                 :            :     {
     126                 :     497025 :       visit.pop_back();
     127                 :            :       bool hasSkolem;
     128                 :    1491075 :       if (cur.getMetaKind() == kind::metakind::PARAMETERIZED
     129 [ +  + ][ +  + ]:     497025 :           && d_hasSkolems[cur.getOperator()])
         [ +  + ][ +  + ]
                 [ -  - ]
     130                 :            :       {
     131                 :        145 :         hasSkolem = true;
     132                 :            :       }
     133                 :            :       else
     134                 :            :       {
     135                 :     496880 :         hasSkolem = false;
     136         [ +  + ]:    1142520 :         for (TNode i : cur)
     137                 :            :         {
     138 [ -  + ][ -  + ]:     811578 :           Assert(d_hasSkolems.find(i) != d_hasSkolems.end());
                 [ -  - ]
     139         [ +  + ]:     811578 :           if (d_hasSkolems[i])
     140                 :            :           {
     141                 :     165938 :             hasSkolem = true;
     142                 :     165938 :             break;
     143                 :            :           }
     144         [ +  + ]:     811578 :         }
     145                 :            :       }
     146                 :     497025 :       d_hasSkolems[cur] = hasSkolem;
     147                 :            :     }
     148         [ +  + ]:   38884342 :   } while (!visit.empty());
     149 [ -  + ][ -  + ]:   37406479 :   Assert(d_hasSkolems.find(n) != d_hasSkolems.end());
                 [ -  - ]
     150                 :   74812958 :   return d_hasSkolems[n];
     151                 :   37406479 : }
     152                 :            : 
     153                 :    5197052 : void SkolemDefManager::getSkolems(TNode n,
     154                 :            :                                   std::unordered_set<Node>& skolems,
     155                 :            :                                   bool useDefs)
     156                 :            : {
     157                 :    5197052 :   NodeNodeMap::const_iterator itd;
     158                 :    5197052 :   std::unordered_set<TNode> visited;
     159                 :    5197052 :   std::unordered_set<TNode>::iterator it;
     160                 :    5197052 :   std::vector<TNode> visit;
     161                 :    5197052 :   TNode cur;
     162                 :    5197052 :   visit.push_back(n);
     163                 :            :   do
     164                 :            :   {
     165                 :   37406479 :     cur = visit.back();
     166                 :   37406479 :     visit.pop_back();
     167         [ +  + ]:   37406479 :     if (!hasSkolems(cur))
     168                 :            :     {
     169                 :            :       // does not have skolems, continue
     170                 :   11143577 :       continue;
     171                 :            :     }
     172                 :   26262902 :     it = visited.find(cur);
     173         [ +  + ]:   26262902 :     if (it == visited.end())
     174                 :            :     {
     175                 :   25015469 :       visited.insert(cur);
     176         [ +  + ]:   25015469 :       if (cur.isVar())
     177                 :            :       {
     178                 :    7571968 :         itd = d_skDefs.find(cur);
     179         [ +  + ]:    7571968 :         if (itd != d_skDefs.end())
     180                 :            :         {
     181         [ +  + ]:    7571935 :           skolems.insert(useDefs ? itd->second : Node(cur));
     182                 :            :         }
     183                 :    7571968 :         continue;
     184                 :            :       }
     185         [ +  + ]:   17443501 :       if (cur.getMetaKind() == kind::metakind::PARAMETERIZED)
     186                 :            :       {
     187                 :    3046782 :         visit.push_back(cur.getOperator());
     188                 :            :       }
     189                 :   17443501 :       visit.insert(visit.end(), cur.begin(), cur.end());
     190                 :            :     }
     191         [ +  + ]:   37406479 :   } while (!visit.empty());
     192                 :    5197052 : }
     193                 :            : 
     194                 :            : }  // namespace prop
     195                 :            : }  // namespace cvc5::internal