README.md
1# tiny-regex-c
2# A small regex implementation in C
3### Description
4Small and portable [Regular Expression](https://en.wikipedia.org/wiki/Regular_expression) (regex) library written in C.
5
6Design is inspired by Rob Pike's regex-code for the book *"Beautiful Code"* [available online here](http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html).
7
8Supports a subset of the syntax and semantics of the Python standard library implementation (the `re`-module).
9
10### Current status
11All supported regex-operators seem to work properly according to the test-set, with the following exception:
12
13There is a problem with ranges (e.g. `[0-9]` for a digit 0-9) combined with inverted character-cases, e.g. `[^ab]` for anything but 'a' or 'b' - like `[^-0-9]` for anything not '-' or a digit 0-9. I think the code mathces too broadly in that case.
14
15I think you should test the patterns you are going to use. You can easily modify the test-harness to generate tests for your intended patterns to check for compliance.
16
17**I will gladly accept patches correcting bugs.**
18
19### Design goals
20The main design goal of this library is to be small, correct, self contained and use few resources while retaining acceptable performance and feature completeness. Clarity of the code is also highly valued.
21
22### Notable features and omissions
23- Small code and binary size: <500 SLOC, ~3kb binary for x86. Statically #define'd memory usage / allocation.
24- No use of dynamic memory allocation (i.e. no calls to `malloc` / `free`).
25- To avoid call-stack exhaustion, iterative searching is preferred over recursive by default (can be changed with a pre-processor flag).
26- No support for capturing groups or named capture: `(^P<name>group)` etc.
27- Thorough testing : [exrex](https://github.com/asciimoo/exrex) is used to randomly generate test-cases from regex patterns, which are fed into the regex code for verification. Try `make test` to generate a few thousand tests cases yourself.
28- Compiled for x86 using GCC 4.7.4 and optimizing for size, the binary takes up ~2-3kb code space and allocates ~0.5kb RAM :
29 ```
30 > gcc -Os -c re.c
31 > size re.o
32 text data bss dec hex filename
33 2319 0 544 2863 b2f re.o
34
35 ```
36 For ARM/Thumb using GCC 4.8.1 it's around 1.5kb code and less RAM :
37 ```
38 > arm-none-eabi-gcc -Os -mthumb -c re.c
39 > size re.o
40 text data bss dec hex filename
41 1418 0 280 1698 6a2 re.o
42
43 ```
44 For 8-bit AVR using AVR-GCC 4.8.1 it's around 2kb code and less RAM :
45 ```
46 > avr-gcc -Os -c re.c
47 > size re.o
48 text data bss dec hex filename
49 2128 0 130 2258 8d2 re.o
50 ```
51
52
53
54### API
55This is the public / exported API:
56```C
57/* Typedef'd pointer to hide implementation details. */
58typedef struct regex_t* re_t;
59
60/* Compiles regex string pattern to a regex_t-array. */
61re_t re_compile(const char* pattern);
62
63/* Finds matches of the compiled pattern inside text. */
64int re_matchp(re_t pattern, const char* text);
65
66/* Finds matches of pattern inside text (compiles first automatically). */
67int re_match(const char* pattern, const char* text);
68```
69
70### Supported regex-operators
71The following features / regex-operators are supported by this library.
72
73NOTE: inverted character classes are buggy - see the test harness for concrete examples.
74
75
76 - `.` Dot, matches any character
77 - `^` Start anchor, matches beginning of string
78 - `$` End anchor, matches end of string
79 - `*` Asterisk, match zero or more (greedy)
80 - `+` Plus, match one or more (greedy)
81 - `?` Question, match zero or one (non-greedy)
82 - `[abc]` Character class, match if one of {'a', 'b', 'c'}
83 - `[^abc]` Inverted class, match if NOT one of {'a', 'b', 'c'}
84 **`NOTE: This feature is currently broken for some usage of character ranges!`**
85 - `[a-zA-Z]` Character ranges, the character set of the ranges { a-z | A-Z }
86 - `\s` Whitespace, \t \f \r \n \v and spaces
87 - `\S` Non-whitespace
88 - `\w` Alphanumeric, [a-zA-Z0-9_]
89 - `\W` Non-alphanumeric
90 - `\d` Digits, [0-9]
91 - `\D` Non-digits
92
93### Usage
94Compile a regex from ASCII-string (char-array) to a custom pattern structure using `re_compile()`.
95
96Search a text-string for a regex and get an index into the string, using `re_match()` or `re_matchp()`.
97
98The returned index points to the first place in the string, where the regex pattern matches.
99
100If the regular expression doesn't match, the matching function returns an index of -1 to indicate failure.
101
102### Examples
103Example of usage:
104```C
105/* Standard null-terminated C-string to search: */
106const char* string_to_search = "ahem.. 'hello world !' ..";
107
108/* Compile a simple regular expression using character classes, meta-char and greedy + non-greedy quantifiers: */
109re_t pattern = re_compile("[Hh]ello [Ww]orld\\s*[!]?");
110
111/* Check if the regex matches the text: */
112int match_idx = re_matchp(pattern, string_to_search);
113if (match_idx != -1)
114{
115 printf("match at idx %d.\n", match_idx);
116}
117```
118
119For more usage examples I encourage you to look at the code in the `tests`-folder.
120
121### TODO
122- Fix the implementation of inverted character classes.
123- Fix implementation of branches (`|`), and see if that can lead us closer to groups as well, e.g. `(a|b)+`.
124- Add `example.c` that demonstrates usage.
125- Add `tests/test_perf.c` for performance and time measurements.
126- Testing: Improve pattern rejection testing.
127
128### FAQ
129- *Q: What differentiates this library from other C regex implementations?*
130
131 A: Well, the small size for one. <500 lines of C-code compiling to 2-3kb ROM, using very little RAM.
132
133### License
134All material in this repository is in the public domain.
135
136
137
138
139