DEV Community: Crystal Durham

dyn* doesn't need to be special

Crystal Durham — Thu, 07 Apr 2022 16:05:39 +0000

or: more storage API propaganda

A response to @nikomatsakis's dyn*: can we make dyn sized?

dyn* Trait is a way to own a value of dyn Trait without knowing how the pointee is stored. In short, dyn* Trait acts as "&move dyn Trait", owning the pointee and dropping it, while also containing a clever feature I'm calling "owning vtables" allowing it to also transparently own the memory the pointee is stored in.

When you have a normal Box<dyn Trait>, the pointer itself looks something like

struct Box<dyn Trait> {
    data: ptr::NonNull<{unknown}>,
    vtable: &'static TraitVtable<{unknown}>,
}

and the vtable something like

struct TraitVtable<T: Trait> {
    layout: Layout = Layout::new::<T>();
    drop_in_place: unsafe fn(*mut T)
        = ptr::drop_in_place::<T>;
    // ... the contents of Trait
}

so that dyn Trait can recover the type information needed to interact with the pointee. The trick of dyn* is in using an owning vtable, best explained with a simple example:

Box<T as dyn Trait>'s vtable's drop_in_place is ptr::drop_in_place::<T>
Box<T as dyn Trait> as dyn* Trait's vtable's drop_in_place is Box::drop

In this manner, any smart pointer with an into_raw(self) -> *mut T can be owned transparently as dyn* Trait by generating a new vtable which replaces drop_in_place with a shim that from_raws the smart pointer and then drops it¹.

With more complicated vtable shims, you can even shove any pointer-sized value into a dyn*, by dealing it a data "pointer" of ptr::invalid(value) and the vtable shimming back to the original trait implementation on value directly.

And now, we need to talk about the storages API proposal for a bit.

But what does this have to with dyn*?

We'll get there! ... Hey, does Amos know you're here?

Actually, yes.

... Anyway, on the current nightly, Box and other allocating types are generic over trait Allocator. Allocator is a fairly standard abstraction over heap allocation, providing methods fn allocate(&self, Layout) -> Result<ptr::NonNull<[u8]>, AllocError> and fn deallocate(&self, ptr::NonNull<u8>, Layout).

The storages API adds another layer on top of this, dealing in a generic Self::Handle<T> type instead of ptr::NonNull<T> directly. In short²:

trait Storage {
    type Handle<T: ?Sized>: Copy;
    type Error;
    fn create(&mut self, meta: <T as Pointee>::Metadata) -> Result<Self::Handle<T>, Self::Error>;
    fn destroy(&mut self, Self::Handle<T>);
    // 👇
    fn resolve(&self, Self::Handle<T>) -> ptr::NonNull<T>;
}

To illustrate the benefit, consider a potential implementation:

struct InlineStorage<const LAYOUT: Layout> {
    data: UnsafeCell<MaybeUninit<[u8; LAYOUT.size()]>>,
    align: PhantomAlignTo<LAYOUT.align()>,
}

impl<const LAYOUT: Layout> Storage for InlineStorage<LAYOUT> {
    type Handle<T: ?Sized> = <T as Pointee>::Metadata;
    type Error = !;
    fn create(&mut self, meta: Self::Handle<T>) -> Result<Self::Handle<T>, !> { meta }
    fn destroy(&mut self, _: Self::Handle<T>) {}
    // 👇
    fn resolve(&self, meta: Self::Handle<T>) -> ptr::NonNull<T> {
        ptr::NonNull::from_raw_parts((self as *const _).cast(), meta)
    }
}

Now, you can have Box<T, InlineStorage<Layout::new::<T>()>> be layout-equivalent to storing T directly on the stack.

Amazing.

More importantly, though, is that you can have Box<dyn Trait, InlineStorage<Layout::new::<T>()>> also be layout-equivalent to storing T directly on the stack (plus a vtable pointer), but type-erased so you don't actually know about T anymore.

Oh, I think I see where you're going with this!

So, if we add a fallback to heap allocation ...

struct SmallStorage<const LAYOUT: Layout, A: Allocator = Global> {
    inline: InlineStorage<LAYOUT>,
    outline: AllocStorage<A>,
}

impl<const LAYOUT: Layout, A: Allocator> for SmallStorage<LAYOUT, A> {
    type Handle<T: ?Sized> = ptr::NonNull<T>;
    type Error = AllocError;

    fn create(&mut self, meta: <T as Pointee>::Metadata) -> Result<Self::Handle<T>, AllocError> {
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.create(meta)
        } else {
            let meta = self.outline.create(meta)?;
            Ok(NonNull::from_raw_parts(layout.dangling(), meta))
        }
    }

    fn destroy(&mut self, handle: Self::Handle<T>) {
        let meta = handle.metadata();
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.destroy(meta)
        } else {
            self.outline.destroy(handle)
        }
    }

    fn resolve(&self, handle: Self::Handle<T>) -> ptr::NonNull<T> {
        let meta = handle.metadata();
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.resolve(meta)
        } else {
            self.outline.resolve(handle)
        }
    }
}

... and maybe a type alias for convenience ...

type Dyn<T: ?Sized> = Box<T, SmallStorage<Layout::new::<usize>()>>;

We have the functionality of dyn* as a library type! Instead of dyn* Trait, we have Dyn<dyn Trait> (the stutter is unfortunate³). This is our type that is

The size of Box<dyn Trait>,
Stores small values of dyn Trait inline, and
Owns the storage of dyn Trait, dellocating it on drop.

But wait, you're still missing something.

What, Cool Bear?

dyn* can hold any smart pointer, not just Box. You said so yourself!

Well, but there's a catch: dyn* needs to be DerefMut if it wants to fulfil its life goal of facilitating Pin<dyn* Future> usage. This means that it's restricted to single-ownership smart pointers wait hey that sounds like Box.

It's my belief that there aren't really any Pin<P<dyn Future>> types out there for a P that's not &mut or Box. I don't have any proof, just a feeling.

But the storages Dyn can be extended to support other DerefMut smart pointers, though it might require a second vtable pointer without the language support for easily wrapping the vtable into an owning vtable⁴.

So, storages get us the benefit of dyn* without any of the main problems with dyn*. I think that more than justifies bringing the storages API to std so we can properly spin the wheels on this design and find where it falls short. There's definitely flaws in the storages proposal I haven't spotted yet⁵, but we need to use it to find the rest of them.

Oh, and &move also falls out of storages as Box<T, &mut MaybeUninit<T>>, so that's even more proposed language features handled by the library feature. The storage API is good.

You can do clever things to avoid the from_raw shim, like with Box, where you can just call Box::drop directly, by patching up the other vtable members to take into account the container the smart pointer puts it in. However, since you use the dyn* many times and only drop it once, it seems better to just shim drop_in_place. ↩
For brevity, I omit a lot of details included in the full proposal. Notably, I omit a lot of safety concerns that are put on the user, and the full proposal has static controls for whether a storage can only create a single handle at a time or manages multiple handles, whether a handle is to a single element or to a slice of elements, as well as whether you need exclusive access to the storage to get mutable access to the pointee. ↩
In the olden days (before Rust 2018), we didn't have dyn Trait, it was just &Trait. dyn Trait is better, because you can immediately know that you're dealing with a dyn type rather than a fixed type. However, in this one specific case, omitting the dyn would allow us to write Dyn<Trait> instead, so it's impossible to say if it's good or not,, ↩
Then remaining concern is actually unowning references like &mut dyn Trait. The important thing to note here is that Box<Type, Storage> gives us two axis of customization: I've talked here about Storage for customization of the owning memory, but Type still gives us customization over how its used. For fn(&mut dyn Trait) -> Dyn<dyn Trait>, you can wrap the vtable to remove any drop glue with e.g. ManuallyDrop<dyn Trait>. This is where language support would be useful. ↩
In fact, I spotted one while drafting this post; as currently prototyped, storages are unsound, because the only handle resolution option is by-shared-ref and inline storages aren't using UnsafeCell, thus ultimately violating the aliasing guarantees 💣💥😱 ↩

Dynamically Aligned Types?

Crystal Durham — Mon, 11 Jan 2021 03:54:35 +0000

At this point, you're probably aware of what a dynamically sized type, or DST, is. They're types like [Type] (slices) or dyn Trait (trait object) which don't have a singular known size at compile time. As a result, you can't have a binding with a DST type (e.g. let x: [u8]); every DST has to be behind an indirection (e.g. let x: &[u8]).

