Aimlessly Going Forward

blog by Tomas Sedovic

Safe Rust bindings for path-finding code in C

WARNING: This post has been written before Rust 1.0 and therefore before the language was stabilised! It's not been tested on stable Rust and the double-pointer approach described here is unnecessary. Proceed with caution!

While working on Dose Response, I found myself writing bindings to libtcod (it's a great starting point for roguelikes and I was already familiar with it).

While Rust will let you call into C code directly, it doesn't look patricularly pretty and you're going back into the land of dangling pointers, null references, etc. So one usually writes a thin layer over the C bindings that hides the unsafe bits and exposes a more Rusty interface.

Most of the time, this is quite trivial if a bit tedius: you wrap the raw pointer in a struct, call the init and free functions in the constructor and destructor and create a method for any function that receives that pointer. This is nicely described in Rust's FFI guide.

So the tcod-rs bindings mostly worked like that with one exception: path finding. The situation there is a bit more complicated because there are callbacks involved.

Callbacks in C are a bit complicated. You usually want to access the outside world, but C doesn't have closures.

So the callback usually accepts additional user_data argument of type *void. The user of the library can then provide a pointer to any data they want to make available to the callback, which is then cast to (hopefully) the right type.

That's exactly how it works in libtcod.

When you create a new path finding object, you specify a callback which is supposed to return the cost of each step the algorithm is considering:

// the path finding object type
typedef void *TCOD_path_t;

// the callback function type
typedef float (*TCOD_path_func_t)( int xFrom, int yFrom, int xTo, int yTo,
void *user_data );

// create the path finding object
TCOD_path_t TCOD_path_new_using_function(int map_width, int map_height,
        TCOD_path_func_t func, void *user_data, float diagonalCost);

Converting this to Rust is quite straightforward, but it's very awkward to use and it means that every user of your library will have to deal with unsafe code to handle the user_data object and cast it back and forth.

What you really want to do is to pass in a closure. Closures have access to the environment they were defined in so there's no need for this user_data shenanigans.

The basic idea: when creating a new path finding object, the caller gives us a closure. We put it on the heap (so the C callback can access it as long as the path finding object exists) and store the owned pointer in the struct that represents the safe interface.

We then write a private C callback that gets a pointer to the closure as its user_data, casts it back and calls it.

So here's our path-finding object:

// We need a lifetime declaration because closures capture their environment
// by reference. This should go away once unboxed closures land.
pub struct Path<'a> {
    tcod_path: ffi::TCOD_path_t,
    closure: Box<|int, int, int, int|:'a -> f32>,  // Box<T> means T lives on the heap
}

and our constructor:

impl<'a> Path<'a> {
    pub fn new(width: int, height: int, callback: |int, int, int, int| -> f32,
               diagonal_cost: f32) -> Path {
        let callback_on_heap = box callback;
        let user_data = &*callback_on_heap as *mut |int, int, int, int| -> f32;
        let tcod_path = unsafe {
            ffi::TCOD_path_new_using_function(
                    width as c_int, height as c_int,
                    Some(c_path_callback),
                    user_data as *mut c_void,
                    diagonal_cost as c_float)
        };
        Path {
            tcod_path: tcod_path,
            closure: callback_on_heap,
        }
    }

    // Other methods...
}

So we move the callback on the heap (using the box statement) and cast it to a void pointer. Rust requires you to first cast a box or a reference to a raw pointer of the same type (e.g. *const int) and then cast that to a void pointer (*const int as *const c_void)). You could also use the transmute or transmute_copy functions, but they have slightly different semantics and are much more dangerous.

Now, instead of requiring our users to write the C callback, we write our own:

extern fn "C" c_path_callback(xf: c_int, yf: c_int, xt: c_int, yt: c_int,
                              user_data: *mut c_void) -> c_float {
    let cb_ptr = user_data as *mut |int, int, int, int| -> f32;
    let cb: &mut |int, int, int, int| -> f32 = unsafe { &mut *cb_ptr };
    (*cb)(xf as int, yf as int, xt as int, yt as int) as c_float
}

I.e. we cast the user_data pointer to (a reference to the) closure from earlier, call it and return the result.

This has the huge benefit that the library author can write and test this bit of unsafe code once and everyone else will just use closures and never have to worry about segfaults.

Speaking of segfaults: the code I originally wrote was using transmute and was casting user_data back to Box<|int, int, int, int| -> f32> instead of a reference. Everything compiled fine, but when I actually tried to use it, all hell break loose.

Valgrind was showing reads from unallocated memory and repeated invalid frees. This was a bit strange because my code wasn't supposed to be freeing anything.

Eventually I did remember that owned boxes get freed automaticaly when they go out of scope (obviously -- they're supposed to be the sole owner of the data they point to). So the first time the callback runs, everything is fine, except the cb closure gets freed at the end of it. And every other time, we're reading from freed memory. Which is why we need to cast it to a reference instead.

Let that serve as a cautionary tale that as far as unsafe is concerned, here be dragons. And also, transmute and especially transmute_copy are really dangerous (transmute_copy doesn't even do size checking). If I'd used the double casting trick, I wouldn't have even goten past the compiler with that bug. The writing unsafe code guide is a great starting point (I wish I'd known about it earlier).

Anyway, here's the final code in use:

let checkers_move = |from_x, from_y, to_x, to_y| -> f32 {
    // can only move diagonally:
    if (from_x != to_x) && (from_y != to_y) { 1.0 } else { 0.0 }
};
let (width, height) = (10, 10);
let mut path = Path::new(width, height, checkers_move, 1.0);
path.find(0, 0, 4, 6);
for coords in path.walk() {
    println!("Walking to: {}", coords),
}

\o/

Tomas Sedovic on 18 September, 2014