Forem: Michał Siedlaczek

Transposing options/results with iterators

Michał Siedlaczek — Tue, 05 Jan 2021 01:22:19 +0000

In this article, I would like to share some of my thoughts about a problem I encountered, my process of solving it, and possibly start a discussion about the validity of the proposed approach. I certainly would like to hear any comments and opinions about both the problem and the decisions I made in my solution.

The topic of this article is transforming, or "transposing", an optional collection or an iterator into an iterator of options. You might be familiar with Option::transpose and Result::transpose methods, which transform Option<Result<T, E>> into Result<Option<T>, E> and vice versa. My goal is quite similar, but instead, I would like to transform Option<I: IntoIterator> into impl Iterator<Option<I::Item>> and Result<I: IntoIterator, E> into impl Iterator<Result<I:Item, E>>.

First, I will discuss the motivation behind it and how such operation could be defined. Then, I will walk you through the implementation of this functionality, which uses a trait to extend Option and Result with an additional method. So hopefully, even if the motivation fails to convince you, there is still some value in following the implementation details.

Keywords: rust algorithm iterator

Source Code

I shared the code from this article in a small crate available on Github. I also uploaded the reference documentation if you would like to take a closer look.

Motivation

First, let me share with you what motivated me to look into this problem in the first place. Suppose you have a type that stores two values, one of which is potentially expensive to compute. The latter doesn't need to be provided when creating an object, and if it is missing, it either gets computed or is given a default value.

struct Entry {
    id: String,
    value: u64,
}

impl Entry {
    pub fn new(id: String, value: Option<u64>) -> Self {
        Self {
            id,
            value: value.unwrap_or_else(Self::default_value),
        }
    }
    fn default_value() -> u64 {
        todo!("Compute or provide default")
    }
}

Let's assume that the IDs are read from a file, line by line. The values are computed by some other process and also stored in a file. Our main program takes the first file and optionally the one with values. The details about this particular setup are not important, the point is that we either have all the values or none. We now want to load that data to Vec<Entry>. Here is an example of how it could be done (note that I will panic instead of handling errors for simplicity, but the same can be implemented with proper error handling):

fn load_entries<R: BufRead>(ids: R, values: Option<R>) -> Vec<Entry> {
    let mut values = values.map(|r| {
        r.lines().map(|line| {
            line.expect("cannot read line")
                .parse::<u64>()
                .expect("cannot parse as u64")
        })
    });
    ids.lines()
        .map(|line| {
            let id = line.expect("cannot read line");
            Entry::new(id, values.as_mut().and_then(|values| values.next()))
        })
        .collect()
}

This certainly works, but it is a bit verbose and I must say I dislike the mutable iterator in this context. I wish I could just zip the two together. And this is precisely what I set out to do below.

Iterator Adapter

Our iterator adapter can be easily implemented using std::iter::from_fn as we see below:

fn transpose_into_iter<I: IntoIterator>(iter: Option<I>)
    -> impl Iterator<Item = Option<I::Item>>
{
    let mut inner = iter.map(|i| i.into_iter());
    std::iter::from_fn(move || {
        inner.as_mut().map_or(Some(None), |iter| iter.next().map(Some))
    })
}

That was pretty easy. We simply encapsulate what we did before in the map function. Let's quickly go through the entire function. The argument is of type Option<I> where I implements IntoIterator. This essentially means that we can call into_iter() on any value of type I to get an iterator over its elements. Notice that IntoIterator is trivially implemented for any I: Iterator, in which case into_iter() simply returns self. Many other types implement IntoIterator, such as collections, e.g., Vec and HashSet, slices, and even Option and Result.

IntoIterator has two associated types: Item and IntoIter. The latter is the type resulting iterator, and the former is the type of the elements of that iterator. We can refer to these types with a double colon: I::Item. We exploit this in defining the return type of the function: impl Iterator<Item = Option<I::Item>>. It means that this function returns a type that implements the Iterator trait, and its elements have type Option<I::Item>.In other words, the elements of the resulting iterator will be the elements of the input iterator (if such exists) wrapped in Option.

In the body of the function, we first map the optional value from the type of Option<I: IntoIterator> to Option<I: Iterator>. Then, we return a special from_fn iterator adapter, which simply calls the passed closure each time the iterator's next() method is called. It will always return Some(None) (thus, the actual element returned is None) if inner is None. Notice how this will result in an infinite iterator, always returning None. If inner is Some(_), we will return the next element wrapped in Some until the underlying iterator runs out of elements. A minor change to the code would make it produce None after all existing elements. Notice how the latter would be more general, as we can call take_while(Option::is_some) to reduce it to a finite sequence. However, I decided to stick with the first approach. Let me know if you have an opinion in favor of either of them.

Either way, we can now use this adapter in our example:

fn load_entries_with_transpose<R: BufRead>(ids: R, values: Option<R>)
    -> Vec<Entry>
{
    let values = values.map(|r| {
        r.lines().map(|line| {
            line.expect("cannot read line")
                .parse::<u64>()
                .expect("cannot parse as u64")
        })
    });
    ids.lines()
        .zip(transpose_into_iter(values))
        .map(|(line, value)| Entry::new(line.expect("cannot read line"), value))
        .collect()
}

