CODEWITHSUNDEEP
rust
Stuart
Stuart

Reputation: 654

Unexpected T vs &T as type parameter in Rust

I'm genericising a Graph that I wrote. Current signature is 

#[derive(Debug)]
pub struct Graph<T: Clone + Hash + Eq> {
    nodes: HashMap<T, Node<T>>,
    edges: HashMap<T, Vec<Edge<T>>>
}

#[derive(PartialEq, Debug)]
pub struct Node<T: Clone + Hash + Eq> {
    pub id: T,
    pub x: f64,
    pub y: f64
}

#[derive(PartialEq, Debug)]
pub struct Edge<T: Clone + Hash + Eq> {
    pub id: T,
    pub from_id: T,
    pub to_id: T,
    pub weight: i64
}

I'm using it in a specific function and the calls to other functions are failing to compile.

First, the use:

fn reducer<T>(graph: Graph<T>, untested_nodes: HashSet<T>, mut results: Vec<HashSet<T>>) -> Graph<T>
   where T: Clone + Hash + Eq {
    match untested_nodes.iter().next() {
        None => {
            collapsed_graph(&graph, &results)
        }
        Some(root) => {
            let connected_nodes = explore_from(&root, &graph);
            let difference = untested_nodes.difference(&connected_nodes)
                                           .cloned()
                                           .collect();
            results.push(connected_nodes);
            reducer(graph,
                    difference,
                    results
                    )
        }
    }
}

The signature of explore_from

fn explore_from<T: Clone + Hash + Eq>(root: &T, graph: &Graph<T>) -> HashSet<T> {

The compiler error:

   Compiling efficient_route_planning v0.1.0 (file:///Users/stuart/coding/efficient_route_planning)
src/connected_component.rs:19:55: 19:61 error: mismatched types:
 expected `&weighted_graph::Graph<&T>`,
    found `&weighted_graph::Graph<T>`
(expected &-ptr,
    found type parameter) [E0308]
src/connected_component.rs:19             let connected_nodes = explore_from(&root, &graph);
                                                                                    ^~~~~~
src/connected_component.rs:19:55: 19:61 help: run `rustc --explain E0308` to see a detailed explanation
src/connected_component.rs:20:56: 20:72 error: mismatched types:
 expected `&std::collections::hash::set::HashSet<T>`,
    found `&std::collections::hash::set::HashSet<&T>`
(expected type parameter,
    found &-ptr) [E0308]
src/connected_component.rs:20             let difference = untested_nodes.difference(&connected_nodes)
                                                                                     ^~~~~~~~~~~~~~~~
src/connected_component.rs:20:56: 20:72 help: run `rustc --explain E0308` to see a detailed explanation
src/connected_component.rs:23:26: 23:41 error: mismatched types:
 expected `std::collections::hash::set::HashSet<T>`,
    found `std::collections::hash::set::HashSet<&T>`
(expected type parameter,
    found &-ptr) [E0308]
src/connected_component.rs:23             results.push(connected_nodes);
                                                       ^~~~~~~~~~~~~~~
src/connected_component.rs:23:26: 23:41 help: run `rustc --explain E0308` to see a detailed explanation
error: aborting due to 3 previous errors
Could not compile `efficient_route_planning`.

The full code: https://github.com/shterrett/efficient_route_planning/blob/generic-graph/src/connected_component.rs#L19

As far as I can tell, everything should be &Graph<T>, not &Graph<&T>. I'm not sure where the error is.

Versions:

% multirust show override
multirust: default toolchain: stable
multirust: default location: /Users/xxxxxx/.multirust/toolchains/stable

rustc 1.8.0 (db2939409 2016-04-11)
cargo 0.9.0-nightly (8fc3fd8 2016-02-29)

Upvotes: 1

Views: 905

Answers (1)

malbarbo
malbarbo

Reputation: 11177

The problem seem to be here

let connected_nodes = explore_from(&root, &graph);

untested_nodes.iter().next() returns Option<&T>, so the match Some(root) makes root: &T. This implies that &root is &&T, and the inferred T in explore_from is &T (T of reducer). I expect that removing the reference from root fix this:

let connected_nodes = explore_from(root, &graph);

Upvotes: 4

Related Questions