Baby Steps

A blog about programming, and tiny ways to improve it.

Virtual Structs Part 2: Classes Strike Back

This is the second post summarizing my current thoughts about ideas related to “virtual structs”. In the last post, I described how, when coding C++, I find myself missing Rust’s enum type. In this post, I want to turn it around. I’m going to describe why the class model can be great, and something that’s actually kind of missing from Rust. In the next post, I’ll talk about how I think we can get the best of both worlds for Rust. As in the first post, I’m focusing here primarily on the data layout side of the equation; I’ll discuss virtual dispatch afterwards.

Virtual Structs Part 1: Where Rust’s Enum Shines

One priority for Rust after 1.0 is going to be incorporating some kind of support for “efficient inheritance” or “virtual structs”. In order to motivate and explain this design, I am writing a series of blog posts examining how Rust’s current abstractions compare with those found in other languages.

The way I see it, the topic of “virtual structs” has always had two somewhat orthogonal components to it. The first component is a question of how we can generalize and extend Rust enums to cover more scenarios. The second component is integrating virtual dispatch into this picture.

I am going to start the series by focusing on the question of extending enums. This first post will cover some of the strengths of the current Rust enum design; the next post, which I’ll publish later this week, will describe some of the advantages of a more “class-based” approach. Then I’ll discuss how we can bring those two worlds together. After that, I will turn to virtual dispatch, impls, and matching, and show how they interact.

A Few More Remarks on Reference-counting and Leaks

So there has been a lot of really interesting discussion in response to my blog post. I wanted to highlight some of the comments I’ve seen, because I think they raise good points that I failed to address in the blog post itself. My comments here are lightly edited versions of what I wrote elsewhere.

Isn’t the problem with objects and leak-safe types more general?

Reem writes:

I posit that this is in fact a problem with trait objects, not a problem with Leak; the exact same flaw pointed about in the blog post already applies to the existing OIBITs, Send, Sync, and Reflect. The decision of which OIBITs to include on any trait object is already a difficult one, and is a large reason why std strives to avoid trait objects as part of public types.

I agree with him that the problems I described around Leak and objects apply equally to Send (and, in fact, I said so in my post), but I don’t think this is something we’ll be able to solve later on, as he suggests. I think we are working with something of a fundamental tension. Specifically, objects are all about encapsulation. That is, they completely hide the type you are working with, even from the compiler. This is what makes them useful: without them, Rust just plain wouldn’t work, since you couldn’t (e.g.) have a vector of closures. But, in order to gain that flexibility, you have to state your requirements up front. The compiler can’t figure them out automatically, because it doesn’t (and shouldn’t) know the types involved.

So, given that objects are here to stay, the question is whether adding a marker trait like Leak is a problem, given that we already have Send. I think the answer is yes; basically, because we can’t expect object types to be analyzed statically, we should do our best to minimize the number of fundamental splits people have to work with. Thread safety is pretty fundamental. I don’t think Leak makes the cut. (I said some of the reasons in conclusion of my previous blog post, but I have a few more in the questions below.)

Could we just remove Rc and only have RcScoped? Would that solve the problem?

Original question.

Certainly you could remove Rc in favor of RcScoped. Similarly, you could have only Arc and not Rc. But you don’t want to because you are basically failing to take advantage of extra constraints. If we only had RcScoped, for example, then creating an Rc always requires taking some scoped as argument – you can have a global constant for 'static data, but it’s still the case that generic abstractions have to take in this scope as argument. Moreover, there is a runtime cost to maintaining the extra linked list that will thread through all Rc abstractions (and the Rc structs get bigger, as well). So, yes, this avoids the “split” I talked about, but it does it by pushing the worst case on all users.

Still, I admit to feeling torn on this point. What pushes me over the edge, I think, is that simple reference counting of the kind we are doing now is a pretty fundamental thing. You find it in all kinds of systems (Objective C, COM, etc). This means that if we require that safe Rust cannot leak, then you cannot safely integrate borrowed data with those systems. I think it’s better to just use closures in Rust code – particularly since, as annodomini points out on Reddit, there are other kinds of cases where RAII is a poor fit for cleanup.

Could a proper GC solve this? Is reference counting really worth it?

Original question.