Nice, no more mutable state. We could leave it as is and call it a day, but notice that we will have to have another function for Result because we can't simply overload it for another type. In Rust, function overload is achieved through traits. However, impl Trait return value is not allowed in trait functions, so we will have to come up with a concrete (associated) type.

Implementing Trait

As mentioned before, we have to return a concrete type in a trait.

pub trait IterTranspose {
    fn transpose_into_iter(self) -> T;
}

Now, what should T be? It probably depends what type implements the trait. This is a perfect use for an associated type:

pub trait IterTranspose {
    type Iter: Iterator;
    fn transpose_into_iter(self) -> Self::Iter;
}

Now the return value has a concrete type, but because it is an associated type, it depends on the implementation. What would be Iter for the example above? This is a bit tricky, because we can't express the concrete type of a closure. We could set it to std::iter::FromFn<Box<FnMut() -> Option<T>>> but then we would additionally have to define T and, more importantly, it would introduce dynamic dispatch. Instead, we can create a simple struct that implements Iterator directly, which is as simple as our previous implementation:

pub struct OptionTransposedIter<I> {
    inner: Option<I>,
}

impl<I: Iterator> Iterator for OptionTransposedIter<I> {
    type Item = Option<I::Item>;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner
            .as_mut()
            .map_or(Some(None), |iter| iter.next().map(Some))
    }
}

Now we are ready to implement IterTranspose:

impl<I: IntoIterator> IterTranspose for Option<I> {
    type Iter = OptionTransposedIter<I::IntoIter>;

    fn transpose_into_iter(self) -> Self::Iter {
        OptionTransposedIter {
            inner: self.map(I::into_iter),
        }
    }
}

And finally, this is what our example looks like using the new interface:

fn load_entries_with_transpose<R: BufRead>(ids: R, values: Option<R>)
    -> Vec<Entry>
{
    use IterTranspose;
    let values = values.map(|r| {
        r.lines().map(|line| {
            line.expect("cannot read line")
                .parse::<u64>()
                .expect("cannot parse as u64")
        })
    });
    ids.lines()
        .zip(values.transpose_into_iter())
        .map(|(line, value)| Entry::new(line.expect("cannot read line"), value))
        .collect()
}

Result

The implementation for Result<T, E> is very similar, and I won't repeat it here, but if you are interested in my implementation, visit the Github repository. One important difference is that the Err variant holds a value of type E and needs to produce it repeatedly. This means that it must implement E: Clone. Besides that, the implementation for Result is analogous to the one above.

Summary

We discussed how to transform an Option<I: IntoIter> (or Result<I: IntoIter, E>) to an impl Iterator<Item = I::Item>, similar to how Option::transpose transforms Option<Result<T, E>> into Result<Option<T>, E>. Such operation can be useful, e.g., when we want to zip a collection with another collection that is optional. We first saw how to solve this problem using std::iter::from_fn, and then how to overload our adapter function for multiple types (Option and Result) using a custom trait with an associated type.

Although the problem we solved is rather niche, I found the path to solution interesting. It touches several important parts of Rust, such as iterator, traits, and generic programming. It also addressed a problem I have come across more than once now, and it was fun to approach it as a generic solution and write it as a crate.

If you have any questions or suggestions, don't hesitate to reach out on Twitter or Mastodon.

Type-Safe Discrete Simulation in Rust

Michał Siedlaczek — Mon, 09 Nov 2020 23:10:00 +0000

In this article, I want to share some of my experience from implementing a small discrete-event simulation library. The code is available on github, and the (limited at the moment) documentation on docs.rs. Note that this implementation is experimental, so use caution if you want to use any of the code in the current form.

The main focus of this write-up is the library's type-safe interface. There is no jaw-dropping magic here, but I found the process of writing it very educational, and decided to share what I had learned. If you have any comments you'd like to share, corrections you'd like to make, or questions you'd like to ask, please do reach out, I would be very interested in hearing from you.

Keywords: rust type-safe simulation

I recently found myself in a need of a discrete-event simulation for one of my research projects. Although there are a number of existing open source libraries available for this exact problem, nothing truly worked for me. Many of them are quite old and not maintained for the past few years, some have other issues. The closest one to working for me was SimPy python library. This one, however, turned out to be very slow, and I got impatient with it quickly. SimJulia looks nice, but I have yet to learn Julia, and because the simulation is only part of the project, I wanted to use a language I'm familiar with and know what to expect from. More importantly, the simulations I need to run are not very complicated, so I figured a bespoke solution might be just what I needed. Plus, I could learn a thing or two, so why not.

Nowadays, I default to Rust when there are no language or library constraints. It should be noted that I had found a few Rust libraries that might have worked, but these didn't seem to be either mature or maintained. Therefore, I set out to write some simulation code in Rust. After prototyping several approaches, I ended up with some ideas and requirements for the core simulation module. Here, I want to focus on one important requirement that became clear quite quickly, which is type safety. Because even simple simulations have many moving pieces and are not trivial to test, I wanted to unload as much of correctness checking as possible onto the compiler.

System Components

First, let's talk about the overall system design and look at its pieces and how they interact. Note that this is by no means the best or even a correct way of designing simulations, but it seemed to fit my use case. On the other hand, nothing is written in stone, and I am open to suggestions.
At the highest level, my simulation consists of the following elements:

scheduler, which keeps track of time and events,
state, which stores any mutable information about the simulation,
components, which do some work, interact with each other, and sometimes mutate the state.

The state further distinguishes between regular values and queues, which are used to pass messages between components. Technically speaking, this distinction is not necessary, but queues are so useful that a dedicated interface is just convenient.

Requirements

One should be able to create an unlimited number of different types of components, and seamlessly inject them into the simulation. Each component can have a different type of event it reacts to. Ideally, it should be impossible to request scheduling an event of a wrong type or direct it to a component that doesn't exist. Similarly, it should be impossible to send a wrong type of value over a queue. Whenever possible, these checks should be done at compile time. In any other case, an invalid operation should terminate the simulation immediately with an appropriate error message.

Type-Safe Keys

I want to have an easy way of identifying components, stored objects, and queues with a key that can be easily stored, passed, and copied throughout the system. It would also be used as a handle to refer to the simulation's internal objects from outside of the module. In other words, I want an ID:

struct Key(usize);

Notice how the integer unnamed field is private. This prevents a user from constructing an arbitrary value and using it to, say, schedule an event on a component. The simulation itself takes responsibility for generating valid IDs. However, nothing stops us from passing a key generated for type T and use it to request type U. To rectify that, we can introduce a type marker:

#[derive(Debug, PartialEq, Eq, Hash)]
struct Key<T> {
    id: usize,
    _marker: std::marker::PhantomData<T>,
}
impl<T> Key<T> {
    // NOTE: Must be private or at most `pub(crate)` to not allow creating
    //       from outside of the crate.
    fn new(id: usize) -> Self {
        Key { id, _marker: std::marker::PhantomData }
    }
}

I precede the marker with an underscore to show it will never be used. Notice that I derived a few traits that might be useful for an ID type. But there are some that are still missing. In particular, I did not derive either Clone or Copy. The reason for this is that the compiler won't allow it unless I also constrain T to be Copy, but that would unnecessarily limit the types of values I can, say, store in the simulation state, or the types of events that can be passed. Instead, I can implement these manually:

impl<T> Clone for Key<T> {
    fn clone(&self) -> Self {
        Self::new(self.id)
    }
}
impl<T> Copy for Key<T> {}

Generating Keys

There are certainly several ways of generating these keys, but I will keep it simple. We can have a simple counter field in the simulation and increment it each time we return a new key. There is a trap here, however. Remember that our goal is to ensure type safety, which we did by introducing the type marker. Now, we need to ensure that having received a key, we can only use it to refer to the correct type of objects. If the IDs are unique only within a simulation, nothing stops the user from generating the same numerical ID of different types from two different simulations! It might be a rare problem, but there is a simple fix. Instead of storing the counter in the simulation, we can use an atomic static counter, which will ensure uniqueness of all IDs across the entire program.

use std::sync::atomic::AtomicUsize;
static ID_COUNTER: AtomicUsize = AtomicUsize::new(0);

// NOTE: Private function available only inside the module.
fn next_id() -> usize {
    ID_COUNTER.fetch_add(1, std::sync::atomic::Ordering::SeqCst)
}

State

Having defined the key type, let's use it to implement the simulation state. Let's start with the API.

impl State {
    pub fn insert<V: 'static>(&mut self, value: V) -> Key<V> { ... }
    pub fn remove<V: 'static>(&mut self, key: Key<V>) -> Option<V> { ... }
    pub fn get<V: 'static>(&mut self, key: Key<V>) -> Option<&V> { ... }
    pub fn get_mut<V: 'static>(&mut self, key: Key<V>) -> Option<&mut V> { ... }
}

When inserting a value, we receive a key that can be later used to remove it or get a reference to the stored object. As you can see, the only thing we require from the values is that they don't contain any non-static references, which is indicated by V: 'static lifetime constraint. That's all nice, but how do we actually store values of any given type? Answer: we use an std::any::Any trait object. I recommend reading the documentation to learn more about it, but in short, this is a trait used for type erasure. For example, a Box<T> can be cast to Box<dyn Any> and later downcast to its concrete type. This is illustrated in the implementation below.

struct State {
    values: std::containers::HashMap<usize, Box<dyn std::any::Any>>,
}
impl State {
    #[must_use = "Discarding key results in leaking inserted value"]
    pub fn insert<V: 'static>(&mut self, value: V) -> Key<V> {
        let id = Self::generate_next_id();
        self.store.insert(id, Box::new(value));
        Key::new(id)
    }
    pub fn remove<V: 'static>(&mut self, key: Key<V>) -> Option<V> {
        self.store
            .remove(&key.id)
            .map(|v| *v.downcast::<V>().expect("Ensured by the key type."))

    }
    pub fn get<V: 'static>(&self, key: Key<V>) -> Option<&V> {
        self.store
            .get(&key.id)
            .map(|v| v.downcast_ref::<V>().expect("Ensured by the key type."))
    }
    pub fn get_mut<V: 'static>(&mut self, key: Key<V>) -> Option<&mut V> {
        self.store
            .get_mut(&key.id)
            .map(|v| v.downcast_mut::<V>().expect("Ensured by the key type."))
    }
}

