Generic Variables: simple implicity context passing

language design
1

Hello everyone

I have an idea for a new language feature to solve the problem of types that depend on runtime context to be meaningful. I also made a post about this on Zulip [1], but it isn't getting much traction so I want to share the idea here as well to get more feedback, and check if there was something obvious (or subtle) that I missed.

To avoid restating the problem and bloating this post, check out @tmandry excellent explainer on the issues that arrise when using types that depend on runtime context, and his solutions to them [2].

There is seemingly quite a lot of prior disscussion around this issue, but everyone seems to have differing ideas about just how exactly runtime variable data should influence how types and functions work, if at all [3], [4].

Of cause, I have my own solution. I have thought about it a lot, so to explain its intricacies properly, I needed more words then is allowed for a single post. It's not complicated, just a tough concept to explain without introducing it in small peices seperated by examples. You can read the full explanation (as a pdf) :backhand_index_pointing_right: here, what follows is a high level summery of the idea.

Summary

My solution to this problem is to extend the type system to include a new kind of generic, generic variables. Generic variables would allow types to depend on runtime variables without duplicating references to those variables across every instance of the type or explicitly passing references to them as arguments to all its functions/methods. References to generic variables are implicitly passed to all methods on types that use those variables, making them in scope for the method body. Generic variables are simple in their construction, and work seemlessly with methods, traits, lifetimes, and generic code.

To support this I also propose introducing a new kind of variable whose name can't be shadowed so it can be used in type signature as a concrete subsitution for a generic variable.

2

I've been working on what is essentially this proposal, which I came up with independently (and other people have come up with very similar things too). My early version of it is in this blog post. There's certainly room for improvement for the syntax (my placeholder syntax there is pretty ugly and probably a more ergonomic syntax should be selected before stablising it), but getting the semantics right is hard enough as it is.

I do think that something like this is extremely important; basically every Rust program I've ever written would benefit from it (and the lack of this sort of feature in Rust is actually making me seriously consider changing to a different language). In particular, Rust would greatly benefit from the ability to statically prove that programs cannot panic (as this would guarantee the absence of certain types of bugs, just like the memory safety does), but there are lots of situations where you need a type system feature like this to prove the absence of panics. As you mention, allocators are also a significant use case (programs are most efficient if they use special-purpose local allocators for just about everything, but you need a feature like this to be able to write code using such allocators without memory bloat and without unsafe).

There are a few significant obstacles. As you mentioned in your post (and I mentioned in mine), one of them is dyn. There are some subtle requirements for mixing dyn with this sort of generic to even be sound. (Notably, the variable has to be Sync (assuming that the type of the dyn references it rather than copying a value); this is because existing unsafe code, including in the standard library, assumes that it is sound to send a lifetime from one thread to another, in the sense of "if you have a reference to a Sync value with lifetime 'a on thread 1 you can reborrow it as a reference to a Sync value with lifetime 'a on thread 2", but this would not be true if you could create a non-Sync generic variable.) Actually implementing such a dyn is also nontrivial, because the dyn metadata ends up changing in size as you add more of these generics into it; there is a fairly simple solution by allocating memory, and a much more complicated solution that involves a whole-program analysis, neither of which is really ideal. (All this said, I consider this feature important enough that I would rather use a Rust without dyn rather than a Rust without this feature.)

