(proof-new) Proof node to SExpr utility. (#4512)

This is required for dag-ifying ProofNode output.

3 files changed, 206 insertions, 0 deletions

diff --git a/src/expr/CMakeLists.txt b/src/expr/CMakeLists.txt
index 36675a148..55b2c9baa 100644
--- a/src/expr/CMakeLists.txt
+++ b/src/expr/CMakeLists.txt
@@ -39,6 +39,8 @@ libcvc4_add_sources(
   proof_checker.h
   proof_node.cpp
   proof_node.h
+  proof_node_to_sexpr.cpp
+  proof_node_to_sexpr.h
   proof_node_manager.cpp
   proof_node_manager.h
   proof_rule.cpp
diff --git a/src/expr/proof_node_to_sexpr.cpp b/src/expr/proof_node_to_sexpr.cpp
new file mode 100644
index 000000000..cf58daa3a
--- /dev/null
+++ b/src/expr/proof_node_to_sexpr.cpp
@@ -0,0 +1,139 @@
+/*********************                                                        */
+/*! \file proof_node_to_sexpr.cpp
+ ** \verbatim
+ ** Top contributors (to current version):
+ **   Andrew Reynolds
+ ** This file is part of the CVC4 project.
+ ** Copyright (c) 2009-2019 by the authors listed in the file AUTHORS
+ ** in the top-level source directory) and their institutional affiliations.
+ ** All rights reserved.  See the file COPYING in the top-level source
+ ** directory for licensing information.\endverbatim
+ **
+ ** \brief Implementation of proof node to s-expression
+ **/
+
+#include "expr/proof_node_to_sexpr.h"
+
+#include <iostream>
+
+using namespace CVC4::kind;
+
+namespace CVC4 {
+
+ProofNodeToSExpr::ProofNodeToSExpr()
+{
+  NodeManager* nm = NodeManager::currentNM();
+  std::vector<TypeNode> types;
+  d_argsMarker = nm->mkBoundVar(":args", nm->mkSExprType(types));
+}
+
+Node ProofNodeToSExpr::convertToSExpr(const ProofNode* pn)
+{
+  NodeManager* nm = NodeManager::currentNM();
+  std::map<const ProofNode*, Node>::iterator it;
+  std::vector<const ProofNode*> visit;
+  std::vector<const ProofNode*> constructing;
+  const ProofNode* cur;
+  visit.push_back(pn);
+  do
+  {
+    cur = visit.back();
+    visit.pop_back();
+    it = d_pnMap.find(cur);
+
+    if (it == d_pnMap.end())
+    {
+      d_pnMap[cur] = Node::null();
+      constructing.push_back(cur);
+      visit.push_back(cur);
+      const std::vector<std::shared_ptr<ProofNode>>& pc = cur->getChildren();
+      for (const std::shared_ptr<ProofNode>& cp : pc)
+      {
+        if (std::find(constructing.begin(), constructing.end(), cp.get())
+            != constructing.end())
+        {
+          AlwaysAssert(false)
+              << "ProofNodeToSExpr::convertToSExpr: cyclic proof!" << std::endl;
+          return Node::null();
+        }
+        visit.push_back(cp.get());
+      }
+    }
+    else if (it->second.isNull())
+    {
+      Assert(!constructing.empty());
+      constructing.pop_back();
+      std::vector<Node> children;
+      // add proof rule
+      children.push_back(getOrMkPfRuleVariable(cur->getRule()));
+      const std::vector<std::shared_ptr<ProofNode>>& pc = cur->getChildren();
+      for (const std::shared_ptr<ProofNode>& cp : pc)
+      {
+        it = d_pnMap.find(cp.get());
+        Assert(it != d_pnMap.end());
+        Assert(!it->second.isNull());
+        children.push_back(it->second);
+      }
+      // add arguments
+      const std::vector<Node>& args = cur->getArguments();
+      if (!args.empty())
+      {
+        children.push_back(d_argsMarker);
+        // needed to ensure builtin operators are not treated as operators
+        // this can be the case for CONG where d_args may contain a builtin
+        // operator
+        std::vector<Node> argsSafe;
+        for (const Node& a : args)
+        {
+          Node av = a;
+          if (a.getNumChildren() == 0
+              && NodeManager::operatorToKind(a) != UNDEFINED_KIND)
+          {
+            av = getOrMkNodeVariable(a);
+          }
+          argsSafe.push_back(av);
+        }
+        Node argsC = nm->mkNode(SEXPR, argsSafe);
+        children.push_back(argsC);
+      }
+      d_pnMap[cur] = nm->mkNode(SEXPR, children);
+    }
+  } while (!visit.empty());
+  Assert(d_pnMap.find(pn) != d_pnMap.end());
+  Assert(!d_pnMap.find(pn)->second.isNull());
+  return d_pnMap[pn];
+}
+
+Node ProofNodeToSExpr::getOrMkPfRuleVariable(PfRule r)
+{
+  std::map<PfRule, Node>::iterator it = d_pfrMap.find(r);
+  if (it != d_pfrMap.end())
+  {
+    return it->second;
+  }
+  std::stringstream ss;
+  ss << r;
+  NodeManager* nm = NodeManager::currentNM();
+  std::vector<TypeNode> types;
+  Node var = nm->mkBoundVar(ss.str(), nm->mkSExprType(types));
+  d_pfrMap[r] = var;
+  return var;
+}
+
+Node ProofNodeToSExpr::getOrMkNodeVariable(Node n)
+{
+  std::map<Node, Node>::iterator it = d_nodeMap.find(n);
+  if (it != d_nodeMap.end())
+  {
+    return it->second;
+  }
+  std::stringstream ss;
+  ss << n;
+  NodeManager* nm = NodeManager::currentNM();
+  std::vector<TypeNode> types;
+  Node var = nm->mkBoundVar(ss.str(), nm->mkSExprType(types));
+  d_nodeMap[n] = var;
+  return var;
+}
+
+}  // namespace CVC4
diff --git a/src/expr/proof_node_to_sexpr.h b/src/expr/proof_node_to_sexpr.h
new file mode 100644
index 000000000..3a5cd566a
--- /dev/null
+++ b/src/expr/proof_node_to_sexpr.h
@@ -0,0 +1,65 @@
+/*********************                                                        */
+/*! \file proof_to_sexpr.h
+ ** \verbatim
+ ** Top contributors (to current version):
+ **   Andrew Reynolds
+ ** This file is part of the CVC4 project.
+ ** Copyright (c) 2009-2019 by the authors listed in the file AUTHORS
+ ** in the top-level source directory) and their institutional affiliations.
+ ** All rights reserved.  See the file COPYING in the top-level source
+ ** directory for licensing information.\endverbatim
+ **
+ ** \brief Conversion from ProofNode to s-expressions
+ **/
+
+#include "cvc4_private.h"
+
+#ifndef CVC4__EXPR__PROOF_NODE_TO_SEXPR_H
+#define CVC4__EXPR__PROOF_NODE_TO_SEXPR_H
+
+#include <map>
+
+#include "expr/node.h"
+#include "expr/proof_node.h"
+
+namespace CVC4 {
+
+/** A class to convert ProofNode objects to s-expressions */
+class ProofNodeToSExpr
+{
+ public:
+  ProofNodeToSExpr();
+  ~ProofNodeToSExpr() {}
+  /** Convert the given proof node to an s-expression
+   *
+   * This is useful for operations where it is useful to view a ProofNode as
+   * a Node. Printing is one such example, where a ProofNode can be printed
+   * as a dag after this conversion.
+   *
+   * The s-expression for a ProofNode has the form:
+   *   (SEXPR (VAR "<d_rule>") S1 ... Sn (VAR ":args") (SEXPR <d_args>))
+   * where S1, ..., Sn are the s-expressions for its <d_children>.
+   */
+  Node convertToSExpr(const ProofNode* pn);
+
+ private:
+  /** map proof rules to a variable */
+  std::map<PfRule, Node> d_pfrMap;
+  /** Dummy ":args" marker */
+  Node d_argsMarker;
+  /** map proof nodes to their s-expression */
+  std::map<const ProofNode*, Node> d_pnMap;
+  /**
+   * map nodes to a bound variable, used for nodes that have special AST status
+   * like builtin operators
+   */
+  std::map<Node, Node> d_nodeMap;
+  /** get or make pf rule variable */
+  Node getOrMkPfRuleVariable(PfRule r);
+  /** get or make node variable */
+  Node getOrMkNodeVariable(Node n);
+};
+
+}  // namespace CVC4
+
+#endif /* CVC4__EXPR__PROOF_RULE_H */