contrib/tre/README

   1 Introduction
   2
   3    TRE is a lightweight, robust, and efficient POSIX compliant regexp
   4    matching library with some exciting features such as approximate
   5    (fuzzy) matching.
   6
   7    The matching algorithm used in TRE uses linear worst-case time in
   8    the length of the text being searched, and quadratic worst-case
   9    time in the length of the used regular expression. In other words,
  10    the time complexity of the algorithm is O(M^2N), where M is the
  11    length of the regular expression and N is the length of the
  12    text. The used space is also quadratic on the length of the regex,
  13    but does not depend on the searched string. This quadratic
  14    behaviour occurs only on pathological cases which are probably very
  15    rare in practice.
  16
  17 Features
  18
  19    TRE is not just yet another regexp matcher. TRE has some features
  20    which are not there in most free POSIX compatible
  21    implementations. Most of these features are not present in non-free
  22    implementations either, for that matter.
  23
  24 Approximate matching
  25
  26    Approximate pattern matching allows matches to be approximate, that
  27    is, allows the matches to be close to the searched pattern under
  28    some measure of closeness. TRE uses the edit-distance measure (also
  29    known as the Levenshtein distance) where characters can be
  30    inserted, deleted, or substituted in the searched text in order to
  31    get an exact match. Each insertion, deletion, or substitution adds
  32    the distance, or cost, of the match. TRE can report the matches
  33    which have a cost lower than some given threshold value. TRE can
  34    also be used to search for matches with the lowest cost.
  35
  36    TRE includes a version of the agrep (approximate grep) command line
  37    tool for approximate regexp matching in the style of grep. Unlike
  38    other agrep implementations (like the one by Sun Wu and Udi Manber
  39    from University of Arizona available here) TRE agrep allows full
  40    regexps of any length, any number of errors, and non-uniform costs
  41    for insertion, deletion and substitution.
  42
  43 Strict standard conformance
  44
  45    POSIX defines the behaviour of regexp functions precisely. TRE
  46    attempts to conform to these specifications as strictly as
  47    possible. TRE always returns the correct matches for subpatterns,
  48    for example. Very few other implementations do this correctly. In
  49    fact, the only other implementations besides TRE that I am aware of
  50    (free or not) that get it right are Rx by Tom Lord, Regex++ by John
  51    Maddock, and the AT&T ast regex by Glenn Fowler and Doug McIlroy.
  52
  53    The standard TRE tries to conform to is the IEEE Std 1003.1-2001,
  54    or Open Group Base Specifications Issue 6, commonly referred to as
  55    "POSIX".  It can be found online here. The relevant parts are the
  56    base specifications on regular expressions (and the rationale) and
  57    the description of the regcomp() API.
  58
  59    For an excellent survey on POSIX regexp matchers, see the testregex
  60    pages by Glenn Fowler of AT&T Labs Research.
  61
  62 Predictable matching speed
  63
  64    Because of the matching algorithm used in TRE, the maximum time
  65    consumed by any regexec() call is always directly proportional to
  66    the length of the searched string. There is one exception: if back
  67    references are used, the matching may take time that grows
  68    exponentially with the length of the string. This is because
  69    matching back references is an NP complete problem, and almost
  70    certainly requires exponential time to match in the worst case.
  71
  72 Predictable and modest memory consumption
  73
  74    A regexec() call never allocates memory from the heap. TRE
  75    allocates all the memory it needs during a regcomp() call, and some
  76    temporary working space from the stack frame for the duration of
  77    the regexec() call. The amount of temporary space needed is
  78    constant during matching and does not depend on the searched
  79    string. For regexps of reasonable size TRE needs less than 50K of
  80    dynamically allocated memory during the regcomp() call, less than
  81    20K for the compiled pattern buffer, and less than two kilobytes of
  82    temporary working space from the stack frame during a regexec()
  83    call. There is no time/memory tradeoff. TRE is also small in code
  84    size; statically linking with TRE increases the executable size
  85    less than 30K (gcc-3.2, x86, GNU/Linux).
  86
  87 Wide character and multibyte character set support
  88
  89    TRE supports multibyte character sets. This makes it possible to
  90    use regexps seamlessly with, for example, Japanese locales. TRE
  91    also provides a wide character API.
  92
  93 Binary pattern and data support
  94
  95    TRE provides APIs which allow binary zero characters both in
  96    regexps and searched strings. The standard API cannot be easily
  97    used to, for example, search for printable words from binary data
  98    (although it is possible with some hacking). Searching for patterns
  99    which contain binary zeroes embedded is not possible at all with
 100    the standard API.
 101
 102 Completely thread safe
 103
 104    TRE is completely thread safe. All the exported functions are
 105    re-entrant, and a single compiled regexp object can be used
 106    simultaneously in multiple contexts; e.g. in main() and a signal
 107    handler, or in many threads of a multithreaded application.
 108
 109 Portable
 110
 111    TRE is portable across multiple platforms. Here's a table of
 112    platforms and compilers that have been successfully used to compile
 113    and run TRE:
 114
 115       Platform(s)                       | Compiler(s)
 116       ----------------------------------+------------
 117       AIX 4.3.2 - 5.3.0                 | GCC, C for AIX compiler version 5
 118       Compaq Tru64 UNIX V5.1A/B         | Compaq C V6.4-014 - V6.5-011
 119       Cygwin 1.3 - 1.5                  | GCC
 120       Digital UNIX V4.0                 | DEC C V5.9-005
 121       FreeBSD 4 and above               | GCC
 122       GNU/Linux systems on x86, x86_64, | GCC
 123       ppc64, s390                       |
 124       HP-UX 10.20- 11.00                | GCC, HP C Compiler
 125       IRIX 6.5                          | GCC, MIPSpro Compilers 7.3.1.3m
 126       Max OS X                          |
 127       NetBSD 1.5 and above              | GCC, egcs
 128       OpenBSD 3.3 and above             | GCC
 129       Solaris 2.7-10 sparc/x86          | GCC, Sun Workshop 6 compilers
 130       Windows 98 - XP                   | Microsoft Visual C++ 6.0
 131
 132    TRE 0.7.5 should compile without changes on all of the above
 133    platforms.  Tell me if you are using TRE on a platform that is not
 134    listed above, and I'll add it to the list. Also let me know if TRE
 135    does not work on a listed platform.
 136
 137    Depending on the platform, you may need to install libutf8 to get
 138    wide character and multibyte character set support.
 139
 140  Free
 141
 142    TRE is released under a license which is essentially the same as
 143    the "2 clause" BSD-style license used in NetBSD.  See the file
 144    LICENSE for details.
 145
 146 Roadmap
 147
 148    There are currently two features, both related to collating
 149    elements, missing from 100% POSIX compliance. These are:
 150
 151      * Support for collating elements (e.g. [[.<X>.]], where <X> is a
 152        collating element). It is not possible to support
 153        multi-character collating elements portably, since POSIX does
 154        not define a way to determine whether a character sequence is a
 155        multi-character collating element or not.
 156
 157      * Support for equivalence classes, for example [[=<X>=]], where
 158        <X> is a collating element. An equivalence class matches any
 159        character which has the same primary collation weight as
 160        <X>. Again, POSIX provides no portable mechanism for
 161        determining the primary collation weight of a collating
 162        element.
 163
 164    Note that other portable regexp implementations don't support
 165    collating elements either. The single exception is Regex++, which
 166    comes with its own database for collating elements for different
 167    locales. Support for collating elements and equivalence classes has
 168    not been widely requested and is not very high on the TODO list at
 169    the moment.
 170
 171    These are other features I'm planning to implement real soon now:
 172
 173      * All the missing GNU extensions enabled in GNU regex, such as
 174        [[:<:]] and [[:>:]]
 175
 176      * A REG_SHORTEST regexec() flag for returning the shortest match
 177        instead of the longest match.
 178
 179      * Perl-compatible syntax
 180
 181             [:^class:]
 182                Matches anything but the characters in class. Note that
 183                [^[:class:]] works already, this would be just a
 184                convenience shorthand.
 185
 186             \A
 187                Match only at beginning of string
 188
 189             \Z
 190                Match only at end of string, or before newline at the end
 191
 192             \z
 193                Match only at end of string
 194
 195             \l
 196                Lowercase next char (think vi)
 197
 198             \u
 199                Uppercase next char (think vi)
 200
 201             \L
 202                Lowercase till \E (think vi)
 203
 204             \U
 205                Uppercase till \E (think vi)
 206
 207             (?=pattern)
 208                Zero-width positive look-ahead assertions.
 209
 210             (?!pattern)
 211                Zero-width negative look-ahead assertions.
 212
 213             (?<=pattern)
 214                Zero-width positive look-behind assertions.
 215
 216             (?<!pattern)
 217                Zero-width negative look-behind assertions.
 218
 219    Documentation especially for the nonstandard features of TRE, such
 220    as approximate matching, is a work in progress (with "progress"
 221    loosely defined...)
 222
 223    Mailing lists
 224
 225    tre-general@lists.laurikari.net
 226       This list is for any discussion on the TRE software, including
 227       reporting bugs, feature requests, requests for help, and other
 228       things.
 229
 230    tre-announce@lists.laurikari.net
 231       Subscribe to this list to get announcements of new releases of
 232       TRE.  Alternatively, you can subscribe to the freshmeat.net
 233       project and get similar announcements that way, if you prefer.
 234
 235 Ville Laurikari    <vl@iki.fi>