regrex:
regrex means regret + regex. Something a lot of developers can relate to - an inescapable dread of processing text and having to utilize regular expressions, the meaning of which even the best can forget in two weeks or so.
regrex is a small and primitive implementation of a regular expressions processor in Zig. This project is a combination of several areas of my interest - the Zig programming language itself and learning its capabilities, my fascination with the topic of building interpreters and compilers (being self-taught and having never studied Computer Science as a subject I was still drawn to this topic), and my interest in the C language.
At the core of regrex is a tiny compiler for a limited subset of regular expression grammar. The string pattern is first broken down into a stream of lexical tokens. This stream is then passed to the parser, which produces a basic Abstract Syntax Tree of the expression. Then, the AST is consumed by the compiler, which transforms it into a set of the Intermediate Code Representation (bytecode) instructions, stored within the internal CompiledPattern data structure. To prevent any unwanted meddling with the bytecode buffer, this ‘private’ or ‘internal’ CompiledPattern type is wrapped by the public facing opaque type - Pattern, which exposes the API for performing operations, while keeping the data inaccessible to the end users [1]
The exposed API functions accept the input string to be compared against the pattern, and perform an internal call to a simple ‘backtracking’ virtual machine - basically, a stateful execution loop which holds a ‘stack’ of ‘frames’ - a data structure containing the current bytecode instruction index, its corresponding position in the input and a buffer of capture slots (i.e. byte offsets into the input string, the starting and the ending indices of a match). The core principle is that if executing the current instruction fails, the VM returns to the most recent ‘frame’ and tries to resume execution from its index. Only if both paths fail, the whole operation is considered failed. If the operation was successful and located matches in the input string, the called function returns a Match type, which holds the byte offsets of the full match as well as offsets of matches caught by the capture groups. [2] It is also important to mention that despite we keep the byte offsets into string, the actual operations are performed on a custom data type Rune, which represents a scalar UTF-8 value. At its core it’s just an alias for an unsigned 21-bit integer, which is an exact size of a Unicode code point. This way, regrex can work not only with ASCII, but with other character systems like Cyrillics, Arabic script or Chinese characters as well as alphabets like Japanese kana or Korean hangul.
This project was drawing inspiration primarily from Python’s re module, the most notable examples of which is the naming for the library’s functions and types, and the basic API architecture [3], as well as from PCRE - primarily the backtracking idea. Certain features, as well as the naming convention for the exported C-compatible layer of the library [4], are inspired by POSIX implementation. However, this implementation lacks various features both basic and advanced, from flags to lookarounds or backreferences, and most likely will not be implemented. At its core, this is still a learning project, not a full-fledged production-ready library, and treating it as one would currently be a jump well above my capabilities.
In any case this concludes the introduction of my project. My apologies if the post is too long or too hard to read (English is not my native language), and any constructive criticism will be deeply appreciated.
Supported Zig versions
Successfully built with Zig 0.16.0 and Zig 0.17.0-dev.986 (using zvm)
This design choice particularly was inspired by POSIX regex, which as well exports a ‘public’ struct re_pattern_buffer wrapping over a private type actually storing the compiled pattern ↩︎
There is also MatchArray type which is basically a convenience wrapper over an ArrayList of Matches to simplify handling ownership and releasing memory ↩︎
Library root exposes functions that take a string pattern and the input string and perform operations compiling and disposing of Pattern internally on each call, as well as the compile function that returns an instance of Pattern for reusabillity ↩︎
Strictly speaking this part of the implementation is completely over the top, and in all fairness for a library of this size this is just not needed. This was done solely out of curiosity how well will Zig interop with C and for a possible future sub-project of writing an example of Python or Lua wrapper ↩︎