Due to limitations in the borrow checker, this implies a 'static lifetime

2023-01-22

For the past six months or so I have been work­ing on finite-wasm, a pro­ject aimed at en­for­cing de­term­in­istic re­source lim­its (in time and space) in a runtime ag­nostic and Easy to Reason About way. This pro­ject pro­duces a spe­cific­a­tion (or rather ad­di­tions to the WebAssembly spe­cific­a­tion) de­tail­ing how these lim­its should be en­forced and ana­lyses im­ple­ment­ing the spe­cific­a­tion. Last week I fi­nally pub­lished the very first ver­sion of this code on crates.io, but did­n’t feel com­fort­able mak­ing the re­pos­it­ory pub­lic quite yet – I have a fair bit of im­prove­ments I want to make first. I’ll try to make a point of writ­ing more about this pro­ject at a later date, when the pro­ject is fully pub­lic.

That said, as I was work­ing on the im­prove­ments I en­countered a per­plex­ing lim­it­a­tion in rustc that mani­fests it­self as a note: due to cur­rent lim­it­a­tions in the bor­row check­er, this im­plies a 'static life­time dia­gnost­ic. It seemed great op­por­tun­ity for a stand-alone blog post, if not to doc­u­ment a pos­sible work­around, then to serve as a proof that even ex­per­i­enced Rust de­velopers aren’t im­mune to “fight­ing the bor­row checker” woes. But also be­cause this dia­gnostic mes­sage is quite opaque and is hardly doc­u­mented (I could only find this in­tern­als thread) and writ­ing my ex­per­i­ence down seemed pos­sibly use­ful to the next un­for­tu­nate soul to en­counter a sim­ilar prob­lem. Per­haps this might even in­form a change in rustc?

Fact­ory pat­tern for a no-­com­prom­ise API

In finite-wasm two in­de­pend­ent ana­lyses are provided: max_stack (space) and gas (time). The most straight­for­ward way to run them is to use the analyze func­tion, which will take the bin­ary en­cod­ing of a WebAssembly mod­ule, parse it and col­lect the mod­ule-­level struc­tures rel­ev­ant to the ana­lyses be­fore run­ning all of the ana­lyses on each of the func­tion defined within the mod­ule:

fn analyze(
    wasm: &[u8],
    stack_config: impl StackConfig,
    gas_config: impl GasConfig
) -> Result<Outcome> { ... }

This is as close as it can get to an ideal in­ter­face, but in its quest for ease-of-use, this func­tion also ends up mak­ing some opin­ion­ated choices on user’s be­half. What if they want just the gas ana­lysis and don’t care about the stack con­sump­tion? This in­ter­face provides no way to achieve this.

Ex­ecut­ing these ana­lyses con­di­tion­ally is by no means dif­fi­cult. A boolean ar­gu­ment could be ad­ded to con­trol ex­e­cu­tion of each ana­lys­is. Or, per­haps, each of the con­fig­ur­a­tion ar­gu­ments could have been an Option<_> to keep the num­ber of ar­gu­ments low and the in­ter­face more type-safe. These and sim­ilar straight­for­ward ap­proaches suf­fer from a com­mon prob­lem, though. They all in­tro­duce ad­di­tional runtime over­head, either by for­cing a branch or some dy­namic dis­patch. The ana­lysis loop can get quite hot, mean­ing this sort of forced runtime over­head would only serve to re­duce the over­all through­put in the com­mon case where both ana­lyses are run.

This is where the fact­ory pat­tern comes in. I could set up the con­fig­ur­a­tion types to act as a fact­ory for some ana­lysis type which would run ac­cord­ing to the con­struct­ing con­fig­ur­a­tion. At the same time I could also in­tro­duce a spe­cial NoConfig type that would man­u­fac­ture in­stances of an ana­lysis that does noth­ing at all. This could all be made to op­er­ate on stat­ic­ally known types and use static dis­patch, set­ting the com­piler up for re­moval of code per­tin­ent to the dis­abled ana­lys­is. When en­abled, the ana­lysis would also ex­ecute without any ad­di­tional over­head com­pared to the fact­ory-­free ap­proach! In finite-wasm ana­lyses’ con­texts are cre­ated for each in­di­vidual func­tion in a mod­ule, and hold a ref­er­ence to the con­fig­ur­a­tion and mod­ule-­level facts ana­lysis may need to refer to (e.g. what types are avail­able?) With that in mind, I ended up with the fol­low­ing defin­i­tion of the Factory trait:

