And I'd like to figure out whether two variables - let's say p: Rc<RefCell<TreeNode>> and q: Rc<RefCell<TreeNode>> - are pointing at the same node in a tree.
Before I found ptr_eq, I was exploring if Eq trait would work, so I looked up the std documentation, and found it seems that for both Rc and RefCell, they are equal only when the inner values are equal.
So here's my assumption: when executing p == q, since they are Rc type, so the program will see if the inner RefCell are equal, and see if the inner TreeNode are equal, then see if the val, left, and right fields are equal. But since left and right are Option<Rc<RefCell<TreeNode>>> type, when they are all Some(_), the program will perform the above progress again, and lead to recursive comparison.
Is this what really happens when comparing these two variables? And will this lead to performance reduction?
Compared to what? "Reduction" is only a meaningful concept if you have a baseline to compare to. Structural equality needs to perform all the recursive work, anything else would be wrong. So there's no meaningful baseline to compare against.
I don't really understand how performance can even come into consideration when even the functionality is not decided yet. The decision whether you want identity or structural comparison shouldn't be based on "which one is faster"; it should be based on which one is correct. If your use case calls for deep equality and you implement pointer equality "because it's faster", then you'll get incorrect results.
But does pointer equality imply equality of inner values? I mean if two Rc are pointing at the same address, then shouldn't the results of dereferencing be equal?
Mostly. For well-behaved types, identity implies equality.
There are degenerate cases where identity does not imply equality; the most notable example is floating-point numbers, where NaN != NaN. The irreflexivity of equality is pretty confusing, as in everyday life we assume reflexivity of equality, and consequently, it's not great to have APIs that exhibit this undesirable behavior, but we have to deal with the reality that they exist.
The technical phrasing of this distinction usually exhibits the implementation of the Eq trait (or lack thereof). Reflexively self-equal types can (and usually do) implement Eq, whereas types with non-reflexive equality only implement PartialEq.
(The PartialEq trait does not only or necessarily mean that only or precisely self-equality is false; "partiality" on a set with an equality operator means that not all pairs of elements of the set are comparable. But in practice, the two usually correspond.)
So, you can in theory use ptr_eq to fast-path the equality check if you want but if it returns false you'll need to fall back on the recursive check as @paramagnetic describes. Whether that will make a meaningful difference will depend on your workload, in particular how often you're able to take advantage of the fast path vs. how often it's just a speed bump in doing the recursive comparison.
Unfortunately, the Eq trait can't make comparisons in a different way than PartialEq does (at least until specialization happens). So, to take advantage of this you'll need to restrict all comparisons to payload types that implement Eq. In your example, i32does implement Eq so you can do this if you want:
use std::cell::RefCell;
use std::rc::Rc;
#[derive(Debug)]
struct TreeNode<T> {
val: T,
left: Option<Rc<RefCell<TreeNode<T>>>>,
right: Option<Rc<RefCell<TreeNode<T>>>>,
}
impl<T> PartialEq for TreeNode<T>
where
T: Eq,
{
fn eq(&self, rhs: &Self) -> bool {
if self.val != rhs.val {
return false;
}
if !match (&self.left, &rhs.left) {
(None, None) => true,
(Some(p), Some(q)) => Rc::ptr_eq(p, q) || p == q,
_ => false,
} {
return false;
}
if !match (&self.right, &rhs.right) {
(None, None) => true,
(Some(p), Some(q)) => Rc::ptr_eq(p, q) || p == q,
_ => false,
} {
return false;
}
true
}
}
impl<T> Eq for TreeNode<T> where T: Eq {}