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                 :       6704 : void ArithSubs::addArith(const Node& v, const Node& s)
      22                 :            : {
      23 [ -  + ][ -  + ]:       6704 :   Assert(v.getType().isRealOrInt());
                 [ -  - ]
      24 [ -  + ][ -  + ]:       6704 :   Assert(s.getType().isRealOrInt());
                 [ -  - ]
      25                 :       6704 :   d_vars.push_back(v);
      26                 :       6704 :   d_subs.push_back(s);
      27                 :       6704 : }
      28                 :            : 
      29                 :    1085786 : Node ArithSubs::applyArith(const Node& n, bool traverseNlMult) const
      30                 :            : {
      31         [ +  + ]:    1085786 :   if (d_vars.empty())
      32                 :            :   {
      33                 :      13292 :     return n;
      34                 :            :   }
      35                 :    1072494 :   NodeManager* nm = n.getNodeManager();
      36                 :    1072494 :   std::unordered_map<TNode, Node> visited;
      37                 :    1072494 :   std::vector<TNode> visit;
      38                 :    1072494 :   visit.push_back(n);
      39                 :            :   do
      40                 :            :   {
      41                 :    9347074 :     TNode cur = visit.back();
      42                 :    9347074 :     visit.pop_back();
      43                 :    9347074 :     auto it = visited.find(cur);
      44                 :            : 
      45         [ +  + ]:    9347074 :     if (it == visited.end())
      46                 :            :     {
      47                 :    6248676 :       visited[cur] = Node::null();
      48                 :    6248676 :       auto s = find(cur);
      49         [ +  + ]:    6248676 :       if (s)
      50                 :            :       {
      51                 :    1664333 :         visited[cur] = *s;
      52                 :            :       }
      53         [ +  + ]:    4584343 :       else if (cur.getNumChildren() == 0)
      54                 :            :       {
      55                 :    2001002 :         visited[cur] = cur;
      56                 :            :       }
      57                 :            :       else
      58                 :            :       {
      59         [ +  + ]:    2583341 :         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                 :      14523 :           visited[cur] = cur;
      65                 :            :         }
      66                 :            :         else
      67                 :            :         {
      68                 :    2568818 :           visit.push_back(cur);
      69         [ +  + ]:    8274580 :           for (const Node& cn : cur)
      70                 :            :           {
      71                 :    5705762 :             visit.push_back(cn);
      72                 :    5705762 :           }
      73                 :            :         }
      74                 :            :       }
      75                 :    6248676 :     }
      76         [ +  + ]:    3098398 :     else if (it->second.isNull())
      77                 :            :     {
      78                 :    2568818 :       Node ret = cur;
      79                 :    2568818 :       bool childChanged = false;
      80                 :    2568818 :       std::vector<Node> children;
      81         [ -  + ]:    2568818 :       if (cur.getMetaKind() == kind::metakind::PARAMETERIZED)
      82                 :            :       {
      83                 :          0 :         children.push_back(cur.getOperator());
      84                 :            :       }
      85         [ +  + ]:    8274580 :       for (const Node& cn : cur)
      86                 :            :       {
      87                 :    5705762 :         it = visited.find(cn);
      88 [ -  + ][ -  + ]:    5705762 :         Assert(it != visited.end());
                 [ -  - ]
      89 [ -  + ][ -  + ]:    5705762 :         Assert(!it->second.isNull());
                 [ -  - ]
      90 [ +  + ][ +  + ]:    5705762 :         childChanged = childChanged || cn != it->second;
      91                 :    5705762 :         children.push_back(it->second);
      92                 :    5705762 :       }
      93         [ +  + ]:    2568818 :       if (childChanged)
      94                 :            :       {
      95                 :    2530343 :         ret = nm->mkNode(cur.getKind(), children);
      96                 :            :       }
      97                 :    2568818 :       visited[cur] = ret;
      98                 :    2568818 :     }
      99         [ +  + ]:    9347074 :   } while (!visit.empty());
     100 [ -  + ][ -  + ]:    1072494 :   Assert(visited.find(n) != visited.end());
                 [ -  - ]
     101 [ -  + ][ -  + ]:    1072494 :   Assert(!visited.find(n)->second.isNull());
                 [ -  - ]
     102                 :    1072494 :   return visited[n];
     103                 :    1072494 : }
     104                 :            : 
     105                 :    2592499 : bool ArithSubs::shouldTraverse(const Node& n, bool traverseNlMult)
     106                 :            : {
     107                 :    2592499 :   Kind k = n.getKind();
     108                 :    2592499 :   TheoryId ctid = theory::kindToTheoryId(k);
     109                 :            :   // We always treat transcendental kinds as a black box.
     110                 :            :   // On the other hand, other extended operators e.g. IAND are treated similarly
     111                 :            :   // to multiplication.
     112 [ +  + ][ +  + ]:      33835 :   if ((ctid != THEORY_ARITH && ctid != THEORY_BOOL && ctid != THEORY_BUILTIN)
     113         [ +  + ]:    2582023 :       || isTranscendentalKind(k)
     114 [ +  + ][ +  + ]:    5184998 :       || (!traverseNlMult && (k == Kind::NONLINEAR_MULT || isExtendedNonLinearKind(k))))
         [ +  + ][ +  + ]
                 [ +  + ]
     115                 :            :   {
     116                 :      15831 :     return false;
     117                 :            :   }
     118                 :    2576668 :   return true;
     119                 :            : }
     120                 :            : 
     121                 :       2924 : bool ArithSubs::hasArithSubterm(TNode n, TNode t, bool traverseNlMult)
     122                 :            : {
     123                 :       2924 :   std::unordered_set<TNode> visited;
     124                 :       2924 :   std::vector<TNode> toProcess;
     125                 :       2924 :   toProcess.push_back(n);
     126                 :       2924 :   TNode cur;
     127                 :            :   do
     128                 :            :   {
     129                 :       3673 :     cur = toProcess.back();
     130                 :       3673 :     toProcess.pop_back();
     131         [ -  + ]:       3673 :     if (cur == t)
     132                 :            :     {
     133                 :          0 :       return true;
     134                 :            :     }
     135 [ +  + ][ +  + ]:       3673 :     if (!visited.insert(cur).second || !shouldTraverse(cur, traverseNlMult))
         [ +  + ][ +  + ]
                 [ -  - ]
     136                 :            :     {
     137                 :        159 :       continue;
     138                 :            :     }
     139                 :       3514 :     toProcess.insert(toProcess.end(), cur.begin(), cur.end());
     140         [ +  + ]:       3673 :   } while (!toProcess.empty());
     141                 :       2924 :   return false;
     142                 :       2924 : }
     143                 :            : 
     144                 :            : }  // namespace arith
     145                 :            : }  // namespace theory
     146                 :            : }  // namespace cvc5::internal