Another problem is related to how the type captures the variable (which I don't think you mentioned in your proposal?). Capturing it by shared reference is by far the simplest case: it gives you useful guarantees (that the captured variable won't change in ways other than would be possible through a shared reference), it doesn't put a significant burden on the type checker because shared references are Copy, and it is powerful enough to do a lot of useful things. There have been various suggestions by other people to capture it in other ways (e.g. I was experimenting with allowing captures by mutable reference), but they're both harder to type-check than they look and less useful than they look. (In particular, if you have a mutable reference to something you can swap that thing out, so you end up with no useful guarantees from the type system. You end up being able to implement Cell in safe code, but it isn't useful for implementing anything other than cells.) As such, I would definitely recommend sticking with shared-reference capture, at least initially.

I'm also interested in the theoretical basis, and relationship to other features. Lifetimes are a special case of this feature (a lifetime 'a is equivalent to a variable of type () captured in a generic, except that lifetimes support variance, and for simplicity, variables captured in generics are generally taken not to). It's been commonly proposed to let people pass in their own trait implementations to generic functions (i.e. calling a fn foo<T: Trait>(&T) with a T that doesn't actually implement Trait, by providing an implementation of Trait for T in a generic-like way); I currently believe that that is equivalent to this feature (by providing an implementation that captures a variable as though it were an associated constant), and it can also be used to implement lifetimes (which would make sense if it's equivalent to this feature).

Some existing work, for people interested in reading more (and as a list of references that may be useful for any eventual RFC):

For Rust:

Prior art in other languages:

Other related posts:

3

I'm surprised there no mention of dependent types in neither this post nor in the blog post. They are the first concept I would think of when proposing to allow generic parameters to depend on variables.

4 Likes
4

I'm aware of dependent types (in fact I used to work with a co-worker who was an expert in them, and picked up some dependent types knowledge indirectly like that), but a full dependent-types system isn't at all reasonable as something to add to Rust (they are very complicated both to implement and to work with), and are also much more powerful than is necessary to solve the problems discussed in this thread.

I was planning to mention them if I ever came up with an RFC, but only along the lines of "this is sort-of like dependent types, but much simpler and with only a fraction of the mathematical problems".

1 Like
5

The auto traits, including Sync, would interact with generic variables like have a PhantomData<(&'x0 X0...&'xn XN)> as part of the type, where for the generic variable 0..N, X0..XN are the types of those generic variables, and 'x0..'xn are their lifetimes. So if the generic variables are not Sync, then neither would the type using them be.

Implimenting dyn is non-trivial, and there are trade offs to be made with the way dyn is handled. But I have already thought about it and have a solution. Maybe the not the best solution, but it shows this is possible: We could monomorphise each vtable for each function with generic variables. This allows passing the generic variables through registers and is more flexible in terms of the ABI then some of more dynamic options I've considered. We can point to this monomorphised vtable depending on which function we are in when the dyn pointer is created. This has the issue of some binary bloat and increased compile times, but means the dyn pointer can remaing its current size.

I've got other ideas as well, the design space is huge and there's so many possible solutions at least a couple of them must be good enough.

In my conception of the feature, it's interior mutability/immutability only. As such, capturing works in the obvious way. We could extend the feature in the future to allow mutability of some kind, but I really struggle to imagine why that would be useful, you might as well just store the mutable reference directly on the type, since there can only be one at a time.

6

This probably isn't sound because you can call a method that can name a type without having an instance of that type. For example, FnOnce::call_once() can create a value out of nothing (and is dyn-compatible). This means that you can take a FnOnce which outputs a T that captures a non-Sync variable, send that FnOnce to a different thread, and call it; inside the body of the FnOnce you would probably be able to access the variable because it's mentioned in the type, but you're now accessing it from the wrong thread. The FnOnce can be Sync even if its return type isn't.

I think it's possible that there might be some sort of variance-like analysis that you could use to exclude such cases, but I'm not sure, and it would likely be extremely subtle and hard to get right.

7

But if the variable is non-Sync, and it is captured by reference in the FnOnce, then the FnOnce won't be Send, so you could never send it to a different thread. Because T captures the variable, so does the closure. The only way that wouldn't happen would be if you put T as the return type, but the closure just immediatley calls unreachable! or something. In that case it doesn't matter because the reference is never read from. But in my mental model, the whole system is based soley on type signitures, so even in that case the FnOnce would get conservitively label as non-Send.

8

I'm thinking about something like this:

struct Creator<T: Default + Debug>(PhantomData<fn() -> T>);
impl<T: Default + Debug> FnOnce() for Creator<T> {
    type Output = ();
    extern "rust_call" fn call_once(self) { dbg!(<T as Default>::default()); }
}

pub fn convert_creator<T: Default + Debug>() -> Box<dyn FnOnce + Send> {
    Box::new(Creator::<T>(PhantomData))
}

In current Rust, Creator is unconditionally Sync and Send, regardless of what T is. So convert_creator typechecks in current Rust, and you cannot choose for it to not typecheck without breaking backwards compatibility. (If I had used a FnOnce-like trait that could be implemented stably rather than FnOnce itself, you could write the above code in current stable Rust.)

Now, if you choose T to be a type that captures a non-Sync variable, you get undefined behaviour (because you could send the resulting Box<dyn FnOnce + Send> to another thread and that could potentially lead to trying to debug-print two Ts simultaneously from different threads, that had captured the same non-Sync variable).

9

(And indeed there is such a T: Rc<u32>. || Rc::<u32>::default() is Send and Sync, its return value is not. That doesn't quite seem to include the "capture" step though.)

10

To solve this, there would need to be a new auto trait FnSend, which is applied to a type when all of its generic variables impliment Sync. Now, fn() -> T only impliments Send and Sync if T impliments FnSend.

To keep this backwards compatible, in the same addition this rule is added, all generic and trait delcerations in all previous additions now have an implicit FnSend bound added by the compiler, this bound could be relaxed with ?FnSend. In a future addition, after a sufficant portion of the ecosystem has migrated, the default FnSend bound could be removed in all future additions, and a lint added to warn against using ?FnSend.

FnSend could even be added before the feature itself to give ample time to migrate.

11

Although a new autotrait would work (although the autotrait should probably just be "captures no variables"), there's a pretty high bar for adding those. I suspect it would be easier to just require captured variables to be Sync.

(My experiments in provisional implementations of this suggest that Sync is the only autotrait that is problematic. This is because the soundness requirements on variables captured in types are essentially the same as those on global variables, as both support shared-reference-only access from potentially arbitrary locations in the code; global variables are required to be Sync, so variables captured in types also have to be, but the only other autotrait they require is Sized which is not a problem if you're capturing via shared reference as shared references have a known size.)

12

Is this another formulation of implicit arguments?

Anyway you need to show at least pseudocode, and be more specific on details

13

This feels like a hack to work around the fact that you would like to treat these generic variables like the current generic arguments. IMO they are different, with different semantics, and thus should be treated differently. For example if you intend to implement these by storing a copy/reference of the generic variable on the type, then you should treat that as a hidden field and have it behave like other fields, including affecting Send/Sync.

1 Like
14

It's basically a combination of implicit arguments, and a type-system feature that allows you to prove that the methods of a given type will always be given the same implicit arguments.

One of the most important motivations is with respect to custom allocators that are not zero size: it's inefficient to store a copy of the allocator in each of your custom-allocator Boxes (because that makes all the Boxes bigger and may end up negating the performance gains you hoped to get from a custom allocator), so you want to pass them in as implicit arguments. However, you also need to ensure that you're providing the same implicit argument to Box::drop as you did to Box::new, otherwise you end up deallocating the box using the wrong allocator (which is UB in current Rust).

There are plenty of other use cases (I listed some in the blog post I linked above) ā€“ basically every Rust program I've ever written would benefit from this combination of implicit arguments and a compile-time proof that you get the same argument every time.

1 Like
15

This implementation technique gets halfway there, but precludes implementing traits like Default. The aim is to store a reference to the value on the type itself, not on values of the type (so that, e.g., T::default() can read the value from T).

The hidden-field approach is sufficient in cases where all the type's methods have a receiver that's guaranteed to be a valid value of the type. That can handle most of the use cases, but not all of them. (It's also almost implementable as a library, representing the hidden field as a ZST, and I've spent a couple of years working on such a library on and off ā€“ but my library approach doesn't work in recursive or concurrent contexts, and I haven't released it because I find it hard to be sufficiently confident that it's sound. Part of the problem is that current unsafe Rust is incredibly bad at creating ZSTs that act like references because they need to have provenance, but there is nowhere to store it. Rust's current semantics is only capable of storing strict provenance in things which are at least a pointer wide, but a ZST is too small. Alternatively, you could use exposed provenance, but LLVM doesn't implement exposed provenance correctly at the moment and there's no point in writing theoretically correct code if the compiler is incapable of compiling it correctly.)

16

It is a bit of a big hammer, but couldn't you combine exposed provenance with noop inline assembly blocks as optimisation barriers (story: the assembly blocks read/write the pointers from/to somewhere that the compiler can't track, and thus they trick escape analysis).

17

I was wondering about that. A story of "this writes the pointer to a global variable, then unexposing the provenance reads the pointer" is valid both under Rust's inline asm rules (as that is a thing you could do in Rust), and would work for LLVM. The problem is that, in order to get the story correct, you would need to mark the asm block as "touches memory" and that seems likely to massively destroy optimisation quality because LLVM would assume it might be, e.g., changing the value of local variables (which aren't noalias, only function parameters are).

Now I'm wondering if there's some alternative story that might work (e.g. sending the address over a network and reading it back from there) which would avoid needing to touch memory, but I'm not super-convinced that that would be valid. (LLVM might decide that you can't store a provenance anywhere other than memory or general-purpose registers.)