Notice I added a must_use attribute to insert because dropping the key effectively stops us from ever using that value again.

As I mentioned before, I would like to have additional interface for manipulating queues. The implementation is very similar to the value store, but some extra logic is necessary. I won't get into much details about it, as it's pretty straight forward, and rather tangent to the main point, but here's the code:

struct State {
    values: std::containers::HashMap<usize, Box<dyn std::any::Any>>,
    queues: std::containers::HashMap<usize, Box<dyn std::any::Any>>,
}
impl State {
    pub fn send<V: 'static>(&mut self, queue: QueueId<V>, value: V) -> Result<(), ()> {
        self.queues
            .get_mut(&queue.id)
            .expect("Queues cannot be removed so it must exist.")
            .downcast_mut::<Queue<V>>()
            .expect("Ensured by the key type.")
            .push_back(value)
    }

    pub fn recv<V: 'static>(&mut self, queue: QueueId<V>) -> Option<V> {
        self.queues
            .get_mut(&queue.id)
            .expect("Queues cannot be removed so it must exist.")
            .downcast_mut::<Queue<V>>()
            .expect("Ensured by the key type.")
            .pop_front()
    }

    pub fn len<V: 'static>(&mut self, queue: QueueId<V>) -> usize {
        self.queues
            .get(&queue.id)
            .expect("Queues cannot be removed so it must exist.")
            .downcast_ref::<Queue<V>>()
            .expect("Ensured by the key type.")
            .len()
    }
}

I omit the implementation of Queue itself. In my library, this is a simple wrapper over VecDeque with an added concept of limited capacity. Notice I use a separate QueueId type, which is similar to Key but works only with queues.

Event Entries

Although I want each component to have its own event type, the scheduled events still must be stored together. Furthermore, they need to be accessed in order of their scheduled time. I will use a binary heap for this. Thus, I define the following entry struct.

#[derive(Debug)]
pub struct EventEntry {
    time: Reverse<Duration>,
    component: usize,
    inner: Box<dyn Any>,
}

Notice that because the event type is erased, we store the raw component ID, which will be used to fetch the component. Of course, to use it in a binary heap, we need to also implement the Ord trait to define a total order over time.

Components

Components are the part of the simulation provided by the user, and there should be no constraint on how many we can define. Therefore, we supply a trait that must be implemented for each component.

pub trait Component {
    type Event: 'static;

    fn process_event(
        &self,
        self_id: ComponentId<Self::Event>,
        event: &Self::Event,
        scheduler: &mut Scheduler,
        state: &mut State,
    );
}

A component has an associated type Event and one associated function: process_event. It takes the following arguments:

its own ID: this is because the ID is unknown at the moment of construction (it's assigned by the simulation, recall),
the event,
the scheduler (we'll get back to this shortly),
and the state.

With this interface though, we'll hit a little snag. Recall that the event type is erased when pushed to the heap as EventEntry. Therefore, the scheduler won't know the correct type to downcast to. We could try casting to different types, but this would require us to know all possible event types beforehand. Instead, we will use a little trick:

pub struct EventEntryTyped<'e, E> {
    pub time: Duration,
    pub component_id: ComponentId<E>,
    pub component_idx: usize,
    pub event: &'e E,
}

impl EventEntry {
    #[must_use]
    fn downcast<E: 'static>(&self) -> Option<EventEntryTyped<'_, E>> {
        self.inner.downcast_ref::<E>().map(|event| EventEntryTyped {
            time: self.time.0,
            component_id: ComponentId::new(self.component),
            component_idx: self.component,
            event,
        })
    }
}

trait ProcessEventEntry {
    fn process_event_entry(
        &mut self,
        entry: EventEntry,
        scheduler: &mut Scheduler,
        state: &mut State,
    );
}

impl<E, C> ProcessEventEntry for C
where
    E: 'static,
    C: Component<Event = E>,
{
    fn process_event_entry(
        &mut self,
        entry: EventEntry,
        scheduler: &mut Scheduler,
        state: &mut State,
    ) {
        let entry = entry
            .downcast::<E>()
            .expect("Failed to downcast event entry.");
        self.process_event(entry.component_id, entry.event, scheduler, state);
    }
}

We defined another trait called ProcessEventEntry, which takes the erased EventEntry. Then, we provide a blanket implementation for any defined component that will correctly downcast the event type. This way, a user defining a new component can implement a function that operates on concrete types, and the ugly details are generated for them. Plus, the casting code cannot be overridden (and potentially broken) because the trait is not exposed to the user.

Additionally, I define a separate container for components:

pub struct Components {
    components: Vec<Box<dyn std::any::Any>>,
}

impl Components {
    #[must_use]
    pub fn add_component<E: 'static, C: Component<Event = E> + 'static>(
        &mut self,
        component: C,
    ) -> ComponentId<E> {
        let id = generate_next_id();
        let component: Box<dyn ProcessEventEntry> = Box::new(component);
        self.components.push(Box::new(component));
        ComponentId::new(id)
    }

    pub fn process_event_entry(
        &self,
        entry: EventEntry,
        scheduler: &mut Scheduler,
        state: &mut State,
    ) {
        self.components[entry.component_idx()]
            .downcast_ref::<Box<dyn ProcessEventEntry>>()
            .expect("Only objects implementing  ProcessEventEntry are ever stored.")
            .process_event_entry(entry, scheduler, state);
    }
}

Scheduler

The scheduler adds, retrieves, and executes events. It also keeps track of the simulation clock. Let's start with the latter.

type Clock = Rc<Cell<Duration>>;

pub struct ClockRef {
    clock: Clock,
}

impl ClockRef {
    #[must_use]
    pub fn time(&self) -> Duration {
        self.clock.get()
    }
}

I define a clock as a reference counting pointer. It is owned by the scheduler itself, which has mutable access to it for when it must modify the current time. For any other parts of the simulation, ClockRef only exposes immutable access to the current time. Now, we are ready to define the scheduler.

pub struct Scheduler {
    events: std::containers::BinaryHeap<EventEntry>,
    clock: Clock,
}

impl Scheduler {
    pub fn schedule<E: 'static>(
        &mut self,
        time: Duration,
        component: ComponentId<E>,
        event: E,
    ) {
        let time = self.time() + time;
        self.events.push(EventEntry::new(time, component, event));
    }

    #[must_use]
    pub fn time(&self) -> Duration {
        self.clock.get()
    }

    #[must_use]
    pub fn clock(&self) -> ClockRef {
        ClockRef {
            clock: Rc::clone(&self.clock),
        }
    }

    pub fn pop(&mut self) -> Option<EventEntry> {
        if let Some(event) = self.events.pop() {
            self.clock.replace(event.time.0);
            Some(event)
        } else {
            None
        }
    }
}

