panicked at 'time not implemented on wasm32-unknown-unknown'

[pablosichert]

Hey there,

as already mentioned in #126 I had some problems on target wasm32-unknown-unknown with gracefully handling input that isn't accepted by the grammar.

I got stack traces working now:

panicked at 'time not implemented on wasm32-unknown-unknown', src/libstd/sys/wasm/time.rs:13:9

Stack:

Error
    [...<omitted>...]
    at std::sys::wasm::time::Instant::now::h766434e196ba7d73 (wasm-function[2735]:0xc091e)
    at std::time::Instant::now::hd779be9a0cda9cbc (wasm-function[3030]:0xc1473)
    at lrpar::parser::Parser<StorageT,ActionT>::lr::hce502a5dc7a16768 (wasm-function[61]:0x2c111)
    at lrpar::parser::Parser<StorageT,ActionT>::parse_actions::hfdeea25ce9816fde (wasm-function[318]:0x67fc8)
    [...<omitted>...]

See rust-lang/rust#48564 for more info on that issue in general.

Having a quick glance at the code base, it looks like the calls to std::time::Instant::now could be replaced by calling a function that produces strictly incremental identifiers.

Is that correct, or does some part rely on the actual timestamps?

[ltratt]

lrpar uses elapsed time to know how long time to try recovering from errors, so it does need to have some notion of wall-clock time. I wonder if you can include rust-lang/rust#48564 (comment) in your project? Or whether wasm32-wasi is a suitable target for your usage?

[pablosichert]

lrpar uses elapsed time to know how long time to try recovering from errors [...]

Could you give some insight into what exactly the time is used for – is it some limit until the computation is deemed too expensive and the error recovery is aborted?

I wonder if you can include rust-lang/rust#48564 (comment) in your project?

Unfortunately, that won't affect the lrpar library code.

Or whether wasm32-wasi is a suitable target for your usage?

That sounds interesting, however multiple parts of the toolchain don't seem to support it yet. Also, if I understood correctly, wasm32-wasi is a target that runs in a standalone-runtime outside of the browser. My particular use case is an application running in the browser.

If it doesn't complicate the code base too much, maybe the timing feature could be guarded behind a cargo feature flag?

[ltratt]

Could you give some insight into what exactly the time is used for – is it some limit until the computation is deemed too expensive and the error recovery is aborted?

In essence, yes. [It's slightly more complex than that: error recovery is unbounded in time and space. It turns out that using a time limit is a fairly easy way of stopping us using too much memory!]

If it doesn't complicate the code base too much, maybe the timing feature could be guarded behind a cargo feature flag?

I think we need some way of specifying time (for the reasons above) . If we can find an unobtrusive way of doing this, I guess it's OK. For example, perhaps we can conditionally include a file along the lines of rust-lang/rust#48564 (comment) then we wouldn't make the rest of the code base any worse, since everything would be isolated to one file.

There might be a quick alternative, if you don't need error recovery, that might prevent panics: if you add recoverer(RecoveryKind::None) to your builder in build.rs, you won't get any recovery. I admit that, off hand, I can't remember if that will still call Instant::now() somewhere, but a) it's probably worth trying b) if it does still call Instant::now() it might be easy to alter the code not to when the recoverer is RecoveryKind::None.

[pablosichert]

Thank you, adding recoverer(RecoveryKind::None) helped masking the symptoms for now.

The time limit seems like a plausible solution regarding computation time (and setting a hard limit for when the user can expect a result). However, one could consume more memory than desired when execution is vastly faster on the target system.

I wonder if tracking the number of iterations / recursion depth and limiting the execution accordingly would achieve the same?

[ltratt]

The only possibly better mechanism I can think of is to track memory usage, but that might be hard on some platforms. The current time limit is safe on every grammar I know, and single-threaded performance would probably have to improve by a factor of 4-5x before it became an issue. For better or worse, such an increase in performance seems unlikely to happen any time soon ;)

[pablosichert]

The only possibly better mechanism I can think of is to track memory usage, but that might be hard on some platforms.

Wouldn't tracking some sort of stack depth be a good approximation for that?

For better or worse, such an increase in performance seems unlikely to happen any time soon

True that.

---

Before I head into the adventure of making those changes – what do you think of the following approach: Along the RecoveryKind, a get_cost function and a recovery_budget constant can be provided. For the existing case, this would just be Instant::now and 500.

In my case, I then could conveniently provide an equivalent.

[ltratt]

Wouldn't tracking some sort of stack depth be a good approximation for that?

Unfortunately not. [Previous works tried using vaguely similar ideas, and it's easy to construct grammars that cause them to explode.]

Before I head into the adventure of making those changes – what do you think of the following approach: Along the RecoveryKind, a get_cost function and a recovery_budget constant can be provided. For the existing case, this would just be Instant::now and 500.

I'm reluctant to expose knobs like this to the user because it's going to confuse them unnecessarily: it's got to be grmtools job to get this right IMHO.

One obvious question occurs to me: can we change the Rust WASM backend to call the JavaScript timer? That would solve the problem for grmtools and other libraries too!

[ltratt]

This might be relevant https://crates.io/crates/instant.

[pablosichert]

Having though about it, I share your idea that this issue should be resolved on a platform/backend level rather than in the library.

Implementing syscalls for Wasm doesn't seem to get too much traction, though: https://internals.rust-lang.org/t/what-is-the-plan-regarding-libstd-and-wasm-syscalls/8497.

For my needs I think I'll just fall back to patching the grmtools dependency in my project.

I'll close this issue for now since I don't have any actionable input moving forward. I'll keep an eye on how the Wasm / Wasi / syscalls story progresses.

---

This might be relevant https://crates.io/crates/instant.

This would be an alternative if you want to add support for Wasm directly to this library and consider adding that dependency to be elegant enough.