Rust SuperPower: Why this can happen?!

help
1

Guys! Guys! I was shocked by the SuperPower of rust! Here is the thing:
When I was doing this exercise, I saw a magic solution, which can directly compare two Tree, to check whether is the same.

Exercise Description:

Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Here is the definition of Tree:

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}

In this case, Rust can just do this!

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
        q == p  // direct compare?!
    }
}

And it passed!
Compared with other languages, this method is really shocking.

I can probably understand that this is due to the rust type system (which is the SuperPower), but I really want to know how this is achieved.
Or, it may be due to other reasons.
Pleace tell me the detail. Thanks a lot!

1 Like
2

It's the #[derive(PartialEq)] that does it. By implementing the PartialEq trait, types can be compared via ==, and the #[derive(PartialEq)] annotation calls a derive macro which automatically implements PartialEq for TreeNode.

As a side note, this looks like a leetcode problem, I wouldn't recommend using leetcode to learn rust as they like to force you into unidiomatic patterns, among other issues.

7 Likes
3

Slightly off-topic, but leetcode is kinda shit at teaching good rust with the absurdly frequent use of Rc<RefCell<…>> that these (presumably machine-translated from different languages) exercises have.

I mean, of course, it can be a fun challenge, but be aware that using Rc<RefCell<…>> all the time without any good reason (and by the way, occasionally there are good reasons for Rc<RefCell<…>>) is not idiomatic… neither is this weird impl Solution thing they’re doing that stinks of Java to me (Java doesn’t have free-standing functions, so you must “invent” some classes even when there’s no data and only static methods).

14 Likes
4

In case you’re interested in what PartialEq’s derive implementation does under the hood, you can look at the macro expansion in the rust playground (under TOOLS->Expand macros), or using the “cargo expand” tool.

Relevant part of the generated code for the tree struct at hand looks like

impl ::core::cmp::PartialEq for TreeNode {
    #[inline]
    fn eq(&self, other: &TreeNode) -> bool {
        self.val == other.val && self.left == other.left &&
            self.right == other.right
    }
}

So as you can see, it’s really just a recursive implementation where == for the tree will call == on the value and subtrees.

9 Likes
5

Thanks a lot!
I was wondering whether it is because of the type system that rust can judge equality by directly comparing memory.
Looks like I'm a little over thinking, lmao.

6

I will not practice Rust with LeetCode in the future, I promise to you, :grin:

1 Like
7

It’s not that we can’t judge equality by comparing memory locations (I presume you are referring to memory locations, not just “memory”[1]), instead we don’t want to!

Many, many programming languages do not allow customizable implementations of what == does, so approaches like reference-equality for anything but the most simple value types (like e.g. integers) are best-efforts to get something usable at all. This also has the effect that == can nonetheless often be utterly useless in such languages.

In Rust, for most plain data structures, memory locations are irrelevant, and you care more about values, and == can usefully be implemented to be the most commonly needed/useful operation for comparing things to be equal.

  1. well… if you do mean “simply comparing memory contents”, please correct my interpretation, and we’d have a different thing to discuss why that isn’t a particularly useful approach either ↩︎

3 Likes
8

By the way, I myself couldn’t list good alternatives off the top of my head to do small programming exercises without being presented with unidiomatic code in the testing framework; but I’d hope others can maybe recommend something? Or there might be existing threads containing good recommendations?

1 Like
9

Sorry, I do mean "simply compare memory content". I am very sorry for this misunderstanding.
please forgive my poor English...

10

No problem. In this case, what contents would you consider memory contents? Many types in Rust contain pointers to different memory locations, are such pointers appearing in the direct memory of a value in Rust supposed to be compared by their address, or followed? If it’s just the addresses, then any type with indirections would be compared mostly by memory-locations again.

If pointers are to be followed, there needs to be code to determine what is and isn’t a pointer in the first place, comparable to the trait implementations of PartialEq that we are actually using, only that those allow for user customization of the behavior. After all, the person who defines a struct usually has the best idea what the best way would be to compare them for equality. Or whether perhaps there is no good way at all to compare them for equality, which is a nice possibility, too. The trait-based approach in Rust allows it to be a compile-time error to compare types with == for which there is no sensible concept of “equality” in the first place.

1 Like
11

Fun fact, Rc actually does use reference equality for the fast path when doing the equality check, at least when the inner type implements Eq.

Can't speak for other sites, but codewars.com usually does pretty good, since problems are user submitted.

3 Likes
12

Very profound explanation! I learned a lot!
And I think Advent of Code is also a good way to practice Rust. By only gives you the question and answer, without limit your approach.

13

When I have been trying it, Exercism Rust track seemed to be pretty good.

3 Likes
14

The derived implementations don't "directly compare memory", if by that you mean comparing raw bytes.

As you can see from the expansion, the derived equality operator impl simply forwards to all fields. If your fields are primitives or core types such as String, then they have a sensible, value-based implementation that behaves as you would expect. If the fields themselves are custom types of which the PartialEq impl is also (likely) derived, then that will be used. Whatever PartialEq::eq() does on your field types is what will be used. There is no raw byte comparison, no magic, and no "superpowers". This is simply compositionality.

3 Likes
15

The enablement of pervasive composition is the superpower!

1 Like