Simulation

We now have all the necessary parts and we can put them together.

pub struct Simulation {
    pub state: State,
    pub scheduler: Scheduler,
    pub components: Components,
}

impl Simulation {
    pub fn step(&mut self) -> bool {
        if let Some(event) = self.scheduler.pop() {
            self.components
                .process_event_entry(event, &mut self.scheduler, &mut self.state);
            true
        } else {
            false
        }
    }
}

This is a minimal example. The library implements more user-facing functions directly in the simulation to bypass explicitly accessing state, scheduler, and components, but that's not very interesting. The point is we have everything we need to start building simulations.

Example

Let's briefly go through some component example. Let's say we have one producer, which produces some values, and a consumer, which uses them. The producer will only react to one type of event, at which it will send a value to the producer and schedule itself at some random time interval. The consumer, however, takes some time processing the value. Thus, there will be two events: Received, which indicates that a value was sent by the producer, and Finished, which indicates that the processing has finished.

struct Product;

struct Producer {
    outgoing: QueueId<Product>,
}

struct Consumer {
    incoming: QueueId<Product>,
    working_on: Key<Option<Product>>,
}

struct ProducerEvent;

enum ConsumerEvent {
    Received,
    Finished,
}

impl Producer {
    fn produce() -> Product { ... }
    fn interval() -> std::time::Duration { ... }
}

impl Consumer {
    fn produce() -> Product { ... }
    fn interval() -> std::time::Duration { ... }
}

impl Component for Producer {
    type Event = ProducerEvent;

    fn process_event(
        &self,
        self_id: ComponentId<Self::Event>,
        _event: &Self::Event,
        scheduler: &mut Scheduler,
        state: &mut State,
    ) {
        state.send(self.outgoing, self.produce());
        scheduler.schedule(self.interval(), self_id, Self::Event);
    }
}

impl Component for Consumer {
    type Event = ConsumerEvent;

    fn process_event(
        &self,
        self_id: ComponentId<Self::Event>,
        event: &Self::Event,
        scheduler: &mut Scheduler,
        state: &mut State,
    ) {
        let busy = state.get(self.working_on).is_none();
        match event {
            ConsumerEvent::Received => {
                if busy {
                    if let Some(product) = state.recv(self.incoming) {
                        state
                            .get_mut(self.working_on)
                            .map(|w| *w = Some(product));
                        scheduler.schedule(
                            self.interval(),
                            self_id,
                            ConsumerEvent::Finished
                        );
                    }
                }
            }
            ConsumerEvent::Finished => {
                let product = state
                    .get_mut(self.working_on)
                    .unwrap()
                    .take()
                    .unwrap();
                self.log(product);
                if state.len(self.incoming) > 0 {
                        scheduler.schedule(
                            Duration::default(),
                            self_id,
                            ConsumerEvent::Received
                        );
                }
            }
        }
    }
}

Closing Remarks

In this article, I discussed my implementation of a discrete event simulation. Although the concepts are quite simple and I'm sure I haven't addressed all the issues that will come up in the future, I think there are some solid ideas here. If nothing else, it is a nice showcase of the power and expressiveness of Rust.

There are some trade-offs I made when it comes to performance. Type erasure has its cost, but it provides great flexibility. I have previously experimented with some macros, but they have their own trade-offs, and the relative simplicity of the current solution prevailed. Furthermore, you might have noticed that despite insisting that the implementation is type safe, I still needed to unwrap options with expect, which has some time overhead. I could have used unsafe in several places, but that would make debugging potential bugs much more difficult. I haven't run any benchmarks so far, which I might do at some point if my experiments end up being slow.

If you have any comments, make sure to reach out.

Self-hosted Git Repositories with Gitea

Michał Siedlaczek — Sun, 28 Jun 2020 12:44:56 +0000

