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                 :       6462 : void ArithSubs::addArith(const Node& v, const Node& s)
      22                 :            : {
      23 [ -  + ][ -  + ]:       6462 :   Assert(v.getType().isRealOrInt());
                 [ -  - ]
      24 [ -  + ][ -  + ]:       6462 :   Assert(s.getType().isRealOrInt());
                 [ -  - ]
      25                 :       6462 :   d_vars.push_back(v);
      26                 :       6462 :   d_subs.push_back(s);
      27                 :       6462 : }
      28                 :            : 
      29                 :     168246 : Node ArithSubs::applyArith(const Node& n, bool traverseNlMult) const
      30                 :            : {
      31         [ +  + ]:     168246 :   if (d_vars.empty())
      32                 :            :   {
      33                 :      10611 :     return n;
      34                 :            :   }
      35                 :     157635 :   NodeManager* nm = n.getNodeManager();
      36                 :     157635 :   std::unordered_map<TNode, Node> visited;
      37                 :     157635 :   std::vector<TNode> visit;
      38                 :     157635 :   visit.push_back(n);
      39                 :            :   do
      40                 :            :   {
      41                 :     970997 :     TNode cur = visit.back();
      42                 :     970997 :     visit.pop_back();
      43                 :     970997 :     auto it = visited.find(cur);
      44                 :            : 
      45         [ +  + ]:     970997 :     if (it == visited.end())
      46                 :            :     {
      47                 :     682114 :       visited[cur] = Node::null();
      48                 :     682114 :       auto s = find(cur);
      49         [ +  + ]:     682114 :       if (s)
      50                 :            :       {
      51                 :     173404 :         visited[cur] = *s;
      52                 :            :       }
      53         [ +  + ]:     508710 :       else if (cur.getNumChildren() == 0)
      54                 :            :       {
      55                 :     233525 :         visited[cur] = cur;
      56                 :            :       }
      57                 :            :       else
      58                 :            :       {
      59         [ +  + ]:     275185 :         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                 :      10519 :           visited[cur] = cur;
      65                 :            :         }
      66                 :            :         else
      67                 :            :         {
      68                 :     264666 :           visit.push_back(cur);
      69         [ +  + ]:     813362 :           for (const Node& cn : cur)
      70                 :            :           {
      71                 :     548696 :             visit.push_back(cn);
      72                 :     548696 :           }
      73                 :            :         }
      74                 :            :       }
      75                 :     682114 :     }
      76         [ +  + ]:     288883 :     else if (it->second.isNull())
      77                 :            :     {
      78                 :     264666 :       Node ret = cur;
      79                 :     264666 :       bool childChanged = false;
      80                 :     264666 :       std::vector<Node> children;
      81         [ -  + ]:     264666 :       if (cur.getMetaKind() == kind::metakind::PARAMETERIZED)
      82                 :            :       {
      83                 :          0 :         children.push_back(cur.getOperator());
      84                 :            :       }
      85         [ +  + ]:     813362 :       for (const Node& cn : cur)
      86                 :            :       {
      87                 :     548696 :         it = visited.find(cn);
      88 [ -  + ][ -  + ]:     548696 :         Assert(it != visited.end());
                 [ -  - ]
      89 [ -  + ][ -  + ]:     548696 :         Assert(!it->second.isNull());
                 [ -  - ]
      90 [ +  + ][ +  + ]:     548696 :         childChanged = childChanged || cn != it->second;
      91                 :     548696 :         children.push_back(it->second);
      92                 :     548696 :       }
      93         [ +  + ]:     264666 :       if (childChanged)
      94                 :            :       {
      95                 :     225074 :         ret = nm->mkNode(cur.getKind(), children);
      96                 :            :       }
      97                 :     264666 :       visited[cur] = ret;
      98                 :     264666 :     }
      99         [ +  + ]:     970997 :   } while (!visit.empty());
     100 [ -  + ][ -  + ]:     157635 :   Assert(visited.find(n) != visited.end());
                 [ -  - ]
     101 [ -  + ][ -  + ]:     157635 :   Assert(!visited.find(n)->second.isNull());
                 [ -  - ]
     102                 :     157635 :   return visited[n];
     103                 :     157635 : }
     104                 :            : 
     105                 :     285751 : bool ArithSubs::shouldTraverse(const Node& n, bool traverseNlMult)
     106                 :            : {
     107                 :     285751 :   Kind k = n.getKind();
     108                 :     285751 :   TheoryId ctid = theory::kindToTheoryId(k);
     109                 :            :   // We always treat transcendental kinds and extended nonlinear kinds
     110                 :            :   // as black boxes.
     111 [ +  + ][ +  + ]:      27446 :   if ((ctid != THEORY_ARITH && ctid != THEORY_BOOL && ctid != THEORY_BUILTIN)
     112 [ +  + ][ +  + ]:     277824 :       || isTranscendentalKind(k) || isExtendedNonLinearKind(k)
     113 [ +  + ][ +  + ]:     571502 :       || (!traverseNlMult && k == Kind::NONLINEAR_MULT))
         [ +  + ][ +  + ]
     114                 :            :   {
     115                 :      12065 :     return false;
     116                 :            :   }
     117                 :     273686 :   return true;
     118                 :            : }
     119                 :            : 
     120                 :       2979 : bool ArithSubs::hasArithSubterm(TNode n, TNode t, bool traverseNlMult)
     121                 :            : {
     122                 :       2979 :   std::unordered_set<TNode> visited;
     123                 :       2979 :   std::vector<TNode> toProcess;
     124                 :       2979 :   toProcess.push_back(n);
     125                 :       2979 :   TNode cur;
     126                 :            :   do
     127                 :            :   {
     128                 :       3962 :     cur = toProcess.back();
     129                 :       3962 :     toProcess.pop_back();
     130         [ -  + ]:       3962 :     if (cur == t)
     131                 :            :     {
     132                 :          0 :       return true;
     133                 :            :     }
     134 [ +  + ][ +  + ]:       3962 :     if (!visited.insert(cur).second || !shouldTraverse(cur, traverseNlMult))
         [ +  + ][ +  + ]
                 [ -  - ]
     135                 :            :     {
     136                 :        286 :       continue;
     137                 :            :     }
     138                 :       3676 :     toProcess.insert(toProcess.end(), cur.begin(), cur.end());
     139         [ +  + ]:       3962 :   } while (!toProcess.empty());
     140                 :       2979 :   return false;
     141                 :       2979 : }
     142                 :            : 
     143                 :            : }  // namespace arith
     144                 :            : }  // namespace theory
     145                 :            : }  // namespace cvc5::internal