c++ - 如何安全地在 C++/Ocaml 之间转换树数据结构？

Question

我有一个用 C++ 编写的遗留数据结构和一个 OCaml 中的新工具，该工具有望处理该遗留数据。所以我需要将数据从前者导入/翻译到后者。数据以树的形式存在，通常由访问者处理。

作为一个简单的例子，考虑这个最小的 DSL:

#include <memory>

using namespace std;

class intnode;
class addnode;

struct visitor {
    virtual void visit(const intnode& n) = 0;
    virtual void visit(const addnode& n) = 0;
};

struct node {
    virtual void accept(visitor& v) = 0;
};

struct intnode : public node {
    int x;

    virtual void accept(visitor& v) { v.visit(*this); }
};

struct addnode : public node {
    shared_ptr<node> l;
    shared_ptr<node> r;

    virtual void accept(visitor& v) { v.visit(*this); }
};

它在 OCaml 中的表示如下:

type node = Int of int
          | Plus of node * node

let make_int x = Int x
let make_plus l r = Plus(l,r)

问题是，我如何安全有效地将 C++ 树转换为其 OCaml 表示形式？

到目前为止，我有两种方法:

方法一

编写一个调用 OCaml 构造函数并产生一个 value 的访问者，例如像这样:

value translate(shared_ptr<node> n);

struct translator : public visitor {
    value retval;

    virtual visit(const intnode& n) {
        retval = call(make_int, Val_int(x->value));
    }

    virtual visit(const addnode& n) {
        value l = translate(n.l);
        value r = translate(n.r);
        retval =  call(make_add, l, r);
    }
};

value translate(shared_ptr<node> n)
{
    translator t;
    t.visit(*n);
}

简单地假设 call 完成所有必需的脚手架以回调 OCaml 并调用正确的构造函数。

该方法的问题在于 OCaml 的垃圾收集器。如果 GC 运行，而 C++ 端在堆栈上有一些 value，该值(毕竟是指向 OCaml 堆的指针)可能会失效。所以我需要一些方法来通知 OCaml 仍然需要这些值这一事实。通常这是通过 CAML* 宏完成的，但在这种情况下我该如何做呢？我可以在 visit 方法中使用这些宏吗？

方法二

第二种方法比较复杂。当没有办法安全地存储中间引用时，我可以扭转局面并将 C++ 指针插入 OCaml 堆:

type cppnode (* C++ pointer *)

type functions = {
  transl_plus : cppnode -> cppnode -> node;
  transl_int : int -> node;
}

external dispatch : functions -> cppnode -> node = "dispatch_transl"

let rec translate n = dispatch {transl_plus; transl_int = make_int} n

and transl_plus a b = make_plus (translate a) (translate b)

这里的想法是，“dispatch”函数将所有子节点包装到 CustomVal 结构中，并将它们传递给 OCaml，而不存储任何中间值。对应的访问者只会实现模式匹配。这显然应该适用于 GC，但缺点是效率稍低(因为指针环绕)和可读性可能较低(因为分派(dispatch)和重建之间的区别)。

有没有办法在方法 1 的优雅的同时获得方法 2 的安全性？

Answer 1

即使在递归情况下，我也没有发现在 C 堆栈上构造 OCaml 值有任何问题。在您的示例中，您使用结构成员来存储 OCaml 堆值。这也是可能的，但是，您需要使用 caml_register_global_root 或 caml_register_generational_root 并使用 caml_remove_global_root 或 caml_remove_generational_global_root 释放它们。事实上，您甚至可以构建一个智能指针来保存 OCaml 值。

尽管如此，我仍然看不出有任何理由(至少对于您演示的简化示例而言)为什么您应该为此进入类(class)成员，这就是我要解决的问题:

struct translator : public visitor {

    virtual value visit(const intnode& n) {
        CAMLparam0();
        CAMLlocal1(x);
        x = call(make_int, Val_int(n->value);
        CAMLreturn(x);
    }

    virtual value visit(const addnode& n) {
        CAMLparam0();
        CAMLlocal(l,r,x);
        l = visit(*n.l);
        r = visit(*n.r);
        x = call(make_add, l, r);
        CAMLreturn(x);
    }
};

当然，这假设您有一个可以返回任意类型值的访问者。如果您没有，也不想实现，那么您绝对可以逐步建立您的值(value):

value translate(shared_ptr<node> n);

class builder : public visitor {
    value result;
 public:
    builder() {
       result = Val_unit; // or any better default
       caml_register_generational_global_root(&result);
    }

    virtual ~builder() {
       caml_remove_generational_global_root(&result);
    }

    virtual void visit(const intnode& n) {
        CAMLparam0();
        CAMLlocal1(x);
        x = call(make_int, Val_int(n->value);
        caml_modify_generational_global_root(&result, x);
        CAMLreturn0;
    }

    virtual void visit(const addnode& n) {
        CAMLparam0();
        CAMLlocal(l,r,x);
        l = translate(n.l);
        r = translate(n.r);
        x = call(make_add, l, r);
        caml_modify_generational_global_root(&result,x)
        CAMLreturn0;
    }
};

value translate(share_ptr<node> node) {
  CAMLparam0();
  CAMLlocal1(x);
  builder b;
  b.visit(*node);
  x = b.result;
  CAMLreturn(x);
}

您还可以查看 Berke Durak 的 Aurochs项目，使用 C 就地构建解析树。