Safely presenting a C double linked list of non-owned data

help
1

I'm attempting to wrap a C library with types like this (it's wlroots, using wl_list):

struct wl_list {
	struct wl_list *prev;
	struct wl_list *next;
};

struct container {
    // ...
    struct wl_list available_items;
    struct child *selected_item;
};

struct item {
    int32_t data;
    struct wl_list link;
};

In C code, I would use the provided macro to iterate over the items. If you're curious how that works, the macro does this weird trick where it grabs the container struct of the wl_list (the item) using another macro, wl_container_of.

I've already got something to the effect of:

struct Container(*mut container);
struct Item(*mut item);

impl Container {
    // My question is about the return type here:
    fn available_items(&self) -> ??? {
        // complicated unsafe code
    }

    fn select_item(&self, selected: &Item) {
        // I haven't implemented this yet, but it'll probably be something like:
        unsafe {
            (*self.0).selected_item = selected.0
        }
    }
}

fn main() {
    // I'd like the user of my wrapper to be able to iterate over the available items
    // and select one, something like
    for v in cont.available_items() {
        if v.data() == 2 {
            cont.select_item(v);
        }
    }
}

What's the right type to return for available_items? I feel like I want an iterator; I'm not sure how to represent with the type system that the data is borrowed from C. What's idiomatic/correct here?

To make things more complicated, the items, which are on the heap, are actually owned by the C library I'm wrapping; I need to prevent users of the library from keeping a reference to any of them beyond when the container goes out of scope.

Thanks in advance for the help!

2

Not using a linked list :slight_smile:

Given the C code as defined, the most intuitive thing to do is to create a 3rd wrapper struct:

struct WlList(*mut wl_list);

And then return an instance of that for Container::available_items().

The thing about iterators here is, that likely can't be done without additional allocation per element, if it can be done at all witthout UB. Pointer chasing in Rust is bound to get you into trouble with rustc sooner or later due to lifetime constraints.

As for the FFI side, the reason for my suggestion is that it's generally best to wrap the C code in a way that preserves the semantics of the C API. If desired, rustacean APIs can be built on top of that.

3

This is represented by lifetimes in the Rust type system, so you solve this by making the Item type borrow the container.

use std::marker::PhantomData;

struct Item<'c> {
    ptr: *mut Item,
    _phantom: PhantomData<&'c Container>,
}

Alternatively, you can make the Item type by-value and only ever expose it by reference:

#[repr(C)]
struct Item {
    // we don't actually _use_ these struct fields; this is just so the
    // size matches, not that that actually matters
    prev: *mut Item,
    next: *mut Item,
}

Then you would write &Item everywhere in your API.

Note that either way, you must not use these item-references for mutating the linked list; all mutations (that change the structure of the list and not just data of one item) must go through functions on the Container type, as there's no reasonable way to write signatures for safe operations on the list starting from a node.

Once you do either of these, it should be possible to write an iterator that internally follows the doubly linked list without any trouble, I think.

It should also be possible to offer immutable next() and prev() on Item since the input and output have the same lifetime.

4

Borrowing the container seems to work, thanks!