Cross-compiling OCaml to JS and Wasm: How we made the Semgrep Playground Fast

Semgrep is a fast, open source static analysis tool for finding bugs, detecting vulnerabilities in third-party dependencies, and enforcing code standards. Here at semgrep.dev we also host the Semgrep Playground, where you can write, test, debug, and share Semgrep rules from within your web browser. When a user clicks the Run button, the Playground sends their rule and test code to an instance of Semgrep running within our data center. The rule is evaluated and the results are returned to the user.

This approach works fine, but our monitoring shows that the time between a user clicking Run and seeing results takes about one second on average, which is at odds with our “ludicrous speed” slogan and irritating to our power users.

Semgrep playground average run time hovers around one second.

To quote Jakob Nielsen’s Response Times: The 3 Important Limits:

“1.0 second is about the limit for the user's flow of thought to stay uninterrupted, even though the user will notice the delay. Normally, no special feedback is necessary during delays of more than 0.1 but less than 1.0 second, but the user does lose the feeling of operating directly on the data.”

In this blog post, you’ll learn about how we took these guidelines to heart and made significant improvements to the Playground to provide users with a faster and more seamless experience.

Inspiration

The idea for this project originally came after reading Authzed's exceptional blog post detailing how they run SpiceDB within the browser. Inspired, I began to wonder, "Could we do the same with the Semgrep Playground? And if so, would it be fast?”

Today I’m thrilled to say: Yes! In fact, in-browser Semgrep executes with such impressive speed that we have completely eliminated the need for a Run button. Instead, the Playground automatically re-scans after every keystroke, a feature we refer to as "Turbo Mode." You can activate this feature by simply clicking the Turbo button located in the Playground. Give it a try right now (try changing one of the print(42) lines), or watch the gif below. It’s a truly magical experience.

How does it work?

Unlike SpiceDB, Semgrep is written in OCaml, which doesn’t (yet) have the ability to compile to WebAssembly. There are other ways to run OCaml in the browser, but it was an early indication that our journey was going to be less straightforward than Authzed's.

Js_of_ocaml

OCaml ships with two compilers: ocamlopt, which outputs a native executable, and ocamlc, which outputs OCaml bytecode which can then be executed by the ocamlrun interpreter. As a rule of thumb, native compilation yields superior performance, but bytecode compilation allows your code to be run on more diverse platforms.

We used the open source js_of_ocaml compiler to further transform the bytecode output of ocamlc into JavaScript, allowing us to compile Semgrep into one large JavaScript file.

OCaml code can be compiled as a native executable or bytecode; OCaml bytecode can be compiled to JavaScript.

Running the JavaScript output at this stage resulted in a flurry of “X is not implemented” exceptions because Semgrep also depends on a few C libraries:

• libyaml for YAML parsing

• libpcre for regular expressions

• tree-sitter for language parsing

Js_of_ocaml doesn’t know how to translate these libraries to JavaScript (it only understands OCaml), so it leaves implementing them as an exercise for the user.

Emscripten

This is where WebAssembly came into play. Using Emscripten, the de-facto compiler toolchain for WebAssembly, we recompiled Semgrep’s C libraries and linked them all into one WebAssembly module. Lucky for us, Emscripten is essentially a drop-in replacement for GCC, so we simply had to run emcc where we’d normally run gcc.

Emscripten compiles Semgrep’s C libraries into a WebAssembly module that can be imported in JavaScript.

Glue Code

Building a WebAssembly module only got us halfway there. Many of the difficulties lay in bridging the gap between JavaScript and WebAssembly.

External functions

OCaml programs interact with C libraries through external functions, which tell the compiler that the given OCaml function should be evaluated by calling the C function with the provided name. Our migration strategy was repetitive but straightforward: for each OCaml external function, find its companion C function and translate it into JavaScript.

For example, here is an external function for returning the version of the libpcre library:

1external pcre_version : unit -> string = "pcre_version_stub"

This says that pcre_version is a function with no arguments that returns a string, and its companion C function is named pcre_version_stub. Let’s look at its implementation:

1CAMLprim value pcre_version_stub(value __unused v_unit)
2{
3  return caml_copy_string((char *) pcre_version());
4}

Pretty straightforward. Call the libpcre function pcre_version() and return a copy of the string in a format that OCaml can understand.