Currently in stable Rust, the only dynamically sized types are slices, trait objects, and structs that contain one of those two DSTs. For these, references are "fat": whereas &u8 is physically just a *const u8 pointer to a memory location, &[u8] is a (*const u8, usize) pair, where the second number is the length of the slice. &dyn Trait is roughly (*const ?, &'static VTable), where the pointer is to the object, and the vtable reference holds all of the information about the trait impl. The size is then calculated (in the case of slices) or retrieved (in the case of vtables) when asked for (e.g. by mem::size_of_val).

But what about alignment (and mem::align_of_val)? For slices, it's still statically known; [T] has the same alignment as T. But for trait objects, alignment can vary:

let a: &dyn Sync = &0u16 as &u16;
let b: &dyn Sync = &0u64 as &u64;
dbg!(mem::align_of_val(a));
dbg!(mem::align_of_val(b));

[src/main.rs:6] mem::align_of_val(a) = 2
[src/main.rs:7] mem::align_of_val(b) = 8

Entering the picture, though, are custom DSTs. There's no specific design that the lang team have endorsed, but there are various RFCs already available, and we can think about what we would like from such a feature and what restrictions the language already places on it.

I am not necessarily endorsing the linked RFC specifically, just using it as an example.

The headlining feature for custom DST proposals is the ability to have "thin" DSTs: ones where the pointer is just a pointer, without any extra metadata. (Equivalently, with zero-sized metadata, probably ().) Optimally (using the above-linked RFC's terms) we could have something like

#[repr(C)]
pub struct Thin<T: ?Sized> {
    meta: <T as Pointee>::Metadata,
    data: T,
}

so you could have e.g. &Thin<_> to create a thin-reference supporting value for any type, by just storing the pointer metadata alongside it.

While that specific definition won't ever work (as &Thin<_> inherit pointee metadata from its tail), if alignment is statically known, this is a fairly simple task to accomplish:

// Example only; uses imaginary made up APIs
impl<T: ?Sized> Deref for Thin<T> {
    type Target = T;
    fn deref(&self) -> &T {
        // Thin is repr(C), so meta is
        //   the first field without extra padding
        let meta: <T as Pointee>::Metadata =
            ptr::read(self as *const Self as *const _);
        // Calculate the offset to T
        let meta_layout = Layout::new::<T::Metadata>::new();
        let offset = meta_layout.size()
            + meta_layout.padding_needed_for(mem::align_of::<T>());
        // Assemble pointer to T
        ptr::from_raw_parts((self as *const u8).offset(offset), meta)
    }
}

but as we showed above, for dyn Trait, the alignment isn't statically known! For dyn Trait, you need to have the metadata to look up the alignment. Should be simple enough:

        // Calculate the offset to T
        let meta_layout = Layout::new::<T::Metadata>::new();
        let data_align = Pointee::align_with_meta(meta);
        let offset = meta_layout.size()
            + meta_layout.padding_needed_for(data_align);

However, this runs into a problem: how do I get the alignment of a Thin<_>? If it's Pointee::align_with_meta(Metadata), you can't: Thin doesn't have any pointer metadata, and the information you need to find the alignment is behind the pointer. So, change this to be Pointee::align_of_val(&self), then? But that runs into a chicken-and-egg problem: when composing the value in a containing type, you need to know the alignment to know the offset of the value in order to get a pointer to it!

So, one of two things has to be true:

For any type, it's possible to get its alignment with just the pointer metadata, independent of whether you have a valid pointer to an instance of the type, or
The above is true for T: ?Sized, and a new ? bound is added for unsized types that actually can't be held by value / composed around, only behind an indirection.

The second option, tbh, sounds horrible. This "?SimpleAlignment" is less motivated than ?DynSized (for actually unknowable size, e.g. extern type), and even ?DynSized is fighting tooth and nail (and losing) to avoid being added to the do-not-call list. It would be really nice to have an inline Thin<dyn Trait> so that composition can just work — &[mut] Thin<dyn Trait>, Box<Thin<dyn Trait>>, Rc<Thin<dyn Trait>> — but it's not worth the extra pain.

But it doesn't mean that all is lost, either! By taking a page from Pin's playbook, we turn it around, and wrap the pointer rather than the pointee: Thin<&[mut] dyn Trait>, Thin<Rc<dyn Trait>>, etc. This doesn't quite just work, since we do need to add extra data to the heap part, so it'd be Thin<&Thinnable<dyn Trait>>, which is a bit repetitive, but it shows that it's still possible if really desired.

By the way, I have a crate that does exactly this.

TL;DR takeaways:

I'm a shill, use my crates; numbers go up make me feel good.
Requiring a pointer to get a pointee's alignment is a chicken-and-egg problem; you need the alignment to calculate the offset to produce the pointer. Any custom DST proposal should be Metadata -> Alignment.
It's still possible to use thin pointers to types with dynamic alignment. You just have to un-thin them before actually doing interesting things with them.
align_of_val_raw can be safe, or at least inherits the safety from Pointee::align_with_meta, as it's just a different accessor for the same data.

String interners in Rust

Crystal Durham — Fri, 10 Jul 2020 04:43:31 +0000

This is basically a direct followup to Amos/fasterthanlime's blog post Small strings in Rust. If you haven't read that, I'd highly suggest reading it first: it covers the techniques that I've ~~stolen~~ used here, which I won't go over in much detail.

Amos covers two Rust crates that offer the "small string" optimization: small strings (of less than around 22 bytes) can be stored inline rather than on the heap, like the standard String type. If you have a large number of small strings, this can greatly reduce allocation pressure.

Rather than small string optimization, though, for certain use cases an interner is useful. An interner associates a "symbol" with each unique string that you want to manage. You can then very cheaply copy the symbol around and compare symbols, as they're just a single integer (typically 32 bits). If you need the actual contents of the string again (such as for display), you just ask the interner to translate back from your symbol to a string.

I took a look at a few of the top interning crates for Rust (there are quite a few!) as ranked by lib.rs and compared them to see what their allocation behavior was. The testing harness is basically a direct copy of the one Amos used for small strings.

Specifically, I've tested

string-interner version 0.7.1*
lasso version 0.2.2*
lalrpop-intern version 0.15.1
intaglio version 1.1.0
strena commit 1ddbf48b9f639ffbb4c89b0d51cb005fc0e3a4f7

* These crates have later versions published after this article -- see the postscript for updates.

I couldn't get the ASCII plot to reproduce properly here, so instead you get some xkcd-style plots. All measurements were done on a Windows machine.

Measurement code is available on GitHub.

`std::string::String`

As a baseline, here's the process with just the standard String type. We just create a list of owned strings for each of the strings on a word list of 7776 words.

    fn std_collect_words(&self) {
        crate::ALLOCATOR.set_active(true);
        let mut words: Vec<String> = Vec::with_capacity(WORDS.len());
        crate::ALLOCATOR.mark_point();
        for &word in WORDS {
            words.push(word.into());
            crate::ALLOCATOR.mark_point();
        }
        crate::ALLOCATOR.set_active(false);
    }

 total events | 7777
  peak bytes  | 241.0 KB
 ----------------------------
 alloc events | 7777
 alloc bytes  | 241.0 KB
 ----------------------------
 freed events | 0
 freed bytes  | 0 B

I see a ~190 KB allocation for the words vector, and then a small allocation for each string after.

`string-interner`

A data structure to cache strings efficiently, with minimal memory footprint and the ability to assicate the interned strings with unique symbols. These symbols allow for constant time comparisons and look-ups to the underlying interned string contents. Also, iterating through the interned strings is cache efficient.

Note the changing y axis.

    fn interner_collect_words(&self) {
        crate::ALLOCATOR.set_active(true);
        let mut words = string_interner::DefaultStringInterner::with_capacity(WORDS.len());
        crate::ALLOCATOR.mark_point();
        for &word in WORDS {
            words.get_or_intern(word);
            crate::ALLOCATOR.mark_point();
        }
        crate::ALLOCATOR.set_active(false);
    }

 total events | 7778
  peak bytes  | 588.4 KB
 ----------------------------
 alloc events | 7778
 alloc bytes  | 588.4 KB
 ----------------------------
 freed events | 0
 freed bytes  | 0 B

I see a ~540 KB allocation in two chunks for the interner, and then a small allocation for each string after.

`lasso`

A multithreaded and single threaded string interner that allows strings to be cached with a minimal memory footprint, associating them with a unique key that can be used to retrieve them at any time. A Rodeo allows O(1) internment and resolution and can be turned into a RodeoReader to allow for contention-free resolutions with both key to str and str to key operations. It can also be turned into a RodeoResolver with only key to str operations for the lowest possible memory usage.

Lasso is the only library in this set that has special support for interning from multiple threads. All other libraries always require exclusive access to intern new symbols. We measure the single-thread interner here to be more fair.

    fn lasso_collect_words(&self) {
        crate::ALLOCATOR.set_active(true);
        let mut words: lasso::Rodeo = lasso::Rodeo::with_capacity(WORDS.len());
        crate::ALLOCATOR.mark_point();
        for &word in WORDS {
            words.get_or_intern(word);
            crate::ALLOCATOR.mark_point();
        }
        crate::ALLOCATOR.set_active(false);
    }

 total events | 23
  peak bytes  | 591.8 KB
 ----------------------------
 alloc events | 20
 alloc bytes  | 592.1 KB
 ----------------------------
 freed events | 3
 freed bytes  | 312 B

I see a ~540 KB allocation in three chunks for the interner, and then a chunked allocation of ~4 KiB around every 550 symbols.

`lalrpop-intern`

Simple string interner used by LALRPOP

This test is designed to be a best-case scenario: we know the number of symbols ahead of time and tell the interner about it so it can hopefully pre-allocate. Lalrpop's interner is purely global, though, so we can't do that. This results in a very unfair comparison, so I'm going to defer showing LALRPOP's results until the section without pre-allocation.

`intaglio`

UTF-8 string and bytestring interner and symbol table. Used to implement storage for the Ruby Symbol table and the constant name table in Artichoke Ruby.

    fn intaglio_collect_words(&self) {
        crate::ALLOCATOR.set_active(true);
        let mut words = intaglio::SymbolTable::with_capacity(WORDS.len());
        crate::ALLOCATOR.mark_point();
        for &word in WORDS {
            words.intern(word).unwrap();
            crate::ALLOCATOR.mark_point();
        }
        crate::ALLOCATOR.set_active(false);
    }

 total events | 2
  peak bytes  | 606.2 KB
 ----------------------------
 alloc events | 2
 alloc bytes  | 606.2 KB
 ----------------------------
 freed events | 0
 freed bytes  | 0 B

... wait, what‽ Oh, right, intaglio has special handling when interning &'static str which doesn't bother to copy the strings and just refers to the static string you gave it. Smart, but for a fair comparison we need to stop it from doing that...

    fn intaglio_dyn_collect_words<'a>(&'a self) {
        crate::ALLOCATOR.set_active(true);
        let mut words = intaglio::SymbolTable::with_capacity(WORDS.len());
        crate::ALLOCATOR.mark_point();
        for &word in WORDS {
            words.intern(String::from(word)).unwrap();
            crate::ALLOCATOR.mark_point();
        }
        crate::ALLOCATOR.set_active(false);
    }

 total events | 7778
  peak bytes  | 660.6 KB
 ----------------------------
 alloc events | 7778
 alloc bytes  | 660.6 KB
 ----------------------------
 freed events | 0
 freed bytes  | 0 B

I see a ~610 KB allocation in two chunks for the interner, and then a small allocation for each string after.

`strena`

As opposed to most other interners, this interner stores all of the interned strings in a single concatenated string. This reduces allocation space required for the interned strings, as well as fragmentation of the memory held by the interner.

This is a new string interner I've written with the intent of reducing the amount of fragmented memory a string interner has to hold (thus this comparison). Hopefully it does well:

    fn strena_collect_words(&self) {
        crate::ALLOCATOR.set_active(true);
        let mut words = strena::Interner::with_capacity(strena::Capacity {
            symbols: WORDS.len(),
            bytes: WORDS.len() * 5, // google says average word length is 4.7
        });
        crate::ALLOCATOR.mark_point();
        for &word in WORDS {
            words.get_or_insert(word);
            crate::ALLOCATOR.mark_point();
        }
        crate::ALLOCATOR.set_active(false);
    }

 total events | 5
  peak bytes  | 260.8 KB
 ----------------------------
 alloc events | 4
 alloc bytes  | 260.8 KB
 ----------------------------
 freed events | 1
 freed bytes  | 38.9 KB

I see a ~180 KB allocation in three chunks for the interner, and then a single realloc around 5.5k symbols in, likely because our wordlist has an average word length greater than five.

The benchmark was basically chosen to show off strena's strong side, though, so digest it with that in mind. I can tell it exactly how to pre-allocate to fit the incoming data.

So what?

We've learned that intaglio is the only interner (of these highly ranked ones) that has special support for interning already-'static strings, and that lasso is the only published one that doesn't allocate every interned string separately. However, we also see that using an O(1) interner does have a noticeable memory impact over just a list of strings. At this scale, string-interner has approximately a 145% overhead; lasso, 145%; intaglio, 175%; strena, 10%.

lasso is already doing half of the clever things strena is doing, though; I'll see if it's possible to reduce lasso's memory overhead before publishing strena myself.

But this is a deliberately-crafted best-case scenario for strena, so

What if it's not best-case?

I've adjusted each of the test cases to default-construct the interner. Rapid-fire, how do each of the interners perform in this situation?

 total events | 7799
  peak bytes  | 323.4 KB
 ----------------------------
 alloc events | 7788
 alloc bytes  | 447.5 KB
 ----------------------------
 freed events | 11
 freed bytes  | 196.5 KB

 total events | 7826
  peak bytes  | 795.6 KB
 ----------------------------
 alloc events | 7802
 alloc bytes  | 1.1 MB
 ----------------------------
 freed events | 24
 freed bytes  | 540.8 KB

 total events | 71
  peak bytes  | 799.1 KB
 ----------------------------
 alloc events | 44
 alloc bytes  | 1.1 MB
 ----------------------------
 freed events | 27
 freed bytes  | 541.1 KB

 total events | 15602
  peak bytes  | 1.1 MB
 ----------------------------
 alloc events | 15578
 alloc bytes  | 1.6 MB
 ----------------------------
 freed events | 24
 freed bytes  | 737.3 KB

 total events | 6
  peak bytes  | 811.0 KB
 ----------------------------
 alloc events | 4
 alloc bytes  | 909.3 KB
 ----------------------------
 freed events | 2
 freed bytes  | 303.1 KB

Intaglio has a default capacity of 4096, so it really cheats this measurement. I've used a starting capacity of 0 for the dynamic test for a fair comparison, but keep in mind that you probably do want to prime the interner with a decent capacity estimate you plan to fill.

 total events | 7828
  peak bytes  | 861.2 KB
 ----------------------------
 alloc events | 7803
 alloc bytes  | 1.3 MB
 ----------------------------
 freed events | 25
 freed bytes  | 606.3 KB

 total events | 75
  peak bytes  | 254.0 KB
 ----------------------------
 alloc events | 39
 alloc bytes  | 426.1 KB
 ----------------------------
 freed events | 36
 freed bytes  | 213.1 KB

So what? (again)

For a simple overview, here's the overhead over the simple string collecting approach for each library, in peak memory usage, total bytes allocated, and total bytes freed:

string-interner: 145% / 145% / 175%
lasso: 150% / 145% / 175%
lalrpop: 240% / 260% / 275%
intaglio (dyn): 165% / 190% / 205%
strena: -10% / -5% / 5%

Whoops, I accidentally made my library look really good again. And keep in mind: this is something of a worst-case for interners, as we just straight insert a single symbol at a time for 7776 symbols.

In conclusion

I'll leave a final interpretation of the data I've gathered here to you, the reader. For me, I think I'd recommend using lasso currently, and I plan to see if I can upstream some of the cleverness in strena to lasso to decrease their memory usage closer to strena's.

One weekend later...

and we've got new versions of both string-interner (v0.11) and lasso (v0.3) taking advantage the approach strena uses to minimize memory usage!

 total events | 66
  peak bytes  | 319.9 KB
 ----------------------------
 alloc events | 41
 alloc bytes  | 492.3 KB
 ----------------------------
 freed events | 25
 freed bytes  | 213.4 KB

 total events | 41
  peak bytes  | 409.7 KB
 ----------------------------
 alloc events | 24
 alloc bytes  | 634.0 KB
 ----------------------------
 freed events | 17
 freed bytes  | 285.8 KB

The remaining difference in memory usage is likely down to different cache growth strategies. The different libraries are "ahead" at different points.

Additionally, both libraries have added (the ability to take advantage of) the &'static str optimization from intaglio. The fastest allocation is one you don't have to do, after all!

Open Source really did work in this instance, and I feel strena has served its purpose as a research project and doesn't need to be published. string-interner and lasso are better for it and you can take advantage of one of those instead.

"try fn" without special-casing Result

Crystal Durham — Thu, 09 Apr 2020 03:01:07 +0000

There has been much talk recently about "try fn" in Rust. This is to add some fuel to the fire and address one major argument against try-like sugar for functions: the special casing of Result.

This is explicitly not supposed to be a proposal. This is just meant to open discussion on a new avenue of the "try fn" design space I haven't seen mentioned yet.

Quickly summarizing the potential feature (but please, don't focus on the concrete syntax):

try fn read_to_string(path: &Path) -> String, io::Error {
    let mut file = File::open(path)?;
    let mut string = String::with_capacity(initial_buffer_size(&file));
    file.read_to_string(&mut string)?;
    string
}

essentially would desugar to

fn read_to_string<Return>(path: &Path) -> Return
where
    Return: Try<Ok = String, Error = io::Error>,
{
    try {
        let mut file = File::open(path)?;
        let mut string = String::with_capacity(initial_buffer_size(&file));
        file.read_to_string(&mut string)?;
        string
    }
}

except return would be subject to the exact same "ok wrapping" behavior as the trailing expression.

So, how do we make this feature "worth it"? This would make a lot of code generic that would not necessarily have been generic if it were written as a normal fn() -> Result<Ok, Error>.

The first step is to realize that Try is just "isomorphic to Result," at least in the current definition. The compiler could just compile the function as a -> Result<Ok, Error> function, and then insert the required Try conversion boilerplate into the caller if it wanted a different Try type.

But more importantly, I think the value of a try fn goes hand-in-hand with an "error side-channel" / "lightweight exception" mechanism. try fn would be the way you explicitly suggest the compiler use this mechanism.

I don't want to go into exactly what an alternate ABI for Result/Try would look like for Rust; I don't perfectly understand it myself. What I do understand, though, is that it's an optimization of the happy path over the cold path. It's purely an optimization over -> Result semantics, and should be viewed as such: something the compiler can turn on and off depending on whether it thinks the optimization is beneficial (to the non-error path).

But I do think this kind of try fn is useful to explicitly say "hey, the Try::Error case here is cold," and "optimize for the Try::Ok case." But at the same time, it's mostly useful when most calls into try fn are immediately just annotated with ? themselves, passing along the error.

And I think that may be where the disconnect on the usefulness or "viability" of try fn is. For the majority case, I think library code should not be using try fn. try fn should be used for functions that are primarily just "application style," passing up some mostly opaque eyre::ErrReport that will be caught and logged at some top level. For applications, the error case is an expected failure, but one that you can't really do much about other than acknowledge and move on.

As a final step: say we decide try fn is worth it on the argument above, and send it off to the bikeshed factory to await (pun intended) its final syntax form. How do we make it actually useful, rather than just theoretically desirable?

The main one will be defaulting the return type to be Result if the concrete return type is needed (i.e. it's not immediately ? applied). Doing so might allow the standard library to use try fn for things like fs::read_to_string above.

But I also think that it ties in to the greater error handling story in Rust, which is far from a solved problem. The utility of a try fn mechanism is inherently tied to the shape of errors it carries.

Discuss this on Reddit

Lossless Syntax Trees

Crystal Durham — Sun, 27 Oct 2019 21:18:03 +0000

So you want to parse a programming language. You want to turn some text into a semantic data structure representing the structure of the program as written by the user.

But how exactly do you structure such a semantic model? A Parse Tree (sometimes called a Concrete Syntax Tree, or CST) is what a grammar-based parsing tool like ANTLR typically produces for this purpose. This faithfully represents the structure of the formal parse tree, including meaningless syntax that’s there for disambiguation but often excluding trivia that's allowed to be anywhere, such as whitespace and comments. The traditional improvement to this approach is something called an Abstract Syntax Tree, or AST for short, which models only the meaningful parts of the grammar.

However, for our IDE-ready compiler, there are two key properties that we have to fulfill: the parser needs to be error-tolerant, and it should be roundtripable. We need error-tolerance because even in the face of an incomplete or incorrect input, we need to produce a syntax tree so we can provide things like syntax highlighting and completion on in-progress code. Code in the IDE spends most of its time in an incomplete state as it is being written. As for roundtrippable, we want to be able to transform the syntax tree in the IDE and maintain things like formatting and comments. To get both of these properties, we use rowan, a library implementing a more recent syntax tree design called a Lossless Syntax Tree^†.

The key trick of the rowan LST is structuring a dynamically typed CST such that we can provide a structurally typed AST view into the CST. The untyped nature of the CST also provides for representation of our error tolerance: any node can have arbitrary children, so long as our parser is smart enough to figure out what node is where.

This uses a kind of red-green tree like is used in Roslyn. The green tree is the CST, and is structured like a normal singly-linked tree: each node has a list of its children. The tree is dynamically typed, as it only stores a #[repr(u16)] enum SyntaxKind^‡ alongside the textual width of the node. The red tree is a view into the green tree which is dynamically constructed on-demand, and contains parent pointers along with absolute offsets. The AST layer adds extra type information onto the red tree for what you can do with any given node, though all accessors necessarily return an Option to represent the dynamicism of the concrete tree that allows for it to represent incorrect source code.

To build our compiler to this point, we need to first do a bit of refactoring. The design so far is solid, but a few tweaks will prepare it for the parser. First, we should update any out-of-date dependencies. cargo upgrade--all --allow-prerelease does the trick, giving at the time of writing, just an upgrade from tera@1.0.0-beta.16 to tera@1.0.0-beta.18.

Now, let's remind ourselves of the grammar we're working with:

Program = Statement*;
Statement =
  | If:{ "if" cond:(Expression::Parenthesized) then:Statement { "else" else:Statement }? }
  | While:{ "while" cond:(Expression::Parenthesized) then:Statement }
  | Block:{ "{" then:Statement* "}" }
  | Expression:{ then:Expression? ";" }
  ;
Expression =
  | Parenthesized:{ "(" Expression ")" }
  | Assignment:{ id:Identifier "=" val:Expression }
  | Comparison: #[associativity(left)] { lhs:Expression "<" rhs:Expression }
  | Addition: #[associativity(left)] { lhs:Expression "+" rhs:Expression }
  | Subtraction: #[associativity(left)] { lhs:Expression "-" rhs:Expression }
  | Term:Term
  ;
Term =
  | Identifier:Identifier // token
  | Integer:Integer // token
  | Expression:(Expression::Parenthesized)
  ;

(If you're following along as these are posted, you may note that this is different than the grammar I've used so far; this comes from starting implementing the parser and finding improvements.)

Here we see that a Program is made up of zero-or-more Statement; a Statement is either Statement::If, Statement::While, Statement::Block, or Statement::Expression; and Statement::If is a literal if followed by an Expression::Parenthesized and a Statement, optionally followed by a literal else and another Statement. This describes the structure of a correct tree. We add the nonterminal symbols to our syntax.toml:

nonterminals = [
    "program",
    "statement if",
    "statement while",
    "statement block",
    "statement expression",
    "expression parenthesized",
    "expression assignment",
    "expression comparison",
    "expression addition",
    "expression subtraction",
    "expression term",
    "term identifier",
    "term integer",
    "term expression",
]

In addition, I upgraded the error kind from being listed in the metadata file to being explicitly listed last in the template file. While it is a node kind, it's different than the real nodes of a proper tree, and should be treated specially. Now, we should rename our existing SyntaxKind to TokenKind to clarify that it's just for tokens, then create a new template for SyntaxKind, which includes the nonterminals:

{%- set empty = [] -%}
// Separate variables for terminals and nonterminals
{%- set terminals = empty
    | concat(with=keywords)
    | concat(with=literals)
    | concat(with=punctuation | map(attribute="name"))
    | concat(with=tokens)
-%}
{%- set all_kinds = empty
    | concat(with=terminals)
    | concat(with=nonterminals)
-%}

#[repr(u16)]
#[allow(missing_docs)]
// Add serde to runtime dependencies.
// TokenKind should impl `Serialize` as well.
#[derive(serde::Serialize)]
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub enum SyntaxKind {
    {%- for kind in all_kinds %}
    {{ kind | camel_case }},
    {%- endfor %}
    ERROR,
}

impl SyntaxKind {
    /// The name of this syntax kind.
    pub fn name(self) -> &'static str {
        match self {
            {%- for kind in all_kinds %}
            SyntaxKind::{{ kind | camel_case }} => "{{ kind | camel_case }}",
            {%- endfor %}
            SyntaxKind::ERROR => "ERROR",
        }
    }
}

// We need to convert from TokenKind to SyntaxKind.
// This could be explicitly zero-cost by using a transmute,
// but we stick here to the safe version and let it optimize.
impl From<TokenKind> for SyntaxKind {
    fn from(token: TokenKind) -> SyntaxKind {
        match token {
            {%- for kind in terminals %}
            TokenKind::{{ kind | camel_case }} => SyntaxKind::{{ kind | camel_case }},
            {%- endfor %}
            TokenKind::ERROR => SyntaxKind::ERROR,
        }
    }
}

// For rowan, we also want conversions to/from u16.
impl From<SyntaxKind> for u16 {
    fn from(kind: SyntaxKind) -> u16 {
        kind as u16
    }
}

// This could be explicitly zero-cost by using a transmute,
// but we stick here to the safe version and let it optimize.
impl From<u16> for SyntaxKind {
    fn from(raw: u16) -> SyntaxKind {
        match raw {
            {%- for kind in all_kinds %}
            {{ loop.index }} => SyntaxKind::{{ kind | camel_case }},
            {%- endfor %}
            _ => SyntaxKind::ERROR,
        }
    }
}

We also want to pull the Token struct from tinyc_lexer into tinyc_grammar, and re-export it from tinyc_lexer instead:

use serde::ser::{Serialize, Serializer};

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

#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct Token {
    pub kind: TokenKind,
    pub len: u32,
}

impl Serialize for Token {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.serialize_newtype_variant(
            "Token",
            u16::from(self.kind).into(),
            self.kind.name(),
            &self.len,
        )
    }
}