trait Factory<'a> {
    type Analysis;
    fn manufacture(&'a self, state: &'a State) -> Self::Analysis;
}

// Given any user-defined `Config`, manufacture an effectful analysis
impl<'a, C: Config + 'a> Factory<'a> for C {
    type Analysis = Analysis<'a, C>;
    fn manufacture(&'a self, state: &'a State) -> Self::Analysis {
        Analysis { state, config: self )
    }
}

// No `Config` for this analysis, it won’t run
pub struct NoConfig;
impl<'a> Factory<'a> for NoConfig {
    type Analysis = NoAnalysis;
    fn manufacture(&'a self, _: &'a State) -> Self::Analysis {
        NoAnalysis
    }
}

With this new in­fra­struc­ture in place, ad­just­ing the run_analysis func­tion with a com­bin­a­tion of auto-­pi­lot, and com­piler dia­gnostics led me to the fol­low­ing func­tion with a gen­eric life­time:

// NOTE: For demonstrative purposes I simplified the example to
// just one kind of analysis
fn run_analysis<'a, F: Factory<'a> + 'a>(code: &[u8], f: F) {
    let state = State;
    for function in functions(code) {
        let _analysis = f.manufacture(&state);
        todo!("run analysis and collect results");
    }
}

This does­n’t work at all. The com­piler com­plains that neither f, nor state live long enough in this func­tion. I would­n’t be able to ex­plain what’s the deal with f, but state is quite easy to grok. Con­sider that a caller can call run_analysis::<'static, _>, sub­sti­tut­ing the 'a life­time with 'static. F be­comes Factory<'static> and Factory::<'static>::manufacture re­quires that its state ar­gu­ment is 'static' too. This is prov­ably not the case – state is only alive for the dur­a­tion of the run_analysis func­tion! But I di­gress.

Rust has a mech­an­ism – higher­-ranked trait bounds or HRTBs1 – to say that a trait bound must be valid for any life­time, let­ting the func­tion body op­er­ate on F with its de­sired life­time sub­sti­tu­tions, rather than giv­ing this con­trol to the caller of the func­tion. Re­mov­ing the 'a life­time gen­eric and ad­just­ing the F trait bound to use a HRTB yields:

fn run_analysis<F: for<'a> Factory<'a>>(code: &[u8], f: F) {
    let state = State;
    for function in functions(code) {
        let _analysis = f.manufacture(&state);
        todo!("run analysis and collect results");
    }
}

And in­deed, this works swim­mingly! The ana­lyses are stat­ic­ally in­stan­ti­ated, and get full op­tim­iz­a­tions for this some­what hot code. The API is still really con­veni­ent, flex­ible and ex­tens­ible. If I had to come up with a down­side, it is the need for some ex­tra doc­u­ment­a­tion to guide users to­wards im­ple­ment­ing the Config trait rather than Factory, but that’s a fee I’m will­ing to stom­ach.

Type Eras­ure? Dy­namic Dis­patch? Ref­er­ences?

The in­volved user­-­fa­cing traits, es­pe­cially Config, are us­able as dy­namic ob­jects. If there is any reason for the user to re­sort to type erased con­fig­ur­a­tions, even at the ex­pense of slower ex­e­cu­tion, who am I to stand in their way? Lack of an im­ple­ment­a­tion al­low­ing use of a &impl Config + ?Sized as reg­u­lar Config is a block­er, but that’s an easy fix:

impl<P: Config + ?Sized> Config for &P {}

With type erased Configs as a sup­por­ted use-case, it would­n’t be a ter­rible idea to write a test down too:

     // Somewhere in the code…
+    run_analysis(b"\0wasm", &my_config as &dyn Config);

