Idiomatic bindings to the Starcraft Broodwar game

[0x7CFE]

tl;dr; see "The Question" part.

Good day, rustaceans!

I with my friends are working on the bwapi-rs library that would eventually allow us to write bots for the legendary Starcraft game series using the Rust language (instead of C++ and Java which are the current options).

For over a decade there is a bot developing community around that game. Enthusiasts write bots and compete in various championships. Many of them research AI and Machine Learning. BWAPI is used by universities to teach their students. There is even a twitch channel that broadcasts games online.

As a first step towards our goal we have almost finished the BWAPI-C library which wraps existing C++ BWAPI and exposes bare C interface to be used by any other language capable of FFI. We hope, that our C library would eventually be used by others to bring BWAPI support to their language of choice. So, Rust is only one of such languages.

Right now I'm trying to figure out how to design Rust bindings in a most effective and idiomatic way. Of course, I would like to take advantage of Rust's immense abilities and design an API that's easy to use correctly, but at the same time that prevents you from doing something wrong.

Ok, to explain what means "wrong" I need to give a brief insight to the original BWAPI.

The API

In essence, BWAPI is a wrapper layer around the game engine that exposes an interface to:

• Read the game state (map contents, available resources, unit positions, …)
• Issue a command to a unit (move, attack, build, cast spell, …)
• Extend UI (on screen text, graphic primitives, …)
• And many more…

All of this is done by hacking into the game's memory and a lot of bit twiddling. Of course, all of this sound wildly unsafe or even dangerous. Yet, current implementation is quite stable. Blizzard even shared some info on the game internals, so it is OK.

From bot programmer's point of view, each in-game entity is represented by some object. Within a single game match each object has unique pointer and unique integer id associated with it. Basically, that means that objects are never disposed, so their memory location remains valid, much like Values in LLVM.

However, when match ends, all in-game objects are released and their ids may be reused. And that's where the problem arise, actually.

In order to write sound API in Rust, we need to restrict access to in-game objects and bound their lifetimes correctly. However, bots tend to store a lot of temporary information that is tied to in-game objects, like lists of seen hostile units and their expected position. We should provide a way to refer in-game objects whilst the match is active.

Before I'll write about the problems, let's recall the whole chain. So, we have BWAPI that is a C++ library. Next goes the BWAPI-C library which wraps C++ and yields bare-C API. Then we take the BWAPI-C's headers and bindgen them to generate contents of the bwapi-sys library.

Finally, we write idiomatic bindings around the bwapi-sys to make it actually useful. So, instead of painfully verbose C version:

Iterator* const minerals = (Iterator*) Game_getMinerals(Broodwar);
assert(minerals);

Unit* closest_mineral = NULL;
for (; Iterator_valid(minerals); Iterator_next(minerals)) {
    Unit* const mineral = (Unit*) Iterator_get(minerals);
    assert(mineral);

    if (!closest_mineral || Unit_getDistance_Unit(unit, mineral) < Unit_getDistance_Unit(unit, closest_mineral))
        closest_mineral = mineral;
}

if (closest_mineral)
    Unit_rightClick_Unit(unit, closest_mineral, false);

Iterator_release(minerals);

…we'll have something like this:

if let Some(mineral) = game
    .minerals()
    .min_by_key(|m| unit.distance_to(m)) 
{
    unit.right_click(&mineral, false);
}

All sys objects are wrapped with corresponding trait impls like Iterator and Drop. Also, conversion traits are provided to make distance_to() or right_click() intuitive. So far so good.

As I mentioned before, all in-game entities must be bound to some session object to be sure, that no reference outlives the session. And that is a problem, because we have no control over object lifetimes. All objects are created and released by the game engine, so there is a fixed time window in which we may access the objects.

In order to design sound API we need to express that contract as a lifetime, let's call it 'g. In that case Unit may be defined like this:

#[derive(Clone)]
pub struct Unit<'g> {
    raw: *mut sys::Unit,
    phantom: PhantomData<&'g Game>,
}

Essentially, it is a newtype that wraps a pointer to an opaque struct sys::Unit and ties it's lifetime to 'g. Because we do not control the actual lifetime of a raw object, we may clone Unit, unless clone outlives the game match.

