TRE pairs POSIX regex conformance with edit-distance matching and no heap allocation

Two complexity numbers define what TRE promises

The README leads with the algorithm rather than the feature list, and that ordering is the project in miniature.

The matching algorithm uses linear worst-case time in the length of the text being searched, and quadratic worst-case time in the length of the regular expression used. In the README's phrasing, the time complexity is O(M^2N), where M is the length of the regular expression and N is the length of the text. Space is quadratic on the length of the regex as well, but does not depend on the searched string.

That last part is the practically important half. A matcher whose memory use grows with the input has to allocate while matching. TRE's does not, so a long document does not become a memory problem, and a matching call has a cost you can compute from the pattern size before you run it.

The README is also careful about the caveat. It says this quadratic behaviour occurs only on pathological cases which are probably very rare in practice. That is a claim about the shape of the regex rather than about the input, so an adversarial pattern can still produce a slow call, and the only stated exception to the linear guarantee is back references, which it says may take time growing exponentially with the length of the string, because matching back references is an NP complete problem.

For a library embedded in something with a latency budget, that split is the useful part of the story. Predictable on ordinary patterns, unbounded on one specific feature.

Edit distance as the measure of closeness

The approximate matching feature is the reason most people look at TRE.

The README describes it directly: approximate pattern matching allows matches to be approximate, that is, allows the matches to be close to the searched pattern under some measure of closeness. TRE uses the edit-distance measure, also known as the Levenshtein distance, where characters can be inserted, deleted or substituted in the searched text in order to get an exact match.

Each insertion, deletion or substitution adds the distance, or cost, of the match. TRE can report the matches which have a cost lower than some given threshold value, and it can also be used to search for matches with the lowest cost. So there are two modes of use, a threshold test that answers is there anything close enough, and a minimum search that answers what is the closest thing here.

What makes this more than a fuzzy string comparison is that the pattern is still a regular expression. The edit distance applies to the text, not to the pattern, so you can ask for a regex with wildcards and still tolerate mistakes in the input.

The command line companion extends the same idea. TRE includes a version of the agrep, approximate grep, command line tool for approximate regexp matching in the style of grep. The README contrasts it with other agrep implementations, specifically the one by Sun Wu and Udi Manber from the University of Arizona, and states that the TRE version allows full regexps of any length, any number of errors, and non-uniform costs for insertion, deletion and substitution. Those non-uniform costs are the part other implementations do not offer, and they let you say that a substitution should count more than a deletion, which matters when the input is human typed.

Correct subpattern matches, where most free implementations fail

The strict conformance section makes a claim that is specific enough to test.

POSIX defines the behaviour of regexp functions precisely, and TRE attempts to conform to these specifications as strictly as possible. TRE always returns the correct matches for subpatterns, for example, and the README says very few other implementations do this correctly. The standard TRE tries to conform to is the IEEE Std 1003.1-2001, or Open Group Base Specifications Issue 6.

Subpattern matches are the group references in a pattern, the parts captured by parentheses. Returning the correct matches for them is the kind of detail that separates a careful implementation from a merely working one, because a matcher that gets the group boundaries wrong still returns plausible looking output. The README names the other implementations the author believes get it right: Rx by Tom Lord, Regex++ by John Maddock, and the AT&T ast regex by Glenn Fowler and Doug McIlroy.

For anyone choosing between regex libraries, that list is the actual selection criterion. The README points to the testregex pages by Glenn Fowler of AT&T Labs Research as an excellent survey on POSIX regexp matchers, and that is the tool to point a candidate at if conformance matters more than features.

The library also carries a binary-safe API. TRE provides APIs which allow binary zero characters both in regexps and searched strings, and the README notes that the standard API cannot easily be used to search for printable words from binary data, and that searching for patterns which contain embedded binary zeroes is not possible at all with the standard API. For anyone scanning a binary format with a regex, that is not a nicety.

Memory is allocated at regcomp time, never during matching

The memory behaviour section is unusually specific, and it is the clearest technical case for the library.

A regexec call never allocates memory from the heap. TRE allocates all the memory it needs during a regcomp call, and some temporary working space from the stack frame for the duration of the regexec call. The amount of temporary space needed is constant during matching and does not depend on the searched string.

The README then gives concrete sizes. For regexps of reasonable size TRE needs less than 50K of dynamically allocated memory during the regcomp call, less than 20K for the compiled pattern buffer, and less than two kilobytes of temporary working space from the stack frame during a regexec call. There is no time / memory tradeoff. TRE is also small in code size, and statically linking with TRE increases the executable size by less than 30K, measured with gcc-3.2 on x86 under GNU/Linux.

The phrase no time / memory tradeoff is the interesting one. It means you cannot buy speed with memory here, and you cannot save memory by accepting a slower path. The cost profile is fully determined by the pattern, which is a property you can inspect before running anything.

For a long-running service that matches against a stream of untrusted input, that changes the threat model. There is no allocation to exhaust, so a pattern that causes slow matching is a CPU problem rather than a memory problem. The failure mode is bad but bounded.