It’ll depend on the precise design, but tracing GC most definitely is not a magic bullet. If anything, the problem around leaks is somewhat worse: GC’s don’t give any kind of guarantee about when the destructor bans. So we either have to ban GC’d data from having destructors or ban it from having borrowed pointers; either of those implies a bound very similar to Leak or 'static. Hence I think that GC will never be a “fundamental building block” for abstractions in the way that Rc/Arc can be. This is sad, but perhaps inevitable: GC inherently requires a runtime as well, which already limits its reusability.

On Reference-counting and Leaks

What’s a 1.0 release without a little drama? Recently, we discovered that there was an oversight in one of the standard library APIs that we had intended to stabilize. In particular, we recently added an API for scoped threads – that is, child threads which have access to the stack frame of their parent thread.

The flaw came about because, when designing the scoped threads API, we failed to consider the impact of resource leaks. Rust’s ownership model makes it somewhat hard to leak data, but not impossible. In particular, using reference-counted data, you can construct a cycle in the heap, in which case the components of that cycle may never be freed.

Some commenters online have taken this problem with the scoped threads API to mean that Rust’s type system was fundamentally flawed. This is not the case: Rust’s guarantee that safe code is memory safe is as true as it ever was. The problem was really specific to the scoped threads API, which was making flawed assumptions; this API has been marked unstable, and there is an RFC proposing a safe alternative.

That said, there is an interesting, more fundamental question at play here. We long ago decided that, to make reference-counting practical, we had to accept resource leaks as a possibility. But some recent proposals have suggested that we should place limits on the Rc type to avoid some kinds of reference leaks. These limits would make the original scoped threads API safe. However, these changes come at a pretty steep price in composability: they effectively force a deep distinction between “leakable” and “non-leakable” data, which winds up affecting all levels of the system.

This post is my attempt to digest the situation and lay out my current thinking. For those of you don’t want to read this entire post (and I can’t blame you, it’s long), let me just copy the most salient paragraph from my conclusion:

This is certainly a subtle issue, and one where reasonable folk can disagree. In the process of drafting (and redrafting…) this post, my own opinion has shifted back and forth as well. But ultimately I have landed where I started: the danger and pain of bifurcating the space of types far outweighs the loss of this particular RAII idiom.

All right, for those of you who want to continue, this post is divided into three sections:

  1. Section 1 explains the problem and gives some historical background.
  2. Section 2 explains the “status quo”.
  3. Section 3 covers the proposed changes to the reference-counted type and discusses the tradeoffs involved there.

Modeling Graphs in Rust Using Vector Indices

After reading nrc’s blog post about graphs, I felt inspired to write up an alternative way to code graphs in Rust, based on vectors and indicates. This encoding has certain advantages over using Rc and RefCell; in particular, I think it’s a closer fit to Rust’s ownership model. (Of course, it has disadvantages too.)

I’m going to describe a simplified version of the strategy that rustc uses internally. The actual code in Rustc is written in a somewhat dated “Rust dialect”. I’ve also put the sources to this blog post in their own GitHub repository. At some point, presumably when I come up with a snazzy name, I’ll probably put an extended version of this library up on Anyway, the code I cover in this blog post is pared down to the bare essentials, and so it doesn’t support (e.g.) enumerating incoming edges to a node, or attach arbitrary data to nodes/edges, etc. It would be easy to extend it to support that sort of thing, however.

Little Orphan Impls

We’ve recently been doing a lot of work on Rust’s orphan rules, which are an important part of our system for guaranteeing trait coherence. The idea of trait coherence is that, given a trait and some set of types for its type parameters, there should be exactly one impl that applies. So if we think of the trait Show, we want to guarantee that if we have a trait reference like MyType : Show, we can uniquely identify a particular impl. (The alternative to coherence is to have some way for users to identify which impls are in scope at any time. It has its own complications; if you’re curious for more background on why we use coherence, you might find this rust-dev thread from a while back to be interesting reading.)

The role of the orphan rules in particular is basically to prevent you from implementing external traits for external types. So continuing our simple example of Show, if you are defining your own library, you could not implement Show for Vec<T>, because both Show and Vec are defined in the standard library. But you can implement Show for MyType, because you defined MyType. However, if you define your own trait MyTrait, then you can implement MyTrait for any type you like, including external types like Vec<T>. To this end, the orphan rule intuitively says “either the trait must be local or the self-type must be local”.