All operations on Unit are delegated to library functions like this:

pub fn loaded_units(&self) -> Box<Iterator<Item = Unit<'g>>> {
    unsafe {
        let iter = sys::Unit_getLoadedUnits(self.raw);
        Box::new(BwIterator::from(iter))
    }
}

The loaded_units() method may be used to inspect contents of container units like bunkers, transport and so on. Notice, that we return an iterator that yields Units whose lifetime is also bounded by 'g.

Game Events

BWAPI provides a set of callbacks that fire when various game events occur. I wrapped them in a trait which should be implemented for some user's type later in the actual bot code. It is then registered as an event handler.

pub trait EventHandler<'g> {
    fn on_start(&mut self, game: Game);
    fn on_end(&mut self, is_winner: bool) -> Game;
    fn on_frame(&mut self);
    fn on_send_text(&mut self, text: &str);
    fn on_receive_text(&mut self, player: &mut Player, text: &str);
    fn on_player_left(&mut self, player: &mut Player);
    fn on_nuke_detect(&mut self, target: Position);
    fn on_unit_discover(&mut self, unit: &mut Unit);
    fn on_unit_evade(&mut self, unit: &mut Unit);
    fn on_unit_show(&mut self, unit: &mut Unit);
    fn on_unit_hide(&mut self, unit: &mut Unit);
    fn on_unit_create(&mut self, unit: &mut Unit);
    fn on_unit_destroy(&mut self, unit: &mut Unit);
    fn on_unit_morph(&mut self, unit: &mut Unit);
    fn on_unit_renegade(&mut self, unit: &mut Unit);
    fn on_save_game(&mut self, game_name: &str);
    fn on_unit_complete(&mut self, unit: &mut Unit);
}

Particularly interesting are the first two functions:

fn on_start(&mut self, game: Game);
fn on_end(&mut self, is_winner: bool) -> Game;

Please note, that on_start receives the Game by value and on_end hands it back. Because the game session is a purely dynamic thing, I need a way to tie static lifetimes to some dynamic state.

Game is a singleton object that is a root of the whole API. Every other thing is done by calling it's methods. Every other object is acquired within the lifetime of the Game.

By using ownership transfer technique I'm trying to express the fact, that user code gets access to the full game API only after on_start is fired. At the same point, user must release the whole thing and give up all possible references upon on_end.

By design, user is not able to construct Game directly, so the only option left is to hand back the very same instance of Game that was received at on_start. If we tie all in-game state and all references to that Game instance all will be fine… hopefully.

The Problem

Well… I simply don't know how to express that lifetime 'g correctly. Depending on the implementation attempt, I'm facing either the hell of self referential structs, or a lifetime that is not bounded correctly. In the latter case, I found a way to store Unit outside of game session, hence, break the limitations (see the P.S. below).

There is a lot of unsafety in the implementation details anyway, so the question is how to represent that lifetime at all (unsafe way is OK too).

If it's impossible then it's interesting nevertheless, because it means that BWAPI is an example of a library (of may be even a whole class of libraries) that simply cannot be made safe in Rust terms. So, even safe Rust API would actually be unsound and that's definitely not what we want.

The Question

OK, let's summarize all of the above in a compact form.

The question is how to design sound API that will wrap all of the following:

1. Underlying library controls lifetime of all in-game objects
2. All objects are acquired by opaque raw pointers and never created or released directly
3. There is a fixed amount of time when the whole API may be used, limited by callbacks
4. User references may not outlive that time
5. User code should be able to hold references to in-game objects in containers
6. All API contracts must be expressed in code, it must be impossible to do the wrong thing

Is there a way to express all of the above in an API that would be safe Rust from the user's perspective?

P.S.

In order to avoid XY problem, I tried to skip as much details of my "solution" as possible. Just in case, current state of research may be found here.

Example of API misuse may be found here.

Please note the following struct:

struct Ai<'g> {
    session: Option<Session<'g>>,
    bad: Option<&'g Unit<'g>>
}

The idea was that Session struct would encapsulate all of the game's and AI's state, so it should be impossible to store Unit outside of that session. However, bad is an example of an external reference that potentially outlives the session. Due to incorrect lifetime specification the whole code compiles just fine.

