Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Andrew Reynolds
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2024 by the authors listed in the file AUTHORS
       8                 :            :  * in the top-level source directory and their institutional affiliations.
       9                 :            :  * All rights reserved.  See the file COPYING in the top-level source
      10                 :            :  * directory for licensing information.
      11                 :            :  * ****************************************************************************
      12                 :            :  *
      13                 :            :  * A utility for converting proof nodes.
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "proof/proof_node_converter.h"
      17                 :            : 
      18                 :            : #include "proof/proof.h"
      19                 :            : 
      20                 :            : namespace cvc5::internal {
      21                 :            : 
      22                 :         12 : ProofNodeConverter::ProofNodeConverter(Env& env,
      23                 :            :                                        ProofNodeConverterCallback& cb,
      24                 :         12 :                                        bool autoSym)
      25                 :         12 :     : EnvObj(env), d_cb(cb)
      26                 :            : {
      27                 :         12 : }
      28                 :            : 
      29                 :         12 : std::shared_ptr<ProofNode> ProofNodeConverter::process(
      30                 :            :     std::shared_ptr<ProofNode> pf)
      31                 :            : {
      32                 :            :   // The list of proof nodes we are currently traversing beneath. This is used
      33                 :            :   // for checking for cycles in the overall proof.
      34                 :         24 :   std::vector<std::shared_ptr<ProofNode>> traversing;
      35                 :         24 :   std::shared_ptr<ProofNode> pft = pf;
      36         [ +  - ]:         12 :   Trace("pf-convert") << "ProofNodeConverter::process" << std::endl;
      37                 :            :   std::unordered_map<std::shared_ptr<ProofNode>, std::shared_ptr<ProofNode>>
      38                 :         24 :       visited;
      39                 :            :   std::unordered_map<std::shared_ptr<ProofNode>,
      40                 :         12 :                      std::shared_ptr<ProofNode>>::iterator it;
      41                 :         24 :   std::vector<std::shared_ptr<ProofNode>> visit;
      42                 :         12 :   std::shared_ptr<ProofNode> cur;
      43                 :         12 :   visit.push_back(pf);
      44                 :         12 :   std::map<Node, std::shared_ptr<ProofNode>>::iterator itc;
      45                 :        240 :   do
      46                 :            :   {
      47                 :        252 :     cur = visit.back();
      48                 :        252 :     it = visited.find(cur);
      49         [ +  + ]:        252 :     if (it == visited.end())
      50                 :            :     {
      51                 :        126 :       visited[cur] = nullptr;
      52                 :        126 :       traversing.push_back(cur);
      53                 :        126 :       const std::vector<std::shared_ptr<ProofNode>>& ccp = cur->getChildren();
      54                 :            :       // now, process children
      55         [ +  + ]:        240 :       for (const std::shared_ptr<ProofNode>& cp : ccp)
      56                 :            :       {
      57                 :        114 :         if (std::find(traversing.begin(), traversing.end(), cp)
      58         [ -  + ]:        228 :             != traversing.end())
      59                 :            :         {
      60                 :          0 :           Unhandled()
      61                 :            :               << "ProofNodeConverter::processInternal: cyclic proof! (use "
      62                 :          0 :                  "--proof-check=eager)"
      63                 :          0 :               << std::endl;
      64                 :            :         }
      65                 :        114 :         visit.push_back(cp);
      66                 :            :       }
      67                 :        126 :       continue;
      68                 :            :     }
      69                 :        126 :     visit.pop_back();
      70         [ +  - ]:        126 :     if (it->second == nullptr)
      71                 :            :     {
      72 [ -  + ][ -  + ]:        126 :       Assert(!traversing.empty());
                 [ -  - ]
      73                 :        126 :       traversing.pop_back();
      74                 :        126 :       const std::vector<std::shared_ptr<ProofNode>>& ccp = cur->getChildren();
      75                 :        126 :       std::vector<std::shared_ptr<ProofNode>> pchildren;
      76         [ +  - ]:        126 :       Trace("pf-convert") << "CONVERT " << cur->getRule() << std::endl;
      77         [ +  + ]:        240 :       for (const std::shared_ptr<ProofNode>& cp : ccp)
      78                 :            :       {
      79                 :        114 :         it = visited.find(cp);
      80 [ -  + ][ -  + ]:        114 :         Assert(it != visited.end());
                 [ -  - ]
      81                 :        114 :         pchildren.push_back(it->second);
      82 [ +  - ][ -  - ]:        228 :         Trace("pf-convert") << "- " << cp->getRule() << " " << cp->getResult()
      83 [ -  + ][ -  + ]:        114 :                             << " ... " << it->second->getResult() << std::endl;
                 [ -  - ]
      84                 :            :       }
      85                 :        126 :       std::shared_ptr<ProofNode> ret = processInternal(cur, pchildren);
      86         [ -  + ]:        126 :       if (ret == nullptr)
      87                 :            :       {
      88                 :          0 :         return nullptr;
      89                 :            :       }
      90                 :        126 :       visited[cur] = ret;
      91                 :            :     }
      92         [ +  + ]:        252 :   } while (!visit.empty());
      93         [ +  - ]:         12 :   Trace("pf-convert") << "ProofNodeConverter::process: finished" << std::endl;
      94                 :         12 :   return visited[pf];
      95                 :            : }
      96                 :            : 
      97                 :        126 : std::shared_ptr<ProofNode> ProofNodeConverter::processInternal(
      98                 :            :     std::shared_ptr<ProofNode> pf,
      99                 :            :     const std::vector<std::shared_ptr<ProofNode>>& pchildren)
     100                 :            : {
     101                 :        126 :   ProofRule id = pf->getRule();
     102                 :            :   // use CDProof to open a scope for which the callback converts
     103                 :        378 :   CDProof cpf(d_env, nullptr, "ProofNodeConverter::CDProof", false);
     104                 :        252 :   Node res = pf->getResult();
     105                 :        252 :   std::vector<Node> children;
     106         [ +  + ]:        240 :   for (const std::shared_ptr<ProofNode>& cp : pchildren)
     107                 :            :   {
     108                 :        114 :     children.push_back(cp->getResult());
     109                 :        114 :     cpf.addProof(cp);
     110                 :            :   }
     111                 :        126 :   const std::vector<Node>& args = pf->getArguments();
     112                 :        252 :   Node newRes = d_cb.convert(res, id, children, args, &cpf);
     113         [ -  + ]:        126 :   if (newRes.isNull())
     114                 :            :   {
     115                 :          0 :     return nullptr;
     116                 :            :   }
     117         [ +  - ]:        126 :   Trace("pf-convert") << "Get proof for " << newRes << std::endl;
     118                 :        126 :   return cpf.getProofFor(newRes);
     119                 :            : }
     120                 :            : 
     121                 :            : }  // namespace cvc5::internal