It fits better in tinyc_grammar, which is our crate for raw data boxes than tinyc_lexer, which is our crate implementing the lexer. Other crates could easily want to consume Token without depending on the lexer.

With these improvements, we're ready to start implementing the parser next time.

Discuss this below! | See the result on GitHub!

How did I do on code density this time? Last time felt a bit too much here's the code, so this one tries to focus a bit more on concepts and less on concrete implementation.

† You may also see a Lossless Syntax Tree referred to as a Concrete Syntax Tree. I prefer LST for this concept as a Parse Tree is somewhat commonly called a CST (as mentioned above) and is explicitly not what the LST is. Often times, an LST will simply be called Syntax Tree as well. whether Syntax Tree means CST, AST, or LST is left up to context. There are, of course, also alternate approaches to syntax trees that fall somewhere in-between these three categories.

‡ Actually, rowan uses a struct SyntaxKind(u16) internally and translates between that and the user's syntax kind enum at a higher level. This reduces generics proliferation and allows the library user to use a more complicated sum type than just a C-style enum if desired.

What is a Lexer, Anyway?

Crystal Durham — Fri, 11 Oct 2019 18:58:50 +0000

The first task when implementing any language (that is already specified) is to turn the source code into some sort of Syntax Tree that's meaningful to the computer, rather than the human-optimized surface language.