Thank you very much for your attention! We're really looking forward to any suggestions and/or help!

[eternaleye]

One option might be to invert this a little - namely, rather than on_start and on_end being methods on the EventHandler, instead use something along the lines of the "scoped thread" trick from crossbeam:

extern crate streaming_iterator;
use streaming_iterator::StreamingIterator;

impl Game {
    // Creates a `Session`, allows access to it temporarily, then destroys it
    fn start<F>(f: F) where
        F: FnOnce(&mut Session, &mut StreamingIterator<Item=Event>);
}

impl Session {
    fn minerals<'a>(&'a mut self) -> MineralsIterator<'a>;
    ...
}

Then, that closure pulls events from the StreamingIterator (which unlike Iterator, requires the user give up access to the current element in order to obtain the next), and acts on them by querying the Session. As everything obtained from the Session is bounded by it, and the Game::start function tears it down, this remains safe.

In general, the design you have looks very similar to what I'd expect to see in an inheritance-based design, where one would subclass an existing implementation of EventHandler and override some methods. I personally would find expressing the possible events as an enum to match against much more idiomatic for Rust.

[0x7CFE]

Thank you very much for your suggestion, it indeed looks very interesting! I'll definitely give it a try, just need to wrap my head around it.

Then, that closure pulls events from the StreamingIterator (which unlike Iterator, requires the user give up access to the current element in order to obtain the next), and acts on them by querying the Session.

If I understand correctly, that means that user code will be the one that pulls events, not the library. Don't sure how to deal with such contract in case of BWAPI.

You see, I work with BWAPI by providing callback functions to it. For example, BWAPI triggers the on_frame callback per each game tick which I, in turn, delegate to &EventHandler. You may check out the actual wrapping logic in aimodule.rs.

What should I do in your scheme? Should I generate events on callbacks and put them into queue which will be drained by the user? Of course that may work, but it sounds a little bit over-complicated.

In general, the design you have looks very similar to what I'd expect to see in an inheritance-based design, where one would subclass an existing implementation of EventHandler and override some methods. I personally would find expressing the possible events as an enum to match against much more idiomatic for Rust.

Interesting! Thank you.

[eternaleye]

If I understand correctly, that means that user code will be the one that pulls events, not the library. Don't sure how to deal with such contract in case of BWAPI.

Mm, that's a good point. In essence, what you have is an existing event loop which you want to integrate into, which is also a source of events. Moreover, it's one that's already chosen to use callback-based concurrency. However, that doesn't integrate all that well with most of the asynchronous I/O stuff in Rust, which seems to be converging on readiness-based APIs. You may find this post on the design of Futures in Rust interesting.

There are a few ways to reduce the mismatch, though.

You currently use an &EventHandler, rather than an &mut EventHandler, it seems. This requires internal mutability in the EventHandler implementation, and forces everything to deal with the possibility two methods may overlap execution. However, is this actually possible? If the source of events (BroodWar itself) is single-threaded, and a callback cannot be triggered while another is executing, you should be able to make strong enough guarantees to use &mut EventHandler instead.

If you can use &mut EventHandler, then that implies that the game alternates between two states: Running its own code until it produces an event, and running the user's code until it's finished handling an event. This, then, obviates the need for any more than a single queued item.