The JavaScript implementation is slightly more verbose, but follows the same basic structure: we call libpcre._pcre_version() and make a copy of the string in a format that js_of_ocaml can understand.

1//Provides: pcre_version_stub
2//Requires: libpcre, caml_string_of_jsstring
3function pcre_version_stub() {
4	// _pcre_version() returns a pointer to the version string in the WebAssembly module memory space
5	const pcreVersionPointer = libpcre._pcre_version();
6
7	// UTF8ToString converts an array of bytes containing an UTF-8 string into a JavaScript string
8	const pcreVersionString = libpcre.UTF8ToString(pcreVersionPointer);
9
10	// caml_string_of_jsstring converts a JavaScript string into js_of_ocaml's internal string representation
11  return caml_string_of_jsstring(pcreVersionString);
12}

ocaml-ctypes

Some OCaml libraries also use ocaml-ctypes to automate the conversion of data structures between C and OCaml, which meant that we we also had to implement methods for reading, writing, and allocating memory inside of the WebAssembly module. This will be important later.

Bundling

At this point, the OCaml code was compiled to JavaScript, the C libraries were compiled to WebAssembly, and everything was wired together. Running the program this time yielded an error, complaining that the WebAssembly module was not initialized. Stepping through the code in a debugger revealed that some libpcre functions were called immediately at startup, which meant that the WebAssembly module containing Semgrep’s C libraries had to be loaded before the Semgrep code.

To resolve this, we created an “entrypoint” JavaScript file that ensured the WebAssembly module was imported and fully loaded before importing Semgrep. We bundled this into a single JavaScript package using esbuild.

Esbuild bundles together the outputs of js_of_ocaml and Emscripten.

Mismatched Architectures

There was one last bug to fix: YAML parsing did not work at all!

After many hours of debugging, copious amounts of print statements, and a little cursing, we figured it out: Semgrep was being built on a machine with a 64-bit architecture, whereas WebAssembly is a 32-bit architecture. This is problematic for libraries that use ocaml-ctypes, which assumes that the architecture of your build machine matches the architecture at runtime. When you violate this invariant, all hell breaks loose.

Here’s an example:

The image on the left is a memory dump of a libyaml data structure. Each field is represented by four bytes in the WebAssembly module, as indicated by the memory addresses on the left incrementing by four each time. The image on the right shows ocaml-ctypes attempting to construct the corresponding OCaml value by reading fields from memory.

Under the hood, the fields are read in this order: ptr->type, the three fields of ptr->start_mark, the three fields of ptr->end_mark, and finally, the ptr->data fields. Notice, however, that the memory addresses in “ctypes: read address” don’t line up with the memory dump. The second “ctypes: read address” line should be 91912, not 91936.

The key insight here was that libyaml was writing data to memory under the assumption that integers were 4 bytes wide, and Semgrep was reading that same memory assuming integers were 8 bytes wide. Our YAML parsing library was returning bogus data due to the memory offset mismatches.

The “correct” fix would be to fix the memory offsets by to cross-compiling Semgrep against a 32-bit OCaml compiler. But we were pressed for time, so we instead wrote a temporary hack that would make functional programmers sick to their stomach. We exploited the fact that JavaScript objects are mutable and created an external function that allowed us to overwrite libyaml’s memory offsets to have the correct values:

1external override_yaml_ctypes_field_offset_bytes :
2  ('a, 'b) Yaml_bindings.T.field -> int -> unit
3  = "override_yaml_ctypes_field_offset_bytes"
4
5let apply () =
6  (* Mark is a struct of 3 integers *)
7  override_yaml_ctypes_field_offset_bytes Yaml_types.M.Mark.index 0;
8  override_yaml_ctypes_field_offset_bytes Yaml_types.M.Mark.line 4;
9  override_yaml_ctypes_field_offset_bytes Yaml_types.M.Mark.column 8;
10
11(* etc... *)

1//Provides: override_yaml_ctypes_field_offset_bytes
2function override_yaml_ctypes_field_offset_bytes(field, newOffset) {
3// memory offset is stored at field[2]
4field[2] = newOffset;
5}

Conclusion

Building Turbo Mode has been an amazing learning experience and yet another reminder that speed is a feature! If you have questions/feedback, feel free to drop by #turbo-mode in the Semgrep community Slack.

Happy Grepping!