More precisely, the orphan rules are targeting the case of two “cousin” crates. By cousins I mean that the crates share a common ancestor (i.e., they link to a common library crate). This would be libstd, if nothing else. That ancestor defines some trait. Both of the crates are implementing this common trait using their own local types (and possibly types from ancestor crates, which may or may not be in common). But neither crate is an ancestor of the other: if they were, the problem is much easier, because the descendant crate can see the impls from the ancestor crate.

When we extended the trait system to support multidispatch, I confess that I originally didn’t give the orphan rules much thought. It seemed like it would be straightforward to adapt them. Boy was I wrong! (And, I think, our original rules were kind of unsound to begin with.)

The purpose of this post is to lay out the current state of my thinking on these rules. It sketches out a number of variations and possible rules and tries to elaborate on the limitations of each one. It is intended to serve as the seed for a discussion in the Rust discusstion forums.

Purging Proc

The so-called “unboxed closure” implementation in Rust has reached the point where it is time to start using it in the standard library. As a starting point, I have a pull request that removes proc from the language. I started on this because I thought it’d be easier than replacing closures, but it turns out that there are a few subtle points to this transition.

I am writing this blog post to explain what changes are in store and give guidance on how people can port existing code to stop using proc. This post is basically targeted Rust devs who want to adapt existing code, though it also covers the closure design in general.

To some extent, the advice in this post is a snapshot of the current Rust master. Some of it is specifically targeting temporary limitations in the compiler that we aim to lift by 1.0 or shortly thereafter. I have tried to mention when that is the case.

Allocators in Rust

There has been a lot of discussion lately about Rust’s allocator story, and in particular our relationship to jemalloc. I’ve been trying to catch up, and I wanted to try and summarize my understanding and explain for others what is going on. I am trying to be as factually precise in this post as possible. If you see a factual error, please do not hesitate to let me know.

Multi- and Conditional Dispatch in Traits

I’ve been working on a branch that implements both multidispatch (selecting the impl for a trait based on more than one input type) and conditional dispatch (selecting the impl for a trait based on where clauses). I wound up taking a direction that is slightly different from what is described in the trait reform RFC, and I wanted to take a chance to explain what I did and why. The main difference is that in the branch we move away from the crate concatenability property in exchange for better inference and less complexity.

Attribute and Macro Syntax

A few weeks back pcwalton introduced a PR that aimed to move the attribute and macro syntax to use a leading @ sigil. This means that one would write macros like:

@format("SomeString: {}", 22)


@vec[1, 2, 3]

One would write attributes in the same way:

