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                 :            :  * Builtin proof checker utility.
      11                 :            :  */
      12                 :            : 
      13                 :            : #include "cvc5_private.h"
      14                 :            : 
      15                 :            : #ifndef CVC5__THEORY__BUILTIN__PROOF_CHECKER_H
      16                 :            : #define CVC5__THEORY__BUILTIN__PROOF_CHECKER_H
      17                 :            : 
      18                 :            : #include "expr/node.h"
      19                 :            : #include "proof/method_id.h"
      20                 :            : #include "proof/proof_checker.h"
      21                 :            : #include "proof/proof_node.h"
      22                 :            : 
      23                 :            : namespace cvc5::internal {
      24                 :            : 
      25                 :            : class Env;
      26                 :            : 
      27                 :            : namespace theory {
      28                 :            : 
      29                 :            : class Rewriter;
      30                 :            : 
      31                 :            : namespace builtin {
      32                 :            : 
      33                 :            : /** A checker for builtin proofs */
      34                 :            : class BuiltinProofRuleChecker : public ProofRuleChecker
      35                 :            : {
      36                 :            :  public:
      37                 :            :   /** Constructor. */
      38                 :            :   BuiltinProofRuleChecker(NodeManager* nm, Rewriter* r, Env& env);
      39                 :            :   /** Destructor. */
      40                 :      50866 :   ~BuiltinProofRuleChecker() {}
      41                 :            :   /**
      42                 :            :    * Get substitution for literal exp. Updates vars/subs to the substitution
      43                 :            :    * specified by exp for the substitution method ids.
      44                 :            :    */
      45                 :            :   static bool getSubstitutionForLit(Node exp,
      46                 :            :                                     TNode& var,
      47                 :            :                                     TNode& subs,
      48                 :            :                                     MethodId ids = MethodId::SB_DEFAULT);
      49                 :            :   /**
      50                 :            :    * Get substitution for formula exp. Adds to vars/subs to the substitution
      51                 :            :    * specified by exp for the substitution method ids, which may be multiple
      52                 :            :    * substitutions if exp is of kind AND and ids is SB_DEFAULT (note the other
      53                 :            :    * substitution types always interpret applications of AND as a formula).
      54                 :            :    * The vector "from" are the literals from exp that each substitution in
      55                 :            :    * vars/subs are based on. For example, if exp is (and (= x t) (= y s)), then
      56                 :            :    * vars = { x, y }, subs = { t, s }, from = { (= x y), (= y s) }.
      57                 :            :    */
      58                 :            :   static bool getSubstitutionFor(Node exp,
      59                 :            :                                  std::vector<TNode>& vars,
      60                 :            :                                  std::vector<TNode>& subs,
      61                 :            :                                  std::vector<TNode>& from,
      62                 :            :                                  MethodId ids = MethodId::SB_DEFAULT);
      63                 :            : 
      64                 :            :   /**
      65                 :            :    * Apply substitution on n in skolem form. This encapsulates the exact
      66                 :            :    * behavior of a SUBS step in a proof.
      67                 :            :    *
      68                 :            :    * @param n The node to substitute,
      69                 :            :    * @param exp The (set of) equalities/literals/formulas that the substitution
      70                 :            :    * is derived from
      71                 :            :    * @param ids The method identifier of the substitution, by default SB_DEFAULT
      72                 :            :    * specifying that lhs/rhs of equalities are interpreted as a substitution.
      73                 :            :    * @param ida The method identifier of the substitution application, by
      74                 :            :    * default SB_SEQUENTIAL specifying that substitutions are to be applied
      75                 :            :    * sequentially
      76                 :            :    * @return The substituted form of n.
      77                 :            :    */
      78                 :            :   static Node applySubstitution(Node n,
      79                 :            :                                 Node exp,
      80                 :            :                                 MethodId ids = MethodId::SB_DEFAULT,
      81                 :            :                                 MethodId ida = MethodId::SBA_SEQUENTIAL);
      82                 :            :   static Node applySubstitution(Node n,
      83                 :            :                                 const std::vector<Node>& exp,
      84                 :            :                                 MethodId ids = MethodId::SB_DEFAULT,
      85                 :            :                                 MethodId ida = MethodId::SBA_SEQUENTIAL);
      86                 :            :   /** Apply substitution + rewriting
      87                 :            :    *
      88                 :            :    * Combines the above two steps.
      89                 :            :    *
      90                 :            :    * @param n The node to substitute and rewrite,
      91                 :            :    * @param exp The (set of) equalities corresponding to the substitution
      92                 :            :    * @param ids The method identifier of the substitution.
      93                 :            :    * @param ida The method identifier of the substitution application.
      94                 :            :    * @param idr The method identifier of the rewriter.
      95                 :            :    * @return The substituted, rewritten form of n.
      96                 :            :    */
      97                 :            :   Node applySubstitutionRewrite(Node n,
      98                 :            :                                 const std::vector<Node>& exp,
      99                 :            :                                 MethodId ids = MethodId::SB_DEFAULT,
     100                 :            :                                 MethodId ida = MethodId::SBA_SEQUENTIAL,
     101                 :            :                                 MethodId idr = MethodId::RW_REWRITE);
     102                 :            : 
     103                 :            :   /** get a TheoryId from a node, return false if we fail */
     104                 :            :   static bool getTheoryId(TNode n, TheoryId& tid);
     105                 :            :   /** Make a TheoryId into a node */
     106                 :            :   static Node mkTheoryIdNode(NodeManager* nm, TheoryId tid);
     107                 :            :   /**
     108                 :            :    * @param nm The node manager.
     109                 :            :    * @param n The term to rewrite via ENCODE_EQ_INTRO.
     110                 :            :    * @return The right hand side of the equality concluded by ENCODE_EQ_INTRO
     111                 :            :    * for n.
     112                 :            :    */
     113                 :            :   static Node getEncodeEqIntro(NodeManager* nm, const Node& n);
     114                 :            : 
     115                 :            :   /** Register all rules owned by this rule checker into pc. */
     116                 :            :   void registerTo(ProofChecker* pc) override;
     117                 :            : 
     118                 :            :  protected:
     119                 :            :   /** Return the conclusion of the given proof step, or null if it is invalid */
     120                 :            :   Node checkInternal(ProofRule id,
     121                 :            :                      const std::vector<Node>& children,
     122                 :            :                      const std::vector<Node>& args) override;
     123                 :            : 
     124                 :            :  private:
     125                 :            :   /**
     126                 :            :    * Pointer to the rewriter. Necessary since this uses the rewriter as an
     127                 :            :    * oracle for proof checking.
     128                 :            :    */
     129                 :            :   Rewriter* d_rewriter;
     130                 :            :   /** Reference to the environment. */
     131                 :            :   Env& d_env;
     132                 :            :   /** Pointer to the rewrite database */
     133                 :            :   rewriter::RewriteDb* d_rdb;
     134                 :            : };
     135                 :            : 
     136                 :            : }  // namespace builtin
     137                 :            : }  // namespace theory
     138                 :            : }  // namespace cvc5::internal
     139                 :            : 
     140                 :            : #endif /* CVC5__THEORY__BUILTIN__PROOF_CHECKER_H */