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                 :            :  * A utility for converting proof nodes.
      11                 :            :  */
      12                 :            : 
      13                 :            : #include "proof/proof_node_converter.h"
      14                 :            : 
      15                 :            : #include "proof/proof.h"
      16                 :            : 
      17                 :            : namespace cvc5::internal {
      18                 :            : 
      19                 :      13695 : ProofNodeConverterCallback::ProofNodeConverterCallback() {}
      20                 :      13695 : ProofNodeConverterCallback::~ProofNodeConverterCallback() {}
      21                 :          0 : bool ProofNodeConverterCallback::shouldConvert(
      22                 :            :     CVC5_UNUSED std::shared_ptr<ProofNode> pn)
      23                 :            : {
      24                 :          0 :   return false;
      25                 :            : }
      26                 :            : 
      27                 :      13695 : ProofNodeConverter::ProofNodeConverter(Env& env,
      28                 :            :                                        ProofNodeConverterCallback& cb,
      29                 :      13695 :                                        CVC5_UNUSED bool autoSym)
      30                 :      13695 :     : EnvObj(env), d_cb(cb)
      31                 :            : {
      32                 :      13695 : }
      33                 :            : 
      34                 :      13695 : std::shared_ptr<ProofNode> ProofNodeConverter::process(
      35                 :            :     std::shared_ptr<ProofNode> pf)
      36                 :            : {
      37                 :            :   // The list of proof nodes we are currently traversing beneath. This is used
      38                 :            :   // for checking for cycles in the overall proof.
      39                 :      13695 :   std::vector<std::shared_ptr<ProofNode>> traversing;
      40                 :      13695 :   std::shared_ptr<ProofNode> pft = pf;
      41         [ +  - ]:      13695 :   Trace("pf-convert") << "ProofNodeConverter::process" << std::endl;
      42                 :            :   std::unordered_map<std::shared_ptr<ProofNode>, std::shared_ptr<ProofNode>>
      43                 :      13695 :       visited;
      44                 :            :   std::unordered_map<std::shared_ptr<ProofNode>,
      45                 :      13695 :                      std::shared_ptr<ProofNode>>::iterator it;
      46                 :      13695 :   std::vector<std::shared_ptr<ProofNode>> visit;
      47                 :      13695 :   std::shared_ptr<ProofNode> cur;
      48                 :      13695 :   visit.push_back(pf);
      49                 :      13695 :   std::map<Node, std::shared_ptr<ProofNode>>::iterator itc;
      50                 :            :   do
      51                 :            :   {
      52                 :   21583521 :     cur = visit.back();
      53                 :   21583521 :     it = visited.find(cur);
      54         [ +  + ]:   21583521 :     if (it == visited.end())
      55                 :            :     {
      56                 :    6986314 :       visited[cur] = nullptr;
      57                 :    6986314 :       traversing.push_back(cur);
      58                 :    6986314 :       const std::vector<std::shared_ptr<ProofNode>>& ccp = cur->getChildren();
      59                 :            :       // now, process children
      60         [ +  + ]:   21569826 :       for (const std::shared_ptr<ProofNode>& cp : ccp)
      61                 :            :       {
      62                 :   14583512 :         if (std::find(traversing.begin(), traversing.end(), cp)
      63         [ -  + ]:   29167024 :             != traversing.end())
      64                 :            :         {
      65                 :          0 :           Unhandled()
      66                 :            :               << "ProofNodeConverter::processInternal: cyclic proof! (use "
      67                 :          0 :                  "--proof-check=eager)"
      68                 :          0 :               << std::endl;
      69                 :            :         }
      70                 :   14583512 :         visit.push_back(cp);
      71                 :            :       }
      72                 :    6986314 :       continue;
      73                 :    6986314 :     }
      74                 :   14597207 :     visit.pop_back();
      75         [ +  + ]:   14597207 :     if (it->second == nullptr)
      76                 :            :     {
      77 [ -  + ][ -  + ]:    6986314 :       Assert(!traversing.empty());
                 [ -  - ]
      78                 :    6986314 :       traversing.pop_back();
      79                 :    6986314 :       const std::vector<std::shared_ptr<ProofNode>>& ccp = cur->getChildren();
      80                 :    6986314 :       std::vector<std::shared_ptr<ProofNode>> pchildren;
      81         [ +  - ]:    6986314 :       Trace("pf-convert") << "CONVERT " << cur->getRule() << std::endl;
      82                 :    6986314 :       bool childChanged = false;
      83         [ +  + ]:   21569826 :       for (const std::shared_ptr<ProofNode>& cp : ccp)
      84                 :            :       {
      85                 :   14583512 :         it = visited.find(cp);
      86 [ -  + ][ -  + ]:   14583512 :         Assert(it != visited.end());
                 [ -  - ]
      87                 :   14583512 :         pchildren.push_back(it->second);
      88 [ +  + ][ +  + ]:   14583512 :         childChanged = childChanged || cp != it->second;
      89 [ +  - ][ -  - ]:   29167024 :         Trace("pf-convert") << "- " << cp->getRule() << " " << cp->getResult()
      90 [ -  + ][ -  + ]:   14583512 :                             << " ... " << it->second->getResult() << std::endl;
                 [ -  - ]
      91                 :            :       }
      92                 :    6986314 :       std::shared_ptr<ProofNode> ret;
      93 [ +  + ][ +  + ]:    6986314 :       if (!childChanged && !d_cb.shouldConvert(cur))
         [ +  + ][ +  + ]
                 [ -  - ]
      94                 :            :       {
      95                 :            :         // callback does not need to convert and we did not convert a child,
      96                 :            :         // just take as is.
      97                 :    6104038 :         ret = cur;
      98                 :            :       }
      99                 :            :       else
     100                 :            :       {
     101                 :     882276 :         ret = processInternal(cur, pchildren);
     102                 :            :       }
     103         [ -  + ]:    6986314 :       if (ret == nullptr)
     104                 :            :       {
     105                 :          0 :         return nullptr;
     106                 :            :       }
     107                 :    6986314 :       visited[cur] = ret;
     108 [ +  - ][ +  - ]:    6986314 :     }
     109         [ +  + ]:   21583521 :   } while (!visit.empty());
     110         [ +  - ]:      13695 :   Trace("pf-convert") << "ProofNodeConverter::process: finished" << std::endl;
     111                 :      13695 :   return visited[pf];
     112                 :      13695 : }
     113                 :            : 
     114                 :     882276 : std::shared_ptr<ProofNode> ProofNodeConverter::processInternal(
     115                 :            :     std::shared_ptr<ProofNode> pf,
     116                 :            :     const std::vector<std::shared_ptr<ProofNode>>& pchildren)
     117                 :            : {
     118                 :     882276 :   ProofRule id = pf->getRule();
     119                 :            :   // use CDProof to open a scope for which the callback converts
     120                 :    1764552 :   CDProof cpf(d_env, nullptr, "ProofNodeConverter::CDProof", false);
     121                 :     882276 :   Node res = pf->getResult();
     122                 :     882276 :   std::vector<Node> children;
     123         [ +  + ]:    3510923 :   for (const std::shared_ptr<ProofNode>& cp : pchildren)
     124                 :            :   {
     125                 :    2628647 :     children.push_back(cp->getResult());
     126                 :    2628647 :     cpf.addProof(cp);
     127                 :            :   }
     128                 :     882276 :   const std::vector<Node>& args = pf->getArguments();
     129                 :     882276 :   Node newRes = d_cb.convert(res, id, children, args, &cpf);
     130         [ -  + ]:     882276 :   if (newRes.isNull())
     131                 :            :   {
     132                 :          0 :     return nullptr;
     133                 :            :   }
     134         [ +  - ]:     882276 :   Trace("pf-convert") << "Get proof for " << newRes << std::endl;
     135                 :     882276 :   return cpf.getProofFor(newRes);
     136                 :     882276 : }
     137                 :            : 
     138                 :            : }  // namespace cvc5::internal