At that point, it may be possible to use either some form of coroutine abstraction (though the main Rust crate for this, libfringe, does not support Windows - and I'm not aware of any active bindings to the Fibers API) or inter-thread communication combined with blocking the main thread until the event handler finishes. Either of those would allow using readiness-based APIs, but may be more complex than is desirable.

Another option might be to have your library consume the start / end events, and respond to them by constructing a handler, by making the EventHandler trait inherit from Default, invoke Default::default() on start, and drop the handler on end.

[carols10cents]

I don't have any solutions for you, I just wanted to say that I think what you're working on is cool and this is an incredibly well-written post

[0x7CFE]

don't have any solutions for you, I just wanted to say that I think what you're working on is cool and this is an incredibly well-written post

Oh, thank you very much for your support! It is really pleasing English is not my native language, so it's always a challenge for me. I'll do my best!

[0x7CFE]

You currently use an &EventHandler, rather than an &mut EventHandler, it seems. This requires internal mutability in the EventHandler implementation, and forces everything to deal with the possibility two methods may overlap execution. However, is this actually possible?

Good point. I believe it is impossible. BWAPI itself is completely single threaded, mainly due to it's hacky nature and simply because it hooks to an ancient single threaded game engine.

If the source of events (BroodWar itself) is single-threaded, and a callback cannot be triggered while another is executing, you should be able to make strong enough guarantees to use &mut EventHandler instead.

Honestly speaking, I haven't paid much attention to mutability issues yet. Of course, it should be designed in a consistent way and correlate with underlying implementation. I haven't propagated &mut because I wasn't confident enough, that it would not cause reborrowing issues.

I believe, that Game itself should be treated as internally mutable, mainly because I haven't much control anyway. It's neither Send nor Sync for the moment, so it would probably be OK.

If you can use &mut EventHandler, then that implies that the game alternates between two states: Running its own code until it produces an event, and running the user's code until it's finished handling an event. This, then, obviates the need for any more than a single queued item.

It's very interesting observation! I think it may affect the overall design in a very productive way.

Another option might be to have your library consume the start / end events, and respond to them by constructing a handler, by making the EventHandler trait inherit from Default, invoke Default::default() on start, and drop the handler on end.

Actually, that's very similar to my initial design, but it was refactored during the fight with borrowck

Thank you very much for your time! You already helped a lot. I definitely need to invest some time rethinking the whole thing, though.

[johncf]

I think assigning a static lifetime 'g is not possible with the current design. In order to keep the current design of EventHandler, I'd suggest a slight modification:

pub trait EventHandler<'g> {
    fn on_start(&mut self, game: Game);
    fn on_end(&mut self, is_winner: bool) -> Game;
    fn on_frame(&mut self);
    fn on_send_text(&mut self, text: &str);
    fn on_receive_text(&mut self, player: BWCell<Player>, text: &str);
    fn on_player_left(&mut self, player: BWCell<Player>);
    fn on_nuke_detect(&mut self, target: Position);
    fn on_unit_discover(&mut self, unit: BWCell<Unit>);
    fn on_unit_evade(&mut self, unit: BWCell<Unit>);
    fn on_unit_show(&mut self, unit: BWCell<Unit>);
    fn on_unit_hide(&mut self, unit: BWCell<Unit>);
    fn on_unit_create(&mut self, unit: BWCell<Unit>);
    fn on_unit_destroy(&mut self, unit: BWCell<Unit>);
    fn on_unit_morph(&mut self, unit: BWCell<Unit>);
    fn on_unit_renegade(&mut self, unit: BWCell<Unit>);
    fn on_save_game(&mut self, game_name: &str);
    fn on_unit_complete(&mut self, unit: BWCell<Unit>);
}

Here, BWCell<T> will need to have an API similar to RefCell in std, where borrow() and borrow_mut() would panic based on an internal variable denoting their validity. The internal variable could be stored as part of a structure wrapping the object implementing EventHandler. So, BWCell<T> would look like this:

pub struct BWCell<T> {
    inner: T,
    valid: Rc<Cell<bool>>,
}

And Unit would simply be:

pub struct Unit(*mut sys::Unit);

Now, when the game engine calls on_end, the valid bool value, shared by all objects, should be set to false, so that future borrow and borrow_mut would panic. (Alternatively, those function could return Option<&T>.

Question: In the methods on_send_text and on_receive_text, how is the lifetime of text bound?

[Migi]

Here's another possible solution to your problem. Disclaimer: I don't know for sure if it's totally safe, I'm not an expert on this.

A lot of explanation is written in as comments in the link above, but here's the gist of how it works: A new EventHandler is created every time a new game starts. This is necessary, because 'g is a lifetime parameter of EventHandler, so if you use the same EventHandler for multiple games, then 'g will also be the same, which you don't want of course.

The EventHandler is created in a closure (provided by the user) that is called every time a game starts. That closure receives a Game<'g> with a certain lifetime 'g and it must return a boxed EventHandler<'g>. The lifetime 'g will actually not be the lifetime of the game, it will actually be 'static! However, the closure doesn't know that. It's defined as for<'g> FnMut(...) so it must work with all possible lifetimes 'g, possibly different ones each time the closure is called (i.e., each time a new game starts). That should make it impossible to "store" a Unit<'g> and use it in a different game.

To access the game, each event callback receives a &mut Game<'g> as an argument. You have to make sure that all calls into BWAPI are through that &mut game (not through for example a Unit<'g> alone), because BWAPI is not thread-safe, and not only that, but you're also not allowed to call into BWAPI between event callbacks at all I think. But that should be ok if you only allow acces into BWAPI through &mut Game<'g>, which is only available during event callbacks. I think Game<'g> can then even safely be marked Sync, but I'm not 100% sure.

