A bear playing hopscotch

Rust Reflection: Building a Runtime Reflection System (Part 1)

Sam Scott

Part 1: dyn Class

This is part one of our series on building a runtime reflection system for Rust!

Introduction

We're building Oso, an open source policy engine for authorization. You can use Oso to separate authorization logic from application code by writing policies in our declarative language, called Polar. Oso is built to be embedded directly in the application, which means you can pass in application objects, check types, lookup attributes, and call methods. To do this, it relies on each host language's support for runtime reflection.

This is trivial for languages like Python, for instance, where getting the type from an object is as simple as type(obj), and accessing arbitrary attributes and methods is just getattr(obj, "attr"). We first shipped Oso with support for Python, Ruby and Java, followed by JavaScript.

When we set out to build support for Oso in Rust applications, we had to solve this problem ourselves because Rust doesn't have any out-of-the box support for runtime reflection. It does, however, have some low-level building blocks that we can assemble to create something similar.

This is the first part of a three-part series in which we describe how we implemented a runtime reflection system in Rust for Oso.

In this post, we look at how dynamic type checks work in Rust, and explain how our team built a simple class system that we use as the foundation for the rest of the reflection system and the rest of the series.

Introduction to std::any::Any

The main way to achieve dynamic dispatch in Rust is through the trait system. And the Rust book has this quote for us in design patterns:

No matter whether or not you think Rust is an object-oriented language after reading this chapter, you now know that you can use trait objects to get some object-oriented features in Rust. Dynamic dispatch can give your code some flexibility in exchange for a bit of runtime performance

In some ways, the Mother of all Traits is std::any::Any, which the documentation describes as "A trait to emulate dynamic typing."

This lets us erase a thing's concrete type, and pass around its "trait object" instead:

let s: String = "Hello, World".to_string();
let any: Box<dyn Any> = Box::new(s);

// `any` doesn't have a type, running:
//    println!("{}", any);
// would fail with:
//     error[E0277]: `dyn std::any::Any` doesn't implement `std::fmt::Display`

let mut recovered: Box<String> = any.downcast().expect("failed conversion");
recovered.make_ascii_uppercase();
println!("{}", recovered);

In case you're interested: profiling the bottom code takes 18ns versus approx. 16ns for the version without downcasting. You can see in the assembly there's some 20-30 instructions needed for the conversion: https://godbolt.org/z/Ph6q3b.

A few layers beneath the surface of the Any trait, and what makes the above possible, is TypeId::of::<T>. This method uses a compiler intrinsic to inspect the object's type. The important part is that the original object still has a concrete type, even though that type has temporarily been "lost" to the current scope.

With this one small piece of intrinsic Rust, we begin to build our fully dynamic system.

What is Oso?

As mentioned at the beginning, Oso is a policy engine for authorization. It reads in policies – written in the Polar language – and makes authorization decisions by evaluating the rules against the provided inputs. Polar is a variant of Prolog, and encodes logic as rules. The syntax looks like this:

# True for all inputs that are of type Foo
is_a_foo(input: Foo);

# True if the x attribute of the input is equal to 1
x_is_one(input) if input.x = 1;

The important parts are (a) input: Foo which checks that the input parameter is of type Foo, and where Foo is a type defined in the application; and (b) input.x which is a lookup on input of the attribute x , even if input is an application object. These are the types of use cases that our dynamic system needs to support.

Implementing Class and Instance

We lay the foundation of our runtime reflection system by wrapping types up in classes, and wrapping objects as instances. Starting with just the pieces we've seen so far, the initial implementations for these look like this:

/// Class definition
struct Class {
   /// The name of the class
   name: String,
   /// The corresponding Rust type
   type_id: TypeId,
}

impl Class {
    /// Create a new class definition for the type `T`
    fn new<T>() -> Self {
        Self {
            name: std::any::type_name::<T>(),
            type_id: TypeId::of::<T>(),
        }
    }
}

/// An instance of a class
struct Instance {
    inner: Arc<dyn Any>, // `Arc` because we don't need/want mutability
}

impl Instance {
    /// Construct a new `Instance` from a type that
    /// implements `Any` (i.e. any sized type).
    fn new(obj: impl Any) -> Self {
        Self { 
            inner: Arc::new(obj)
        }
    }
}

With just this in place, we have our simple runtime class system!