struct SomeStruct {

fn foo() { ... }

This proposal was controversial. This debate has been sitting for a week or so. I spent some time last week reading every single comment and I wanted to lay out my current thoughts.

Why change it?

There were basically two motivations for introducing the change.

Free the bang. The first was to “free up” the ! sign. The initial motivation was aturon’s error-handling RFC, but I think that even if we decide not to act on that specific proposal, it’s still worth trying to reserve ! and ? for something related to error-handling. We are very limited in the set of characters we can realistically use for syntactic sugar, and ! and ? are valuable “ASCII real-estate”.

Part of the reason for this is that ! has a long history of being the sigil one uses to indicate something dangerous or surprising. Basically, something you should pay extra attention to. This is partly why we chose it for macros, but in truth macros are not dangerous. They can be mildly surprising, in that they don’t necessarily act like regular syntax, but having a distinguished macro invocation syntax already serves the job of alerting you to that possibility. Once you know what a macro does, it ought to just fade into the background.

Decorators and macros. Another strong motivation for me is that I think attributes and macros are two sides of the same coin and thus should use similar syntax. Perhaps the most popular attribute – deriving – is literally nothing more than a macro. The only difference is that its “input” is the type definition to which it is attached (there are some differences in the implementation side presently – e.g., deriving is based off the AST – but as I discuss below I’d like to erase that distiction eventually). That said, right now attributes and macros live in rather distinct worlds, so I think a lot of people view this claim with skepticism. So allow me to expand on what I mean.

How attributes and macros ought to move closer together

Right now attributes and macros are quite distinct, but looking forward I see them moving much closer together over time. Here are some of the various ways.

Attributes taking token trees. Right now attribute syntax is kind of specialized. Eventually I think we’ll want to generalize it so that attributes can take arbitrary token trees as arguments, much like macros operate on token trees (if you’re not familiar with token trees, see the appendix). Using token trees would allow more complex arguments to deriving and other decorators. For example, it’d be great to be able to say:


where EncoderTypeName<foo> is the name of the specific encoder that you wish to derive an impl for, vs today, where deriving always creates an encodabe impl that works for all encoders. (See Issue #3740 for more details.) Token trees seem like the obvious syntax to permit here.

Macros in decorator position. Eventually, I’d like it to be possible for any macro to be attached to an item definition as a decorator. The basic idea is that @foo(abc) struct Bar { ... } would be syntactic sugar for (something like) @foo((abc), (struct Bar { ... })) (presuming foo is a macro).

An aside: it occurs to me that to make this possible before 1.0 as I envisioned it, we’ll need to at least reserve macro names so they cannot be used as attributes. It might also be better to have macros declare whether or not they want to be usable as decorators, just so we can give better error messages. This has some bearing on the “disadvantages” of the @ syntax discussed below, as well.

Using macros in decorator position would be useful for those cases where the macro is conceptually “modifying” a base fn definition. There are numerous examples: memoization, some kind of generator expansion, more complex variations on deriving or pretty-printing, and so on. A specific example from the past was the externfn! wrapper that would both declare an extern "C" function and some sort of Rust wrapper (I don’t recall precisely why). It was used roughly like so:

externfn! {
    fn foo(...) { ... }

Clearly, this would be nicer if one wrote it as:

fn foo(...) { ... }

Token trees as the interface to rule them all. Although the idea of permitting macros to appear in attribute position seems to largely erase the distinction between today’s “decorators”, “syntax extensions”, and “macros”, there remains the niggly detail of the implementation. Let’s just look at deriving as an example: today, deriving is a transform from one AST node to some number of AST nodes. Basically it takes the AST node for a type definition and emits that same node back along with various nodes for auto-generated impls. This is completely different from a macro-rules macro, which operates only on token trees. The plan has always been to remove deriving out of the compiler proper and make it “just another” syntax extension that happens to be defined in the standard library (the same applies to other standard macros like format and so on).

In order to move deriving out of the compiler, though, the interface will have to change from ASTs to token trees. There are two reasons for this. The first is that we are simply not prepared to standardize the Rust compiler’s AST in any public way (and have no near term plans to do so). The second is that ASTs are insufficiently general. We have syntax extensions to accept all kinds of inputs, not just Rust ASTs.

Note that syntax extensions, like deriving, that wish to accept Rust ASTs can easily use a Rust parser to parse the token tree they are given as input. This could be a cleaned up version of the libsyntax library that rustc itself uses, or a third-party parser module (think Esprima for JS). Using separate libraries is advantageous for many reasons. For one thing, it allows other styles of parser libraries to be created (including, for example, versions that support an extensible grammar). It also allows syntax extensions to pin to an older version of the library if necessary, allowing for more independent evolution of all the components involved.

What are the objections?

There were two big objections to the proposal:

  1. Macros using ! feels very lightweight, whereas @ feels more intrusive.
  2. There is an inherent ambiguity since @id() can serve as both an attribute and a macro.

The first point seems to be a matter of taste. I don’t find @ particularly heavyweight, and I think that choosing a suitable color for the emacs/vim modes will probably help quite a bit in making it unobtrusive. In constrast, I think that ! has a strong connotation of “dangerous” which seems inappropriate for most macros. But neither syntax seems particularly egregious: I think we’ll quickly get used to either one.

The second point regarding potential ambiguities is more interesting. The ambiguities are easy to resolve from a technical perpsective, but that does not mean that they won’t be confusing to users.

Parenthesized macro invocations

The first ambiguity is that @foo() can be interpreted as either an attribute or a macro invocation. The observation is that @foo() as a macro invocation should behave like existing syntax, which means that either it should behave like a method call (in a fn body) or a tuple struct (at the top-level). In both cases, it would have to be followed by a “terminator” token: either a ; or a closing delimeter (), ], and }). Therefore, we can simply peek at the next token to decide how to interpret @foo() when we see it.

