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                 :            :  * Node utilities for the arithmetic rewriter.
      11                 :            :  */
      12                 :            : 
      13                 :            : #include "cvc5_private.h"
      14                 :            : 
      15                 :            : #ifndef CVC5__THEORY__ARITH__REWRITER__NODE_UTILS_H
      16                 :            : #define CVC5__THEORY__ARITH__REWRITER__NODE_UTILS_H
      17                 :            : 
      18                 :            : #include "base/check.h"
      19                 :            : #include "expr/node.h"
      20                 :            : #include "util/integer.h"
      21                 :            : #include "util/rational.h"
      22                 :            : #include "util/real_algebraic_number.h"
      23                 :            : 
      24                 :            : namespace cvc5::internal {
      25                 :            : namespace theory {
      26                 :            : namespace arith {
      27                 :            : namespace rewriter {
      28                 :            : 
      29                 :            : /**
      30                 :            :  * Check whether the node is an arithmetic atom, that is one of LT, LEQ, EQUAL,
      31                 :            :  * GEQ, GT, IS_INTEGER, DIVISIBLE.
      32                 :            :  * Note that DISTINCT somehow belongs to this list, but should already be
      33                 :            :  * eliminated at this point.
      34                 :            :  */
      35                 :   37008309 : inline bool isAtom(TNode n)
      36                 :            : {
      37    [ +  - ][ + ]:   37008309 :   switch (n.getKind())
      38                 :            :   {
      39                 :   25482302 :     case Kind::LT:
      40                 :            :     case Kind::LEQ:
      41                 :            :     case Kind::EQUAL:
      42                 :            :     case Kind::GEQ:
      43                 :            :     case Kind::GT:
      44                 :            :     case Kind::IS_INTEGER:
      45                 :   25482302 :     case Kind::DIVISIBLE: return true;
      46                 :          0 :     case Kind::DISTINCT: Unreachable(); return false;
      47                 :   11526007 :     default: return false;
      48                 :            :   }
      49                 :            : }
      50                 :            : 
      51                 :            : /** Check whether the node wraps a real algebraic number. */
      52                 :    1364647 : inline bool isRAN(TNode n)
      53                 :            : {
      54                 :    1364647 :   return n.getKind() == Kind::REAL_ALGEBRAIC_NUMBER;
      55                 :            : }
      56                 :            : /** Retrieve the wrapped a real algebraic number. Asserts isRAN(n) */
      57                 :        961 : CVC5_NO_DANGLING inline const RealAlgebraicNumber& getRAN(TNode n)
      58                 :            : {
      59 [ -  + ][ -  + ]:        961 :   Assert(isRAN(n));
                 [ -  - ]
      60                 :        961 :   return n.getOperator().getConst<RealAlgebraicNumber>();
      61                 :            : }
      62                 :            : 
      63                 :            : /**
      64                 :            :  * Check whether the parent has a child that is a constant zero. If so, return
      65                 :            :  * this child. Otherwise, return std::nullopt. Works on any kind of iterable,
      66                 :            :  * i.e. both a node or a vector of nodes.
      67                 :            :  */
      68                 :            : template <typename Iterable>
      69                 :    2493158 : std::optional<TNode> getZeroChild(const Iterable& parent)
      70                 :            : {
      71 [ +  + ][ +  + ]:   11700846 :   for (const auto& node : parent)
      72                 :            :   {
      73 [ +  + ][ +  + ]:    5237859 :     if (node.isConst() && node.template getConst<Rational>().isZero())
                 [ +  + ]
      74                 :            :     {
      75                 :     122806 :       return node;
      76                 :            :     }
      77                 :            :   }
      78                 :    2370352 :   return {};
      79                 :            : }
      80                 :            : 
      81                 :            : /** Create a Boolean constant node */
      82                 :     861993 : inline Node mkConst(NodeManager* nm, bool value) { return nm->mkConst(value); }
      83                 :            : /** Create an integer constant node */
      84                 :       6160 : inline Node mkConst(NodeManager* nm, const Integer& value)
      85                 :            : {
      86                 :       6160 :   return nm->mkConstInt(value);
      87                 :            : }
      88                 :            : 
      89                 :            : /** Create a real algebraic number node */
      90                 :   24210145 : inline Node mkConst(NodeManager* nm, const RealAlgebraicNumber& value)
      91                 :            : {
      92                 :   24210145 :   return nm->mkRealAlgebraicNumber(value);
      93                 :            : }
      94                 :            : 
      95                 :            : /** Make a nonlinear multiplication from the given factors */
      96                 :   21301561 : inline Node mkNonlinearMult(NodeManager* nm, const std::vector<Node>& factors)
      97                 :            : {
      98    [ +  + ][ + ]:   21301561 :   switch (factors.size())
      99                 :            :   {
     100                 :   13105596 :     case 0: return nm->mkConstInt(Rational(1));
     101                 :   13034817 :     case 1: return factors[0];
     102                 :    1713946 :     default: return nm->mkNode(Kind::NONLINEAR_MULT, factors);
     103                 :            :   }
     104                 :            : }
     105                 :            : 
     106                 :            : /**
     107                 :            :  * Create the product of `multiplicity * monomial`. Assumes that the monomial is
     108                 :            :  * either a product of non-values (neither rational nor real algebraic numbers)
     109                 :            :  * or a rational constant.
     110                 :            :  * If the monomial is a constant, return the product of the two numbers. If the
     111                 :            :  * multiplicity is one, return the monomial. Otherwise return `(MULT
     112                 :            :  * multiplicity monomial)`.
     113                 :            :  */
     114                 :            : Node mkMultTerm(const Rational& multiplicity, TNode monomial);
     115                 :            : 
     116                 :            : /**
     117                 :            :  * Create the product of `multiplicity * monomial`. Assumes that the monomial is
     118                 :            :  * either a product of non-values (neither rational nor real algebraic numbers)
     119                 :            :  * or a rational constant.
     120                 :            :  * If multiplicity is rational, defer to the appropriate overload. If the
     121                 :            :  * monomial is one, return the product of the two numbers. Otherwise return the
     122                 :            :  * nonlinear product of the two, i.e. `(NONLINEAR_MULT multiplicity *monomial)`.
     123                 :            :  */
     124                 :            : Node mkMultTerm(const RealAlgebraicNumber& multiplicity, TNode monomial);
     125                 :            : 
     126                 :            : /**
     127                 :            :  * Create the product of `multiplicity * monomial`, where the monomial is given
     128                 :            :  * as the (implicitly multiplied, possibly unsorted) list of children. Assumes
     129                 :            :  * that monomial is either empty (implicitly one) or  a list of non-values
     130                 :            :  * (neither rational nor real algebraic numbers). If multiplicity is rational,
     131                 :            :  * sort the monomial, create a nonlinear mult term and defer to the appropriate
     132                 :            :  * overload. Otherwise return the nonlinear product of the two, i.e.
     133                 :            :  * `(NONLINEAR_MULT multiplicity *monomial)`. The monomial is taken as rvalue as
     134                 :            :  * it may be modified in the process.
     135                 :            :  *
     136                 :            :  */
     137                 :            : Node mkMultTerm(NodeManager* nm,
     138                 :            :                 const RealAlgebraicNumber& multiplicity,
     139                 :            :                 std::vector<Node>&& monomial);
     140                 :            : 
     141                 :            : /**
     142                 :            :  * Remove TO_REAL from t, returns t[0] if t has kind TO_REAL.
     143                 :            :  */
     144                 :            : TNode removeToReal(TNode t);
     145                 :            : /**
     146                 :            :  * Ensure that t has real type if tn is the real type. Do so by applying
     147                 :            :  * TO_REAL to t.
     148                 :            :  */
     149                 :            : Node maybeEnsureReal(TypeNode tn, TNode t);
     150                 :            : /** Same as above, without a check for the type of tn. */
     151                 :            : Node ensureReal(TNode t);
     152                 :            : 
     153                 :            : }  // namespace rewriter
     154                 :            : }  // namespace arith
     155                 :            : }  // namespace theory
     156                 :            : }  // namespace cvc5::internal
     157                 :            : 
     158                 :            : #endif