18

Maybe you could set up a dummy extern variable and tell llvm that it specifically reads and writes to that variable, rather than memory in general.

There could also be a story based on (non-network) syscalls I suspect. You could say that the pointer is transferred to the kernel and then later returned from it (e.g. buffers in io-uring works like this as I understand it).

19

A type is not a valid place where to store a value since types don't exist at runtime.

You could argue that instead of storing the reference on the values of the type they are passed to all methods of that type, but this is obviously different and has other implications (e.g. on when you can convert a function item to a function pointer).

20

The implementation that most people who propose something like this initially have in mind is usually to pass the variable to all methods/functions whose generic parameters mention the type in question (including indirectly). (This is why dyn causes such trouble: it's the only way you can have access to values/methods of an unnamed type without having the type in your generics.)

I think a better viewpoint is to consider the variables to act like an invariant lifetime, and to pass the variable to all methods/functions whose generic parameters mention the lifetime in question (again, including indirectly). This handles dyn correctly from the type system point of view, because dyn also has a lifetime (although the actual implementation is nontrivial, as it is hard to produce an appropriate vtable). The problem then becomes "in current Rust, a dyn Send + 'a is unconditionally safe to send between threads", on the basis that the Send is safe to send, but if you are treating this sort of reference as using the same rules as lifetimes, the 'a can itself be unsafe to send. Thus, captured variables have to be Sync so that their lifetimes are always safely sendable.

This is in general a complex topic to explain (which is why I've spent over two years on a proposal for this without actually RFCing it ā€“ it's been taking a long time to pin down the details, and a long time to work out how to explain them in a way that isn't too difficult to understand). The intuitive explanation of it, and the most commonly proposed, is "let types take captures of variables as generic parameters", but the resulting captures are extremely similar in how they behave to lifetimes, to the extent that you can model current Rust lifetimes as being a sort of generalised lifetime with type () and variable-capturing generic parameters as being the same sort of generalised lifetime with type &T. (From this point of view, type of a generalised lifetime needs to be Copy + Sync + Send to avoid breaking the borrow checker, thus the type T of a variable it captures needs to be Sync.)

2 Likes