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                 :            :  * CaDiCaL proof tracer.
      11                 :            :  *
      12                 :            :  * Implementation of a CaDiCaL proof tracer.
      13                 :            :  */
      14                 :            : 
      15                 :            : #ifndef CVC5__PROP__CADICAL__PROOF_TRACER_H
      16                 :            : #define CVC5__PROP__CADICAL__PROOF_TRACER_H
      17                 :            : 
      18                 :            : #include <cadical/tracer.hpp>
      19                 :            : #include <cstdint>
      20                 :            : #include <unordered_map>
      21                 :            : #include <vector>
      22                 :            : 
      23                 :            : #include "proof/proof_node.h"
      24                 :            : #include "prop/sat_solver_types.h"
      25                 :            : #include "prop/theory_proxy.h"
      26                 :            : 
      27                 :            : namespace cvc5::internal::prop::cadical {
      28                 :            : 
      29                 :            : class CadicalPropagator;
      30                 :            : 
      31                 :            : /**
      32                 :            :  * Proof tracer implementation for tracing CaDiCaL LRUP proofs.
      33                 :            :  *
      34                 :            :  * This tracer keeps track of the original clauses sent to CaDiCaL (input
      35                 :            :  * clauses and theory lemmas) as well as derived clauses and their
      36                 :            :  * antecedents. All input clauses added during solving are considered theory
      37                 :            :  * lemmas.
      38                 :            :  *
      39                 :            :  * When the empty clause (ProofTracer::conclude_unsat) is derived we store
      40                 :            :  * the final clause ids that were used to derive the empty clause in
      41                 :            :  * d_final_clauses. The input clauses that are reachable from the
      42                 :            :  * final clause ids through the stored antecedents correspond to the unsat core.
      43                 :            :  */
      44                 :            : 
      45                 :            : class ProofTracer : public CaDiCaL::Tracer
      46                 :            : {
      47                 :            :  public:
      48                 :            :   enum class ClauseType : uint8_t
      49                 :            :   {
      50                 :            :     ASSUMPTION,  // assumption clause
      51                 :            :     INPUT,       // input clause
      52                 :            :     THEORY,      // theory lemma
      53                 :            :     DERIVED,     // derived clause
      54                 :            :   };
      55                 :            : 
      56                 :            :   struct ClauseInfo
      57                 :            :   {
      58                 :            :     ClauseInfo() = default;
      59                 :      13784 :     ClauseInfo(uint64_t id,
      60                 :            :                ClauseType ctype,
      61                 :            :                const std::vector<int32_t>& lits,
      62                 :            :                const std::vector<uint64_t>& ants = {})
      63                 :      13784 :         : clause_id(id), type(ctype), literals(lits), antecedents(ants)
      64                 :            :     {
      65                 :      13784 :     }
      66                 :            : 
      67                 :            :     uint64_t clause_id;
      68                 :            :     ClauseType type;
      69                 :            :     std::vector<int32_t> literals;
      70                 :            :     std::vector<uint64_t> antecedents;
      71                 :            :   };
      72                 :            : 
      73                 :            :   ProofTracer(const CadicalPropagator& propagator);
      74                 :            : 
      75                 :            :   void add_original_clause(uint64_t clause_id,
      76                 :            :                            bool redundant,
      77                 :            :                            const std::vector<int>& clause,
      78                 :            :                            bool restored) override;
      79                 :            : 
      80                 :            :   void add_derived_clause(uint64_t clause_id,
      81                 :            :                           bool redundant,
      82                 :            :                           const std::vector<int>& clause,
      83                 :            :                           const std::vector<uint64_t>& antecedents) override;
      84                 :            : 
      85                 :            :   void add_assumption_clause(uint64_t clause_id,
      86                 :            :                              const std::vector<int>& clause,
      87                 :            :                              const std::vector<uint64_t>& antecedents) override;
      88                 :            : 
      89                 :            :   void conclude_unsat(CaDiCaL::ConclusionType type,
      90                 :            :                       const std::vector<uint64_t>& clause_ids) override;
      91                 :            : 
      92                 :            :   /**
      93                 :            :    * Backwards traversal of clausal proof starting from the empty clause.
      94                 :            :    * @param core Proof core containing visited clause ids.
      95                 :            :    */
      96                 :            :   void compute_proof_core(std::vector<uint64_t>& core) const;
      97                 :            : 
      98                 :            :   /**
      99                 :            :    * Generates the chain resolution proof from CaDiCaL's LRUP proof.
     100                 :            :    */
     101                 :            :   std::shared_ptr<ProofNode> get_chain_resolution_proof(ProofNodeManager* pnm,
     102                 :            :                                                         NodeManager* nm,
     103                 :            :                                                         TheoryProxy* proxy);
     104                 :            : 
     105                 :            :  private:
     106                 :            :   /**
     107                 :            :    * Helper to find pivot literals.
     108                 :            :    * @param marked_vars Cache of already marked variables.
     109                 :            :    * @param lit Current literal to mark.
     110                 :            :    * @return Whether other polarity of given literal has been already marked.
     111                 :            :    */
     112                 :            :   bool mark_var(std::unordered_map<int32_t, uint8_t>& marked_vars, int32_t lit);
     113                 :            : 
     114                 :            :   /**
     115                 :            :    * Helper to produce chain resolution proof step for a derived clause.
     116                 :            :    *
     117                 :            :    * Produces a chain resolution proof step for the given derived clause cid.
     118                 :            :    * From the extracted SAT proof core we get that a clause C was derived by
     119                 :            :    * resolving antecedents A0,...,An. For each resolution step in the chain we
     120                 :            :    * compute the pivot literal and its polarity, starting by resolving An and
     121                 :            :    * An-1 (backwards resolution). The children of this chain resolution step are
     122                 :            :    * the proof steps of each antecedent, i.e., steps[A0],...,steps[An]. The
     123                 :            :    * arguments are the pivot literals and their polarities and the derived
     124                 :            :    * clause C as a node.
     125                 :            :    *
     126                 :            :    *              steps[A0],...,steps[An] | C,(polarities...),(pivots...)
     127                 :            :    * CHAIN_M_RES --------------------------------------------------------
     128                 :            :    *                                   steps[cid]
     129                 :            :    *
     130                 :            :    * @param cid Clause id of derived clause to produce proof step for.
     131                 :            :    * @param proxy Theory proxy to get node mapping.
     132                 :            :    * @param pnm Proof node manager instance.
     133                 :            :    * @param nm Node manager instance.
     134                 :            :    * @param steps Maps derived clauses to chain resolution proof step that
     135                 :            :    *              derived that clause.
     136                 :            :    * @param activation_literals Set of current activation literals, used to
     137                 :            :    *                            filter out from clauses as they are only
     138                 :            :    *                            relevant for push/pop.
     139                 :            :    * @return A chain resolution step for producing clause cid.
     140                 :            :    */
     141                 :            :   std::shared_ptr<ProofNode> chain_resolution_step(
     142                 :            :       uint64_t cid,
     143                 :            :       TheoryProxy* proxy,
     144                 :            :       ProofNodeManager* pnm,
     145                 :            :       NodeManager* nm,
     146                 :            :       const std::unordered_map<uint64_t, std::shared_ptr<ProofNode>>& steps,
     147                 :            :       const std::unordered_set<int64_t>& activation_literals);
     148                 :            : 
     149                 :            :   const CadicalPropagator& d_propagator;
     150                 :            :   /** Maps clause ids to clause info. */
     151                 :            :   std::unordered_map<uint64_t, ClauseInfo> d_clauses;
     152                 :            :   /** Stores the final clause ids used to conclude unsat. */
     153                 :            :   std::vector<uint64_t> d_final_clauses;
     154                 :            : };
     155                 :            : 
     156                 :            : }  // namespace cvc5::internal::prop::cadical
     157                 :            : 
     158                 :            : #endif