This is the task of Parsing. Parsing is a wide and well studied field in computer science, and formally, is the problem of just recognizing if any given string is a member of some language.

Slightly more concretely, parsing is the task of turning a list of symbols into a data structure representing some higher level of structure. In the case of parsing, the set of input symbols are characters†.

Traditionally, parsing of programming languages is split up into two phases: the lexing stage and the parsing stage. In truth, both of these stages are parsers: they both take an input list of symbols and produce a higher level of structure. It's just that the lexer's output is used as the parser's input.

This separation is useful because the lexer's job is simpler than the parser's. The lexer just turns the meaningless string into a flat list of things like "number literal", "string literal", "identifier", or "operator", and can do things like recognizing reserved identifiers ("keywords") and discarding whitespace. Formally, a lexer recognizes some set of Regular languages. A "regular" language is one that can be parsed without any extra state in a single non-backtracking pass. This makes it very efficient: you only have to look at one byte at a time to make decisions, and all of the decisions can even be packed into a decision matrix called a Finite Automaton. If you've ever used a regular expression, you've written a recognizer for a regular language‡.

The parser has the much harder job of turning the stream of "tokens" produced by the lexer into a parse tree representing the structure of the parsed language. The separation of the lexer and the parser allows the lexer to do its job well and for the parser to work on a simpler, more meaningful input than the raw text.

While there are many ways to generate lexers, we'll be implementing our lexer by hand so that the structure of it can be seen. The simplest form of the lexer is fn(&str) -> Token, where Token is a (Kind, Length) pair. That's the API we'll implement, though for convenience we also provide a fn(&str) -> impl Iterator<Item=Token> access point. Note that this is an infallible transform: on unexpected characters we just return an error token.

Let's look at our Tiny-C grammar again to determine what our lexer has to recognize:

Program = Statement;
Statement =
  | If:{ "if" cond:ParenExpr then:Statement else:{ "else" then:Statement } }
  | While:{ "while" cond:ParenExpr then:Statement }
  | Block:{ "{" then:Statement* "}" }
  | Expr:{ then:Statement? ";" }
  ;
ParenExpr = "(" Expr ")";
Expr =
  | Assign:{ id:Id "=" val:Expr }
  | Test:{ lhs:Expr "<" rhs:Expr }
  | Sum:{ lhs:Expr "+" rhs:Term }
  | Diff:{ lhs:Expr "-" rhs:Term }
  ;
Term =
  | Id:{ 'a'..='z'+ }
  | Int:{ '0'..='9'+ }
  | Expr:ParenExpr
  ;

The terminal productions in the grammar are those without any inner structure, and those are what the lexer produces. We have the literal strings/keywords of if, else, and while; punctuation of {/}, ;, (/), =, <, +, and -; and the terminal productions of Id (one or more lowercase ascii characters) and Int (one or more ascii digits).

Now that we know what we're implementing, we have to decide how we want to structure our workspace. For typical development, I use IntelliJ IDEA with IntelliJ Rust. For this series, though, I will be assuming an environment of Visual Studio Code with rust-analyzer, due to VSCode's utility for developing language servers. The canonical repo is located at https://github.com/cad97/tinyc.

Since we want to build a modular compiler, we're going to want to split things up into separate crates. So set up a virtual manifest in a new directory and create our first crate, tinyc_grammar. The grammar crate will hold the definition of our grammar types and be almost exclusively generated from metadata. We're only going to set up the terminal token types right now, but this sets up the framework for continuing onward. The build-dependencies we'll need (managed with cargo-edit):

cargo add -sB glob heck serde tera toml --allow-prerelease

At the time of writing, that gives glob@0.3, heck@0.3, serde@1.0, tera@1.0.0-beta.16, and toml@0.5. We also need to enable serde's "derive" feature.

We now need a folder to hold our metadata about the language. In it, we create syntax.toml.

# The keywords of our language.
keywords = [
    "else",
    "if",
    "while",
]

# Literal data embedded in the source.
literals = [
    "integer",
]

# Symbols alongside names for them.
punctuation = [
    ['{', "left curly bracket"],
    ['}', "right curly bracket"],
    ['(', "left parenthesis"],
    [')', "right parenthesis"],
    ['+', "plus sign"],
    ['-', "hyphen minus"],
    ['<', "less than sign"],
    [';', "semicolon"],
    ['=', "equals sign"],
]

# Tokens that don't fall into one of the above categories.
# "error" is for errors: when we encounter something unexpected.
# "whitespace" is the white space between tokens, and is explicit in our lexer.
tokens = [
    "error",
    "identifier",
    "whitespace",
]

We also need to create the Tera template for our syntax kind enum, syntax_kinds.rs:

// This is just a workaround: for some reason
// a tera filter expression cannot start with a literal empty array
{%- set empty = [] -%}
// Create a variable for accessing every kind
// by concatenating each individual kind
{%- set all_kinds = empty
    | concat(with=keywords)
    | concat(with=literals)
    | concat(with=punctuation | map(attribute="name"))
    | concat(with=tokens)
-%}

// Rowan internally stores kind as a u16
#[repr(u16)]
// We won't be generating docs
#[allow(missing_docs)]
// Derive all of the standard traits we can
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub enum SyntaxKind {
    {%- for kind in all_kinds %}
    // list each kind in camel_case
    {{ kind | camel_case }},
    {%- endfor %}
}

In Tera syntax, {% %} is a control statement. At the top, we set all_kinds to define an array of every kind to allow us to use the list multiple times without constructing it every time. In the enum definition, we iterate over every kind in all_kinds and use {{ }} to paste in each kind transformed into camel_case.

Now that we've set up our metadata, we can actually generate our grammar crate! Create a build.rs and add the following:

use {
    glob::glob,
    heck::*,
    serde::{Deserialize, Serialize},
    std::{
        collections::HashMap,
        env,
        error::Error,
        fs,
        path::{Path, PathBuf},
    },
    tera::{self, Context, Tera, Value},
    toml,
};

/// The manifest directory.
const MANIFEST: &str = env!("CARGO_MANIFEST_DIR");
/// Project-relative path to the syntax metadata.
const SYNTAX_CONFIG: &str = "meta/syntax.toml";
/// Directory containing the Tera templates.
const TEMPLATE_DIR: &str = "meta";

/// The sytnax kinds enum template.
pub const SYNTAX_KINDS: &str = "syntax_kinds.rs";

/// Easy access to the project root path.
fn project_root() -> &'static Path {
    // We take the 2nd ancestor as our crate's manifest is two folders deep.
    Path::new(MANIFEST).ancestors().nth(2).unwrap()
}

/// The structured syntax metadata.
///
/// We derive Serialize to serialize to a Tera config object
/// and Deserialize to deserialize from the metadata file.
#[derive(Serialize, Deserialize)]
struct SyntaxConfig {
    keywords: Vec<String>,
    literals: Vec<String>,
    punctuation: Vec<PunctuationConfig>,
    tokens: Vec<String>,
}

/// A punctuation config item, represented in toml as `["character", "name"]`.
///
/// We derive Serialize so the Tera config object has named members,
/// but implement Deserialize manually to deserialize from an unnamed sequence.
///
/// Note that this means `de::from_str(ser::to_string(punctuation_config))`
/// does not work, as the two formats do not line up. This is only ok to do
/// here because these are the _only_ de/serialization tasks we care about.
#[derive(Serialize)]
struct PunctuationConfig {
    character: char,
    name: String,
}

impl<'de> Deserialize<'de> for PunctuationConfig {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::de::Deserializer<'de>,
    {
        #[derive(Deserialize)]
        #[serde(rename = "PunctuationConfig")]
        struct Helper(char, String);
        // We implement deserialize by just delegating to a helper tuple struct type.
        Helper::deserialize(deserializer).map(|helper| PunctuationConfig {
            character: helper.0,
            name: helper.1,
        })
    }
}

/// A helper function to make Tera filter functions `(value, keys) -> Value`
/// out of a simpler `(T) -> T` transformation.
fn make_filter_fn<'a, T: Into<Value> + serde::de::DeserializeOwned>(
    name: &'a str,
    f: impl Fn(T) -> T + Sync + Send + 'a,
) -> impl tera::Filter + 'a {
    move |value: &Value, _: &HashMap<String, Value>| -> tera::Result<Value> {
        let val = tera::try_get_value!(name, "value", T, value);
        Ok(f(val).into())
    }
}

fn main() -> Result<(), Box<dyn Error>> {
    let root = project_root();
    let templates = root.join(TEMPLATE_DIR).join("**/*.rs");
    let syntax_config = root.join(SYNTAX_CONFIG);
    // All generated files go into `$OUT_DIR` and are `include!`d from there.
    let out = PathBuf::from(env::var("OUT_DIR")?);

    // We have to tell cargo we depend on these files
    // so that cargo will rerun the build script when the files change.
    println!("cargo:rerun-if-changed={}", syntax_config.to_string_lossy());
    for path in glob(&templates.to_string_lossy())? {
        println!("cargo:rerun-if-changed={}", path?.to_string_lossy());
    }

    let tera = {
        // Initialize Tera.
        let mut tera = Tera::new(&root.join(templates).to_string_lossy())?;
        // Add the `camel_case` filter using `heck`.
        tera.register_filter(
            "camel_case",
            make_filter_fn("camel_case", |s: String| s.to_camel_case()),
        );
        tera
    };

    // Read in the context file.
    let config: SyntaxConfig = toml::from_str(&fs::read_to_string(syntax_config)?)?;
    // And convert it into the Tera-compatible form.
    let context = Context::from_serialize(config)?;

    // Write out the generated file.
    fs::write(
        out.join(SYNTAX_KINDS),
        tera.render(SYNTAX_KINDS, context.clone())?,
    )?;
    Ok(())
}

