Support wasm32

[kolayne]

Add support for the wasm32-wasi* targets wasm32-unknown-unknown target!

CC: @uuuvn

[kolayne]

@eugenebokhan, I started working on supporting the wasm32-wasi* targets in xgrammar-rs, and I have a question.

Context

Since xgrammar-rs compiles C++ code when building, we need the C++ standard library implementation for WASI to support wasm32-wasi*. It is required both to build xgrammar-rs itself, and to build some of its dependencies, e.g., cxx. So, when building, we need a wasi sysroot.

Notably, we also require that it supports C++ exceptions. But this is not necessary at the dependencies building stage, only necessary for the xgrammar-rs compilation stage.

There is the official wasi-sdk, which allows to build a sysroot that includes the C++ std implementation. It is packed by some OSs (e.g., wasi-sdk on MacPorts), although some OSs provide other implementations. Since 3 weeks ago (WebAssembly/wasi-sdk#606), it supports exceptions. Note: the PR was merged into master but this has not been released yet. Also, even after the new version is released, exceptions support is behind a configuration flag, so chances are that some OSs will continue to provide wasi-sdk compiled without exceptions support.

Question

The question is where we should get the wasi sysroot from. On the one hand, I feel hestitant about requiring the user to manually obtain the SDK and compile it (although the instructions are pretty trivial). On the other hand, I don't see any other way: we require the wasi sysroot at the dependencies building stage, which is before our build.rs is even compiled.

So, are we okay with asking the user to provide the wasi sysroot (according to our instructions) for wasm builds? Or do you have any other suggestions?

[uuuvn]

We want general wasm, not just wasi. Uzu currently targets wasi because we haven't rewritten our model loading code to work with wasm-ish host passes buffers approach yet, but xgrammar-rs should work in pure wasm, not just wasm-wasi

[uuuvn]

https://github.com/mlc-ai/xgrammar/tree/main/web

xgrammar has official js bindings that allegedly work in web browsers (no wasi), do they also require wasi-sdk to build?

[uuuvn]

https://brson.github.io/2022/10/26/creating-wasm-opt-rust-bindings-with-cxx/

Look what I found

[eugenebokhan]

@kolayne Hi!

Currently, we have two rust bindings implementations:

• https://github.com/trymirai/xgrammar/tree/rust
• https://github.com/trymirai/xgrammar-rs

The first one is a fork of a xgrammar official project that was intended to be merged into the upstream. It used the cpp sources directly which was quite handy. Despite the mlc team was quite happy to see rust adoption and was almost ready the merge our bindings, they decided to move on with the TVM-FFI approach approach.

Given the tight time constrains that led us to a standalone xgrammar-rs repo that used prefetching of the original cpp git repo and compiling the sources from it.

Ideally what we would like to do now, is to reincarnate the fork and migrate it to the TVM-FFI approach and investigate the WASM support there.

What concerns the wasi sysroot, we believe that installation of a rust crate should be absolutely pain-free and should not require any extra steps from the user. However the nature of such hybrid language crates does force us to install at least cmake to handle the compilation, so if there is no a good rust idiomatic workaround for it, that's fine to have a documented requirement for the necessary sdk to be installed.

Uzu already does have a cargo tools setup command that installs all the necessary third-party tools to successfully build the project. We can confider extending the current list with the xgrammar ones.

[kolayne]

@uuuvn,

xgrammar has official js bindings that allegedly work in web browsers (no wasi), do they also require wasi-sdk to build?

No, they don't. I just assumed we want xgrammar-rs to support wasi, since uzu supports wasi.

Xgrammar seems to only officially support emscripten, although it can also be compiled for wasi. The build process is different though. I haven't investigated emscripten too much, but I suspect that supporting both wasi and emscripten will require slightly different build process and have different build-time dependencies (such as the C++ stdlib implementation).

---

https://brson.github.io/2022/10/26/creating-wasm-opt-rust-bindings-with-cxx/

Look what I found

Looked through it briefly, will consider more carefully tomorrow. But when I try to locally compile the project locally, the build for wasi succeeds, while the build for emscripten fails because I have not provided the emscripten toolchain:

Details

$ cargo build --target wasm32-unknown-emscripten 
   Compiling link-cplusplus v1.0.7
error: failed to run custom build command for `link-cplusplus v1.0.7`

Caused by:
  process didn't exit successfully: `/home/nikolai/Docs/mirai/wasm-opt-rs/target/debug/build/link-cplusplus-ff374c5217115d46/build-script-build` (exit status: 1)
  --- stdout
  TARGET = Some("wasm32-unknown-emscripten")
  OPT_LEVEL = Some("0")
  HOST = Some("x86_64-unknown-linux-gnu")
  cargo:rerun-if-env-changed=CXX_wasm32-unknown-emscripten
  CXX_wasm32-unknown-emscripten = None
  cargo:rerun-if-env-changed=CXX_wasm32_unknown_emscripten
  CXX_wasm32_unknown_emscripten = None
  cargo:rerun-if-env-changed=TARGET_CXX
  TARGET_CXX = None
  cargo:rerun-if-env-changed=CXX
  CXX = None
  cargo:rerun-if-env-changed=CXXFLAGS_wasm32-unknown-emscripten
  CXXFLAGS_wasm32-unknown-emscripten = None
  cargo:rerun-if-env-changed=CXXFLAGS_wasm32_unknown_emscripten
  CXXFLAGS_wasm32_unknown_emscripten = None
  cargo:rerun-if-env-changed=TARGET_CXXFLAGS
  TARGET_CXXFLAGS = None
  cargo:rerun-if-env-changed=CXXFLAGS
  CXXFLAGS = None
  cargo:rerun-if-env-changed=CRATE_CC_NO_DEFAULTS
  CRATE_CC_NO_DEFAULTS = None
  DEBUG = Some("true")
  CARGO_CFG_TARGET_FEATURE = Some("bulk-memory,multivalue,mutable-globals,nontrapping-fptoint,reference-types,sign-ext")
  running: "em++" "-O0" "-ffunction-sections" "-fdata-sections" "-fPIC" "-g" "-fno-omit-frame-pointer" "-Wall" "-Wextra" "-o" "/home/nikolai/Docs/mirai/wasm-opt-rs/target/wasm32-unknown-emscripten/debug/build/link-cplusplus-fee094823c0def5d/out/dummy.o" "-c" "/home/nikolai/Docs/mirai/wasm-opt-rs/target/wasm32-unknown-emscripten/debug/build/link-cplusplus-fee094823c0def5d/out/dummy.cc"

  --- stderr


  error occurred: Failed to find tool. Is `em++` installed?

Perhaps, the wasm-opt guys delegate the toolchain selection to one of their dependencies. But this might be harder for us to do, since we have the requirement for C++ exceptions support, which is still a new thing on wasi (emscripten seems to handle exceptions just fine).

[kolayne]

https://brson.github.io/2022/10/26/creating-wasm-opt-rust-bindings-with-cxx/

Look what I found

Just looked into the project a bit more carefully. Their build process seems roughly the same and requires the sdk for the corresponding platform to compile C++ code. When building for emscripten, it requires the emscripten toolchain (error above); when building for wasi, it requires the wasi stdlib implementation provided by wasi-sdk (issue brson/wasm-opt-rs#168).

One difference is that, unlike us, wasm-opt-rs only requires the SDK at the build.rs time, so they can solve it by downloading and building it automatically as part of their build process. We can't do that because we use autocxx: it is our library dependency, rather than a build-time dependency. Thus, its dependency cxx must be compiled for the wasm* target, which requires an SDK before the build.rs is executed. So, unless we are willing to restructure all of xgrammar-rs to get rid of autocxx, I don't think we can do anything about the SDK requirement.

[kolayne]

@uuuvn suggested that we target bare-metal wasm (i.e., wasm32-unknown-unknown). He also shared https://github.com/rafaelbeckel/test-c-rust-wasm - a repo with examples of linking C and C++ code that uses portions of the standard libraries with Rust for wasm32-unknown-unknown ¹.

They achieve this by building musl and llvm's libcxx (in a way that is not officially supported; musl does not even officially support wasm32 at all) at their build.rs stage. We could investigate the possibility of applying a similar approach in our case: it should work as long as the upstream xgrammar only uses the portion of stdlib that is portable to bare-metal wasm32.

However, the problem of autocxx stays. As long as it is our dependency, we cannot build the wasm sysroot at the build.rs stage, we need it earlier. Which means that we would need to make the user perform the hacky builds of standard libraries.

Anyway, I will try to look into tvm-ffi. At a first glance, does not seem like it is to magically solve our stdlib problems, but, since it does not require autocxx (?), we can, hopefully, relieve the user of extra steps by keeping all the hacky stuff in build.rs.

Footnotes

1. Note: as of writing, the repository does not have a license, so we cannot reuse their code and would have to reimplement it. ↩

[eugenebokhan]

@kolayne I believe we can try dropping the autocxx dependency if it will make things easier for us

[kolayne]

I mean, isn't autocxx a framework that all of xgrammar-rs is designed on top of?

On the other hand, I don't see any other good options.

In any case, if we are moving to a different binding generation system (which is also likely to break compatibility with old bindings), it would be nice to switch to the upstream's tvm-ffi (if we manage to make them work on bare-metal wasm32, which I am still investigating). I will return tomorrow with more details on it.

[kolayne]

News.

TVM-FFI

I spent a few hours investigating TVM-FFI's support for bare-metal wasm (as opposed to emscripten, which is used a lot), and I drowned in tons of old forum questions, issues, and broken examples. I could make any of the ones I found work.

I also investigated the way xgrammar generates its TVM-FFI bindings (which they call python bindings, but it doesn't actually have anything to do with python other than their build method). By throwing python away reconstructing a similar build pipeline we may be able to build it for an arbitrary platform if we port libtvm_ffi.so to that platform.

However, most notably! No matter the platform and the build method, TVM-FFI bindings are untyped, meaning that in our rust bindings the rust side will still need to explicitly declare the exported functions (or generated them based on the source code). Thus, I see no advantage in reusing TVM-FFI over binding our rust code to the c++ code directly.

---

Context

Now, there's two major problems that we want to solve:

1. We want to compile xgrammar bindings in a pain-free way, posing minimal requirements on the user.
2. We want to compile xgrammar bindings in a portable way, so that it could also be integrated in browser.

Here are my suggestions.

Compiling without inputs from user

The current problem is the dependency on autocxx; moving away from it means that we need to rewrite the bindings generation code.

Today I found furiosa-ai/xgrammar-rs, another library/binding to xgrammar. By disabling the default features and applying a few minor changes, I managed to compile all of its dependencies for wasm32-unknown-unknown (which also means they will compile for all other wasm32* targets), which is very promising. My changes need to be reapplied properly and some problems need to be fixed in their build script, but the big picture is: since all the dependencies just compile, we can perform all our toolchain/sysroot setup in build.rs.

I wonder if we have to rewrite our library to the stack they use or if we can just switch uzu to depend on furiosa-ai/xgrammar-rs. @eugenebokhan, could you take a look at the library (the interface it exports) and say if there is anything missing or if there are any non-trivial incompatibilities that would complicate the transition?

Being compatible with the browser

There's two ways we could go (both are compatible with furiosa-ai/xgrammar-rs).

Compiling for bare-metal

If our bindings compile for the bare-metal platform (wasm32-unknown-unknown), this is the most portable option. But making it work requires that we:

• Port a C standard library (selected parts) to the bare-metal platform. Maybe can reuse something like trevyn/wasm32-unknown-unknown-openbsd-libc ¹ or JohnSully/wasm_muscl, but both are built using non-conventional tools; to be investigated;
• Port a C++ standard library (selected parts) - it seems like a common approach is to use llvm's libcxx, maybe can reuse parts of the build process of WebAssembly/wasi-sdk;
• Port xgrammar, obviously. Though, also not a trivial task, since xgrammar includes things such as <iostream>, <mutex>, <thread>, and other stuff that might not have bare-metal wasm counterparts.

In my current understanding, each of the bullet points above is a separate task of considerable size. Rather than spending resources on this approach I wonder if the following option would suffice.

Compiling for wasi + using a shim

The alternative approach would be to compile for wasi (incomparably easier than bare-metal, since nearly complete C&C++ standard libraries are available) and then using a shim library to run that in browser. A few projects exist for that, e.g., shim libraries from bytecodealliance/jco, wasmerio/wasmer-js, etc.

@uuuvn, what do you think? Should compilation to wasi + a shim library satisfy our requirements?
Can we construct a minimal example that is expected to work in browser that we could use to verify if this bundle works?

---

Note: I will be gone for the next few days.

Footnotes

1. Not licensed 😡 ↩

[uuuvn]

We definitely don't want to port much other than maybe some trivial stuff inside of xgrammar itself ourselves. Surely there is already a good libc and libcxx that just work with upstream clang in wasm32-unknown-unknown on the subset of standard functions we need for xgrammar to work? iostream/mutex can be noops I think (prints are not used for anything we care about, there is no threading in wasm), if wasm uses threads for anything we need we might have to patch it to not do it though.

If it turns out that there is no such thing I guess shim might be the least horrible way to do it

[eugenebokhan]

Comparison with furiosa approach

Where furiosa is better

1. DLPack via dlpark.** Uses the maintained dlpark crate (SafeManagedTensorVersioned) so callers can interop with ndarray tensors. mirai exposes raw DLTensor pointers and pushes that burden on the user.

2. HuggingFace integration: huggingface_hub.rs provides snapshot_download, compile_glob_pattern, allow/ignore patterns, from_pretrained, from_path, from_backend_str. mirai's hf feature only exposes a single from_huggingface(&Tokenizer) constructor — we have to download the model ourselves.

3. EOS-token auto-discovery: parse_eos_token reads generation_config.json / config.json and adds them to stop tokens. Nothing equivalent in mirai.

4. Tracing integration: furiosa emits structured logs (e.g. vocab-size mismatch warning).

5. fork() for speculative decoding: exposes GrammarMatcher::fork() (the upstream Fork() shared-ptr clone) — explicitly designed for speculative / branching decoding. Mirai has no equivalent (it does expose traverse_draft_tree in testing, but no fork).

6. is_completed() matcher state: distinguishes root-rule completion from stop-token termination. Mirai only has is_terminated().

7. Error path is exception-safe: every C++ call goes through a try/catch that returns {success, value, strdup(e.what())} and a Drop impl that frees the C string. Mirai's shim layer takes a std::string* out-param — workable but more verbose.

Where mirai is better

1. Cross-platform reach: we compile for Windows, macOS, iOS, Linux and are up to add WASM.

2. More upstream API exposed: we wrap things furiosa doesn't:

   • Grammar::serialize_json / deserialize_json, to_string_ebnf / Display
   • TokenizerInfo::dump_metadata, serialize_json, deserialize_json, from_vocab_and_metadata_bytes, special_token_ids
   • CompiledGrammar::serialize_json / deserialize_json
   • GrammarMatcher::find_jump_forward_string, debug_print_internal_state, accept_bytes
   • set_max_recursion_depth / get_max_recursion_depth / get_serialization_version (config module)
   • Rich testing module: ebnf_to_grammar_no_normalization, json_schema_to_ebnf, qwen_xml_tool_calling_to_ebnf, regex_to_ebnf, get_masked_tokens_from_bitmask, is_single_token_bitmask, traverse_draft_tree, generate_range_regex, generate_float_range_regex, print_grammar_fsms

3. Newer xgrammar: pinned to v0.1.33 vs. furiosa's older 0.1.31+40 commit and we are targeting to use the latest one and potentially be merged into the main xgrammar repo.

4. StructuralTagItem struct API: we offer a typed compile_structural_tag(tags, triggers) that builds the JSON internally. Furiosa only accepts a raw JSON string (compile_structural_tag(&str)).

5. apply_token_bitmask_inplace_cpu exposed: furiosa only fills bitmasks while we also wrap the upstream "apply mask to logits" CPU kernel.

6. No nightly-only crate dependency: furiosa uses cpp 0.5 which compiles fine, but our autocxx stack — once built — produces nicer Rust signatures (e.g. cxx::UniquePtr, Pin<&mut T>) instead of cpp_class! opaque values. Whether this is "better" depends on taste, but it gives stronger compile-time guarantees on RAII. However we are considering to remove autocxx dep.

[kolayne]

Surely there is already a good libc and libcxx that just work with upstream clang in wasm32-unknown-unknown on the subset of standard functions we need for xgrammar to work?

Doesn't seem so. I've linked relevant projects that I found in my previous comment (and there are also a few projects that they link to). None of them are maintained (last commit 2-9 years ago), and they all look like there's much more effort to put into porting before they can be relied on. The most mature-looking one (with the last commit from 9 years ago) is archived because its former users moved to wasi.

---

Today's findings

Another attempt with autocxx, on wasi

Hoping to avoid shifting to another code generation library, I tried using autocxx with wasi once again.

Good news: I've found a (questionable) solution to our initial problem with it: by patching cxx (essentially, removing src/cxx.c) I managed to compile both cxx and autocxx for wasm32-* without providing a sysroot. This requires some more work to properly exclude the problematic part of cxx, but it's possible.

It also takes some changes to the build script, which I will attach here as a patch, just in case someone needs it in the future: 0001-STASH-Some-raw-build.rs-fixes-to-make-build-work-wit.patch

Bad news is, however: code generated by autocxx for wasm32-* targets fails to compile with a lot of type-check errors. I could not find any similar errors on the web, nor descriptions of other attempts to use autocxx on wasm. We are not likely to get help from the developers either: there seems to be no activity on the repository for over a year (also: google/autocxx#1507). Fixing autocxx generated code errors will likely require good understanding of the autocxx engine, and it seems far from trivial.

So, for now, sticking to the original plan of giving up autocxx and switching to another library. I will investigate existing binding generation libraries and their compatibility with wasm tomorrow.