I believe that, using this disambiguation rule, almost all existing code would continue to parse correctly if it were mass-converted to use @foo in place of the older syntax. The one exception is top-level macro invocations. Today it is common to write something like:

declaremethods!(foo, bar)

struct SomeUnrelatedStruct { ... }

where declaremethods! expands out to a set of method declarations or something similar.

If you just transliterate this to @, then the macro would be parsed as a decorator:

@declaremethods(foo, bar)

struct SomeUnrelatedStruct { ... }

Hence a semicolon would be required, or else {}:

@declaremethods(foo, bar);
struct SomeUnrelatedStruct { ... }

@declaremethods { foo, bar }
struct SomeUnrelatedStruct { ... }

Note that both of these are more consistent with our syntax in general: tuple structs, for example, are always followed by a ; to terminate them. (If you replace @declaremethods(foo, bar) with struct Struct1(foo, bar), then you can see what I mean.) However, today if you fail to include the semicolon, you get a parser error, whereas here you might get a surprising misapplication of the macro.

Macro invocations with braces, square or curly

Until recently, attributes could only be applied to items. However, recent RFCs have proposed extending attributes so that they can be applied to blocks and expressions. These RFCs introduce additional ambiguities for macro invocations based on [] and {}:

  • @foo{...} could be a macro invocation or an annotation @foo applied to the block {...},
  • @foo[...] could be a macro invocation or an annotation @foo applied to the expression [...].

These ambiguities can be resolved by requiring inner attributes for blocks and expressions. Hence, rather than @cold x + y, one would write (@!cold x) + y. I actually prefer this in general, because it makes the precedence clear.

OK, so what are the options?

Using @ for attributes is popular. It is the use with macros that is controversial. Therefore, how I see it, there are three things on the table:

  1. Use @foo for attributes, keep foo! for macros (status quo-ish).
  2. Use @foo for both attributes and macros (the proposal).
  3. Use @[foo] for attributes and @foo for macros (a compromise).

Option 1 is roughly the status quo, but moving from #[foo] to @foo for attributes (this seemed to be universally popular). The obvious downside is that we lose ! forever and we also miss an opportunity to unify attribute and macro syntax. We can still adopt the model where decorators and macros are interoperable, but it will be a little more strange, since they look very different.

The advantages of Option 2 are what I’ve been talking about this whole time. The most significant disadvantage is that adding a semicolon can change the interpretation of @foo() in a surprising way, particularly at the top-level.

Option 3 offers most of the advantages of Option 2, while retaining a clear syntactic distinction between attributes and macro usage. The main downside is that @deriving(Eq) and @inline follow the precedent of other languages more closely and arguably look cleaner than @[deriving(Eq)] and @[inline].

What to do?

Currently I personally lean towards options 2 or 3. I am not happy with Option 1 both because I think we should reserve ! and because I think we should move attributes and macros closer together, both in syntax and in deeper semantics.

Choosing between options 2 and 3 is difficult. It seems to boil down to whether you feel the potential ambiguities of @foo() outweigh the attractiveness of @inline vs @[inline]. I don’t personally have a strong feeling on this particular question. It’s hard to say how confusing the ambiguities will be in practice. I would be happier if placing or failing to place a semicolon at the right spot yielded a hard error.

So I guess I would summarize my current feeling as being happy with either Option 2, but with the proviso that it is an error to use a macro in decorator position unless it explicitly opts in, or Option 3, without that proviso. This seems to retain all the upsides and avoid the confusing ambiguities.

Appendix: A brief explanation of token trees

Token trees are the basis for our macro-rules macros. They are a variation on token streams in which tokens are basically uninterpreted except that matching delimeters ((), [], {}) are paired up. A macro-rules macro is then “just” a translation from a token tree to another token. This output token tree is then parsed as normal. Similarly, our parser is actually not defined over a stream of tokens but rather a token tree.

Our current implementation deviates from this ideal model in some respects. For one thing, macros take as input token trees with embedded asts, and the parser parses a stream of tokens with embedded token trees, rather than token trees themselves, but these details are not particularly relevant to this post. I also suspect we ought to move the implementation closer to the ideal model over time, but that’s the subject of another post.