Now we just have to include! the generated file from our lib.rs:

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

and we have our grammar crate up and running! At this point you can do cargo doc to see our progress so far.

The next step is actually writing the lexer, so we can actually run something. So let's create our lexer!

cargo new --lib crates/lexer --name tinyc_lexer
cd crates/lexer
cargo add ../grammar
code src/lib.rs

use std::u32;
// Re-export for ease of use.
pub use grammar::SyntaxKind;

/// A single token in the document stream.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct Token {
    /// The kind of token.
    pub kind: SyntaxKind,
    /// How many bytes this token is.
    pub len: u32,
}

/// Convenience function for repeatedly applying `lex`.
pub fn tokenize(mut source: &str) -> impl Iterator<Item = Token> + '_ {
    // Our compiler tooling assumes source files < 4 GiB in size.
    assert!(source.len() < u32::MAX as usize);
    std::iter::from_fn(move || {
        if source.is_empty() {
            return None;
        }
        let token = lex(source);
        source = &source[token.len as usize..];
        Some(token)
    })
}

/// Lex the first token off of the source string.
pub fn lex(source: &str) -> Token {
    debug_assert!(!source.is_empty());
    debug_assert!(source.len() < u32::MAX as usize);
    // Classify the token.
    if source.starts_with(is_whitespace) {
        // Whitespace token.
        Token {
            kind: SyntaxKind::Whitespace,
            len: source.find(is_not_whitespace).unwrap_or(source.len()) as u32,
        }
    } else if source.starts_with(is_digit) {
        // Integer token.
        Token {
            kind: SyntaxKind::Integer,
            len: source.find(is_not_digit).unwrap_or(source.len()) as u32,
        }
    } else if source.starts_with(is_ident) {
        // Identifier token.
        let len = source.find(is_not_ident).unwrap_or(source.len());
        Token {
            // This is a new function on `SyntaxKind` we'll add next.
            kind: SyntaxKind::from_identifier(&source[..len]),
            len: len as u32,
        }
    } else {
        // Punctuation token.
        let ch = source.chars().next().unwrap();
        Token {
            kind: match ch {
                '{' => SyntaxKind::LeftCurlyBracket,
                '}' => SyntaxKind::RightCurlyBracket,
                '(' => SyntaxKind::LeftParenthesis,
                ')' => SyntaxKind::RightParenthesis,
                '+' => SyntaxKind::PlusSign,
                '-' => SyntaxKind::HyphenMinus,
                '<' => SyntaxKind::LessThanSign,
                ';' => SyntaxKind::Semicolon,
                '=' => SyntaxKind::EqualsSign,
                // Unknown tokens are an error.
                _ => SyntaxKind::Error,
            },
            len: ch.len_utf8() as u32,
        }
    }
}

// Helper functions for classifying characters.
fn is_whitespace(c: char) -> bool {
    c.is_whitespace()
}

fn is_not_whitespace(c: char) -> bool {
    !is_whitespace(c)
}

fn is_digit(c: char) -> bool {
    c.is_ascii_digit()
}

fn is_not_digit(c: char) -> bool {
    !is_digit(c)
}

fn is_ident(c: char) -> bool {
    'a' <= c && c <= 'z'
}

fn is_not_ident(c: char) -> bool {
    !is_ident(c)
}

We also need to add a couple new functions to our syntax_kinds.rs:

impl SyntaxKind {
    /// The syntax kind for a keyword.
    pub fn from_keyword(ident: &str) -> Option<SyntaxKind> {
        match ident {
            {% for keyword in keywords -%}
            "{{ keyword }}" => Some(SyntaxKind::{{ keyword | camel_case }}),
            {% endfor -%}
            _ => None,
        }
    }

    /// The syntax kind for an identifer.
    ///
    /// Note that this doesn't do any validation of the identifier,
    /// it just uses whatever you give it.
    pub fn from_identifier(ident: &str) -> SyntaxKind {
        SyntaxKind::from_keyword(ident).unwrap_or(SyntaxKind::Identifier)
    }
}

And with that, we have our lexer written! Again, use cargo doc to see the API of the lexer.

But to truly show that the lexer works, we need to write some tests. To do so easily, we'll be using the conformance::tests testing library (disclaimer: I am the author). So add conformance and serde_yaml as dev-dependencies to our lexer crate and create a new test file:

cargo add -sD conformance serde_yaml
code ./tests/conformance.rs

use {
    conformance, serde_yaml,
    tinyc_lexer::{tokenize, Token},
};

#[conformance::tests(exact, serde=serde_yaml, file="tests/main.yaml.test")]
fn lex_tokens(s: &str) -> Vec<Token> {
    tokenize(s).collect()
}

We'll use the examples from the canonical implementation as our tests:

code ./tests/main.yaml.test

1
===
a=b=c=2<3;
---
[] # empty tests for now
...

2
===
{ i=1; while (i<100) i=i+i; }
---
[]
...

3
===
{ i=125; j=100; while (i-j) if (i<j) j=j-i; else i=i-j; }
---
[]
...

4
===
{ i=1; do i=i+10; while (i<50); }
---
[]
...

5
===
{ i=1; while ((i=i+10)<50) ; }
---
[]
...

6
===
{ i=7; if (i<5) x=1; if (i<10) y=2; }
---
[]
...

If you run the test now, you'll get an error:

error[E0277]: the trait bound `tinyc_lexer::Token: serde::ser::Serialize` is not satisfied
   --> crates\lexer\tests\conformance.rs:6:1
    |
6   | #[conformance::tests(exact, serde=serde_yaml, file="tests/main.yaml.test")]
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `serde::ser::Serialize` is not implemented for `tinyc_lexer::Token`
    | 
   ::: D:\usr\.cargo\registry\src\github.com-1ecc6299db9ec823\serde_yaml-0.8.11\src\ser.rs:421:8
    |
421 |     T: ser::Serialize,
    |        -------------- required by this bound in `serde_yaml::ser::to_string`
    |
    = note: required because of the requirements on the impl of `serde::ser::Serialize` for `std::vec::Vec<tinyc_lexer::Token>`

The Serialize implementation is what we use to compare the expected output with what we actually produce. So we add a new helper in the syntax_kinds.rs template:

impl SyntaxKind {
    /// The name of this syntax kind.
    pub const fn name(self) -> &'static str {
        match self {
            {% for kind in all_kinds -%}
            SyntaxKind::{{ kind | camel_case }} => "{{ kind | camel_case }}",
            {% endfor -%}
            #[allow(unreachable_patterns)]
            _ => "", // For the future
        }
    }
}

and for tinyc_lexer::Token, we implement Serialize manually. Why? Because we can get a much nicer serialization (Token: length) than the default one if we didn't change it ({ kind: "Token", len: length }).

cargo add -s serde
code src/serde.rs

use {
    super::*,
    serde::ser::{Serialize, Serializer},
};

impl Serialize for Token {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.serialize_newtype_variant(
            // The name of the type
            "Token",
            // TokenKind is `#[repr(u16)]`, so this cast is legal
            self.kind as u16 as u32,
            // Using our added helper to get the name of the kind
            self.kind.name(),
            // The data payload of the serialized newtype variant
            &self.len,
        )
    }
}

This serializes Token as if it were enum Token { Kind(u32) }, which is really what it acts like; we just separate it to a (kind, length) tuple because generating and manipulating the kind without the length is useful for the compiler. (Don't forget to include the file with mod serde.)

If you run the test now, the tests will compile but fail, as we're asserting that the examples lex into an empty sequence of tokens. Unfortunately, the diff provided by the default assert_eq! is really hard to read for large data like this without IDE integration like IntelliJ-Rust has.

---- main_yaml_1 stdout ----
thread 'main_yaml_1' panicked at 'assertion failed: `(left == right)`
  left: `"---\n- Identifier: 1\n- EqualsSign: 1\n- Identifier: 1\n- EqualsSign: 1\n- Identifier: 1\n- EqualsSign: 1\n- Integer: 1\n- LessThanSign: 1\n- Integer: 1\n- Semicolon: 1"`,
 right: `"---\n[]"`', crates\lexer\tests\conformance.rs:6:1
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

However, an unescape tool along with a diff tool makes sense of the output. Check that the produced output is what it's supposed to be, then copy it into the test file to insure you know if it changes in the future.

And with that, we have a working lexer! Next time, we'll take the first steps towards parsing the tokens into a syntax tree.

Discuss this below! | See the result on GitHub!

† Characters are a lie. Rather, we work on Unicode Abstract Characters, or codepoints. That's the 32 bit value that Rust's char datatype represents. Unfortunately, a human-perceived character is a nebulous concept and not even consistent between human languages. Unicode has the concept of an (Extended) Grapheme Cluster which attempts to roughly approximate this, but that requires a parser of its own and is beyond what we need; working on codepoints is enough. Anyway, outside of literal strings, most programming languages don't allow anything other than ASCII.

‡ Some regular expression engines allow non-regular extensions to the regular expression language. Regular expressions are convenient, and having to stick to regular parsing techniques is restrictive, so features like backreferences were introduced for a limited form of context-sensitive parsing. Some engines like Rust's regex crate don't implement these nonregular features, and that allows them to completely eliminate "regex performance pitfalls".

Conformance Testing in Rust

Crystal Durham — Fri, 04 Oct 2019 21:20:28 +0000

I'm excited to announce conformance::tests, a new crate I've published as part of building the Tiny-C compiler for the Crafting IDE-Ready-Compilers series.

The idea of this crate is to make it simpler to test any API which takes the shape of a &str -> impl serde::Serialize + serde::Deserialize function. It works with any serde compatible data format, though I find that serde_yaml or ron give the most readable diffs for a failed test.

Using the Tiny-C lexer and YAML for serialization, here's what a test looks like:

simple_test
===
a=b=c=2<3;
---
- Identifier: 1
- EqualsSign: 1
- Identifier: 1
- EqualsSign: 1
- Identifier: 1
- EqualsSign: 1
- Integer: 1
- LessThanSign: 1
- Integer: 1
- Semicolon: 1
...

and to hook it up to the standard Rust test runner, all that has to be written is:

#[conformance::tests(exact,
    ser = serde_yaml::to_string,
    de = serde_yaml::from_str,
    file = "tests/yaml.test")]
fn lex_tokens(s: &str) -> Vec<Token> {
    tokenize(s).collect()
}

A test in the test file is represented by a test name (which needs to be a valid rust identifier continuation), terminated by a === on its own line, the test input string, terminated by a --- on its own line, and the serialized expected output, terminated by a ... on its own line. A test file contains any number of these tests. (The extension of the file does not matter, but idiomatically should be format.test.) The file name (excluding the extension) is also required to be a valid Rust identifier (or a . is also allowed).

The procedural macro is applied to the function that you want to test. The function must have the shape of taking a single parameter of type &str and returning a type that can be de/serialized by serde. The arguments to the macro itself are:

exact: the produced value must exactly match the expected value. In the future, a separate mode where the produced value is just required to be a superset of the expected value is planned.
ser: a path to a function of shape fn<T: serde::Serialize>(&T) -> String.
de: a path to a function of shape fn<T: serde::Deserialize>(&str) -> Result<T, impl std::error::Error>.
file: a file path string relative to the cargo manifest directory to the intended test file.

Of course, multiple conformance::tests attributes can be applied to the same function to run the tests in multiple files.