Done, and done. Does it work? Of course it does… not?! rustc’s eval­u­ation of my new test case is as fol­lows:

error[E0597]: `my_config` does not live long enough
  --> src/main.rs:55:29
   |
55 |     run_analysis(b"\0wasm", &my_config as &dyn Config);
   |     ------------------------^^^^^^^^^^----------------
   |     |                       |
   |     |                       borrowed value does not live long enough
   |     argument requires that `my_config` is borrowed for `'static`
56 | }
   |  - `my_config` dropped here while still borrowed
   |
note: due to current limitations in the borrow checker, this implies a `'static` lifetime
  --> src/main.rs:41:24
   |
41 | pub fn run_analysis<F: for<'a> Factory<'a>>(code: &[u8], f: F) {
   |                        ^^^^^^^^^^^^^^^^^^^

“Be­trayal with a cap­ital B! There’s no way rustc would slight me like this!” I thought. I threw a fit (and all solu­tions I could think of) at it; I pleaded, cried and did puppy eyes. rustc was hav­ing none of it.

At that point a de­pressed my­self figured it was a great time to take my dog out for a walk. Walk­ing is a nice, re­lax­ing activ­ity, it helps with main­tain­ing the bare min­imum phys­ical activ­ity levels, and for whatever reason the only time I come up with good ideas is dur­ing these walks. Might have some­thing to do with high CO₂ PPM levels mak­ing hu­man­ity go stu­pid2, but I di­gress again. What mat­ters is that this walk was ex­actly what I needed to come up with a work­around.

Box<dyn Trait>: 'static?

Dy­namic ob­jects re­quire some in­dir­ec­tion to be­come Sized. This is not a par­tic­u­larly novel re­quire­ment. But then, ref­er­ences aren’t the only way to in­tro­duce in­dir­ec­tion. Box<T> is a com­mon choice too! With its im­ple­ment­a­tions of Deref and DerefMut, it is easy to use it as both a plain and mut­able ref­er­ence within the func­tion body. Most im­port­antly Box<T> is (most of the time) 'static! That er­ror mes­sage was com­plain­ing about 'static so might a Box<dyn Config> work as an al­tern­at­ive too?

+impl<P: Config + ?Sized> Config for Box<P> {}

-    run_analysis(b"\0wasm", &my_config as &dyn Config);
+    run_analysis(b"\0wasm", Box::new(my_config) as Box<dyn Config>);

In­deed this works great, it builds and be­haves as one would ex­pect! De­pend­ing on the use-case there are some other smart pointer con­tain­ers that could be ap­plic­able. An un­for­tu­nate lim­it­a­tion of a Box is that the own­er­ship of the Config needs to be passed into the analysis func­tion, which is­n’t strictly ne­ces­sary in ab­sence of com­piler lim­it­a­tions. In my case do­ing so is­n’t that big of a deal – run­ning analysis even with a really small mod­ule is heavy enough in­tern­ally that a clone or two to in­voke the func­tion will never be­come a pain point. Not to men­tion that Arc could work great as a way to mit­ig­ate this cost of clone, at least where con­fig­ur­a­tions do not re­quire mut­able ref­er­ence ac­cess to self.

So there you have it, if you are deal­ing with the er­ror mes­sage about bor­row checked lim­it­a­tions, con­sider an op­tion of re­pla­cing your &T ref­er­ences with Boxes, Arcs or some other own­ing smart point­ers.

1. Ex­plain­ing how HRTBs work is prob­ably some­what out of scope for this blog post, es­pe­cially given the tar­get audi­ence be­ing people who have got­ten into trouble with rustc over them in the first place, but I’ll modify this post with a link to a good tu­torial if I find one.↩︎

2. Re­search on this topic is really con­flict­ing, with some ex­per­i­ments show­ing a strong cor­rel­a­tion between in­creas­ing levels of CO₂ and a de­crease in cog­nit­ive abil­ity, and oth­ers find­ing no cor­rel­a­tion what­so­ever. My self-in­tro­spec­tion would sug­gest a strong sup­port to­wards this idea, but it might be con­firm­a­tion bias too.↩︎