kokke / kokke/tiny-regex-c

Add Precompiled Regex Code Generator

Open
#59 4 comments 2 reactions 0 assignees View on GitHub
Dominant language
C
Stars
1.5k
Forks
212
PR merge metrics
No merged PRs in 30d

Description

I decided to use this library for a scripting language I'm working on. Here's a link to the directory that uses it if you're interested: https://github.com/stitchlang/stitch/tree/fedf09a6a522e8e48c963075c84aa44cfc74a951/src

One thing I wanted was to "compile" my regular expressions at compile time rather than runtime. Not only is this more performant, but it means I can have as many as I want (see https://github.com/kokke/tiny-regex-c/issues/3) and I don't need to allocate dynamic memory for them.

To solve this, I first noted that the `regex_t` data-structure is very simple:

```c
typedef struct regex_t
{
unsigned char type; /* CHAR, STAR, etc. */
union
{
unsigned char ch; /* the character itself */
unsigned char* ccl; /* OR a pointer to characters in class */
} u;
} regex_t;
```

I was able to write a function that takes a `regex_t` object and generates "C initializtion" code to "recreate itself". This function was easy to write becuase `re.c` already has a function named `re_print` that does something very similar. Here's what it looks like:

```c
#include
static regex_t INLINE_WHITESPACE[] = {
{ .type = 2 }, // BEGIN
{ .type = 8, { .ccl = (unsigned char*)" \t" } }, // CHAR_CLASS
{ .type = 6 }, // PLUS
{ .type = 0 }, // UNUSED
};
static regex_t USER_ID[] = {
{ .type = 2 }, // BEGIN
{ .type = 7, { .ch = '$' } }, // CHAR
{ .type = 8, { .ccl = (unsigned char*)"a-zA-Z0-9_\\." } }, // CHAR_CLASS
{ .type = 6 }, // PLUS
{ .type = 7, { .ch = '$' } }, // CHAR
{ .type = 4 }, // QUESTIONMARK
{ .type = 0 }, // UNUSED
};
static regex_t NEWLINE[] = {
{ .type = 2 }, // BEGIN
{ .type = 7, { .ch = '\n' } }, // CHAR
{ .type = 0 }, // UNUSED
};
static regex_t QUOTED_STRING[] = {
{ .type = 2 }, // BEGIN
{ .type = 7, { .ch = '"' } }, // CHAR
{ .type = 9, { .ccl = (unsigned char*)"\"" } }, // INV_CHAR_CLASS
{ .type = 5 }, // STAR
{ .type = 7, { .ch = '"' } }, // CHAR
{ .type = 0 }, // UNUSED
};
static regex_t COMMENT[] = {
{ .type = 2 }, // BEGIN
{ .type = 7, { .ch = '#' } }, // CHAR
{ .type = 9, { .ccl = (unsigned char*)"\n" } }, // INV_CHAR_CLASS
{ .type = 5 }, // STAR
{ .type = 0 }, // UNUSED
};
static regex_t OPEN_PAREN[] = {
{ .type = 2 }, // BEGIN
{ .type = 7, { .ch = '(' } }, // CHAR
{ .type = 0 }, // UNUSED
};
static regex_t CLOSE_PAREN[] = {
{ .type = 2 }, // BEGIN
{ .type = 7, { .ch = ')' } }, // CHAR
{ .type = 0 }, // UNUSED
};
static regex_t ESCAPE_SEQUENCE[] = {
{ .type = 2 }, // BEGIN
{ .type = 7, { .ch = '@' } }, // CHAR
{ .type = 8, { .ccl = (unsigned char*)"@#$\")(" } }, // CHAR_CLASS
{ .type = 0 }, // UNUSED
};
```

With the C initialization code, I can compile my regex objects directly into my final binary. Now I don't need to call `re_compile` at runtime. I can have as many regular expressions as I want and there's no need for dynamic memory.

Note that one big piece to this puzzle was exposing the `regex_t` definition to the user by moving it to the public header file `re.h`. Without this, the user would not be able to initalize the objects at compile-time.

For reference here's the function I wrote to generate this initialization code (https://github.com/stitchlang/stitch/blob/fedf09a6a522e8e48c963075c84aa44cfc74a951/src/tokens/compiler.c#L21). As you can see it's quite trivial. If a similar function were added to the library, even in a separate file like `cgenerator.c` then others would easily be able to do this as well.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reading re.c's existing re_print function and the regex_t definition discussed for re.h. Compare the proposed approach with src/tokens/compiler.c in the linked Stitch example, then assess a separate cgenerator.c entry point. Done means generated C initialization recreates regex objects without calling re_compile at runtime.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
tooling
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.