GitHub is arguably the most popular git hosting service out there, and it's easy to see why: it's free (for open source projects), it's powerful, and because it's already familiar, it's easy to get a new project up and running without much hustle. Moreover, ever since GitHub's acquisition by Microsoft, I have noticed a growing effort to deliver a full-featured CI/CD solution. Microsoft's investment also seems to ensure the platform's longevity and stability. But this change in ownership has a flip side, too. We all remember Microsoft's hostile attitude towards both Linux and open source, and, despite their recent claims of the newfound love and appreciation for both, there is a fair share of skepticism in the community, and therefore much reluctance to put their code on GitHub.

Of course, there are alternatives. Probably the biggest contender to GitHub is GitLab, which is used by quite a number of open source projects, such as GNOME, Inkscape, and mutt to name a few. It is offered both as a paid service (although limited free tier is available for open source projects) and a self-hosted application. Interestingly, the latter comes in two flavors: free Community Edition (missing certain features), distributed under the MIT license, and Enterprise Edition, distributed under a proprietary license (even though the code is openly available). But if you read the title of this post carefully, then you know this is not about GitLab. Instead, I will talk about another git hosting platform. Gitea, as stated on their official website, is a community managed lightweight code hosting solution, and is published under the MIT license. I decided to try it out and write down my experience with setting it up for personal my use.

Keywords: git gitea digitalocean https

Objectives

Before I set out to work, I set myself a few goals. For this exercise, I wanted a self-hosted instance of Gitea (obviously), in which I could deploy my dotfiles repository. I wanted to have a domain pointed to the Gitea instance, and finally, I also wanted to connect to it via HTTPS. I divided the work into a few steps I will describe one by one in this article:

Obtaining server instance.
Installing and running Gitea.
Routing a domain to the server.
Setting up Let's Encrypt certificate.
Creating a new repository.

Gitea Droplet

Right from the start, I cheated a bit. Having already a DigitalOcean account, I decided to spin up the smallest available droplet, which at the moment of writing cost me $5 a month, and is more than enough for this exercise. Of course, depending on your needs, you may require a larger instance or may choose to deploy Gitea on another cloud service, or your own hardware. I took the easy route and created a dedicated 1-Click App from DigitalOcean Marketplace, which easily covered both points 1 and 2 without breaking a sweat!

Installing a 1-Click App is a very easy and intuitive process, but for completeness' sake, here's a quick guide. Once logged in to your dashboard, you have to choose Droplets from the Create menu in the top right corner. In the Choose an image section, select Marketplace, and search for Gitea. At the moment of this writing, the only option available is Gitea 1.11.6 on Ubuntu 20.04. Next, you have to select your plan—I picked Standard plan with 1 GB of RAM, 1 CPU, 25 GB SSD disk, and monthly transfer of 1,000 GB for $5/mo. You have an option of adding block storage, which I skipped. Then, you have several more options, such as selecting the data center, authenticating method (SSH or password), and enabling system-level backup for additional cost. When done, just hit Create Droplet, and wait for it to start. Once it's running, you should be able to click on the item in your dashboard to get a similar view to the one below:

Write down your IP, you'll need it to connect to the server and to configure your domain. Notice a Get Started link at the top. When clicked, it shows some additional instructions from the maintainer of the Gitea 1-Click App. In particular, it instructs us what to do to finish our configuration:

Once Droplet has been created, please modify values in /var/lib/gitea/conf/app.ini to insert your DOMAIN. The password for the gitea_admin user is located in /root/.digitalocean_password please use this to connect to your Gitea install at http://\${IP}/ and login to create your new user.

Following these instructions, you have to connect to your server first:

ssh root@YOUR_IP

Retrieve your password from /root/.digitalocean_password, and go to http://YOUR_IP in your browser. Your Gitea website should now load and you should be able to log in with gitea_admin user. The first thing you want to do is to create a new account with your own password, and remove the gitea_admin user, or at least change its password. You can do that by clicking the little avatar icon in the top right corner, and selecting Site Administration. Then, go to User Accounts tab, and click Create User Account.

Congratulations, your Gitea is up and running!

Routing a Domain

Right now, both the website and the repositories are only accessible by the IP. I am assuming here that you already have a domain registered. To point it, or any of its subdomains, to the Gitea website, you'll need to access your domain registrar's DNS settings and add a resource record. For example:

In the above configuration, @ indicates the root domain, e.g., msiedlaczek.com, while git indicates a subdomain. In either case, the Data field should contain your droplet's IP.

Note that populating the changes may take some time. For instance, Google Domains informs that it could take up to 48 h, although in my case, it took less than 24 h. Still, you won't be able to use your domain immediately.

Configuring HTTPS

Let's Encrypt is a nonprofit Certificate Authority. It makes it very easy to acquire new certificates, as well as automatically renew them. Instead of configuring Gitea to use TSL certificate directly, I chose to use a reverse proxy with nginx instead. Essentially, it means that I want to use nginx to set up HTTPS connection, which in turn will redirect the traffic to the Gitea server.

First, I changed my Gitea configuration in /var/lib/gitea/conf/app.ini to listen on localhost:3000:

[server]
PROTOCOL = http
ROOT_URL = https://git.msiedlaczek.com
DOMAIN = localhost
HTTP_PORT = 3000

