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                 :            :  * candidate_rewrite_database
      11                 :            :  */
      12                 :            : 
      13                 :            : #include "cvc5_private.h"
      14                 :            : 
      15                 :            : #ifndef CVC5__THEORY__QUANTIFIERS__CANDIDATE_REWRITE_DATABASE_H
      16                 :            : #define CVC5__THEORY__QUANTIFIERS__CANDIDATE_REWRITE_DATABASE_H
      17                 :            : 
      18                 :            : #include <vector>
      19                 :            : 
      20                 :            : #include "options/options.h"
      21                 :            : #include "theory/quantifiers/candidate_rewrite_filter.h"
      22                 :            : #include "theory/quantifiers/expr_miner.h"
      23                 :            : #include "theory/quantifiers/sygus_sampler.h"
      24                 :            : 
      25                 :            : namespace cvc5::internal {
      26                 :            : namespace theory {
      27                 :            : namespace quantifiers {
      28                 :            : 
      29                 :            : /** CandidateRewriteDatabase
      30                 :            :  *
      31                 :            :  * This maintains the necessary data structures for generating a database
      32                 :            :  * of candidate rewrite rules (see Noetzli et al "Syntax-Guided Rewrite Rule
      33                 :            :  * Enumeration for SMT Solvers" SAT 2019). The primary responsibilities
      34                 :            :  * of this class are to perform the "equivalence checking" and "congruence
      35                 :            :  * and matching filtering" in Figure 1. The equivalence checking is done
      36                 :            :  * through a combination of the sygus sampler object owned by this class
      37                 :            :  * and the calls made to copies of the SolverEngine in ::addTerm. The rewrite
      38                 :            :  * rule filtering (based on congruence, matching, variable ordering) is also
      39                 :            :  * managed by the sygus sampler object.
      40                 :            :  */
      41                 :            : class CandidateRewriteDatabase : public ExprMiner
      42                 :            : {
      43                 :            :  public:
      44                 :            :   /**
      45                 :            :    * Constructor
      46                 :            :    * @param env Reference to the environment
      47                 :            :    * @param doCheck Whether to check rewrite rules using subsolvers.
      48                 :            :    * @param rewAccel Whether to construct symmetry breaking lemmas based on
      49                 :            :    * discovered rewrites (see option sygusRewSynthAccel()).
      50                 :            :    * @param filterPairs Whether to filter rewrite pairs using filtering
      51                 :            :    * techniques from the SAT 2019 paper above.
      52                 :            :    * @param rec Whether we are recursively finding rules for all subterms
      53                 :            :    * added to this class
      54                 :            :    */
      55                 :            :   CandidateRewriteDatabase(Env& env,
      56                 :            :                            bool doCheck,
      57                 :            :                            bool rewAccel = false,
      58                 :            :                            bool filterPairs = true,
      59                 :            :                            bool rec = false);
      60                 :        330 :   ~CandidateRewriteDatabase() {}
      61                 :            :   /**  Initialize this class */
      62                 :            :   void initialize(const std::vector<Node>& var, SygusSampler* ss) override;
      63                 :            :   /**  Initialize this class
      64                 :            :    *
      65                 :            :    * Serves the same purpose as the above function, but we will be using
      66                 :            :    * sygus to enumerate terms and generate samples.
      67                 :            :    *
      68                 :            :    * tds : pointer to sygus term database. We use the extended rewriter of this
      69                 :            :    * database when computing candidate rewrites,
      70                 :            :    * f : a term of some SyGuS datatype type whose values we will be
      71                 :            :    * testing under the free variables in the grammar of f. This is the
      72                 :            :    * "candidate variable" CegConjecture::d_candidates.
      73                 :            :    */
      74                 :            :   void initializeSygus(const std::vector<Node>& vars,
      75                 :            :                        TermDbSygus* tds,
      76                 :            :                        Node f,
      77                 :            :                        SygusSampler* ss);
      78                 :            :   /** add term
      79                 :            :    *
      80                 :            :    * Notifies this class that the solution sol was enumerated. This may
      81                 :            :    * cause a candidate-rewrite to be printed on the output stream out.
      82                 :            :    *
      83                 :            :    * @param sol The term to add to this class.
      84                 :            :    * @param rewrites The set of rewrite rules discovered on this call.
      85                 :            :    * @return A previous term eq_sol added to this class, such that sol is
      86                 :            :    * equivalent to eq_sol based on the criteria used by this class. We return
      87                 :            :    * only terms that are verified to be equivalent to sol.
      88                 :            :    */
      89                 :            :   Node addOrGetTerm(Node sol, std::vector<Node>& rewrites);
      90                 :            :   /**
      91                 :            :    * Same as above, returns true if the return value of addTerm was equal to
      92                 :            :    * sol, in other words, sol was a new unique term. This assumes false for
      93                 :            :    * the argument rec.
      94                 :            :    */
      95                 :            :   bool addTerm(Node sol, std::vector<Node>& rewrites) override;
      96                 :            :   /** Enable the (extended) rewriter for this class */
      97                 :            :   void enableExtendedRewriter();
      98                 :            :   /** Was the given rewrite verified? */
      99                 :            :   bool wasVerified(const Node& rewrite) const;
     100                 :            : 
     101                 :            :  private:
     102                 :            :   /** (required) pointer to the sygus term database of d_qe */
     103                 :            :   TermDbSygus* d_tds;
     104                 :            :   /** Whether we use the extended rewriter */
     105                 :            :   bool d_useExtRewriter;
     106                 :            :   /** the function-to-synthesize we are testing (if sygus) */
     107                 :            :   Node d_candidate;
     108                 :            :   /** whether we are checking equivalence using subsolver */
     109                 :            :   bool d_doCheck;
     110                 :            :   /**
     111                 :            :    * If true, we use acceleration for symmetry breaking rewrites (see option
     112                 :            :    * sygusRewSynthAccel()).
     113                 :            :    */
     114                 :            :   bool d_rewAccel;
     115                 :            :   /** if true, we filter pairs of terms to check equivalence */
     116                 :            :   bool d_filterPairs;
     117                 :            :   /** whether we are using sygus */
     118                 :            :   bool d_using_sygus;
     119                 :            :   /** Whether we check rewrite rules for all subterms added to this class */
     120                 :            :   bool d_rec;
     121                 :            :   /** candidate rewrite filter */
     122                 :            :   CandidateRewriteFilter d_crewrite_filter;
     123                 :            :   /** the cache for results of addTerm */
     124                 :            :   std::unordered_map<Node, Node> d_add_term_cache;
     125                 :            :   /** The options for subsolver calls */
     126                 :            :   Options d_subOptions;
     127                 :            :   /** The set of rewrites that succeeded verification */
     128                 :            :   std::unordered_set<Node> d_verified;
     129                 :            : };
     130                 :            : 
     131                 :            : }  // namespace quantifiers
     132                 :            : }  // namespace theory
     133                 :            : }  // namespace cvc5::internal
     134                 :            : 
     135                 :            : #endif /* CVC5__THEORY__QUANTIFIERS__CANDIDATE_REWRITE_DATABASE_H */