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                 :            :  * The theory of uninterpreted functions (UF)
      11                 :            :  */
      12                 :            : 
      13                 :            : #include "cvc5_private.h"
      14                 :            : 
      15                 :            : #ifndef CVC5__THEORY__UF__THEORY_UF_H
      16                 :            : #define CVC5__THEORY__UF__THEORY_UF_H
      17                 :            : 
      18                 :            : #include "expr/node.h"
      19                 :            : #include "theory/care_pair_argument_callback.h"
      20                 :            : #include "theory/theory.h"
      21                 :            : #include "theory/theory_eq_notify.h"
      22                 :            : #include "theory/theory_state.h"
      23                 :            : #include "theory/uf/diamonds_proof_generator.h"
      24                 :            : #include "theory/uf/distinct_extension.h"
      25                 :            : #include "theory/uf/proof_checker.h"
      26                 :            : #include "theory/uf/symmetry_breaker.h"
      27                 :            : #include "theory/uf/theory_uf_rewriter.h"
      28                 :            : 
      29                 :            : namespace cvc5::internal {
      30                 :            : namespace theory {
      31                 :            : namespace uf {
      32                 :            : 
      33                 :            : class CardinalityExtension;
      34                 :            : class HoExtension;
      35                 :            : class ConversionsSolver;
      36                 :            : class LambdaLift;
      37                 :            : 
      38                 :            : class TheoryUF : public Theory
      39                 :            : {
      40                 :            :  public:
      41                 :            :   class NotifyClass : public TheoryEqNotifyClass
      42                 :            :   {
      43                 :            :    public:
      44                 :      51315 :     NotifyClass(TheoryInferenceManager& im, TheoryUF& uf)
      45                 :      51315 :         : TheoryEqNotifyClass(im), d_uf(uf)
      46                 :            :     {
      47                 :      51315 :     }
      48                 :            : 
      49                 :     793438 :     void eqNotifyNewClass(TNode t) override
      50                 :            :     {
      51         [ +  - ]:    1586876 :       Trace("uf-notify") << "NotifyClass::eqNotifyNewClass(" << t << ")"
      52                 :     793438 :                          << std::endl;
      53                 :     793438 :       d_uf.eqNotifyNewClass(t);
      54                 :     793438 :     }
      55                 :            : 
      56                 :    9728503 :     void eqNotifyMerge(TNode t1, TNode t2) override
      57                 :            :     {
      58         [ +  - ]:   19457006 :       Trace("uf-notify") << "NotifyClass::eqNotifyMerge(" << t1 << ", " << t2
      59                 :    9728503 :                          << ")" << std::endl;
      60                 :    9728503 :       d_uf.eqNotifyMerge(t1, t2);
      61                 :    9728503 :     }
      62                 :            : 
      63                 :    1537900 :     void eqNotifyDisequal(TNode t1, TNode t2, TNode reason) override
      64                 :            :     {
      65         [ +  - ]:    3075800 :       Trace("uf-notify") << "NotifyClass::eqNotifyDisequal(" << t1 << ", " << t2
      66                 :    1537900 :                          << ", " << reason << ")" << std::endl;
      67                 :    1537900 :       d_uf.eqNotifyDisequal(t1, t2, reason);
      68                 :    1537900 :     }
      69                 :            : 
      70                 :            :    private:
      71                 :            :     /** Reference to the parent theory */
      72                 :            :     TheoryUF& d_uf;
      73                 :            :   }; /* class TheoryUF::NotifyClass */
      74                 :            : 
      75                 :            :  private:
      76                 :            :   /** The associated cardinality extension (or nullptr if it does not exist) */
      77                 :            :   std::unique_ptr<CardinalityExtension> d_thss;
      78                 :            :   /** the lambda lifting utility */
      79                 :            :   std::unique_ptr<LambdaLift> d_lambdaLift;
      80                 :            :   /** the higher-order solver extension (or nullptr if it does not exist) */
      81                 :            :   std::unique_ptr<HoExtension> d_ho;
      82                 :            :   /** the conversions solver */
      83                 :            :   std::unique_ptr<ConversionsSolver> d_csolver;
      84                 :            :   /** Diamonds proof generator */
      85                 :            :   DiamondsProofGenerator d_dpfgen;
      86                 :            : 
      87                 :            :   /** node for true */
      88                 :            :   Node d_true;
      89                 :            : 
      90                 :            :   /** All the function terms that the theory has seen */
      91                 :            :   context::CDList<TNode> d_functionsTerms;
      92                 :            : 
      93                 :            :   /** Symmetry analyzer */
      94                 :            :   SymmetryBreaker d_symb;
      95                 :            : 
      96                 :            :   /** called when a new equivalance class is created */
      97                 :            :   void eqNotifyNewClass(TNode t);
      98                 :            : 
      99                 :            :   /** called when two equivalance classes have merged */
     100                 :            :   void eqNotifyMerge(TNode t1, TNode t2);
     101                 :            : 
     102                 :            :   /** called when two equivalence classes are made disequal */
     103                 :            :   void eqNotifyDisequal(TNode t1, TNode t2, TNode reason);
     104                 :            : 
     105                 :            :  public:
     106                 :            :   /** Constructs a new instance of TheoryUF w.r.t. the provided context.*/
     107                 :            :   TheoryUF(Env& env,
     108                 :            :            OutputChannel& out,
     109                 :            :            Valuation valuation,
     110                 :            :            std::string instanceName = "");
     111                 :            : 
     112                 :            :   ~TheoryUF();
     113                 :            : 
     114                 :            :   //--------------------------------- initialization
     115                 :            :   /** get the official theory rewriter of this theory */
     116                 :            :   TheoryRewriter* getTheoryRewriter() override;
     117                 :            :   /** get the proof checker of this theory */
     118                 :            :   ProofRuleChecker* getProofChecker() override;
     119                 :            :   /**
     120                 :            :    * Returns true if we need an equality engine. If so, we initialize the
     121                 :            :    * information regarding how it should be setup. For details, see the
     122                 :            :    * documentation in Theory::needsEqualityEngine.
     123                 :            :    */
     124                 :            :   bool needsEqualityEngine(EeSetupInfo& esi) override;
     125                 :            :   /** finish initialization */
     126                 :            :   void finishInit() override;
     127                 :            :   //--------------------------------- end initialization
     128                 :            : 
     129                 :            :   //--------------------------------- standard check
     130                 :            :   /** Do we need a check call at last call effort? */
     131                 :            :   bool needsCheckLastEffort() override;
     132                 :            :   /** Post-check, called after the fact queue of the theory is processed. */
     133                 :            :   void postCheck(Effort level) override;
     134                 :            :   /** Notify fact */
     135                 :            :   void notifyFact(TNode atom, bool pol, TNode fact, bool isInternal) override;
     136                 :            :   //--------------------------------- end standard check
     137                 :            : 
     138                 :            :   /** Collect model values in m based on the relevant terms given by termSet */
     139                 :            :   bool collectModelValues(TheoryModel* m,
     140                 :            :                           const std::set<Node>& termSet) override;
     141                 :            : 
     142                 :            :   TrustNode ppRewrite(TNode node, std::vector<SkolemLemma>& lems) override;
     143                 :            :   void preRegisterTerm(TNode term) override;
     144                 :            :   TrustNode explain(TNode n) override;
     145                 :            : 
     146                 :            :   void ppStaticLearn(TNode in, std::vector<TrustNode>& learned) override;
     147                 :            :   void presolve() override;
     148                 :            : 
     149                 :            :   void computeCareGraph() override;
     150                 :            : 
     151                 :            :   EqualityStatus getEqualityStatus(TNode a, TNode b) override;
     152                 :            : 
     153                 :          0 :   std::string identify() const override { return "THEORY_UF"; }
     154                 :            : 
     155                 :            :  private:
     156                 :            :   /** Called when preregistering terms of kind APPLY_UF or HO_APPLY */
     157                 :            :   void preRegisterFunctionTerm(TNode node);
     158                 :            :   /** Explain why this literal is true by building an explanation */
     159                 :            :   void explain(TNode literal, Node& exp);
     160                 :            : 
     161                 :            :   /** Overrides to ensure that pairs of lambdas are not considered disequal. */
     162                 :            :   bool areCareDisequal(TNode x, TNode y) override;
     163                 :            :   /**
     164                 :            :    * Overrides to use the theory state instead of the equality engine, since
     165                 :            :    * for higher-order, some terms that do not occur in the equality engine are
     166                 :            :    * considered.
     167                 :            :    */
     168                 :            :   void processCarePairArgs(TNode a, TNode b) override;
     169                 :            :   /**
     170                 :            :    * Compute relevant terms. Used in higher-order.
     171                 :            :    */
     172                 :            :   void computeRelevantTerms(std::set<Node>& termSet) override;
     173                 :            :   /**
     174                 :            :    * Is t a higher order type? A higher-order type is a function type having
     175                 :            :    * an argument type that is also a function type. This is used for checking
     176                 :            :    * logic exceptions.
     177                 :            :    */
     178                 :            :   bool isHigherOrderType(TypeNode tn);
     179                 :            :   TheoryUfRewriter d_rewriter;
     180                 :            :   /** Proof rule checker */
     181                 :            :   UfProofRuleChecker d_checker;
     182                 :            :   /** A (default) theory state object */
     183                 :            :   TheoryState d_state;
     184                 :            :   /** A (default) inference manager */
     185                 :            :   TheoryInferenceManager d_im;
     186                 :            :   /** the distinct extension */
     187                 :            :   DistinctExtension d_distinct;
     188                 :            :   /** The notify class */
     189                 :            :   NotifyClass d_notify;
     190                 :            :   /** Cache for isHigherOrderType */
     191                 :            :   std::map<TypeNode, bool> d_isHoType;
     192                 :            :   /** The care pair argument callback, used for theory combination */
     193                 :            :   CarePairArgumentCallback d_cpacb;
     194                 :            : }; /* class TheoryUF */
     195                 :            : 
     196                 :            : }  // namespace uf
     197                 :            : }  // namespace theory
     198                 :            : }  // namespace cvc5::internal
     199                 :            : 
     200                 :            : #endif /* CVC5__THEORY__UF__THEORY_UF_H */