The repository layout backs this up. The library lives in lib/ with headers in include/, the command line tool in src/, and there is a python/ directory, a po/ directory for translations, a win32/ directory, and tests/ for the test suite.

Building TRE from a source tree that has to be regenerated first

The build is autotools, and the first step is not a compile.

The prerequisites listed are autoconf, automake, gettext including autopoint, libtool, and zip as an optional item. Then the tree has to be prepared: change to the root of the source directory and run the autogen script.

./utils/autogen.sh

The README says this regenerates various things using the prerequisite tools so that you end up with a buildable tree. That is the standard autotools arrangement, and it means a fresh clone is not buildable until this step has run.

After that, the standard configure and make sequence follows.

./configure
make
make check
make install

make check runs the test suite, which is the step to keep in a packaging pipeline.

For producing a source tarball, there are two routes. In a prepared tree, the configure and make dist combination creates one. Alternatively, running the build-sources script builds the source code packages and puts them in the dist subdirectory, and that script needs a working zip command.

./utils/build-sources.sh

The repository root shows the full shape of the project: configure.ac and Makefile.am for autotools, m4/ for the macro directory, tre.pc.in for the pkg-config template, tre.spec.in for the RPM spec template, doc/, po/ and utils/ as directories, plus AUTHORS, THANKS, TODO, NEWS and a ChangeLog.old. The presence of both a pkg-config template and a spec template says the packaging story was designed in from the start.

Where TRE is the wrong choice

There is one feature the README rules out in performance terms, and one deployment shape it does not cover.

Back references are the performance problem. The README says the maximum time consumed by any regexec call is always directly proportional to the length of the searched string, with one exception: if back references are used, the matching may take time that grows exponentially with the length of the string, because matching back references is an NP complete problem and almost certainly requires exponential time to match in the worst case. The reasoning is correct and the consequence is fixed. If your pattern needs a back reference, you have traded away the one guarantee the library offers.

There is a second, quieter constraint in the quadratic space behaviour. Space is quadratic in the length of the regex, which means a very long pattern has a very large compiled buffer. The stated figures, under 50K for regcomp and under 20K for the compiled pattern buffer, apply to regexps of reasonable size. A pattern with thousands of alternatives is a different object, and the library does not describe a limit.

On the deployment side, TRE is a C library with a configure script. There is no package manager entry in the README, no container image, and no description of platforms beyond the four in the test table. If you need a dependency you can install with one command and upgrade automatically, that is a real cost here.

The last thing to weigh is the project itself. The repository is not archived, and the last push was on 2026-05-23. The only listed release is v0.9.0 from 2024-09-20. So there is current work in the tree and a recent release history that does not show it, which is the shape of a maintained project that releases rarely, but it does mean you should not assume a tag exists for the state you are reading.

Threads, wide characters, and the licence that does not match the label

Two smaller features matter more than they look in the README's layout, because they sit in sections a reader tends to skim.

TRE is completely thread safe. All the exported functions are re-entrant, and a single compiled regexp object can be used simultaneously in multiple contexts, for example in main and in a signal handler, or in many threads of a multithreaded application. Re-entrancy at the object level is a stronger property than thread safety at the library level, and it means a compiled pattern can be shared without a lock around the match call.

The character handling side is equally concrete. TRE supports multibyte character sets, which makes it possible to use regexps with, for example, Japanese locales, and TRE also provides a wide character API. Depending on the platform, you may need to install libutf8 to get wide character and multibyte character set support.

The portability table lists the platforms and compilers used to develop and test TRE: FreeBSD 14.1 with Clang 18, Ubuntu 22.04 with GCC 11, macOS 14.6 with Clang 14, and Windows 11 with Microsoft Visual Studio 2022. TRE should compile without changes on most modern POSIX-like platforms, and be easily portable to any platform with a hosted C implementation.

The licence is where the documentation is vaguest. The README says TRE is released under a license which is essentially the same as the 2 clause BSD-style license used in NetBSD, and points to the LICENSE file for details. The licence field on the repository is a custom type that GitHub cannot classify, so an automated scan and the LICENSE file will disagree. Read the file rather than the label if you are shipping this in a product, and note that a library linked into your binary is a different question from one you copy code out of, and that difference is one for your own counsel rather than this review.

Editorial conclusion

Adopt TRE when you need POSIX-conformant regular expressions in C with predictable memory behaviour, when you need to search text that may contain mistakes, or when you need wide character and binary-safe matching that a stock POSIX API will not give you. Do not adopt it if you need back references with predictable performance, since the README states matching back references may take exponentially long, and do not adopt it for a project that needs a large catalogue of already-maintained patterns. Before adopting, read the LICENSE file directly, since the repository licence classification does not match the terms the README describes, and confirm that your toolchain has autoconf, automake, gettext with autopoint and libtool available, because the build starts from ./utils/autogen.sh.

Frequently asked questions

Official sources

1. Issues
2. laurikari/tre on GitHub
3. README
4. Releases