how to make external recursive type insertable to a HashSet

Question

I use https://github.com/dtolnay/clang-ast to parse the JSON produced by Clang representing an AST to be available as a Rust data type, specifically the Node. I'd like to insert the nodes from the tree (Node<T> is recursive structure) into a HashSet. I could not even insert the root note:

use std::collections::HashSet;
use log::debug;
use std::env;
use serde::Deserialize;

pub type Node = clang_ast::Node<Clang>;

#[derive(Deserialize)]
#[derive(Debug)]
pub enum Clang {
    BinaryOperator(BinaryOperator),
    Other,
}

#[derive(Deserialize, Debug)]
pub struct BinaryOperator {
    pub opcode: String,
    pub range: clang_ast::SourceRange,
}

fn main() {
    env_logger::init();

    let json = std::fs::read_to_string("ast.json").unwrap();
    let node :Node = serde_json::from_str(&json).unwrap();
    let mut node_set = HashSet::new();
    node_set.insert(node);
}

this fails the compilation with:

error[E0277]: the trait bound `clang_ast::Node<Clang>: Eq` is not satisfied
   --> src/main.rs:28:21
    |
28  |     node_set.insert(node);
    |              ------ ^^^^ the trait `Eq` is not implemented for `clang_ast::Node<Clang>`
    |              |
    |              required by a bound introduced by this call
    |
note: required by a bound in `HashSet::<T, S>::insert`
...

So, I tried to add the Eq and PartialEq implementations using (following some advice from How to implement Eq and Hash for my own structs to use them as a HashMap key?):

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

impl Eq for Node {}

however this fails with:

error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
 --> src/main.rs:8:1
  |
8 | impl PartialEq for Node {
  | ^^^^^---------^^^^^----
  | |    |             |
  | |    |             `clang_ast::Node` is not defined in the current crate
  | |    `clang_ast::Node` is not defined in the current crate
  | impl doesn't use only types from inside the current crate
  |
  = note: define and implement a trait or new type instead

How do I make this work ? Also, why does the language/compiler imposes such limit ?

Following the answers on Implement foreign trait for foreign type does not really help because there are more pieces to the puzzle (implementing Eq, PartialEq, the Hash trait, dealing with the recursive nature of clang_ast::Note<T>).

Answer 1

How do I make this work ?

Define a newtype wrapper e.g. struct Node(clang:ast::Node<Clang>).

, or implement the trait on clang_ast::Node<Clang> rather than just clang_ast::Node¹.

Also, why does the language/compiler imposes such limit ?

Coherence. There should be only one implementation of a trait for a struct (ignoring specialisation). Allowing crates to implement traits they didn't define on types they didn't define is an opportunity for conflicts and incoherences (where one dependency uses one implementation and an other library uses an other incompatible implementation) which could lead to unsafety if they interact with the same objects in different ways (e.g. a generic collection of some sort, like a hashset).

Here though per the implementation coherence rules since Clang is a local type as long as there are no uncovered types appearing as one of its parameters it should be fine (I could not test this on the playground as clang_ast is to minor to figure there, but it works fine with Box).

In other contexts (like Box) overlapping can also be an issue, but here clang_ast::Node does not implement PartialEq at all, not even conditionally. Until that happens there's no issue.

---

[1]: incidentally you may want to report that the error message is misleading, since Node is a generic type I don't think it makes sense that Rust accepts this attempt. In fact I can not reproduce it, on the playground trying to impl PartialEq for Box fails with "error[E0107]: missing generics for struct Box".

edit: struct out the completely incorrect bits where I thought the coherence rules were less strict than they actually are (which is only the case for Box, Pin, and reference types).