If all you want to do is use the library, you now know everything you need to know to use it. But I find the details of how it works interesting to discuss, so read on to see.

The Rust Custom Test Frameworks feature is still experimental and unstable. But, while #[test_case] might simplify the implementation of conformance, it's not needed and by using just #[test] we work on stable.

In order to integrate natively into the standard #[test] test runner, a unique #[test] function is emitted for each test in the test file.

To do the actual testing work, we emit a single function:

#[cfg(test)]
fn #testing_fn(expected: &str, actual: &str) -> Result<(), Box<dyn ::std::error::Error>> {
    const _: &str = include_str!(#filepath);
    let actual = #ser(&#fn_name(actual))?;
    let expected = #ser(&#de::<#tested_type>(expected)?)?; // normalize
    assert_eq!(actual, expected);
    Ok(())
}

We call the function by the file name, such that multiple files can be tested in the same Rust namespace. The file path is include_str!'d to add a data dependency onto the test file so changing it will recompile the crate. (Hopefully Rust doesn't get smart enough to just recompile the const until a real API for reading files in a procedural macro in a principled way is stabilized.)

For each function in the test file, we emit a function that delegates to #testing_fn:

#[test]
fn #test_name() -> Result<(), Box<dyn ::std::error::Error>> {
    #testing_fn(#output, #input)
}

The function name is assembled as {filename}_{testname}, thus the requirements on naming for the filename and test name. The output and input to the test are sliced out of the test file and included as string literals in the generated token stream.

Because the comparison is just done by assert_eq, that's the whole macro. Complete with all the formalities, it's just under 200 lines (plus syn{features=[full]})! The test failure is best viewed with IntelliJ Rust since they provide a diff view of assert_eq! failures, or with some other assert_eq patch like pretty-assertions to provide an in-terminal diff.

There's a few features I'd like to add to conformance::tests that I'd love to have community assistance in designing.

"Includes"/"superset" mode, as opposed to the current "strict" mode. The produced value includes at least the specified data, but is allowed to include more data. This is mostly useful for testing part of a structure, omitting data not relevant to the test.
serde = shortcut: give a path to a serde_json/serde_yaml-like module/crate, that exposes a to_string and from_str appropriate for ser and de.
A smarter diff algorithm. While comparing the string serialized version of data structures is nicely minimal and utilitarian, I can't help but think we can do better and use some sort of "minimizing diff" algorithm (like Longest Common Sub-sequence is for sequences) that can generally apply to the serde data model. This might even be required for the "superset" mode.
Remove the Deserialize requirement. It's currently just used to normalize the serialized format; removing it means many more things can be tested through conformance::tests, even if they can't deserialize well.

If you're interested, check out the repository, and get a bonus sneak peek at the content of next week's post for the Tiny-C lexer.

Crafting IDE-Ready Compilers

Crystal Durham — Fri, 27 Sep 2019 18:27:47 +0000

This is the introductory post of a series, so normally you would find a motivational section here. Why should you learn how to build a compiler? I'm not going to bother with that; Crafting Interpreters did it better than I could, anyway. The short of it is, well, writing compilers is fun, and covers a lot of techniques for solving problems.

We're going to start by implementing an interpreter for the Tiny-C language. Tiny-C is a significantly stripped down C-style language where there is only one data type, no variable declarations, no functions, the only control flow options are if and while, and the only expressions are +, -, and <. Because of this, the grammar is simple enough I can include it here inline:

Program = Statement;
Statement =
  | If:{ "if" cond:ParenExpr then:Statement else:{ "else" then:Statement } }
  | While:{ "while" cond:ParenExpr then:Statement }
  | Block:{ "{" then:Statement* "}" }
  | Expr:{ then:Statement? ";" }
  ;
ParenExpr = "(" Expr ")";
Expr =
  | Assign:{ id:Id "=" val:Expr }
  | Test:{ lhs:Expr "<" rhs:Expr }
  | Sum:{ lhs:Expr "+" rhs:Term }
  | Diff:{ lhs:Expr "-" rhs:Term }
  ;
Term =
  | Id:{ 'a'..='z'+ }
  | Int:{ '0'..='9'+ }
  | Expr:ParenExpr
  ;

(Note that this is slightly modified from the original Tiny-C to better fit how we are going to build the compiler.) The simplicity of the language allows us to focus on the structure of the compiler rather than the intricacies of the language. If you don't fully understand the above grammar, don't worry: we'll be covering it in more detail in the future.

Additionally, we'll be writing the compiler in a fully IDE-ready style. This means our compiler will also serve as the intelligence engine powering a language server protocol server. Though our language is simple, we want to write the compiler as if it were a full-fat compiler for a full-fat language. By doing so, we can transfer what we learn here to real languages' intelligence engines.

Because we're trying to build a real compiler, we'll be taking full advantage of the available tooling for building compilers in Rust. Rust's ownership semantics make the compartmentalization and complex data flows through a compiler easier to see. For libraries, we'll be using at least rowan, salsa, and lsp-server.

With any luck, once we've implemented the interpreter for Tiny-C, we'll continue on to write a backend with Cranelift, and maybe even continue on to designing and writing a full language 👀

I plan to have a post in the series out at least every other Friday. Next time: we set up the repository structure and lex the language into its component tokens. We'll also be getting our first venture into code generation along the way.

Discuss this below! | on Reddit! | on Twitter! | on Discord! | Watch me live!

Rust Must-Know Crates

Crystal Durham — Tue, 07 May 2019 21:24:53 +0000

This is my collection of Rust crates that I often find myself using. Not every project needs to use all of them, but most projects are better off knowing that they exist. Crates are very loosely ordered within their heading from more generally useful to more niche application.

This list will be kept somewhat up to date as my preferences and the ecosystem shift. This is obviously not a complete list of great crates, but just an introduction to the great ecosystem of Rust utilities available to programmers.

Cargo Plugins

cargo-edit

This tool extends Cargo to allow you to add, remove, and upgrade dependencies by modifying your Cargo.toml file from the command line.

Currently available subcommands:

cargo add

cargo rm

cargo upgrade

cargo-outdated

A cargo subcommand for displaying when Rust dependencies are out of date.

cargo-tree

A Cargo subcommand that visualizes a crate's dependency graph in a tree-like format.

cargo-update

A Cargo subcommand for checking and applying updates to installed executables.

cargo-expand

Print out the result of macro expansion and #[derive] expansion applied to the current crate.

cargo-modules

A cargo plugin for showing an overview of a crate's modules.

cargo-tarpaulin

Tarpaulin is designed to be a code coverage reporting tool for the Cargo build system, named for a waterproof cloth used to cover cargo on a ship. Currently, tarpaulin provides working line coverage but is still in the early development stage and therefore may contain some bugs.

cargo-audit

Audit Cargo.lock for crates with security vulnerabilities reported to the RustSec Advisory Database.

cargo-crev

A tool helping Rust users review crates they use, and share it with the community. It works as a recomendation system, helps identify poor quality, protects against many attack vectors, and aims at driving the quality of Rust ecosystem even higher, by encouraging continous peer review culture.

cargo-clone

Fetch the source code of a Rust crate.

cargo clone will likely be added to cargo proper at some point.

Derives

derive-more

Rust has lots of builtin traits that are implemented for its basic types, such as Add, Not or From. However, when wrapping these types inside your own structs or enums you lose the implementations of these traits and are required to recreate them. This is especially annoying when your own structures are very simple, such as when using the commonly advised newtype pattern (e.g. MyInt(i32)).

This library tries to remove these annoyances and the corresponding boilerplate code. It does this by allowing you to derive lots of commonly used traits for both structs and enums.

Derives for:

smart-default

Custom derive for automatically implementing the Default trait with customized default values.

derive-builder

Rust macro to automatically implement the builder pattern for arbitrary structs. A simple #[derive(Builder)] will generate a FooBuilder for your struct Foo with all setter-methods and a build method.

strum

A set of macros and traits for working with enums and strings easier in Rust.

Derives for:

Meta-programming (macros)

syn

Syn is a parsing library for parsing a stream of Rust tokens into a syntax tree of Rust source code.

proc-macro2

A runtime-compatible wrapper around the procedural macro API of the compiler's proc_macro crate.

proc-quote

The quote! macro as a procedural macro, instead of the original quote! macro, implemented with macro_rules!.

The quote! macro turns Rust syntax tree data structures into tokens of source code.

paste

A flexible way to paste together identifiers in a macro, including using pasted identifiers to define new items.

Testing

insta

Snapshots tests (also sometimes called approval tests) are tests that assert values against a reference value (the snapshot). This is similar to how assert_eq! lets you compare a value against a reference value but unlike simple string assertions snapshot tests let you test against complex values and come with comprehensive tools to review changes.

trybuild

Trybuild is a test harness for invoking rustc on a set of test cases and asserting that any resulting error messages are the ones intended.

Criterion

Helps you write fast code by detecting and measuring performance improvements or regressions, even small ones, quickly and accurately. You can optimize with confidence, knowing how each change affects the performance of your code.

Other Libraries

Regex

A Rust library for parsing, compiling, and executing regular expressions. Its syntax is similar to Perl-style regular expressions, but lacks a few features like look around and backreferences. In exchange, all searches execute in linear time with respect to the size of the regular expression and search text.

lazy-static

A macro for declaring lazily evaluated statics in Rust.

Using this macro, it is possible to have statics that require code to be executed at runtime in order to be initialized. This includes anything requiring heap allocations, like vectors or hash maps, as well as anything that requires non-const function calls to be computed.

Rayon

Rayon is a data-parallelism library for Rust. It is extremely lightweight and makes it easy to convert a sequential computation into a parallel one. It also guarantees data-race freedom.

serde

Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

The Serde ecosystem consists of data structures that know how to serialize and deserialize themselves along with data formats that know how to serialize and deserialize other things. Serde provides the layer by which these two groups interact with each other, allowing any supported data structure to be serialized and deserialized using any supported data format.

typetag

Serde serializable and deserializable trait objects.

This crate provides a macro for painless serialization of &dyn Trait trait objects and serialization + deserialization of Box<dyn Trait> trait objects.

Crossbeam

A set of tools for concurrent programming.

Itertools

Extra iterator adapters, functions and macros.

Rand

A Rust library for random number generation.

Rand provides utilities to generate random numbers, to convert them to useful types and distributions, and some randomness-related algorithms.

log

A Rust library providing a lightweight logging facade.

WalkDir

A cross platform Rust library for efficiently walking a directory recursively. Comes with support for following symbolic links, controlling the number of open file descriptors and efficient mechanisms for pruning the entries in the directory tree.

Directories

A tiny mid-level library that provides platform-specific standard locations of directories for config, cache and other data on Linux, Windows and macOS by leveraging the mechanisms defined by the XDG base/user directory specifications on Linux, the Known Folder API on Windows, and the Standard Directory guidelines on macOS.

tempfile

A secure, cross-platform, temporary file library for Rust. In addition to creating temporary files, this library also allows users to securely open multiple independent references to the same temporary file (useful for consumer/producer patterns and surprisingly difficult to implement securely).

num

A collection of numeric types and traits for Rust, including bigint, complex, rational, range iterators, generic integers, and more!

StructOpt

Parse command line argument by defining a struct. It combines clap with custom derive.

ScopeGuard

Rust crate for a convenient RAII scope guard that will run a given closure when it goes out of scope, even if the code between panics (assuming unwinding panic).

ref-cast

Safely cast &T to &U where the struct U contains a single field of type T.

select-rustc

Macros for conditional compilation according to rustc compiler version, analogous to #[cfg(...)] and #[cfg_attr(...)].

On "Async Streams" in Rust