Note the ROOT_URL setting, which will make all the repository links generate correctly with the domain name instead of localhost. Before we move on, we need to restart the Gitea service:

systemctl restart gitea

Now we need to install and configure nginx. We also need to adjust the firewall to allow the HTTPS request to nginx.

apt-get install nginx
sudo ufw allow 'Nginx HTTPS'

However, we'll start the configuration with HTTP only. The configuration file /etc/nginx/nginx.conf has a http block. Within that block, we need to put the following:

server {
    server_name git.msiedlaczek.com;
    location / {
        proxy_pass http://localhost:3000;
    }
}

Let's save the changes and restart nginx:

systemctl restart nginx

It might seem we only complicated the situation, because we added more configuration yet ended up exactly where we started. But these changes will make our job easier in a moment.

To set up Let's Encrypt, I recommend following this dedicated tutorial, which exactly explains each step. If you're using different operating system than Ubuntu 20.04, or want to use Apache instead of nginx, you can choose one of dozens of versions of this tutorial for different software/OS combinations. Here, I will only briefly explain what we are doing.

To automate certificate acquisition, we will use cerbot, which not only will create the certificate, but also configure nginx with a little help of the certbot-nginx plugin. It boils down to two steps. First, install certbot and the plugin:

apt-get update
apt-get install software-properties-common
add-apt-repository universe
apt-get update
apt-get install certbot python3-certbot-nginx

Then, run the following command:

sudo certbot --nginx

That's it! certbot should get and install the certificates, and modify the nginx configuration to use them. You can check out the changes made by certbot in /etc/nginx/nginx.conf. Now, go to your browser and verify that you now connect via HTTPS.

Creating a Repository

I almost didn't include this section, but in the end, I wanted to make a point, which is this: if you ever used either GitHub or GitLab, you'll feel right at home using Gitea. To create a new repository, you simply click on a familiar-looking plus sign in the top right corner, and select Repository. Then, you choose name and description, and optionally generate .gitignore, license, and README. Finally, just hit Create Repository, and you're good to go! In your repository's Code tab, you have an option to copy the link to the repository: both SSH and HTTPS links should contain you domain name.

Conclusion