[0x7CFE]

@Migi, thank you very much for your time! Your solution is interesting and very well documented! Something similar was suggested by @qthree a little bit earlier.

Currently I'm trying to figure out, which variant would be the best for the actual implementation.

[0x7CFE]

BWCell<T> will need to have an API similar to RefCell in std, where borrow() and borrow_mut() would panic based on an internal variable denoting their validity. The internal variable could be stored as part of a structure wrapping the object implementing EventHandler.

@johncf, thank you for the suggestion. Actually, the use of internal mutability was probably the first thing that came to my mind. Of course that would work, but it would be the best, if compiler will prevent us from writing improper code in the first place. I believe, that the whole thing may be implemented statically, and looks like we have now three proposals that exploit static lifetimes

[Migi]

@0x7CFE, oh I didn't see that suggestion by @qthree. I still don't see it actually, maybe it was deleted?

Also, that suggestion might not be completely successful at preventing the use of Units from one game in a different game. It makes sure that you can't access Self::Data outside the event handlers, but nothing actually forces the &'a mut Units to be stored inside Self::Data in the first place. You can store them elsewhere, because the lifetime 'a is valid as long as Ai exists, the same lifetime is used for all games.

Here's an example where units are stored for more than 1 game. I only modified the code in userspace.

I tried a similar solution at first, but I gave up with that method because I think if you want to enforce that users only store data of the game inside Self::Data, it requires higher-kinded types/lifetimes (Self::Data would instead have to be Self::Data<'b> or something similar).

[0x7CFE]

…oh I didn't see that suggestion by @qthree. I still don't see it actually, maybe it was deleted?

Oops, that's my fault. I received that solution on gitter and forgot to mention it here.

Also, that suggestion might not be completely successful at preventing the use of Units from one game in a different game. It makes sure that you can't access Self::Data outside the event handlers, but nothing actually forces the &'a mut Units to be stored inside Self::Data in the first place.

Oh, I believe you're right! Could you please explain, how your solution prevents that?

I think if you want to enforce that users only store data of the game inside Self::Data, it requires higher-kinded types/lifetimes (Self::Data would instead have to be Self::Data<'b> or something similar).

Speaking about higher kinded lifetimes, is there a way to use them directly? I tried something like for<'a> EventHandler<'a> but didn't managed to make it work.

[Migi]

Could you please explain, how your solution prevents that?

It's prevented by the fact that each time a new game starts, a new Game<'g> is created with a unique (from the point of view of usercode at least) invariant lifetime 'g. So the lifetime 'g is not reused for multiple games, unlike the lifetime 'a in @qthree's solution.

Speaking about higher kinded lifetimes, is there a way to use them directly?

No, because Rust doesn't have higher-kinded types or lifetimes (HKT). The for<'a> EventHandler<'a> is a higher-ranked trait bound (HRTB). I get these confused all the time too, I always have to look it up. Maybe there is a way to use HRTB's here to make it work, but I don't know how. The problem is that the associated type Self::Data is a type, not a trait bound, and we want to make it into a higher-kinded type Self::Data<'a> parameterized by 'a. I don't think this is possible in current Rust.

[0x7CFE]

It's prevented by the fact that each time a new game starts, a new Game<'g> is created with a unique (from the point of view of usercode at least) invariant lifetime 'g. So the lifetime 'g is not reused for multiple games, unlike the lifetime 'a in @qthree's solution.

Got it, thank you! I think, now I understand lifetimes a little better.

No, because Rust doesn't have higher-kinded types or lifetimes (HKT). The for<'a> EventHandler<'a> is a higher-ranked trait bound (HRTB).

Ah, I see. Indeed, I confused them too.