Dynamic type checking

As shown in the brief snippet of Polar earlier, we want to be able to type-check using the syntax input: Foo. This translates into our class system as: "is input an instance of the Foo class"?

We could track what type the object had when we created it by storing the TypeId, but it's actually even simpler to recover the TypeId of the inner object stored on our Instance using the Any::type_id trait method:

impl Instance {
    /// Check whether this is an instance of the provided class
    fn instance_of(&self, class: &Class) -> bool {
        self.inner.as_ref().type_id() == class.type_id
    }
}

Not bad!

Note one important detail: when writing this example I initially wrote self.inner.type_id() == class.type_id . This is not the same thing as the code above, because Arc<dyn Any> also implements std::any::Any, and thus has a type ID. To avoid making these kinds of mistakes, we've found that the best practice is to restrict the number of places directly accessing the dyn Any object to as few as possible, providing helper functions for even the simplest of methods.

To test that this is working:

#[test]
fn test_instance_of() {
    struct Foo {}
    struct Bar {}

    let foo_class: Class = Class::new::<Foo>();
    let bar_class: Class = Class::new::<Bar>();
    let foo_instance: Instance = Instance::new(Foo {});

    assert!(foo_instance.instance_of(&foo_class));
    assert!(!foo_instance.instance_of(&bar_class));
}

And there we have it – we were able to successfully determine at runtime the class of the Instance!

Future extension: traits as interfaces

Now that we have our class system up and running, what else can we do with it? One pattern used in Oso policies is using inheritance to write rules over multiple objects. For example, we might model "vets can treat all pets," as can_treat("vet", pet: Pet), but "only doctors can treat a human" as can_treat("doctor", human: Human).

Rust doesn't really have any notion of subtypes (except for lifetimes, which are out of scope for this post) but it does have traits. And traits are like interfaces. So perhaps we should be able to use traits again in some way?

Revisiting the docs for std::any::Any we find:

Note that &dyn Any is limited to testing whether a value is of a specified concrete type, and cannot be used to test whether a type implements a trait.

Well, then.

Not all hope is lost, there are some interesting approaches out there to do just what we need. The most prominent approach I could find is query_interface. Or this blog post on dynamic casting for traits.

Digging into how query_interface works: there's a fair amount of unsafety and casting pointers and vtable manipulation. All fun stuff, but the disappointing part (for us) is that the "check whether a type implements a trait" is really handled at compile-time by the macro. There are lines like:

let x = ::std::ptr::null::<Foo>() as *const dyn MyTrait;

Which will error at compile-time if Foo doesn't implement MyTrait:

138 |     let x = ::std::ptr::null::<Foo>() as *const dyn MyTrait;
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `MyTrait` is not implemented for `Foo`

It's doing the wildly unsafe casting-trait-objects-to-other-trait-objects-at-runtime, but the checks are all done at compile-time. And the trait bounds are explicitly "registered" through use of the macro: interfaces!(Foo: dyn MyTrait).

Given that we're not yet interested in using trait implementations, rather just checking whether a type implements a trait or not, this approach doesn't help us get any closer to making our runtime reflection system support traits as interfaces.

If instead we scope the task to registering trait implementations as part of a macro, we can get there with something more straightforward:

trait HasInterface {
    fn has_interface<T: 'static + ?Sized>() -> bool;
}

impl HasInterface for Foo {
    fn has_interface<T: 'static + ?Sized>() -> bool {
        // compile-time assertions
        static_assertions::assert_impl_all!(Foo: MyTrait);

        // runtime check
        match std::any::TypeId::of::<T>() {
            x if x == std::any::TypeId::of::<dyn MyTrait>() => true,
            // ... etc
            _ => false,
        }
    }
}

The above code is safe, and can easily be automated through a macro. However, it does have the same limitation as query_interface – the traits need to be object safe.

Conclusion

We've built the foundation of our runtime reflection system through classes and instances, and we've shown some simple dynamic type checking using the built in Any trait.

Up next, things start getting a bit more complicated as we attempt to replicate Python's getattr magic method, and make it possible to look up attributes on Rust structs dynamically at runtime. Join us for Part 2: dyn Attribute.

And if you find these interesting problems to work on, we're hiring!

Want us to remind you?
We'll email you before the event with a friendly reminder.

Write your first policy