基于cons单元的树结构中共享结构与自引用检测方案咨询

问题背景 #

我正在开发一款类Lisp编程语言，采用cons单元存储数据（便于实现垃圾回收），需要实现函数检测两种场景：

• 对象是否自引用（例如Lisp中的#1=(#1#)）
• 两个对象是否存在共享结构（例如(#1=(123) #1#)）

目前实现的递归函数如下：

bool points_to(obj* from, obj* to) {
    if (from == NULL) return false;
    if (from == to || points_to(from->car, to)) return true;
    return points_to(from->cdr, to);
}

该函数可检测直接自引用的循环列表，但遇到包含自引用对象的非自引用头部结构（如(1 2 . #1=(3 . #1))）时，会出现栈溢出或无限挂起。已知Lisp/Scheme通过#N=/ #N#标记实现此类检测，但不清楚具体算法，使用C++开发，可遍历所有已分配对象或借助垃圾回收的递归标记功能。

核心问题分析 #

递归版本的points_to未记录已访问对象，遇到循环结构时会无限递归，最终触发栈溢出或死循环。Lisp/Scheme的#N=标记本质是为首次访问的对象分配唯一标识，后续遇到相同对象时直接复用标识，核心思路就是追踪已访问节点，避免重复遍历。

解决方案：带访问追踪的检测算法 #

核心思路 #

无论是检测自引用还是共享结构，核心都是避免重复遍历同一对象，需维护一个已访问对象的集合（或利用GC标记位）：

• 自引用检测：遍历对象结构时记录访问过的cons单元，若当前节点已在集合中，说明存在循环/自引用。
• 共享结构检测：先遍历第一个对象并标记所有可达节点，再遍历第二个对象，若发现已标记的节点则说明存在共享；或同时遍历两个对象，用集合追踪交叉出现的节点。

基于GC标记位的高效实现 #

若可借助GC的递归标记功能，直接复用对象的标记位（给obj添加marked布尔字段）是最高效的方案，无需额外分配集合内存：

// 重置所有已分配对象的标记位
void reset_all_marks() {
    for (auto obj : all_allocated_objs) {
        obj->marked = false;
    }
}

1. 检测单个对象是否存在自引用（循环结构）

bool has_self_reference(obj* root) {
    if (root == nullptr) return false;
    if (root->marked) {
        // 再次访问到已标记节点，说明存在循环
        return true;
    }
    root->marked = true;
    // 递归检查car和cdr分支
    if (has_self_reference(root->car)) return true;
    if (has_self_reference(root->cdr)) return true;
    // 检测完成后可重置标记，避免干扰GC
    root->marked = false;
    return false;
}

2. 检测两个对象是否存在共享结构

// 标记某个对象的所有可达节点
void mark_reachable(obj* root) {
    if (root == nullptr || root->marked) return;
    root->marked = true;
    mark_reachable(root->car);
    mark_reachable(root->cdr);
}

bool has_shared_structure(obj* a, obj* b) {
    reset_all_marks();
    mark_reachable(a);
    // 遍历b的结构，检查是否有节点已被标记
    std::function<bool(obj*)> check_shared = [&](obj* node) {
        if (node == nullptr) return false;
        if (node->marked) return true;
        return check_shared(node->car) || check_shared(node->cdr);
    };
    bool result = check_shared(b);
    reset_all_marks();
    return result;
}

通用points_to函数改进版（带访问追踪） #

若需保留原points_to的语义（检测from是否能到达to），需添加已访问集合避免循环：

// 内部递归函数，带访问集合
bool points_to_internal(obj* from, obj* to, std::unordered_set<obj*>& visited) {
    if (from == nullptr) return false;
    if (visited.count(from)) return false; // 跳过已访问节点
    visited.insert(from);
    if (from == to) return true;
    return points_to_internal(from->car, to, visited) || points_to_internal(from->cdr, to, visited);
}

// 对外接口
bool points_to(obj* from, obj* to) {
    std::unordered_set<obj*> visited;
    return points_to_internal(from, to, visited);
}

迭代式实现（避免栈溢出） #

对于极深的结构，递归仍可能触发栈溢出，可改用栈模拟递归：

bool points_to_iterative(obj* from, obj* to) {
    if (from == nullptr || to == nullptr) return false;
    std::unordered_set<obj*> visited;
    std::stack<obj*> traverse_stack;
    traverse_stack.push(from);

    while (!traverse_stack.empty()) {
        obj* current = traverse_stack.top();
        traverse_stack.pop();
        if (current == to) return true;
        if (visited.count(current)) continue;
        visited.insert(current);
        // 先压入cdr，保证遍历顺序和递归一致
        if (current->cdr != nullptr) traverse_stack.push(current->cdr);
        if (current->car != nullptr) traverse_stack.push(current->car);
    }
    return false;
}

关键注意事项 #

• 使用unordered_set时，需确保obj*可被正确哈希；若用自定义内存池，可改用对象的唯一ID或内存偏移量作为集合键。
• 借助GC标记位时，检测完成后必须重置标记，避免干扰GC的正常标记-清除流程。
• 迭代式遍历更适合处理超深结构，彻底避免栈溢出风险。

内容的提问来源于stack exchange，提问作者dragoncoder047