Crossing the Impossible FFI Boundary, and My Gradual Descent Into Madness

Anyone trying to make a new mainstream language is completely insane, unless they're backed by a large corporation. 0

There are only two exceptions in the last 25 years that come close: Scala and Kotlin. 1 2 They did this by seamlessly building on an existing ecosystem, specifically Java's.

But what if you're a low-level, memory-safe language like Vale, Austral, or Ante? There's no existing ecosystem of fast, memory-safe code to use.

And unfortunately, seamlessly building on Rust's ecosystem is impossible...

...or so we thought!

The impossible task

Anyone who has tried to make Java call C, or Python call Javascript, or C call Rust, can tell you that it's really difficult to call functions from other languages.

Heroes throughout the ages have created tools like SWIG, CXX, etc. which at least make it possible for a user to reach across the Foreign Function Interface (FFI) boundary, if they can figure out the correct incantations. 3

But even with these tools, it's so difficult that we often just give up and call a microservice instead. 4

Calling into Rust is even harder; you can't just slap an extern onto your function, because Rust doesn't have a stable ABI; rustc-compiled functions don't have a predictable signature that the linker can recognize.

On top of that, we can't send normal Rust objects to C. We instead have to make new structs with #[repr(C)], which have rather restrictive rules about what they can contain.

And there are even more challenges here!

1. Rust has generics. If our language defines OurStruct, how would Rust create a Vec<OurStruct> when rustc doesn't know anything about OurStruct, like how big it is?
2. If calling from a language without a borrow checker, how do we uphold the Rust code's memory safety guarantees?
3. In the case of Vale, how do we uphold other guarantees that Rust doesn't respect, like higher RAII, fearless FFI, determinism, and perfect replayability?

It's a no-man's land that we dare not tread on, an uncrossable chasm, a mountain-sized wall of ice that we dare not scale. 5

But before we talk about how it could be done, what would it even look like?

What would it look like?

Our ultimate goal is to write this Vale code:

import rust.std.vec.Vec;

exported func main() {
  vec = Vec<int>.with_capacity(42);
  println("Length: " + vec.capacity());
}

Length: 42

...which would successfully make a Rust Vec and call capacity on it. 6

But first thing's first: a proof-of-concept for C!

In the last post, we talked about how C can treat Rust objects as opaque types, basically blobs of raw bytes that cannot be read directly.

TL;DR: By treating them as opaque, our C code was able to receive normal Rust objects (without repr(C)) from normal Rust functions (without no_mangle). We then hand this unreadable data back to other Rust functions to manipulate it, extract data from it, or do other useful things with it.

That was all under the hood, of course. With the proof-of-concept tool, the coder sees something more like this:

Under the hood, the tool automatically generates some Rust code, such as this definition for VecInt:

#[repr(C, align(8))]
pub struct VecInt([u8; 24]);

and this definition for VecInt_with_capacity:

#[no_mangle]
pub extern "C" fn VecInt_with_capacity(param_0_c: usize) -> VecInt {
  let param_0_rs: usize = unsafe { mem::transmute(param_0_c) };
  let result_rs: alloc::vec::Vec::<u64> =
      alloc::vec::Vec::<u64>::with_capacity(param_0_rs);
  let result_c: VecInt = unsafe { mem::transmute(result_rs) };
  return result_c;
}

...and then uses cbindgen to generate an equivalent C header into "rust_deps/rust_deps.h".

If you want to know more about that, check out the last post that describes it a little more.

However, the post very mysteriously left out the hardest part...

How does the tool get the correct information from:

#pragma rsuse VecInt = std::vec::Vec<u64>
#pragma rsfn VecInt_with_capacity = VecInt::with_capacity

to be able to generate the above Rust code?

Gathering type information

Let's look at this line first:

#pragma rsuse VecInt = std::vec::Vec<u64>

The tool needs to somehow generate this Rust code:

#[repr(C, align(8))]
pub struct VecInt([u8; 24]);

It needs three pieces of information about std::vec::Vec:

• Its size: 24 bytes.
• Its alignment: 8 bytes. 7 8
• Its real name: alloc::vec::Vec (we'll use this later).

The tool gathers this information by running a small Rust program (playground link) and reading the output:

fn main() {
  println!(
    "{} {} {}",
    std::mem::size_of::<std::vec::Vec::<u64>>(),
    std::mem::align_of::<std::vec::Vec::<u64>>(),
    std::any::type_name::<std::vec::Vec::<u64>>());
}

24 8 alloc::vec::Vec<u64>

(That's actually a simplified version, here's a more accurate example)

In other words, to be able to build our C program, our tool will first run this temporary Rust program. 9

A little weird, but straightforward!

Now, how does it generate the VecInt_with_capacity function we saw above?

Gathering function information

Given this line:

#pragma rsfn VecInt_with_capacity = VecInt::with_capacity

The tool needs to generate this Rust code:

#[no_mangle]
pub extern "C" fn VecInt_with_capacity(param_0_c: usize) -> VecInt {
  let param_0_rs: usize = unsafe { mem::transmute(param_0_c) };
  let result_rs: alloc::vec::Vec::<u64> =
      alloc::vec::Vec::<u64>::with_capacity(param_0_rs);
  let result_c: VecInt = unsafe { mem::transmute(result_rs) };
  return result_c;
}

To do that, it needs to know:

• The real name: alloc::vec::Vec::<u64>::with_capacity
• The return type: alloc::vec::Vec::<u64>
• The parameter types: usize

These are actually pretty tricky to determine.

I was hoping that I could just use std::any::type_name (playground link) or say this:

println!("fn {}", std::signature_of::<Vec<int>::with_capacity>());

But there is no signature_of, I just made that up.

This is the part I left out of the last post because the path from here becomes treacherous... and the only way forward is too arcane, too terrible to consider.

A horrifying idea

(Or, skip to the final approach!)

I considered a few other options, such as using macros to search through functions, or using the syn crate... but neither of those approaches has access to the information we need.

If we could just see all the functions for a given type, then perhaps we could search them for the correct overload, and print out their parameters.

So I thought, let's read rustc's MIR!

MIR is rustc's "Mid-level Intermediate Representation". rustc turns Rust source code into HIR, then MIR, then eventually, LLVM IR, which later gets turned into assembly code.

If we could search through the Rust libraries' MIR, maybe we could find the right function and print its parameters out!

An even better horrifying idea

But first, I asked on the Rust discord server if that really was the best way to get all the structs and functions for a target crate.

Luckily, Helix/noop_noob and anden3 arrived and told me a much better solution: get rustdoc's JSON output and read it with rustdoc_types!

That's probably way, way easier than reading MIR. To this day, I don't know if using MIR would have worked well.

Bless these two heroes, and may their names ever live on in glory.

Of course, I was then met with horrified reactions when I explained what I'd use it for.

I hope they never learn of the dark sorcery they helped me unleash on this world.

Let's be clear: rustdoc was not made for this. It was made to generate lovely HTML pages like this one. And even though it has JSON output, it's not even stabilized, and organizes its information for, you know, making documentation.

What could go wrong?

Anyway, I made the tool invoke rustdoc 10 and load the resulting JSON in with rustdoc_types and serde.

Then, the tool reads every single fn, struct, impl, trait, type, and use in every crate, and collects their relationships into a bunch of hash maps. 11 12

The quest begins!

At first, things were pretty easy. rustdoc_types::Function has pretty straightforward information:

pub struct Function {
    pub decl: FnDecl, // Parameters, return types
    pub generics: Generics, // <T>, where, etc.
    pub header: Header, // const, unsafe, async, etc.
    pub has_body: bool,
}

It wasn't terribly hard to loop through all the functions and compare their types to the ones supplied by the user.

Though, there were some tricky parts:

• To find a struct's method, we need to find all impls for that struct, and look through all of them.
• Sometimes, a struct's method is defined in a different crate entirely. 13
• Types often didn't know that they were using the default drop method.
• _Unwind_Reason_Code and some things in std::detect are referenced but somehow don't exist.

But it all worked! 14

At least, until I tried this line:

#pragma rsfn OsString_from_str = std::ffi::OsString::from

...which made the program burst into flames.

Why's that?

Because there are multiple overloads for the OsString::from function!

The tool couldn't figure out which to use.

Rust Function Overloads

Some already know about function overloading in Rust, but for those unfamiliar with the term, Wikipedia says:

And unfortunately for us, that's exactly what's happening here with the from method.

You see, we actually want to call this from method at os_str.rs:1595:

impl<T: ?Sized + AsRef<OsStr>> From<&T> for OsString {
    fn from(s: &T) -> OsString {
        s.as_ref().to_os_string()
    }
}

...because our &str is a kind of AsRef<OsStr>, as specified by os_str.rs:574:

impl AsRef<OsStr> for str {
    ...
}

However, we don't want to call this from function at os_str.rs:563 which makes an OsString from a String:

impl From<String> for OsString {
  fn from(s: String) -> OsString {
    OsString { inner: Buf::from_string(s) }
  }
}

And we also don't want to call this from function at convert/mod.rs:765, which can turn any T into itself:

impl<T> From<T> for T {
  fn from(t: T) -> T {
    t
  }
}

For clarity, here's that last one again, but replacing T with OsString:

impl From<OsString> for OsString {
  fn from(t: OsString) -> OsString {
    t
  }
}

In other words, there are three overloads:

• OsString::from(t: OsString)
• OsString::from(s: String)
• OsString::from(s: T) where T: ?Sized + AsRef<OsStr>

I concluded that when there are multiple overloads, the user can't say this anymore:

#pragma rsfn OsString_from_str = std::ffi::OsString::from

They must be more specific: 15

#pragma rsfn OsString_from_str = std::ffi::OsString::From<&str>::from

...and then our tool can narrow down the right overload somehow.

The descent into madness

It looked impossible. But I had an idea... an insane idea.

Sometimes, when the universe tells you something is too crazy to work, you just can't resist the urge to call its bluff.

And sometimes, you know that if you make a solution horrifying enough, it will inspire a legion of internet-goers to come up with something better.

So now here we stand, on the edge of sanity, knowing that the only path forward is through a forest of madness and a fiery chasm of sheer and utter folly.

Let's implement some Rust overload resolution logic!

And to do that, let's evaluate some generics too!

You'll see what I mean below.

Implementing overload resolution and generics

Remember, the tool has access to a lot of information. It knows about every struct, fn, trait, impl, and so on.

So why not use that information to narrow down which function we're calling?

For example, when the tool encounters this line:

#pragma rsfn OsString_from_str = std::ffi::OsString::From<&str>::from

Let's make it figure out which impl we're referring to as From<&str>.

To do that, the tool loops through all the impls for std::ffi::OsString. 16

It encounters os_str.rs:1595's impl, repeated here:

impl<T: ?Sized + AsRef<OsStr>> From<&T> for OsString {
    fn from(s: &T) -> OsString {
        s.as_ref().to_os_string()
    }
}

First, it attempts to match the user's From<&str> against the impl's From<&T>.

It succeeds, and along the way it figured out the impl's generic parameters, specifically that T = str.

Finally, it figures out the function's parameters. With T = str, it becomes:

    fn from(s: &str) -> OsString {

It then adds this to the final list of "eligible functions", hoping that we'll end up with only one.

Continuing on, the tool sees the next impl from os_str.rs:563:

impl From<String> for OsString {
  fn from(s: String) -> OsString {
    OsString { inner: Buf::from_string(s) }
  }
}

And it properly rejects it because the user's From<&str> doesn't match this From<String>.

Continuing on, the tool sees the next impl from convert/mod.rs:765:

impl<T> From<T> for T {
  fn from(t: T) -> T {
    t
  }
}

And with some clever logic, 17 our process can properly reject this one too.

We're left with one surviving overload. Success!

But let's take a step back, and recognize just how cursed this whole thing is.

It's complex: the generics and overload resolution logic, and all of their supporting infrastructure, is something like 1,700 lines of rather intricate code.

To make it solid enough to merge into the main branch, it could end up anywhere between 12,000 18 and 1,000,000 lines, depending on the temperaments of various deities.

And handling generics is a lot more perilous than I made it sound.

If you don't believe me, know that above, we didn't even check to see if our &str matched the predicate ?Sized + AsRef<OsStr>. We also didn't deal with conditionally compiled functions or whatever the heck this thing is. 19

Plus, as I got it working for more and more test cases, the number of unimplemented!() markers in the code didn't lessen... it only grew larger and larger.

So, despite all the fun I was having, I was getting slightly worried about this endeavor.

Wisdom prevails

Let's travel back in time a bit.

Before I even started with this overload resolution, I knew what I was getting into.

After all, I've implemented seven different iterations of generics and overload resolution for Vale, each larger and more powerful than the last.

Back then, I knew in my bones that I was standing on the edge of sanity, and the only path forward was through that forest of madness and that fiery chasm of sheer and utter folly and so on. 20

So before I started implementing it, I also lit the beacons and called for aid.

In other words, I posted on the Rust internals forum, sent a couple emails, and even tried baiting a better solution out of everyone in the last post:

Unfortunately, nobody had a better approach, which meant using rustdoc was the only way forward.

Eventually, I'd gotten the overload resolution working for over half the test cases.

Then, I got a reply to one of my emails!

A better solution: Rust sorcery!

The reply was from Alex Kladov, also known as matklad, the author of rust-analyzer and IntelliJ Rust. He's also working on TigerBeetle (a Zig database which has a really cool approach to handling memory by the way), and he's the MVP of this post. 21

He suggested that I do the following magic (playground link):

trait Reflect<Args> {
    fn reflect();
}

fn reflect<T: Reflect<Args>, Args>(_: T) {
    T::reflect()
}

impl <F, T> Reflect<(T,)> for F where F: Fn(T) {
    fn reflect() {
        println!("1 {}", std::mem::size_of::<T>())
    }
}

impl <F, T, U> Reflect<(T, U, )> for F where F: Fn(T, U) {
    fn reflect() {
        println!("1 {} {}", std::mem::size_of::<T>(), std::mem::size_of::<U>())
    }
}

fn main() {
    reflect(Vec::<std::ffi::OsString>::clear);
    reflect(Vec::<std::ffi::OsString>::push);
}

1 8
1 8 24

This code takes a function (such as Vec<OsString>::push) and figures out what kind of Fn trait it implements and what kind of arguments it takes.

I then expanded it to this code which also prints out the function's real name and return type too.

And it worked! By the time this Rust-based solution passed the fourth test case, I was celebrating.

More function overloading troubles

Unfortunately, this approach also had trouble with overloaded functions.

Remember this line?

#pragma rsfn OsString_from_str = std::ffi::OsString::from

This is the line that originally caused the rustdoc-based solution to have overload resolution and generics-resolving logic.

Our new Rust-based solution generates this line, which Rust doesn't like:

reflect(std::ffi::OsString::from);

I tried all sorts of things:

reflect(std::ffi::OsString::From<&str>::from);`

reflect(std::ffi::OsString::from::<&str>);`

type FromStrToOsString = fn(&str) -> OsString;
let thing: FromStrToOsString = OsString::from;
reflect(thing);

...but nothing worked.

So, hope dashed, I resumed the rustdoc-based solution, with all its complex overload-resolution and generics-resolving logic.

Persistence

But a good engineer never gives up on finding a simpler solution!

So, in parallel with finishing the rustdoc-based solution, I was still trying to make the Rust-based solution work for overloaded functions.

Finally, on the fourth day of this whole quest, I was able to make a function that selects the correct overload for a given function (playground link).

fn select_overload_1<R, P1>(thing: impl Fn(P1) -> R + PrintFn<(R, P1, )>)
-> impl Fn(P1) -> R + PrintFn<(R, P1,)> {
    thing
}

It could be called like this:

print_fn(select_overload_1::<_, &str>(std::ffi::OsString::from));

That's it! A mere few lines, to do what my 3,200 line prototype struggled with.

Truly, it is a strange fate that we should suffer so much over so small a thing.

Huge thanks to Alex for providing the foundation for this eventual solution!

Moral of the story: always be searching for a simpler approach than the one you're currently implementing. 22

Luckily, this meant that I could delete all of the complex overload resolution and generics logic in the tool.

I have never been so relieved to delete thousands of lines!

And as it turns out, a lot of the rustdoc infrastructure will actually come back for some of the Vale integration, so this cursed endeavor wasn't completely fruitless.

On top of that, it's good to know just how far we can take this rustdoc information. The implications for code generation are pretty huge. I could imagine some of you will read all this and think of some equally insane uses for this kind of power.

Update: An even better solution!

And then, after reading this very post, literallyvoid found a simple one-line solution:

print_fn(<std::ffi::OsString as From<&str>>::from);

Is that even valid Rust syntax? Apparently! 23

And I bet a few you already know about this, and you've been dying this entire time, reading about this cursed side-quest! That makes me chuckle.

Huge thanks to literallyvoid, for seeing the solution that so many of us didn't!

The final approach

I emerge, battered and bloody, not sure what curséd arcana I've wrought.

But it works! And it does it without too much complexity. 24

In the end, it:

• Reads all the #pragma rsuse lines from a given C file.
• Generates a temporary Rust program which looks like this to print types' names and sizes and alignments, and functions' names and parameters and returns.
• Invokes cargo run on the temporary program to gather its output.
• Until I can remove it, still uses information from cargo rustdoc to correct some user-given type names. 25
• Generates a Rust library that will allow C to call into the Rust functions, using the technique from the last post.

That's it! You now know the tool's secret rituals for crossing the impossible boundary between Rust and C.

If you're curious, the code is here (but be warned, it's not cleaned up yet). 26 27

I don't have any specific plans to turn this C proof-of-concept into a production-quality tool that would enable calling Rust from C, but if anyone wants to take it from here, I'd be happy to assist!

From here, the next step is to finish integrating this tool into Vale, so that we can accomplish the original goal:

import rust.std.vec.Vec;

exported func main() {
  vec = Vec<int>.with_capacity(42);
  println("Length: " + vec.capacity());
}

Length: 42

We're closer than you might think! 28

A veil, a ritual, and a leather-bound tome

The last post showed how we use opaque types to "directly" call into Rust functions.

And then this post talked about how we used some arcane Rust generics to select the correct functions and structs, and gather information about them.

However, there are still some unanswered questions:

1. If our language defines OurStruct, how would Rust create a Vec<OurStruct> when rustc doesn't know anything about OurStruct, like how big it is?
2. If calling from a language without a borrow checker, how do we uphold the Rust code's memory safety guarantees?
3. In the case of Vale, how do we uphold other guarantees that Rust doesn't respect, like higher RAII, fearless FFI, determinism, and perfect replayability?

The keys to these questions lie deep in the grimoire, hidden to the untrained eye.

We'll talk about them in the next post!

Thank you!

A lot of people helped make this happen:

• Huge thanks to Alex Kladov (matklad), who showed me the basic Rust sorcery that let us print out functions' arguments and return types. Without Alex's help, this would still be a complex beast!
• Thank you to Helix/noop_noob and anden3 from the Rust discord server, for telling me about rustdoc's JSON output!
• And another big thanks to Jeff Niu, snej, kornel, and bjorn3 for fixes and advice on how to correctly use these opaque types with FFI!

With all our powers combined, we might cross this impossible FFI boundary, and make it so languages worldwide can call into Rust code much more easily.

That's all!

If you have any questions, always feel free to reach out via email, twitter, the discord server, or the subreddit.

Onward!

- Evan Ovadia

PS. If you enjoyed reading this, consider buying an adorable snow bird plushie from my partner's etsy store!

She broke free from big tech to chase her dream of sharing cute birds with the world, so I'd love it if her little shop takes off!