C++ Boost

Regex++, Appendices.

Copyright (c) 1998-2001

Dr John Maddock

Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Dr John Maddock makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.


Appendix 1: Implementation notes

This is the first port of regex++ to the boost library, and is based on regex++ 2.x, see changes.txt for a full list of changes from the previous version. There are no known functionality bugs except that POSIX style equivalence classes are only guaranteed correct if the Win32 localization model is used (the default for Win32 builds of the library).

There are some aspects of the code that C++ puritans will consider to be poor style, in particular the use of goto in some of the algorithms. The code could be cleaned up, by changing to a recursive implementation, although it is likely to be slower in that case.

The performance of the algorithms should be satisfactory in most cases. For example the times taken to match the ftp response expression "^([0-9]+)(\-| |$)(.*)$" against the string "100- this is a line of ftp response which contains a message string" are: BSD implementation 450 micro seconds, GNU implementation 271 micro seconds, regex++ 127 micro seconds (Pentium P90, Win32 console app under MS Windows 95).

However it should be noted that there are some "pathological" expressions which may require exponential time for matching; these all involve nested repetition operators, for example attempting to match the expression "(a*a)*b" against N letter a's requires time proportional to 2N. These expressions can (almost) always be rewritten in such a way as to avoid the problem, for example "(a*a)*b" could be rewritten as "a*b" which requires only time linearly proportional to N to solve. In the general case, non-nested repeat expressions require time proportional to N2, however if the clauses are mutually exclusive then they can be matched in linear time - this is the case with "a*b", for each character the matcher will either match an "a" or a "b" or fail, where as with "a*a" the matcher can't tell which branch to take (the first "a" or the second) and so has to try both. Be careful how you write your regular expressions and avoid nested repeats if you can! New to this version, some previously pathological cases have been fixed - in particular searching for expressions which contain leading repeats and/or leading literal strings should be much faster than before. Literal strings are now searched for using the Knuth/Morris/Pratt algorithm (this is used in preference to the Boyer/More algorithm because it allows the tracking of newline characters).

Some aspects of the POSIX regular expression syntax are implementation defined:


Appendix 2: Thread safety

Class reg_expression<> and its typedefs regex and wregex are thread safe, in that compiled regular expressions can safely be shared between threads. The matching algorithms regex_match, regex_search, regex_grep, regex_format and regex_merge are all re-entrant and thread safe. Class match_results is now thread safe, in that the results of a match can be safely copied from one thread to another (for example one thread may find matches and push match_results instances onto a queue, while another thread pops them off the other end), otherwise use a separate instance of match_results per thread.

The POSIX API functions are all re-entrant and thread safe, regular expressions compiled with regcomp can also be shared between threads.

The class RegEx is only thread safe if each thread gets its own RegEx instance (apartment threading) - this is a consequence of RegEx handling both compiling and matching regular expressions.

Finally note that changing the global locale invalidates all compiled regular expressions, therefore calling set_locale from one thread while another uses regular expressions will produce unpredictable results.

There is also a requirement that there is only one thread executing prior to the start of main().


Appendix 3: Localization

 Regex++ provides extensive support for run-time localization, the localization model used can be split into two parts: front-end and back-end.

Front-end localization deals with everything which the user sees - error messages, and the regular expression syntax itself. For example a French application could change [[:word:]] to [[:mot:]] and \w to \m. Modifying the front end locale requires active support from the developer, by providing the library with a message catalogue to load, containing the localized strings. Front-end locale is affected by the LC_MESSAGES category only.

Back-end localization deals with everything that occurs after the expression has been parsed - in other words everything that the user does not see or interact with directly. It deals with case conversion, collation, and character class membership. The back-end locale does not require any intervention from the developer - the library will acquire all the information it requires for the current locale from the underlying operating system / run time library. This means that if the program user does not interact with regular expressions directly - for example if the expressions are embedded in your C++ code - then no explicit localization is required, as the library will take care of everything for you. For example embedding the expression [[:word:]]+ in your code will always match a whole word, if the program is run on a machine with, for example, a Greek locale, then it will still match a whole word, but in Greek characters rather than Latin ones. The back-end locale is affected by the LC_TYPE and LC_COLLATE categories.