By no means is this post supposed to convince anyone to replace GitHub or GitLab with self-hosted Gitea instance. Rather, it shows how easy it is to get it up and running in a few hours at a very low cost (although this will depend on one's needs). I personally find it quite reassuring that there is a fully open source, community-driven solution out there, and for that reason I am inclined to give it a fair shake.

Protobuf code generation in Rust

Michał Siedlaczek — Sat, 27 Jun 2020 15:06:37 +0000

Today, I learned how to correctly use Cargo build scripts. Or, more precisely, I learned how to do one particular thing correctly, but it was significant enough for me that I decided write it down. Of course, had I read the Cargo Book more carefully before, I would have saved myself some time, and there would be no dramatic revelation, and no reason to write this post either. I guess what I am trying to say is: thank goodness my reading sucks.

Keywords: cargo build scripts code generation

Context

My problem arose while implementing a little library that reads from and writes to a Protocol Buffer stream. As described by the authors themselves:

Protocol buffers are a language-neutral, platform-neutral extensible mechanism for serializing structured data.

The very first step is to define a message format in Protobuf's dedicated grammar. The message is parsed by the Protobuf library (available for various programming languages), and related code is generated for the target language (in our case, Rust). Each message is an object with a bunch of getters and setters (details differ depending on the language). These messages then can be read from or written to streams available in the Protobuf library. It is all quite straightforward. Take this simple message from the Protobuf web page:

message Person {
  required string name = 1;
  required int32 id = 2;
  optional string email = 3;
}

In Rust, we would use the following chunk of code to construct a Person:

let mut person = Person::new();
person.set_name("Butler");

The details are not very important here. What is important is that this code needs to be generated before the project is compiled, or else there would be no Person to speak of. And, if possible, we would prefer if it was neatly integrated into our build system.

Cargo build scripts

Our situation is by no means unique. Probably the most canonical example is a library that provides Rust API bindings to some C library, such as libc, git2, and many others. Before compiling our Rust crate, we first need to compile the C code, and maybe even generate Rust FFI bindings from C headers (see bindgen crate). Because this is a common pattern and Rust ecosystem is fantastic, there is a standard solution for this: build scripts.

Simply put, Cargo allows us to define a build script, by default named build.rs and located at the root of the project. This is essentially a regular executable (with main function and all), except Cargo provides a bunch of environment variables with useful build information. The build script in turn communicates back to Cargo by writing instructions to the standard output. For example, printing cargo:warning=MESSAGE will instruct Cargo to print a warning to the terminal. More on that a little later, but for now here is a simple example that compiles a C source file using cc crate:

fn main() {
    cc::Build::new()
        .file("src/example.c")
        .compile("example");
}

Note that there is a special section in Cargo.toml where you can define dependencies that are only used for building: [dev-dependencies].

Generating Protobuf code

Now that we have basic information about build scripts, we can take a shot at generating the Rust code for Protobuf messages. Luckily, there is already a crate that will make it very simple:

[dev-dependencies]
protobuf-codegen-pure = "2.14" # Might be different by the time you read this

[dependencies]
protobuf = "2.14" # This will be needed to use the generated code as protobuf messages

A quick look at the documentation explains it all:

fn main() {
    protobuf_codegen_pure::Codegen::new()
        .out_dir("src/protos")
        .inputs(&["protos/person.proto"]),
        .include("protos")
        .run()
        .expect("Codegen failed.");
}

Let's break it down. We first create a Codegen object, which implements a builder pattern. Then, we define where the generated files should be created. Finally, we need to point to the input files that contain the message definitions, and to the directory containing these files. That's it. Simple, right?

Well, not so fast. There is a catch. See, Cargo doesn't want us to write to the src directory:

Build scripts may save any output files in the directory specified in the OUT_DIR environment variable. Scripts should not modify any files outside of that directory.

But why would they care? Well, it is a security concern. If a crate is built remotely, we don't want to allow what is effectively a user-defined program to write anywhere they want. A good example is Docs.rs, which hosts API documentation of all crates available on crates.io. They limit the program's write permissions to only one directory and pass it via an environment variable OUT_DIR. In fact, if you follow the instructions from protobuf-codegen-pure crate, your documentation on Docs.rs will fail to build (this is precisely how I found out about all of this!).

Correcting the build script

So how do we fix our build script? Let's try this:

fn main() {
    let out_dir_env = env::var_os("OUT_DIR").unwrap();
    let out_dir = Path::new(&out_dir_env);
    protobuf_codegen_pure::Codegen::new()
        .out_dir(out_dir)
        .inputs(&["protos/person.proto"]),
        .include("protos")
        .run()
        .expect("Codegen failed.");
}

But where is our file now and how do we use it? Rust provides include! macro that copies the content of a file to the file it is invoked from. For example, here is a little snippet from lib.rs showcasing this:

include!(concat!(env!("OUT_DIR"), "/person.rs"));

fn new_person(name: &str) -> Person {
    let mut person = Person::new();
    person.set_name(name);
    person
}

Does it work now? Unfortunately, not quite. protobuf-codegen-pure takes liberty to add some module-level comments and attributes suppressing certain warnings, which now fail to compile:

error: an inner attribute is not permitted in this context
 --> /home/elshize/dev/ciff/target/debug/build/ciff-e8fd3067377fd4eb/out/common_index_format_v1.rs:5:1
  |
5 | #![allow(unknown_lints)]
  | ^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: inner attributes, like `#![no_std]`, annotate the item enclosing them, and are usually found at the beginning of source files. Outer attributes, like `#[test]`, annotate the item following them.

This is caused by the indirection of include!. The good news is that it is a known problem and chances are this is already resolved when you are reading it. But since I don't have the luxury of travelling through time, I would like to find a workaround. Besides, it is a good opportunity to show how powerful build scripts really are. We are by no means limited to what the codegen library generates for us.

The objective is to get rid of those failing comments and attributes. On the other hand, I would still like to be able to suppress warnings from the generated code. To do that, we can create person.rs module, which will simply define attributes and include the generated code, which can be later re-exported by lib.rs. For example:

#![allow(unknown_lints)]
#![allow(clippy::all)]
#![allow(clippy::pedantic)]
#![allow(box_pointers)]
#![allow(dead_code)]
#![allow(missing_docs)]
#![allow(non_camel_case_types)]
#![allow(non_snake_case)]
#![allow(non_upper_case_globals)]
#![allow(trivial_casts)]
#![allow(unsafe_code)]
#![allow(unused_imports)]
#![allow(unused_results)]
include!(concat!(env!("OUT_DIR"), "/person.rs"));

Great, now the only thing that is left is to remove these from the generated file. This can be easily done in build.rs. Once the file is successfully generated, we can read it line by line and filter out any line that starts with #! or //!.

fn main() {
    let out_dir_env = env::var_os("OUT_DIR").unwrap();
    let out_dir = Path::new(&out_dir_env);
    protobuf_codegen_pure::Codegen::new()
        .out_dir(out_dir)
        .inputs(&["protos/person.proto"]),
        .include("protos")
        .run()
        .expect("Codegen failed.");
    // Resolve the path to the generated file.
    let path = out_dir.join("person.rs");
    // Read the generated code to a string.
    let code = read_to_string(&path).expect("Failed to read generated file");
    // Write filtered lines to the same file.
    let mut writer = BufWriter::new(File::create(path).unwrap());
    for line in code.lines() {
        if !line.starts_with("//!") && !line.starts_with("#!") {
            writer.write_all(line.as_bytes()).unwrap();
            writer.write_all(&[b'\n']).unwrap();
        }
    }
}

Result? See for yourself.

Conclusions

I have a few takeaways from my little experiment. First, the Rust ecosystem, although rich and powerful, it not yet fully matured. Certain details are still being ironed out, such as those in protobuf-codegen-pure. But this is to be expected. I think what is more important is that these libraries are out there, and how many people are actively working on making them better each day. But most of all, I am often blown away by how well thought out many functionalities of Rust or Cargo are, especially compared to those available, say, in C++. Build scripts are one of those gems that elevate Rust to the great piece of technology it is.

Questions? Comments? I am @elshize on Twitter and @siedlaczek at Mastodon.Social. Feel free to say hi.