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                 :            :  * Implementation of shadow elimination node conversion
      11                 :            :  */
      12                 :            : 
      13                 :            : #include "expr/elim_shadow_converter.h"
      14                 :            : 
      15                 :            : #include "expr/bound_var_manager.h"
      16                 :            : #include "expr/subtype_elim_node_converter.h"
      17                 :            : #include "util/rational.h"
      18                 :            : 
      19                 :            : using namespace cvc5::internal::kind;
      20                 :            : 
      21                 :            : namespace cvc5::internal {
      22                 :            : 
      23                 :     615392 : ElimShadowNodeConverter::ElimShadowNodeConverter(NodeManager* nm, const Node& q)
      24                 :     615392 :     : NodeConverter(nm), d_closure(q)
      25                 :            : {
      26 [ -  + ][ -  + ]:     615392 :   Assert(q.isClosure());
                 [ -  - ]
      27                 :     615392 :   d_vars.insert(d_vars.end(), q[0].begin(), q[0].end());
      28                 :     615392 : }
      29                 :            : 
      30                 :      66436 : ElimShadowNodeConverter::ElimShadowNodeConverter(
      31                 :      66436 :     NodeManager* nm, const Node& n, const std::unordered_set<Node>& vars)
      32                 :      66436 :     : NodeConverter(nm)
      33                 :            : {
      34                 :      66436 :   d_closure = n;
      35                 :      66436 :   d_vars.insert(d_vars.end(), vars.begin(), vars.end());
      36                 :      66436 : }
      37                 :            : 
      38                 :   12959013 : Node ElimShadowNodeConverter::postConvert(Node n)
      39                 :            : {
      40         [ +  + ]:   12959013 :   if (!n.isClosure())
      41                 :            :   {
      42                 :   12809972 :     return n;
      43                 :            :   }
      44                 :     149041 :   std::vector<Node> oldVars;
      45                 :     149041 :   std::vector<Node> newVars;
      46         [ +  + ]:     347142 :   for (size_t i = 0, nvars = n[0].getNumChildren(); i < nvars; i++)
      47                 :            :   {
      48                 :     198101 :     const Node& v = n[0][i];
      49         [ +  + ]:     198101 :     if (std::find(d_vars.begin(), d_vars.end(), v) != d_vars.end())
      50                 :            :     {
      51                 :        570 :       Node nv = getElimShadowVar(d_closure, n, i);
      52                 :        570 :       oldVars.push_back(v);
      53                 :        570 :       newVars.push_back(nv);
      54                 :        570 :     }
      55                 :     198101 :   }
      56         [ +  + ]:     149041 :   if (!newVars.empty())
      57                 :            :   {
      58                 :            :     return n.substitute(
      59                 :        564 :         oldVars.begin(), oldVars.end(), newVars.begin(), newVars.end());
      60                 :            :   }
      61                 :     148477 :   return n;
      62                 :     149041 : }
      63                 :            : 
      64                 :        576 : Node ElimShadowNodeConverter::getElimShadowVar(const Node& q,
      65                 :            :                                                const Node& n,
      66                 :            :                                                size_t i)
      67                 :            : {
      68                 :        576 :   NodeManager* nm = n.getNodeManager();
      69                 :        576 :   BoundVarManager* bvm = nm->getBoundVarManager();
      70                 :        576 :   Node ii = nm->mkConstInt(Rational(i));
      71                 :       1152 :   Node cacheVal = BoundVarManager::getCacheValue(q, n, ii);
      72                 :            :   // must be robust to subtype elimination
      73                 :        576 :   SubtypeElimNodeConverter senc(nm);
      74                 :        576 :   cacheVal = senc.convert(cacheVal);
      75                 :       1152 :   return bvm->mkBoundVar(BoundVarId::ELIM_SHADOW, cacheVal, n[0][i].getType());
      76                 :        576 : }
      77                 :            : 
      78                 :     615392 : Node ElimShadowNodeConverter::eliminateShadow(const Node& q)
      79                 :            : {
      80 [ -  + ][ -  + ]:     615392 :   Assert(q.isClosure());
                 [ -  - ]
      81                 :     615392 :   NodeManager* nm = q.getNodeManager();
      82                 :     615392 :   ElimShadowNodeConverter esnc(nm, q);
      83                 :            :   // eliminate shadowing in all children
      84                 :     615392 :   std::vector<Node> children;
      85                 :            :   // drop duplicate variables
      86                 :     615392 :   std::vector<Node> vars;
      87                 :     615392 :   bool childChanged = false;
      88         [ +  + ]:    2032972 :   for (size_t i = 0, nvars = q[0].getNumChildren(); i < nvars; i++)
      89                 :            :   {
      90                 :    1417580 :     const Node& v = q[0][i];
      91         [ +  + ]:    1417580 :     if (std::find(vars.begin(), vars.end(), v) == vars.end())
      92                 :            :     {
      93                 :    1417574 :       vars.push_back(v);
      94                 :            :     }
      95                 :            :     else
      96                 :            :     {
      97                 :            :       // should not eliminate shadowing from lambda, since order of variables
      98                 :            :       // matters.
      99 [ -  + ][ -  + ]:          6 :       Assert(q.getKind() != Kind::LAMBDA);
                 [ -  - ]
     100                 :          6 :       Node vn = getElimShadowVar(q, q, i);
     101                 :          6 :       vars.push_back(vn);
     102                 :          6 :       childChanged = true;
     103                 :          6 :     }
     104                 :    1417580 :   }
     105         [ +  + ]:     615392 :   if (childChanged)
     106                 :            :   {
     107                 :          6 :     children.push_back(nm->mkNode(Kind::BOUND_VAR_LIST, vars));
     108                 :            :   }
     109                 :            :   else
     110                 :            :   {
     111                 :     615386 :     children.push_back(q[0]);
     112                 :            :   }
     113         [ +  + ]:    1289845 :   for (size_t i = 1, nchild = q.getNumChildren(); i < nchild; i++)
     114                 :            :   {
     115                 :     674453 :     children.push_back(esnc.convert(q[i]));
     116                 :            :   }
     117                 :    1230784 :   return nm->mkNode(q.getKind(), children);
     118                 :     615392 : }
     119                 :            : 
     120                 :            : }  // namespace cvc5::internal