Crystal Durham — Mon, 15 Apr 2019 20:36:10 +0000

Context: For await loops discussion started by @withoutboats on Internals.

Step 1: What is a `Stream`?

I found the most clear consise explanation comes from @withoutboats again on a different Internals thread:

            | Evaluated immediately     | Evaluated asynchronously
------------------------------------------------------------------------
Return once | `fn() -> T`    (Function) | `async fn() -> T`    (Future)
Yield many  | `fn() yield T` (Iterator) | `async fn() yield T` (Stream)

When you use a Function, you evaluate some routine to retrieve a value.
When you use an Iterator, you evaluate some routine to retrieve the next value, multiple times.
When you use a Future, you await some routine to retrieve a value.
When you use a Stream, you await some routine to retrieve the next value, multiple times.

Step 2: How do we use a `Stream`?

To determine this, let's look at the other points in the matrix.

Function

Trivial: function().

Iterator

A for loop: for item in iterator().

This effectively desugars to code using the Iterator trait (simplified):

let __iter = iterator();
while let Some(item) = __iter.next() {
    // your block
}

Future

The exact syntax to be used to await a Future is still being decided by the lang team. The only fairly decided thing is that it will involve the reserved keyword await. I'll use await!(future) in this document as it's the current unstable syntax and fully unambiguous.

This is extremely simplified, but awaiting a future expands to roughly the following in concept:

let __future = __stack_pin!(future);
loop {
    match __future.poll(__async_context_waker!()) {
        Poll::Ready(value) => break value,
        Poll::Pending => __async_yield_execution!(),
    }
}

Stream

So, how are Streams used before syntax sugar? This is important to understand the semantics we're trying to represent.

We have Iterator, but instead of the function Iterator::next, we have the future Stream::poll_next.

let __stream = __stack_pin!(stream);
while let Some(item) = await!(__future_from_poll!(__stream::poll_next)) {
    // your block
}

This still hides some details in the await!(__future_from_poll!()), so lets inline that:

let __stream = __stack_pin!(stream);
while let Some(item) = loop {
    match __stream.poll_next(__async_context_waker!()) {
        Poll::Ready(value) => break value,
        Poll::Pending => __async_yield_execution!(),
    }
} {
    // your block
}

Wow, everything makes some amount of sense! But how do we actually use this, because this is a lot of boilerplate to use what seems like a useful data type.

Step 3: What Not

The logical operation happening here is awaiting the next value from the stream, for every element in the stream: a combination of iterators (for item in iterator) and futures (await!(future)).

The "obvious" solution would be async for item in stream. But this is the wrong direction: async is the enabler, but await is how you poll a future to completion.

Another enticing solution is to make for just work with Streams and do the equivalent of impl<I: Iterator> Stream for I. But we made (are making) the await operation explicit on futures for good reason, and shouldn't lose that for streams, if for no other reason than it would be inconsistent.

I've seen in multiple places the suggestion to use for item in await!(stream). Hopefully, the above expansions illustrate why that doesn't work semantically. This would instead be awaiting a Future<Item=Iterator>.

Step 4: Possibilities

I personally think that await for item in stream reads perfectly for what the semantics are. Those semantics are that we await "something" to get each item out of the stream, or in other words, we "(a)wait for each item in the stream". There's also no possibility of being confused with await!(for item in stream {}), as for loops don't (and can't) return a value.

@withoutboats also suggests that we could make await a pattern, giving us for await item in stream. I don't hate it, but there's a problem with this.

await as a pattern (here I'll still use await!(pattern) for clarity) I would expect to be the same as awaiting the rhs of the pattern. Or in code, the following two statements would be equivalent:

let value = await!(future);
let await!(value) = future;

This was actually proposed previously in the venerable async/await bikeshedding thread.

The problem is that this now suggests that Stream<Item=T> is Iterator<Item=Future<Item=T>>. Maybe some streams could meet this type. But the current definition of Stream is closer to a StreamingIterator<Item=Future<Item=T>>, as the poll_next requires a pin mut ref to the stream. This borrowing is required for many real streams. (I expect Stream to be abused for StreamingIterator if it works for such and we don't have StreamingIterator yet.)

This could be made to work fairly simply: make for work with StreamingIterator with a fallback for Iterator behavior, and let streams be used by the above composition of StreamingIterator and Future.

But this still lacks the "await?" behavior that many real futures will want (as most async is so because of IO). And even if we add ? to patterns as well, this still means we have two ways of doing the same await operation: expr position (for chaining, which was a focus of the bikeshedding thread) and pat position.

Step 5: Conclusions

I think that await for is the best of the currently proposed syntaxes, at least while awaiting on futures includes the keyword await.

In any case, this is a difficult choice with many tradeoffs, and one that's even harder to make without knowing what the final await syntax is going to be. But it's one that needs to be at least considered when stabilizing await.

Great Rust CI

Crystal Durham — Sat, 20 Jan 2018 03:39:40 +0000

Great CI means coding with confidence. And the CI-compatible tooling situation for Rust is great, so you should take advantage of it.

If you don't know the full details of all of the available tools, though, it can be difficult to set up the perfect CI. So here, I'll walk you through the setup that I'm using.

Install local tools.

Here's what I use every day:

Clippy: code linting for more opinionated things than what rustc gives you.

For now, clippy will only work with the latest nightly. Install and update nightly rust with rustup, then run cargo +nightly install clippy --force to force a clippy install built against your current nightly. Use it with cargo +nightly clippy.
Rustfmt: automatic code formatting.

For many (though not all, sadly) nightlies, rustfmt can be managed using rustup, just like you can for rls. If the nightly that you're on contains rustfmt, you can do rustup component add rustfmt-preview. If your nightly doesn't contain rustfmt-preview, you can install it from crates.io: cargo +nightly install rustfmt-nightly --force. Having both the rustup managed and cargo managed versions can lead to conflicts, so use one or the other. Use it with cargo +nightly fmt.
Cargo-Update: check for and update cargo-install-ed binaries.

Not as much help for clippy/rustfmt, which need to be force-reinstalled for every new nightly (because they link against it), but invaluable for seamlessly updating other tools (including itself). (Requires CMake)
Optional: Cargo-Edit: modify the build manifest (Cargo.toml) from the command line with simple commands, rather than editing the file by hand.
Optional: IDE support. I use IntelliJ IDEA with the IntelliJ Rust plugin. There's also RLS for VSCode, or you could use Vim or Emacs if you're into that kind of thing (no judging!).

Create your project!

$ cargo new great-ci
     Created library `great-ci` project

It's good practice to set up .git/info/exclude to tell git to ignore your IDE files. For me, that means the contents of the git exclude are:

.idea/
*.iml

And for the purpose of this example, let's make a tiny "Hello World" style library:

//! Example library for great CI integration!

use std::fmt;

/// Greetings to some target
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct Greeting<'a>(&'a str);

impl<'a> Greeting<'a> {
    /// Construct a Greeter to greet a target
    pub fn greet(target: &str) -> Greeting {
        Greeting(target)
    }
}

impl<'a> fmt::Display for Greeting<'a> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Greetings, {}!", self.0)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        assert_eq!(2 + 2, 4);
    }

    #[test]
    fn greet_author() {
        let greeter = Greeting::greet("CAD97");
        assert_eq!(greeter.to_string(), "Greetings, CAD97!");
    }
}

Add a LICENSE and README, then it's time to commit and get the code online.

$ git add .
$ git commit -m "Initial commit"
$ git remote add CAD97 git@github.com:CAD97/great-ci.git
$ git push -u CAD97 master

Set up CI

The part that we care about! I use Travis CI, Cargo-Travis, Codecov, and Bors for my CI stack.

So let's switch to a feature branch and set up a basic bors.toml

status = [
    "continuous-integration/travis-ci/push"
]

and .travis.yml:

language: rust

rust:
  - stable
  - beta
  - nightly

script: |
  cargo build --verbose &&
  cargo test  --verbose &&
  cargo doc   --verbose

branches:
  only:
    - staging # bors r+
    - trying  # bors try
    - master

don't forget to enable Travis and Bors for the repository (I did), and then send a PR. If all goes well, your CI is green and you can merge with bors r+.

Testing rustfmt and clippy

When you're working with a project you expect to get large, it can help to enforce standard formatting, and clippy does wonders for preventing simple mistakes and nudging people away from questionable API decisions.

Because rustfmt and clippy are somewhat unstable, requiring certain small ranges of nightly compilers and sometimes breaking, and changing default formatting or adding lints may break your build, we depend on specific versions of the tools, and you can update the versions manually.

We use a matrix include on Travis to add the check:

cache: cargo
matrix:
  include:
    - rust: nightly-2018-01-12
      env: # use env so updating versions causes cache invalidation
        - CLIPPY_VERSION=0.0.179
      before_script:
        - rustup component add rustfmt-preview
        - cargo install clippy --version $CLIPPY_VERSION || echo "clippy already installed"
      script:
        - cargo fmt -- --write-mode=diff
        - cargo clippy -- -D clippy

Here we install clippy using cargo install, or succeed if it's already installed. We install rustfmt using rustup, because in Travis's Rust setup, rustfmt is already tracked by rustup, so the cargo-fmt executable exists, and an install without --force will fail. And if we don't pick a nightly toolchain that actually contains cargo-fmt, using it will fail. Here we have rust: nightly-2018-01-12 CLIPPY_VERSION=0.0.179 because this is the latest toolchain as-of-writing where rustfmt-preview is in, and the latest version of clippy which builds on that nightly.

Installing tools like rustfmt and clippy takes time, and CI is made great when it's fast, so we enable Travis's Rust Cargo cache to cache cargo's symbols. This speeds up the build because cargo doesn't have to recompile dependencies, whether these be build dependencies or tools.

The cache is keyed by the language version (here rust: nightly-2018-01-18) and the env (here CLIPPY_VERSION=0.0.180), and shared between build jobs with the same rust version and env. By putting clippy's version in the env, we separate the tool build's cache from the other caches, and ensure that a version update causes a rebuild.

You may be tempted to stick these environment variables in the CI configuration, so that you can update them without an extra commit to the repository. This is ill-advisable, for two main reasons. Primarily, version bumping these tools has a high likelihood of changing requirements for your build, and the breakage will show up unannounced. This change should be marked in your repository. Secondarily, the use of env here also serves to separate the cache for these tools from the other caches. If the specified rust version is the most up-to-date nightly, this cache and the nightly cache would clobber each other. And you don't want to force installation of these tools on CI builds that don't require it, because we want those zippy CI greens.

So make these changes, submit a PR, and we're go for the last step!

Using cargo-travis

