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                 :            :  * Arithmetic substitution utility.
      11                 :            :  */
      12                 :            : 
      13                 :            : #include "theory/arith/arith_subs.h"
      14                 :            : 
      15                 :            : #include "theory/arith/arith_utilities.h"
      16                 :            : 
      17                 :            : namespace cvc5::internal {
      18                 :            : namespace theory {
      19                 :            : namespace arith {
      20                 :            : 
      21                 :       8089 : void ArithSubs::addArith(const Node& v, const Node& s)
      22                 :            : {
      23 [ -  + ][ -  + ]:       8089 :   Assert(v.getType().isRealOrInt());
                 [ -  - ]
      24 [ -  + ][ -  + ]:       8089 :   Assert(s.getType().isRealOrInt());
                 [ -  - ]
      25                 :       8089 :   d_vars.push_back(v);
      26                 :       8089 :   d_subs.push_back(s);
      27                 :       8089 : }
      28                 :            : 
      29                 :    1116553 : Node ArithSubs::applyArith(const Node& n, bool traverseNlMult) const
      30                 :            : {
      31         [ +  + ]:    1116553 :   if (d_vars.empty())
      32                 :            :   {
      33                 :      13635 :     return n;
      34                 :            :   }
      35                 :    1102918 :   NodeManager* nm = n.getNodeManager();
      36                 :    1102918 :   std::unordered_map<TNode, Node> visited;
      37                 :    1102918 :   std::vector<TNode> visit;
      38                 :    1102918 :   visit.push_back(n);
      39                 :            :   do
      40                 :            :   {
      41                 :    9484315 :     TNode cur = visit.back();
      42                 :    9484315 :     visit.pop_back();
      43                 :    9484315 :     auto it = visited.find(cur);
      44                 :            : 
      45         [ +  + ]:    9484315 :     if (it == visited.end())
      46                 :            :     {
      47                 :    6351245 :       visited[cur] = Node::null();
      48                 :    6351245 :       auto s = find(cur);
      49         [ +  + ]:    6351245 :       if (s)
      50                 :            :       {
      51                 :    1684290 :         visited[cur] = *s;
      52                 :            :       }
      53         [ +  + ]:    4666955 :       else if (cur.getNumChildren() == 0)
      54                 :            :       {
      55                 :    2048193 :         visited[cur] = cur;
      56                 :            :       }
      57                 :            :       else
      58                 :            :       {
      59         [ +  + ]:    2618762 :         if (!shouldTraverse(cur, traverseNlMult))
      60                 :            :         {
      61                 :            :           // Do not traverse beneath applications that belong to another theory
      62                 :            :           // besides (core) arithmetic. Notice that transcendental function
      63                 :            :           // applications are also not traversed here.
      64                 :      17306 :           visited[cur] = cur;
      65                 :            :         }
      66                 :            :         else
      67                 :            :         {
      68                 :    2601456 :           visit.push_back(cur);
      69         [ +  + ]:    8381397 :           for (const Node& cn : cur)
      70                 :            :           {
      71                 :    5779941 :             visit.push_back(cn);
      72                 :    5779941 :           }
      73                 :            :         }
      74                 :            :       }
      75                 :    6351245 :     }
      76         [ +  + ]:    3133070 :     else if (it->second.isNull())
      77                 :            :     {
      78                 :    2601456 :       Node ret = cur;
      79                 :    2601456 :       bool childChanged = false;
      80                 :    2601456 :       std::vector<Node> children;
      81         [ -  + ]:    2601456 :       if (cur.getMetaKind() == kind::metakind::PARAMETERIZED)
      82                 :            :       {
      83                 :          0 :         children.push_back(cur.getOperator());
      84                 :            :       }
      85         [ +  + ]:    8381397 :       for (const Node& cn : cur)
      86                 :            :       {
      87                 :    5779941 :         it = visited.find(cn);
      88 [ -  + ][ -  + ]:    5779941 :         Assert(it != visited.end());
                 [ -  - ]
      89 [ -  + ][ -  + ]:    5779941 :         Assert(!it->second.isNull());
                 [ -  - ]
      90 [ +  + ][ +  + ]:    5779941 :         childChanged = childChanged || cn != it->second;
      91                 :    5779941 :         children.push_back(it->second);
      92                 :    5779941 :       }
      93         [ +  + ]:    2601456 :       if (childChanged)
      94                 :            :       {
      95                 :    2561211 :         ret = nm->mkNode(cur.getKind(), children);
      96                 :            :       }
      97                 :    2601456 :       visited[cur] = ret;
      98                 :    2601456 :     }
      99         [ +  + ]:    9484315 :   } while (!visit.empty());
     100 [ -  + ][ -  + ]:    1102918 :   Assert(visited.find(n) != visited.end());
                 [ -  - ]
     101 [ -  + ][ -  + ]:    1102918 :   Assert(!visited.find(n)->second.isNull());
                 [ -  - ]
     102                 :    1102918 :   return visited[n];
     103                 :    1102918 : }
     104                 :            : 
     105                 :    2630730 : bool ArithSubs::shouldTraverse(const Node& n, bool traverseNlMult)
     106                 :            : {
     107                 :    2630730 :   Kind k = n.getKind();
     108                 :    2630730 :   TheoryId ctid = theory::kindToTheoryId(k);
     109                 :            :   // We always treat transcendental kinds and extended nonlinear kinds
     110                 :            :   // as black boxes.
     111 [ +  + ][ +  + ]:      36896 :   if ((ctid != THEORY_ARITH && ctid != THEORY_BOOL && ctid != THEORY_BUILTIN)
     112 [ +  + ][ +  + ]:    2617905 :       || isTranscendentalKind(k) || isExtendedNonLinearKind(k)
     113 [ +  + ][ +  + ]:    5261460 :       || (!traverseNlMult && k == Kind::NONLINEAR_MULT))
         [ +  + ][ +  + ]
     114                 :            :   {
     115                 :      19182 :     return false;
     116                 :            :   }
     117                 :    2611548 :   return true;
     118                 :            : }
     119                 :            : 
     120                 :       3655 : bool ArithSubs::hasArithSubterm(TNode n, TNode t, bool traverseNlMult)
     121                 :            : {
     122                 :       3655 :   std::unordered_set<TNode> visited;
     123                 :       3655 :   std::vector<TNode> toProcess;
     124                 :       3655 :   toProcess.push_back(n);
     125                 :       3655 :   TNode cur;
     126                 :            :   do
     127                 :            :   {
     128                 :       4645 :     cur = toProcess.back();
     129                 :       4645 :     toProcess.pop_back();
     130         [ -  + ]:       4645 :     if (cur == t)
     131                 :            :     {
     132                 :          0 :       return true;
     133                 :            :     }
     134 [ +  + ][ +  + ]:       4645 :     if (!visited.insert(cur).second || !shouldTraverse(cur, traverseNlMult))
         [ +  + ][ +  + ]
                 [ -  - ]
     135                 :            :     {
     136                 :        325 :       continue;
     137                 :            :     }
     138                 :       4320 :     toProcess.insert(toProcess.end(), cur.begin(), cur.end());
     139         [ +  + ]:       4645 :   } while (!toProcess.empty());
     140                 :       3655 :   return false;
     141                 :       3655 : }
     142                 :            : 
     143                 :            : }  // namespace arith
     144                 :            : }  // namespace theory
     145                 :            : }  // namespace cvc5::internal