Expecting and getting different types

Question

I am trying to learn rust following this https://github.com/dhole/rust-homework/tree/master/hw03, which follows this https://rust-unofficial.github.io/too-many-lists/second-option.html, and when I try to do this:

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    left: Link<T>,
    right: Link<T>,
}

pub struct BST<T: std::cmp::PartialOrd> {
    root: Link<T>,
}

impl<T: std::cmp::PartialOrd> BST<T> {
    pub fn new() -> Self {
        BST { root: None }
    }

    pub fn insert(&mut self, elem: T) -> bool {
        self.root.insert(elem)
    }
}

trait InsertSearch<T: std::cmp::PartialOrd> {
    fn insert(&mut self, elem: T) -> bool;
}

impl<T: std::cmp::PartialOrd> InsertSearch<T> for Link<T> {
    fn insert(&mut self, elem: T) -> bool {
        true
    }
}

I get the following 2 erros:

error[E0308]: mismatched types
  --> src\second.rs:35:34
   |
23 | impl<T: std::cmp::PartialOrd> BST<T> {
   |      - this type parameter
...
35 |                 self.root.insert(elem)
   |                                  ^^^^ expected struct `Box`, found type parameter `T`
   |
   = note:      expected struct `Box<second::Node<T>>`
           found type parameter `T`

Why is it expecting a Box, when I am calling Option<Box<Node<T>>>::insert(T)?

error[E0308]: mismatched types
  --> src\second.rs:35:17
   |
28 |     pub fn insert(&mut self, elem: T) -> bool {
   |                                          ---- expected `bool` because of return type
...
35 |                 self.root.insert(elem)
   |                 ^^^^^^^^^^^^^^^^^^^^^^ expected `bool`, found mutable reference
   |
   = note:           expected type `bool`
           found mutable reference `&mut Box<second::Node<T>>`

And this one really confuses me. Why is it getting &mut Box<second::Node<T>>, when the return type of the insert function is bool? What am I calling then?

Nitpick: PartialOrd is in the prelude, you don't need to fully-qualify it. — Chayim Friedman

Chayim Friedman Chayim Friedman · Accepted Answer · 2022-07-28T16:16:43

Both errors have the same reason: you're not calling the insert(). function you defined. You call another function.

Remember Link is actually Option<_> (Option<Box<Node<T>>>, to be precise). And Option has an insert() method. And it takes T (not your T, the Option's T, which is Box<Node<T>> in this case) and produces &mut T (&mut Box<Node<T>>). And when you call some method, you always call an inherent method if one exists; only if there is no inherent method with that name you call a trait method, but in this case there is.

The solution can be to use Universal Function Call Syntax - <Link<T> as InsertSearch<T>>::insert(&mut self.root, elem), but I would recommend just making Link a newtype struct instead of a type alias. That is,

struct Link<T>(Box<Node<T>>);

This way, you can define an inherent insert() method, and you don't inherit Option's methods.

Expecting and getting different types

1 Answers