Getting 'Missing Lifetime specifier' error

Question

This is my code:

use std::ptr;

struct Query<T>{
  data: T,
  prev: & Query<T>,
  next: & Query<T>,
}
impl<T> Query<T>{
  fn new(name: T) -> Query<T>{
    Query{
      data: name,
      prev: ptr::null(),
      next: ptr::null(),
    }
  }
}

I keep getting 'missing lifetime specifier' where I am referencing &Query<T>. How do I fix this error?

Answer 1

First, note that &T/&mut T and *const T/*mut T are different types of pointers in Rust. The former are called "references" and they are statically checked in various ways (including borrowing analysis) and they can't be null or point to some invalid object. The latter are called "raw pointers" and are used primarily in abstractions implementations and for FFI.

Consequently, writing

Query {
    data: name,
    prev: ptr::null(),
    next: ptr::null(),
}

when prev and next are of type &Whatever is incorrect - ptr::null() returns values of type *const Whatever which is not compatible (safely) with &Whatever.

References in Rust always have some lifetime associated with them - it is used by the compiler to check that references always point to valid pieces of data. This lifetime is specified in reference type: &'a T. In most cases the compiler can infer correct lifetimes automatically, so you seldom need to write them in types of local variables or even in function declarations:

let x: &str = "hello";

fn print_str(s: &str) { println!("{}", s); }

However, when you want to put references to a structure, there is just no way the compiler can infer the lifetime in the structure declaration (because it can be arbitrary and depends on the way the structure values are used), and so you need to specify lifetime parameters explicitly:

struct Query<'a, T> {
    data: T,
    prev: &'a Query<'a, T>,
    next: &'a Query<'a, T>,
}

In this particular case, though, it seems that you want to implement some kind of doubly linked structure. Unfortunately, Rust references can't be used for this. Lifetime requirements prohibit creation of loops via references - you just can't store a reference to x in y if x has a reference to y inside it. The only way such structure can be constructed is through mutation:

let mut x = SomeStructure(None);
let y = SomeStructure(Some(&x));
x.0 = Some(&y);

But you can't mutate an object which has a reference pointing to it, that is, the above code is invalid.

The thing you're trying to achieve is usually called intrusive data structures, and for now they are not well supported in Rust. There is an RFC issue on that, and we may probably see some progress on them in future.

There are several things you can do here, the most easiest one probably would be to refactor your code in such a way that you won't need to use a doubly-linked structure. Almost always you can put your data in a contiguous array like Vec and use indices to access it, and most likely it would be more efficient even for simple traversal because of cache locality.

Another option would be to use a non-intrusive linked list, like the one which is available in the standard library.

And, of course, you can always drop to using raw pointers. There is nothing wrong in using them when they are required, and most of the standard library abstractions (like the linked list above) are using them in some way internally. In your case, however, they should be the last resort - most likely there are ways to do what you want without them.