Magic behind match: no implementation for `&std::option::Option<ListNode> == std::option::Option<_>

Viewed 117

I'm newbie in Rust from Python. This is my 4th day of learning Rust.

After my first question Type casting for Option type, I have a follow up question related to syntax match and ownership concept.


Firstly, I declare a ListNode struct with new implementation.

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct ListNode {
  pub val: i32,
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      val
    }
  }
}

My goal is to compare if two nodes are same by comparing the val of node. Here's my ugly implementation.

fn is_same(a: &Option<ListNode>, b: &Option<ListNode>) -> bool {
    if a == None && b == None { return true; }
    else if a == None && b != None { return false; }
    else if a != None && b == None { return false; }

    let ca: ListNode = a.clone().unwrap_or(ListNode::new(0));
    let cb: ListNode = b.clone().unwrap_or(ListNode::new(0));
    if ca.val == cb.val { return true; }
    else { return false; }
}

fn main() {
    let a: Option<ListNode> = Some(ListNode::new(0));
    let b: Option<ListNode> = Some(ListNode::new(0));
    
    println!("{:?}", is_same(&a, &b));
}

Then, I got many errors...

no implementation for `&std::option::Option<ListNode> == std::option::Option<_>

According to my knowledge of ownership concept, using * for borrowed parameter should be optional. But, to make the comparison work, I need to add *. Below modified function works. (One additional found is that, using a.clone() is fine but *a.clone() is wrong with error type `ListNode` cannot be dereferenced.)

fn is_same(a: &Option<ListNode>, b: &Option<ListNode>) -> bool {
    if *a == None && *b == None { return true; }
    else if *a == None && *b != None { return false; }
    else if *a != None && *b == None { return false; }

    let ca: ListNode = a.clone().unwrap_or(ListNode::new(0));
    let cb: ListNode = b.clone().unwrap_or(ListNode::new(0));
    if ca.val == cb.val { return true; }
    else { return false; }
}

Since above solution code is too ugly, here's another implementation by using match without redundant unwrap_or and *.

fn is_same(a: &Option<ListNode>, b: &Option<ListNode>) -> bool {
    match (a, b) {
        (None, None) => true,
        (None, _) => false,
        (_, None) => false,
        (Some(a), Some(b)) => a.val == b.val,
    }
}

This works perfectly, a and b are successfully compared with None without * and unwrap_or.


Those code ends to below questions:

  • Why * is needed to compare with None in my original code?
  • What is the magic behind match? How does this syntax make code skip using * and unwrap_or for comparison?
1 Answers

Why * is needed to compare with None in my original code?

It's not needed per-se, but Eq is only implemented for identical types, so you need to compare either two Option<T> or two &Option<T>. From this you might see that comparing your nodes to &None would also have worked.

What is the magic behind match? How does this syntax make code skip using * and unwrap_or for comparison?

Match Ergonomics. Basically, match will attempt to automatically add references to patterns in order to try and resolve the types.

Also I don't know if you've noticed and just want to work harder, but Option<T: Eq> implements Eq, so is_same(&a, &b) could just be written a == b.

And an other thing, #[inline] is usually recommended against, it's generally better to avoid providing hints unless you've specifically looked at the generated output and the compiler refuses to yield what you're looking for otherwise. Keep in mind: the code here is so simple that in release mode and even using the complicated version of is_same with a bunch of dereferences, llvm finds out what's what and just loads and formats a constant true.

Related