There are three separate localization mechanisms supported by regex++:

Win32 localization model.

This is the default model when the library is compiled under Win32, and is encapsulated by the traits class w32_regex_traits. When this model is in effect there is a single global locale as defined by the user's control panel settings, and returned by GetUserDefaultLCID. All the settings used by regex++ are acquired directly from the operating system bypassing the C run time library. Front-end localization requires a resource dll, containing a string table with the user-defined strings. The traits class exports the function:

static std::string set_message_catalogue(const std::string& s);

which needs to be called with a string identifying the name of the resource dll, before your code compiles any regular expressions (but not necessarily before you construct any reg_expression instances):

boost::w32_regex_traits<char>::set_message_catalogue("mydll.dll");

Note that this API sets the dll name for both the narrow and wide character specializations of w32_regex_traits.

This model does not currently support thread specific locales (via SetThreadLocale under Windows NT), the library provides full Unicode support under NT, under Windows 9x the library degrades gracefully - characters 0 to 255 are supported, the remainder are treated as "unknown" graphic characters.

C localization model.

This is the default model when the library is compiled under an operating system other than Win32, and is encapsulated by the traits class c_regex_traits, Win32 users can force this model to take effect by defining the pre-processor symbol BOOST_REGEX_USE_C_LOCALE. When this model is in effect there is a single global locale, as set by setlocale. All settings are acquired from your run time library, consequently Unicode support is dependent upon your run time library implementation. Front end localization requires a POSIX message catalogue. The traits class exports the function:

static std::string set_message_catalogue(const std::string& s);

which needs to be called with a string identifying the name of the message catalogue, before your code compiles any regular expressions (but not necessarily before you construct any reg_expression instances):

boost::c_regex_traits<char>::set_message_catalogue("mycatalogue");

Note that this API sets the dll name for both the narrow and wide character specializations of c_regex_traits. If your run time library does not support POSIX message catalogues, then you can either provide your own implementation of <nl_types.h> or define BOOST_RE_NO_CAT to disable front-end localization via message catalogues.

Note that calling setlocale invalidates all compiled regular expressions, calling setlocale(LC_ALL, "C") will make this library behave equivalent to most traditional regular expression libraries including version 1 of this library.

C++ localization model.

This model is only in effect if the library is built with the pre-processor symbol BOOST_REGEX_USE_CPP_LOCALE defined. When this model is in effect each instance of reg_expression<> has its own instance of std::locale, class reg_expression<> also has a member function imbue which allows the locale for the expression to be set on a per-instance basis. Front end localization requires a POSIX message catalogue, which will be loaded via the std::messages facet of the expression's locale, the traits class exports the symbol:

static std::string set_message_catalogue(const std::string& s);

which needs to be called with a string identifying the name of the message catalogue, before your code compiles any regular expressions (but not necessarily before you construct any reg_expression instances):

boost::cpp_regex_traits<char>::set_message_catalogue("mycatalogue");

Note that calling reg_expression<>::imbue will invalidate any expression currently compiled in that instance of reg_expression<>. This model is the one which closest fits the ethos of the C++ standard library, however it is the model which will produce the slowest code, and which is the least well supported by current standard library implementations, for example I have yet to find an implementation of std::locale which supports either message catalogues, or locales other than "C" or "POSIX".

Finally note that if you build the library with a non-default localization model, then the appropriate pre-processor symbol (BOOST_REGEX_USE_C_LOCALE or BOOST_REGEX_USE_CPP_LOCALE) must be defined both when you build the support library, and when you include <boost/regex.hpp> or <boost/cregex.hpp> in your code. The best way to ensure this is to add the #define to <boost/regex/detail/regex_options.hpp>.

Providing a message catalogue:

In order to localize the front end of the library, you need to provide the library with the appropriate message strings contained either in a resource dll's string table (Win32 model), or a POSIX message catalogue (C or C++ models). In the latter case the messages must appear in message set zero of the catalogue. The messages and their id's are as follows:
 

  Message id Meaning Default value  
  101 The character used to start a sub-expression. "("  
  102 The character used to end a sub-expression declaration. ")"  
  103 The character used to denote an end of line assertion. "$"  
  104 The character used to denote the start of line assertion. "^"  
  105 The character used to denote the "match any character expression". "."  
  106 The match zero or more times repetition operator. "*"  
  107 The match one or more repetition operator. "+"  
  108 The match zero or one repetition operator. "?"  
  109 The character set opening character. "["  
  110 The character set closing character. "]"  
  111 The alternation operator. "|"  
  112 The escape character. "\\"  
  113 The hash character (not currently used). "#"  
  114 The range operator. "-"  
  115 The repetition operator opening character. "{"  
  116 The repetition operator closing character. "}"  
  117 The digit characters. "0123456789"  
  118 The character which when preceded by an escape character represents the word boundary assertion. "b"  
  119 The character which when preceded by an escape character represents the non-word boundary assertion. "B"  
  120 The character which when preceded by an escape character represents the word-start boundary assertion. "<"  
  121 The character which when preceded by an escape character represents the word-end boundary assertion. ">"  
  122 The character which when preceded by an escape character represents any word character. "w"  
  123 The character which when preceded by an escape character represents a non-word character. "W"  
  124 The character which when preceded by an escape character represents a start of buffer assertion. "`A"  
  125 The character which when preceded by an escape character represents an end of buffer assertion. "'z"  
  126 The newline character. "\n"  
  127 The comma separator. ","  
  128 The character which when preceded by an escape character represents the bell character. "a"  
  129 The character which when preceded by an escape character represents the form feed character. "f"  
  130 The character which when preceded by an escape character represents the newline character. "n"  
  131 The character which when preceded by an escape character represents the carriage return character. "r"  
  132 The character which when preceded by an escape character represents the tab character. "t"  
  133 The character which when preceded by an escape character represents the vertical tab character. "v"  
  134 The character which when preceded by an escape character represents the start of a hexadecimal character constant. "x"  
  135 The character which when preceded by an escape character represents the start of an ASCII escape character. "c"  
  136 The colon character. ":"  
  137 The equals character. "="  
  138 The character which when preceded by an escape character represents the ASCII escape character. "e"  
  139 The character which when preceded by an escape character represents any lower case character. "l"  
  140 The character which when preceded by an escape character represents any non-lower case character. "L"  
  141 The character which when preceded by an escape character represents any upper case character. "u"  
  142 The character which when preceded by an escape character represents any non-upper case character. "U"  
  143 The character which when preceded by an escape character represents any space character. "s"  
  144 The character which when preceded by an escape character represents any non-space character. "S"  
  145 The character which when preceded by an escape character represents any digit character. "d"  
  146 The character which when preceded by an escape character represents any non-digit character. "D"  
  147 The character which when preceded by an escape character represents the end quote operator. "E"  
  148 The character which when preceded by an escape character represents the start quote operator. "Q"  
  149 The character which when preceded by an escape character represents a Unicode combining character sequence. "X"  
  150 The character which when preceded by an escape character represents any single character. "C"  
  151 The character which when preceded by an escape character represents end of buffer operator. "Z"  
  152 The character which when preceded by an escape character represents the continuation assertion. "G"  
  153 The character which when preceeded by (? indicates a zero width negated forward lookahead assert. !  


 

Custom error messages are loaded as follows:
 

  Message ID Error message ID Default string  
  201 REG_NOMATCH "No match"  
  202 REG_BADPAT "Invalid regular expression"  
  203 REG_ECOLLATE "Invalid collation character"  
  204 REG_ECTYPE "Invalid character class name"  
  205 REG_EESCAPE "Trailing backslash"  
  206 REG_ESUBREG "Invalid back reference"  
  207 REG_EBRACK "Unmatched [ or [^"  
  208 REG_EPAREN "Unmatched ( or \\("  
  209 REG_EBRACE "Unmatched \\{"  
  210 REG_BADBR "Invalid content of \\{\\}"  
  211 REG_ERANGE "Invalid range end"  
  212 REG_ESPACE "Memory exhausted"  
  213 REG_BADRPT "Invalid preceding regular expression"  
  214 REG_EEND "Premature end of regular expression"  
  215 REG_ESIZE "Regular expression too big"  
  216 REG_ERPAREN "Unmatched ) or \\)"  
  217 REG_EMPTY "Empty expression"  
  218 REG_E_UNKNOWN "Unknown error"  


 

Custom character class names are loaded as followed:
 

  Message ID Description Equivalent default class name  
  300 The character class name for alphanumeric characters. "alnum"  
  301 The character class name for alphabetic characters. "alpha"  
  302 The character class name for control characters. "cntrl"  
  303 The character class name for digit characters. "digit"  
  304 The character class name for graphics characters. "graph"  
  305 The character class name for lower case characters. "lower"  
  306 The character class name for printable characters. "print"  
  307 The character class name for punctuation characters. "punct"  
  308 The character class name for space characters. "space"  
  309 The character class name for upper case characters. "upper"  
  310 The character class name for hexadecimal characters. "xdigit"  
  311 The character class name for blank characters. "blank"  
  312 The character class name for word characters. "word"  
  313 The character class name for Unicode characters. "unicode"  


 

Finally, custom collating element names are loaded starting from message id 400, and terminating when the first load thereafter fails. Each message looks something like: "tagname string" where tagname is the name used inside [[.tagname.]] and string is the actual text of the collating element. Note that the value of collating element [[.zero.]] is used for the conversion of strings to numbers - if you replace this with another value then that will be used for string parsing - for example use the Unicode character 0x0660 for [[.zero.]] if you want to use Unicode Arabic-Indic digits in your regular expressions in place of Latin digits.

Note that the POSIX defined names for character classes and collating elements are always available - even if custom names are defined, in contrast, custom error messages, and custom syntax messages replace the default ones.


Appendix 4: Example Applications

There are three demo applications that ship with this library, they all come with makefiles for Borland, Microsoft and gcc compilers, otherwise you will have to create your own makefiles.

regress.exe:

A regression test application that gives the matching/searching algorithms a full workout. The presence of this program is your guarantee that the library will behave as claimed - at least as far as those items tested are concerned - if anyone spots anything that isn't being tested I'd be glad to hear about it.

Files: parse.cpp, regress.cpp, tests.cpp.

jgrep.exe

A simple grep implementation, run with no command line options to find out its usage. Look at fileiter.cpp/fileiter.hpp and the mapfile class to see an example of a "smart" bidirectional iterator that can be used with regex++ or any other STL algorithm.

Files: jgrep.cpp, main.cpp.

timer.exe

A simple interactive expression matching application, the results of all matches are timed, allowing the programmer to optimize their regular expressions where performance is critical.

Files: regex_timer.cpp.

The snippets examples contain the code examples used in the documentation:

regex_match_example.cpp: ftp based regex_match example.

regex_search_example.cpp: regex_search example: searches a cpp file for class definitions.

regex_grep_example_1.cpp: regex_grep example 1: searches a cpp file for class definitions.

regex_merge_example.cpp: regex_merge example: converts a C++ file to syntax highlighted HTML.

regex_grep_example_2.cpp: regex_grep example 2: searches a cpp file for class definitions, using a global callback function.

regex_grep_example_3.cpp: regex_grep example 2: searches a cpp file for class definitions, using a bound member function callback.

regex_grep_example_4.cpp: regex_grep example 2: searches a cpp file for class definitions, using a C++ Builder closure as a callback.

regex_split_example_1.cpp: regex_split example: split a string into tokens.

regex_split_example_2.cpp: regex_split example: spit out linked URL's.


Appendix 5: Header Files

There are two main headers used by this library: <boost/regex.hpp> provides full access to the entire library, while <boost/cregex.hpp> provides access to just the high level class RegEx, and the POSIX API functions.


Appendix 6: Redistributables

 If you are using Microsoft or Borland C++ and link to a dll version of the run time library, then you will also link to one of the dll versions of regex++. While these dll's are redistributable, there are no "standard" versions, so when installing on the users PC, you should place these in a directory private to your application, and not in the PC's directory path. Note that if you link to a static version of your run time library, then you will also link to a static version of regex++ and no dll's will need to be distributed. The possible regex++ dll and library names are computed according to the following formula:

"boost_regex_"
+ BOOST_LIB_TOOLSET
+ "_"
+ BOOST_LIB_THREAD_OPT
+ BOOST_LIB_RT_OPT
+ BOOST_LIB_LINK_OPT
+ BOOST_LIB_DEBUG_OPT

These are defined as:

BOOST_LIB_TOOLSET: The compiler toolset name (vc6, vc7, bcb5 etc).

BOOST_LIB_THREAD_OPT: "s" for single thread builds,
"m" for multithread builds.

BOOST_LIB_RT_OPT: "s" for static runtime,
"d" for dynamic runtime.

BOOST_LIB_LINK_OPT: "s" for static link,
"i" for dynamic link.

BOOST_LIB_DEBUG_OPT: nothing for release builds,
"d" for debug builds,
"dd" for debug-diagnostic builds (_STLP_DEBUG).

Note: you can disable automatic library selection by defining the symbol BOOST_REGEX_NO_LIB when compiling, this is useful if you want to statically link even though you're using the dll version of your run time library, or if you need to debug regex++.


Notes for upgraders

This version of regex++ is the first to be ported to the boost project, and as a result has a number of changes to comply with the boost coding guidelines.

Headers have been changed from <header> or <header.h> to <boost/header.hpp>

The library namespace has changed from "jm", to "boost".

The reg_xxx algorithms have been renamed regex_xxx (to improve naming consistency).

Algorithm query_match has been renamed regex_match, and only returns true if the expression matches the whole of the input string (think input data validation).

Compiling existing code:

The directory, libs/regex/old_include contains a set of headers that make this version of regex++ compatible with previous ones, either add this directory to your include path, or copy these headers to the root directory of your boost installation. The contents of these headers are deprecated and undocumented - really these are just here for existing code - for new projects use the new header forms.


Further Information (Contacts and Acknowledgements)

The author can be contacted at John_Maddock@compuserve.com, the home page for this library is at http://ourworld.compuserve.com/homepages/John_Maddock/regexpp.htm, and the official boost version can be obtained from www.boost.org/libraries.htm.

I am indebted to Robert Sedgewick's "Algorithms in C++" for forcing me to think about algorithms and their performance, and to the folks at boost for forcing me to think, period. The following people have all contributed useful comments or fixes: Dave Abrahams, Mike Allison, Edan Ayal, Jayashree Balasubramanian, Jan Bölsche, Beman Dawes, Paul Baxter, David Bergman, David Dennerline, Edward Diener, Peter Dimov, Robert Dunn, Fabio Forno, Tobias Gabrielsson, Rob Gillen, Marc Gregoire, Chris Hecker, Nick Hodapp, Jesse Jones, Martin Jost, Boris Krasnovskiy, Jan Hermelink, Max Leung, Wei-hao Lin, Jens Maurer, Richard Peters, Heiko Schmidt, Jason Shirk, Gerald Slacik, Scobie Smith, Mike Smyth, Alexander Sokolovsky, Hervé Poirier, Michael Raykh, Marc Recht, Scott VanCamp, Bruno Voigt, Alexey Voinov, Jerry Waldorf, Rob Ward, Lealon Watts, Thomas Witt and Yuval Yosef. I am also grateful to the manuals supplied with the Henry Spencer, Perl and GNU regular expression libraries - wherever possible I have tried to maintain compatibility with these libraries and with the POSIX standard - the code however is entirely my own, including any bugs! I can absolutely guarantee that I will not fix any bugs I don't know about, so if you have any comments or spot any bugs, please get in touch.

Useful further information can be found at:

A short tutorial on regular expressions can be found here.

The Open Unix Specification contains a wealth of useful material, including the regular expression syntax, and specifications for <regex.h> and <nl_types.h>.

The Pattern Matching Pointers site is a "must visit" resource for anyone interested in pattern matching.

Glimpse and Agrep, use a simplified regular expression syntax to achieve faster search times.

Udi Manber and Ricardo Baeza-Yates both have a selection of useful pattern matching papers available from their respective web sites.


Copyright Dr John Maddock 1998-2000 all rights reserved.