Cargo-travis enables you to easily use kcov and upload coverage information to codecov or coveralls. Additionally, added by myself recently, it allows you to upload documentation for your crate to GitHub pages and maintain an understandable git history and directory structure allowing you to document multiple branches (master/beta/release branches to imitate Rust's nightly/beta/stable trains) if you so wish.

Because these tasks can take a while, and are more for informing decisions rather than to hard gate PRs, I stick these into a allowed-failure matrix line for my builds. This means that Travis passes as soon as the four above jobs pass (rust: [stable, beta, nightly], rustfmt&clippy), and allows the cargo-travis job to continue running in the background.

Our .travis.yml additions:

env: # required for allow_failures
matrix:
  fast_finish: true
  allow_failures:
    - env: NAME='cargo-travis'
  include:
    - env: NAME='cargo-travis'
      sudo: required # travis-ci/travis-ci#9061
      before_script:
        - cargo install cargo-update || echo "cargo-update already installed"
        - cargo install cargo-travis || echo "cargo-travis already installed"
        - cargo install-update -a
      script:
        - |
          cargo build    --verbose &&
          cargo coverage --verbose &&
          bash <(curl -s https://codecov.io/bash) -s target/kcov
        - |
          cargo doc --verbose &&
          cargo doc-upload
      addons: # required for kcov
        apt:
          packages:
            - libcurl4-openssl-dev
            - libelf-dev
            - libdw-dev
            - binutils-dev
            - cmake

If you want to use Coveralls, just use cargo coveralls instead of cargo coverage. If you don't want to use Codecov, just remove the line for the Codecov bash script.

This isn't enough for the doc-upload task, however (though this will not make your CI go red, as we allow this job to fail). In order to upload documentation, the doc-upload script needs permission to push to your GitHub repository. The easiest way, which we will use here, is a GitHub token, but you can read more about the options at the cargo-travis README.

In order to generate a GitHub token, navigate to your tokens settings page. While you're there, review your currently issued tokens, and revoke those that you're no longer using. Generate a new token, give it a descriptive name (this can be edited later) (I suggest repo-name-doc-upload) and the public_repo scope (this can be edited later). Make sure to copy the token once it's generated, as you will never be able to see it again (though you can regenerate it)! This token gives anyone with the token access to act as you when read/writing to any public repository you have the permission to read/write to, so keep it safe. Add it to the GH_TOKEN environment variable on Travis and make sure that "Display value in build log" is set to off.

Once you send your PR, the new job will kick off.

A few things to note about this setup:

CI will pass before coverage is done. This is intentional, as we want to see quick CI feedback for tests passing/failing, and coverage doesn't need to slow down that feedback loop for PRs (or the time it takes to bors r+ and merge). We still want to see those stats, though, and Codecov/Coveralls will still do its analysis and leave a comment once the coverage information is uploaded.
cargo-travis will take a good long time the first time around; you have to build a large number of tools, including kcov itself. Hopefully, however, all of this will be cached, so subsequent builds will be much faster.
Documentation will be built when CI builds the master branch only. You can specify which branches to build by passing (optionally multiple) --branch NAME arguments to cargo doc-upload.
doc-upload does not build documentation for you, so you need to call cargo doc yourself. This is so that you can, if your library offers feature flags or other conditional compilation, build up a directory in target/doc (rustdoc's output directory) which doc-upload will then use when uploading to GitHub pages.
Documentation ends up living at https://<user>.github.io/<repo>/<branch>/<crate>/, which is https://cad97.github.io/great-ci/master/great_ci/ for this example.
Coverage is 100% 🎉

Further extensions

If you want to (or need to) test on a Windows platform, AppVeyor is often used. This CI can be used in parallel to this Travis setup with no problems. Make sure to tell Bors to wait for the AppVeyor build, however!

Don't forget that you can suppress rustfmt and clippy warnings if you don't want them to apply to certain blocks of code. If it's an issue in the source library, submit an issue, or if it's just a disagreement, check the configuration and see if you can change it there.

For the security-minded, the public_repo scope of the GitHub token may be too broad. This is a solved problem; the solution is repo-specific deploy keys. If you provide a deploy key for your repository and load it into Travis (and don't provide a token), doc-upload will use it.

You've got the CI set up, brag about it in your README using badges and by embedding coverage charts! Shields|IO provides consistently-styled badges for practically every service, and Codecov graphs are 🔥🔥🔥.

The base page of your GitHub pages (<user>.github.io/<repo>/) is going to 404, as no index.html exists at the root of your gh-pages branch. The same for the branch root (<user>.gihub.io/<repo>/<branch>). doc-upload deliberately doesn't mess with your root directory or the index.html at the branch root so that you can include a HTML redirect at these spots or a more informative index if you want. For a HTML redirect, use the following:

<meta http-equiv="refresh" content="0; url=<crate>">
<a href="<crate>">Redirect</a>

Discuss this on Reddit and tell me if I left something out or something is outdated!

See the public repository on GitHub!

Refutable Let and Rust in 2018

Crystal Durham — Thu, 11 Jan 2018 03:54:02 +0000

This examines the postponed RFC #1303 "Add a let...else expression", addressing the RFC issue #373 "Explicit refutable let.

This probably will end up formatted like an RFC, and I'd be willing to adapt it to a new RFC since the old one was postponed nearly two years ago now.

A motivating example

Consider a simple example:

if let Some(a) = make_a() {
    if let Some(b) = make_b(a) {
        if let Some(c) = make_c(b) {
            Ok(c)
        } else {
            Err("Failed to make C")?
        }
    } else {
        Err("Failed to make B")?
    }
} else {
    Err("Failed to make A")?
}

There are two key problems here. The first is locality of error handling. The error for line 1 is returned on line 12 of this tiny example. The second is rightward drift. The actual meat of the function (here just Ok(c)) is indented three levels deep. This RFC introduces a "refutable let binding" in order to address both of these issues.

First, let me address the obvious refactor to this minimal example. The current function signatures look something like the following:

fn make_a()     -> Option<A>;
fn make_b(a: A) -> Option<B>;
fn make_c(b: B) -> Option<C>;

The obvious "best" answer would be for these to return a Result with a descriptive error message that you could then propogate with ?. In a real case, though, maybe Option really is the right semantic type to return, and maybe it's vendor code you can't change, etc. etc..

Secondly: You could Option::ok_or_else?. This is how I would write this today. To be fully honest, I'd maybe still write it that way, because ok_or_else is the exact behavior that I want and is very clear. But assume for the sake of argument that this is a more complicated example, such as destructuring a complicated ADT enum. I use Option here for simplicity.

The third option is to destructure using match:

let a = match make_a() {
    Some(a) => a,
    _ => Err("Failed to make A")?,
};
let b = match make_b(a) {
    Some(b) => b,
    _ => Err("Failed to make B")?,
};
let c = match make_c(b) {
    Some(c) => c,
    _ => Err("Failed to make C")?,
};
Ok(c)

or by "stuttering" an if let:

let a = if let Some(a) = make_a() {
    a
} else {
    Err("Failed to make A")?
};
let b = if let Some(b) = make_b(a) {
    b
} else {
    Err("Failed to make B")?
};
let c = if let Some(c) = make_c(b) {
    c
} else {
    Err("Failed to make C")?
};
Ok(c)

playground

Here is the same example using a refutable let:

let Some(a) = make_a() else {
    Err("Failed to make A")?
};
let Some(b) = make_b(a) else {
    Err("Failed to make B")?
};
let Some(c) = make_c(b) else {
    Err("Failed to make C")?
};
Ok(c)

This is actually implementable using macro_rules macros, though not without some difficulty. playground

Why?

The point of a refutable let is that you have some destructuring to do, and you want to handle the case where you cannot destructure by diverging from the function.

The simple desugar of let...else is the following transformation:

let PAT = EXPR else BLOCK;
// =>
let (bindings) = match EXPR {
    PAT => (bindings),
    _ => BLOCK: !,
}

where BLOCK: ! is type ascription. The ascribed ! type makes it such that BLOCK needs to diverge (this effectively means return, break or continue). (bindings) here is a tuple of all assigned bindings in the pattern, so that they can be moved out of the pattern and into the containing scope.

You can hopefully see that this pattern reduces the required stuttering in using a match or a let = if let for this pattern of early-return to handle errors locally. More key, however, is that this enforces the diverge. If you write a match or let = if let or unwrap_or_else or anything other than a ?, then the error handling branch could instead be a default value branch. Requiring the diverge at a language level increases the guarantees that a reader has when reading the code.

Problems and alternate syntaxes

Consider parsing the following:

let foo = if bar { baz() } else { quux() };

// Option 1:
let foo = 
    (if bar { 
        baz()
    } else {
        quux()
    });

// Option 2:
let foo = (if bar { baz() })
else { quux() };

The second is actually a vailid parse option if baz() is of type (). if COND { () } is valid in expr position and has type (). playground

Unfortunately, this ambiguity means that if PAT = EXPR else is not a possible unambiguous syntax; there is a reason else isn't in the follow set for expr.

Other proposed syntaxes:

<keyword> let PAT = EXPR else BLOCK

Suffers from the same ambiguity.

if !let PAT = EXPR BLOCK

Not ambiguous, but suffers from overloading if let, which doesn't put bindings into the scope that contains it.

<keyword> let PAT = EXPR BLOCK

Unambiguous, but requires a new keyword. Keyword possibilities include unless.

Recently

Two RFCs recently popped up that relate to this are #2221 Guard Clause Flow Typing and #2260 if- and while- let chains.

The former is looking to get the same functionality from flow typing, and the author seems to not consider let...else as being a valid "guard". I'll not say more, lest I assert something that isn't true.

The latter looks to allow chaining if let to reduce nesting. Though this doesn't seem direclty related, it was mentioned often that having a refutable let would much reduce the necessity of being able to chain if let together at one block level.

Looking forward to #Rust2018

Unless I've missed some glorious obvious-in-retrospect syntax, if !let PAT = EXPR BLOCK seems to be the only no-new-keyword-viable solution to the refutable let. Probably, this will end up being the syntax to use, and while maybe alien now, it might become as second nature as if let is now.

I can introduce a new RFC proposing using this syntax again, and detailing the problems with the other syntaxes. Maybe there the design can be fully, properly 🚲 :shed: (you pick the emoji :slight_smile:).

For the rest of Rust in 2018, I agree with much of the other #Rust2018 posts. Rust would probably be best served by a tick/tock cycle, where this year is spent on paying down stabilization debt. Many great features are just around the corner and just need that final push on design/implementation work.

This is not to say nothing new should happen; WebAssembly work should continue, the RFC machine should continue moving (though we shouldn't tell people to go submit ideas as rapidly as happened before the impl period cutoff). Stabilizing key tools, landing the impl period features, and (re)clarifying stability. Some way to endorse crates as high quality, ready-for-production libraries. Async/await/generators.

These are all great things which have been started. Let's move them towards finished together!

Oh, and my never-gonna-happen breakage whishlist: make all of the Iterator fn return impl Iterator instead of concrete types. impl Trait all of the things.

UPDATE to above: u/QuietMisdreavus pointed out the flaw with this:

This is actually a loss of information in many cases. Several of the Iterator wrappers also conditionally implement DoubleEndedIterator, ExactSizeIterator, FusedIterator, etc, based on their contained type. As far as i know, there's no way to represent that in impl Trait syntax.

Having realized the error of my ways, this is no longer a choice I would make.

DEV Community: Crystal Durham

dyn* doesn't need to be special

Dynamically Aligned Types?

String interners in Rust

std::string::String

So what?

What if it's not best-case?

So what? (again)

In conclusion

One weekend later...

"try fn" without special-casing Result

Lossless Syntax Trees

Related Reading

What is a Lexer, Anyway?

Related Reading

Conformance Testing in Rust

Crafting IDE-Ready Compilers

Related Reading

Rust Must-Know Crates

Cargo Plugins

Derives

Meta-programming (macros)

Testing

Other Libraries

On "Async Streams" in Rust

Step 1: What is a Stream?

Step 2: How do we use a Stream?

Function

Iterator

Future

Stream

Step 3: What Not

Step 4: Possibilities

Step 5: Conclusions

Great Rust CI

Install local tools.

Create your project!

Set up CI

Testing rustfmt and clippy

Using cargo-travis

Further extensions

Refutable Let and Rust in 2018

A motivating example

Why?

Problems and alternate syntaxes

Recently

Looking forward to #Rust2018

`std::string::String`

Step 1: What is a `Stream`?

Step 2: How do we use a `Stream`?