diff options
-rw-r--r-- | COPYING | 504 | ||||
-rwxr-xr-x | GrokHtml.c | 343 | ||||
-rwxr-xr-x | GrokHtml.java | 73 | ||||
-rw-r--r-- | Makefile | 57 | ||||
-rwxr-xr-x | TestIt.java | 172 | ||||
-rw-r--r-- | regex/COPYRIGHT | 20 | ||||
-rw-r--r-- | regex/Makefile | 130 | ||||
-rw-r--r-- | regex/README | 32 | ||||
-rw-r--r-- | regex/WHATSNEW | 108 | ||||
-rw-r--r-- | regex/cclass.h | 27 | ||||
-rw-r--r-- | regex/cname.h | 102 | ||||
-rw-r--r-- | regex/debug.c | 242 | ||||
-rw-r--r-- | regex/debug.ih | 14 | ||||
-rw-r--r-- | regex/engine.c | 1019 | ||||
-rw-r--r-- | regex/engine.ih | 35 | ||||
-rw-r--r-- | regex/main.c | 510 | ||||
-rw-r--r-- | regex/main.ih | 19 | ||||
-rwxr-xr-x | regex/mkh | 76 | ||||
-rw-r--r-- | regex/regcomp.c | 1603 | ||||
-rw-r--r-- | regex/regcomp.ih | 51 | ||||
-rw-r--r-- | regex/regerror.c | 126 | ||||
-rw-r--r-- | regex/regerror.ih | 12 | ||||
-rw-r--r-- | regex/regex.3 | 509 | ||||
-rw-r--r-- | regex/regex.7 | 235 | ||||
-rw-r--r-- | regex/regex.h | 74 | ||||
-rw-r--r-- | regex/regex2.h | 134 | ||||
-rw-r--r-- | regex/regexec.c | 138 | ||||
-rw-r--r-- | regex/regfree.c | 37 | ||||
-rw-r--r-- | regex/split.c | 316 | ||||
-rw-r--r-- | regex/tests | 477 | ||||
-rw-r--r-- | regex/utils.h | 22 | ||||
-rw-r--r-- | test.html | 11 | ||||
-rw-r--r-- | treexpr.c | 1145 | ||||
-rw-r--r-- | treexpr.h | 107 |
34 files changed, 8480 insertions, 0 deletions
@@ -0,0 +1,504 @@ + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. + + <one line to give the library's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James Random Hacker. + + <signature of Ty Coon>, 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! + + diff --git a/GrokHtml.c b/GrokHtml.c new file mode 100755 index 0000000..2314336 --- /dev/null +++ b/GrokHtml.c @@ -0,0 +1,343 @@ +/* GrokHtml.c - Tree expression language JNI interface source file + + Copyright (C) 2005 Dell, Inc. + + Authors: David Barksdale <amatus@ocgnet.org> + + + + This library is free software; you can redistribute it and/or + + modify it under the terms of the GNU Lesser General Public + + License as published by the Free Software Foundation; either + + version 2.1 of the License, or (at your option) any later version. + + + + This library is distributed in the hope that it will be useful, + + but WITHOUT ANY WARRANTY; without even the implied warranty of + + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + + Lesser General Public License for more details. + + + + You should have received a copy of the GNU Lesser General Public + + License along with this library; if not, write to the Free Software + + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include <ctype.h> +#include <string.h> +#include <jni.h> +#include <libxml/HTMLtree.h> +#include <libxml/HTMLparser.h> +#include "treexpr.h" +#include "GrokHtml.h" + +#ifdef HTML_PARSE_RECOVER +#define PARSER_OPTIONS ( HTML_PARSE_RECOVER | HTML_PARSE_NOERROR | HTML_PARSE_NOWARNING ) +#else +#define PARSER_OPTIONS ( HTML_PARSE_NOERROR | HTML_PARSE_NOWARNING ) +#endif + +#if 0 +/* 64-bit machine */ +#define JLONG_TO_POINTER( x ) ((void *)( x )) +#define POINTER_TO_JLONG( x ) ((jlong)( x )) +#else +/* 32-bit machine */ +#define JLONG_TO_POINTER( x ) ((void *)(int)( x )) +#define POINTER_TO_JLONG( x ) ((jlong)(int)( x )) +#endif + +/* + * Class: GrokHtml + * Method: FreeMachine + * Signature: (J)V + */ +JNIEXPORT void JNICALL Java_GrokHtml_FreeMachine( JNIEnv *env, jobject obj, jlong Machine ) +{ + free_machine((struct machine *)JLONG_TO_POINTER( Machine )); +} + +/* + * Class: GrokHtml + * Method: ParseExpression + * Signature: (Ljava/lang/String;)J + */ +JNIEXPORT jlong JNICALL Java_GrokHtml_ParseExpression( JNIEnv *env, jobject obj, jstring Expression ) +{ + const char *expr, *residue; + struct machine *m; + + expr = (char *)(*env)->GetStringUTFChars( env, Expression, JNI_FALSE ); + residue = parse_treexpr( expr, &m ); + if( residue == NULL ) + { + jclass exc; + jmethodID id; + jstring message; + jobject ex; + + /* + * There was an error parsing, throw Java exception + */ + + /* First lookup the java.text.ParseException class */ + exc = (*env)->FindClass( env, "java/text/ParseException" ); + if( exc == NULL ) + return 0; + + /* Grab the method ID for the constructor: ParseException( String s, int errorOffset ) */ + id = (*env)->GetMethodID( env, exc, "<init>", "(Ljava/lang/String;I)V" ); + if( id == 0 ) + return 0; + + /* Convert the error message from the parser to a java string object */ + message = (*env)->NewStringUTF( env, m->error ); + + /* Create the exception object */ + /* NB: m->buf is a pointer into the origional string where the error occured, so we + take the difference from expr to find errorOffset, this will not be accurate if + the string contained any non-ASCII characters */ + ex = (*env)->NewObject( env, exc, id, message, (jint)( m->buf - expr )); + + /* Throw it */ + (*env)->Throw( env, ex ); + + /* Free the left-over memory used by the parser */ + free_machine( m ); + (*env)->ReleaseStringUTFChars( env, Expression, expr ); + return 0; + } + + /* + * If residue is an empty string here then the entire thing was read as an expression. + * It might be considered an error if there is some stuff left over, but it also might + * be usefull to ignore it to be a little more robust. For now it's ignored. + */ + + /* Clean up and return the pointer as a long */ + (*env)->ReleaseStringUTFChars( env, Expression, expr ); + return POINTER_TO_JLONG( m ); +} + +/* + * Class: GrokHtml + * Method: FreeDocument + * Signature: (J)V + */ +JNIEXPORT void JNICALL Java_GrokHtml_FreeDocument( JNIEnv *env, jobject obj, jlong Document ) +{ + xmlFreeDoc((htmlDocPtr)JLONG_TO_POINTER( Document )); +} + +/* + * Class: GrokHtml + * Method: OpenDocumentFromURI + * Signature: (Ljava/lang/String;)J + */ +JNIEXPORT jlong JNICALL Java_GrokHtml_OpenDocumentFromURI( JNIEnv *env, jobject obj, jstring URI ) +{ + const char *uri; + htmlDocPtr doc; + + uri = (char *)(*env)->GetStringUTFChars( env, URI, JNI_FALSE ); + doc = htmlReadFile( uri, NULL, PARSER_OPTIONS ); + (*env)->ReleaseStringUTFChars( env, URI, uri ); + if( doc == NULL ) + { + jclass exc; + + /* Throw a runtime exception */ + exc = (*env)->FindClass( env, "java/lang/RuntimeException" ); + if( exc == NULL ) + return 0; + + (*env)->ThrowNew( env, exc, "Error opening HTML document" ); + return 0; + } + return POINTER_TO_JLONG( doc ); +} +
+/*
+ * Class: GrokHtml
+ * Method: OpenDocumentFromBytes
+ * Signature: ([B)J
+ */
+JNIEXPORT jlong JNICALL Java_GrokHtml_OpenDocumentFromBytes( JNIEnv *env, jobject obj,
+ jbyteArray Bytes )
+{
+ jsize len;
+ jbyte *bytes;
+ htmlDocPtr doc;
+
+ len = (*env)->GetArrayLength( env, Bytes );
+ bytes = (*env)->GetByteArrayElements( env, Bytes, NULL );
+ doc = htmlReadMemory((char *)bytes, len, NULL, NULL, PARSER_OPTIONS );
+ (*env)->ReleaseByteArrayElements( env, Bytes, bytes, JNI_ABORT );
+ if( doc == NULL )
+ {
+ jclass exc;
+
+ /* Throw a runtime exception */
+ exc = (*env)->FindClass( env, "java/lang/RuntimeException" );
+ if( exc == NULL )
+ return 0;
+
+ (*env)->ThrowNew( env, exc, "Error opening HTML document" );
+ return 0;
+ }
+ return POINTER_TO_JLONG( doc );
+
+}
+ +/* + * Class: GrokHtml + * Method: OpenDocumentFromString + * Signature: (Ljava/lang/String;)J + */ +JNIEXPORT jlong JNICALL Java_GrokHtml_OpenDocumentFromString( JNIEnv *env, jobject obj,
+ jstring Document ) +{ + const char *document; + htmlDocPtr doc; + + document = (char *)(*env)->GetStringUTFChars( env, Document, JNI_FALSE ); + doc = htmlReadMemory( document, strlen( document ), NULL, + NULL, PARSER_OPTIONS ); + (*env)->ReleaseStringUTFChars( env, Document, document ); + if( doc == NULL ) + { + jclass exc; + + /* Throw a runtime exception */ + exc = (*env)->FindClass( env, "java/lang/RuntimeException" ); + if( exc == NULL ) + return 0; + + (*env)->ThrowNew( env, exc, "Error opening HTML document" ); + return 0; + } + return POINTER_TO_JLONG( doc ); +} + +/* + * Class: GrokHtml + * Method: SearchDocument + * Signature: (JLjava/lang/String;J)Ljava/lang/String; + */ +JNIEXPORT jstring JNICALL Java_GrokHtml_SearchDocument( JNIEnv *env, jobject obj, jlong Document, + jstring Pattern, jlong Machine ) +{ + const char *pattern; + struct match *z; + struct regex_match **re, *cur; + char *buf; + jstring retval; + int i, j, k, sub, len; + + /* Search the document */ + z = document_process((struct machine *)JLONG_TO_POINTER( Machine ), + (htmlDocPtr)JLONG_TO_POINTER( Document )); + if( z == NULL ) + { + jclass exc; + + /* Throw a runtime exception */ + exc = (*env)->FindClass( env, "java/lang/RuntimeException" ); + if( exc == NULL ) + return NULL; + + (*env)->ThrowNew( env, exc, "No match found" ); + + /* Clean up and return */ + return NULL; + } + + /* Count subexpressions */ + pattern = (char *)(*env)->GetStringUTFChars( env, Pattern, JNI_FALSE ); + sub = 0; + for( i = 0; pattern[i] != 0; i++ ) + if( pattern[i] == '\\' && isdigit( pattern[i + 1] ) && sub < pattern[i + 1] - '0' ) + sub = pattern[i + 1] - '0'; + + /* Allocate an array for matches, only enough to hold what we're going to use */ + re = malloc( sub * sizeof( struct regex_match * )); + if( re == NULL ) + { + jclass exc; + + /* Throw an out of memory error */ + exc = (*env)->FindClass( env, "java/lang/OutOfMemoryError" ); + if( exc == NULL ) + return NULL; + + (*env)->ThrowNew( env, exc, "Unable to allocate memory" ); + + /* Clean up and return */ + (*env)->ReleaseStringUTFChars( env, Pattern, pattern ); + return NULL; + } + + /* Fill in array */ + for( i = 0, cur = z->re; cur != NULL && i < sub; cur = cur->next, i++ ) + re[i] = cur; + if( i < sub ) + { + jclass exc; + + /* Throw an index out of bounds exception */ + exc = (*env)->FindClass( env, "java/lang/IndexOutOfBoundsException" ); + if( exc == NULL ) + return NULL; + + (*env)->ThrowNew( env, exc, "Not enough matches to satisfy pattern" ); + + /* Clean up and return */ + free( re ); + (*env)->ReleaseStringUTFChars( env, Pattern, pattern ); + return NULL; + } + + /* Calculate size of output buffer */ + len = 1; + for( i = j = 0; pattern[i] != 0; i++ ) + if( pattern[i] == '\\' && isdigit( pattern[i + 1] )) + { + sub = pattern[++i] - '1'; + for( k = re[sub]->match.rm_so; k < re[sub]->match.rm_eo; k++ ) + len++; + } + else + len++; + + /* Allocate output buffer */ + buf = malloc( len ); + if( buf == NULL ) + { + jclass exc; + + /* Throw an out of memory error */ + exc = (*env)->FindClass( env, "java/lang/OutOfMemoryError" ); + if( exc == NULL ) + return NULL; + + (*env)->ThrowNew( env, exc, "Unable to allocate memory" ); + + /* Clean up and return */ + free( re ); + (*env)->ReleaseStringUTFChars( env, Pattern, pattern ); + return NULL; + } + + /* Fill in output buffer */ + for( i = j = 0; pattern[i] != 0; i++ ) + if( pattern[i] == '\\' && isdigit( pattern[i + 1] )) + { + sub = pattern[++i] - '1'; + for( k = re[sub]->match.rm_so; k < re[sub]->match.rm_eo; k++ ) + buf[j++] = re[sub]->str[k]; + } + else + buf[j++] = pattern[i]; + buf[j++] = 0; + + /* Clean up and return the string */ + free( re ); + (*env)->ReleaseStringUTFChars( env, Pattern, pattern ); + retval = (*env)->NewStringUTF( env, buf ); + free( buf ); + return retval; +} diff --git a/GrokHtml.java b/GrokHtml.java new file mode 100755 index 0000000..a78159e --- /dev/null +++ b/GrokHtml.java @@ -0,0 +1,73 @@ +/* GrokHtml.java - Tree expression language JNI interface source file + + Copyright (C) 2005 Dell, Inc. + + Authors: David Barksdale <amatus@ocgnet.org> + + + + This library is free software; you can redistribute it and/or + + modify it under the terms of the GNU Lesser General Public + + License as published by the Free Software Foundation; either + + version 2.1 of the License, or (at your option) any later version. + + + + This library is distributed in the hope that it will be useful, + + but WITHOUT ANY WARRANTY; without even the implied warranty of + + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + + Lesser General Public License for more details. + + + + You should have received a copy of the GNU Lesser General Public + + License along with this library; if not, write to the Free Software + + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +class GrokHtml { + /* + * Free memory associated with a machine pointer + */ + public native void FreeMachine( long Machine ); + + /* + * Compile a tree expression into a machine, we return a machine pointer for use + * with the SearchDocument function + */ + public native long ParseExpression( String Expression ) + throws java.text.ParseException; + + /* + * Free memory associated with an document pointer + */ + public native void FreeDocument( long Document ); + + /* + * Open an HTML document from the specified URI, for example http://example.com/file.html + * we return a document pointer for use with the SearchDocument function + */ + public native long OpenDocumentFromURI( String URI ) + throws java.lang.RuntimeException; +
+ /*
+ * Parse a byte[] as an HTML document, we return a document pointer for use with
+ * the SearchDocument function
+ */
+ public native long OpenDocumentFromBytes( byte[] Document )
+ throws java.lang.RuntimeException;
+ + /* + * Parse a string as an HTML document, we return a document pointer for use with + * the SearchDocument function. You might run into some character set problems
+ * using this function; for best results use OpenDocumentFromBytes using the exact
+ * bytes returned from the web server + */ + public native long OpenDocumentFromString( String Document ) + throws java.lang.RuntimeException; + + /* + * Search the given Document using the given Machine, the resulting matches are + * are copied into a new string using the Pattern string as a template + */ + public native String SearchDocument( long Document, String Pattern, long Machine ) + throws java.lang.RuntimeException, java.lang.OutOfMemoryError, + java.lang.IndexOutOfBoundsException; + + /* + * These native functions are defined in GrokHtml.dll (or GrokHtml.so) + */ + static { System.loadLibrary( "GrokHtml" ); } +}
\ No newline at end of file diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..589cbfa --- /dev/null +++ b/Makefile @@ -0,0 +1,57 @@ +# Commands to use +# for linux or freebsd or probably cygwin: +CC = gcc +RM = rm -f +JAVA = java +JAVAC = javac +JAVAH = javah + +# Shared object prefix and suffix +# for linux: +LIB = lib +DOTSO = .so +# for windows or cygwin: +# LIB = +# DOTSO = .dll + +# Source files +SOURCES = regex/regcomp.c regex/regerror.c regex/regexec.c regex/regfree.c \ + treexpr.c GrokHtml.c + +# libxml2 flags +XMLINCL = $(shell xml2-config --cflags) +XMLLIBS = $(shell xml2-config --libs) + +# java flags +# for linux using SUN jdk15: +# JAVAINCL = -I/opt/jdk-1.5.0/include -I/opt/jdk-1.5.0/include/linux +# for linux using sablevm: +JAVAINCL = -I/usr/include/sablevm +# for freebsd using jdk15 from portage: +# JAVAINCL = -I/usr/local/jdk1.5.0/include -I/usr/local/jdk1.5.0/include/freebsd + +INCL = -I./regex $(XMLINCL) $(JAVAINCL) +LIBS = $(XMLLIBS) +CFLAGS += -O2 -Wall + +all: $(LIB)GrokHtml$(DOTSO) + +GrokHtml.h: GrokHtml.class + $(JAVAH) -classpath . -jni -o $@ GrokHtml + +GrokHtml.class: GrokHtml.java + $(JAVAC) $< + +TestIt.class: TestIt.java + $(JAVAC) $< + +$(LIB)GrokHtml$(DOTSO): $(SOURCES) GrokHtml.h + $(CC) $(LIBS) $(CFLAGS) $(INCL) -shared -o $@ $(SOURCES) + +test: $(LIB)GrokHtml$(DOTSO) TestIt.class + LD_LIBRARY_PATH=$(LD_LIBRARY_PATH):. $(JAVA) TestIt + +clean: + $(RM) $(LIB)GrokHtml$(DOTSO) + $(RM) GrokHtml.h + $(RM) *.class diff --git a/TestIt.java b/TestIt.java new file mode 100755 index 0000000..74088d1 --- /dev/null +++ b/TestIt.java @@ -0,0 +1,172 @@ +class TestIt +{ + public static void main( String[] args ) + { + GrokHtml foo = new GrokHtml(); + long m1 = 0, m2 = 0, doc1 = 0, doc2 = 0; + String expr; + + /* Parse an easy expression */ + expr = "tr -> td -> text:\"foo = (.*)\""; + try + { + m1 = foo.ParseExpression( expr ); + System.out.println( "Expression 1 parsed correctly" ); + } + catch( java.text.ParseException e ) + { + System.out.println( "Error parsing expression 1: " + e.getMessage( ) + "\n" + expr ); + int i, off = e.getErrorOffset( ); + for( i = 0; i < off; i++ ) + System.out.print( " " ); + System.out.println( "^" ); + } + + /* Parse another easy expression */ + expr = "tr -> td -> text:\"bar = (.*)\""; + try + { + m2 = foo.ParseExpression( expr ); + System.out.println( "Expression 2 parsed correctly" ); + } + catch( java.text.ParseException e ) + { + System.out.println( "Error parsing expression 2: " + e.getMessage( ) + "\n" + expr ); + int i, off = e.getErrorOffset( ); + for( i = 0; i < off; i++ ) + System.out.print( " " ); + System.out.println( "^" ); + } + + /* Parse a broken expression */ + expr = "table<border=\"0\" foo=>"; + try + { + long m = foo.ParseExpression( expr ); + System.out.println( "This expression should not parse correctly" ); + } + catch( java.text.ParseException e ) + { + System.out.println( "Error parsing broken expression: " + e.getMessage( ) + "\n" + expr ); + int i, off = e.getErrorOffset( ); + for( i = 0; i < off; i++ ) + System.out.print( " " ); + System.out.println( "^" ); + } + + /* Open a document from a byte[] */ + try + { + String testdoc = "<h1>Foo!</h1><h2>Bar!</h2><table><tr><td>foo = baz</td></tr></table>"; + doc1 = foo.OpenDocumentFromBytes( testdoc.getBytes( "US-ASCII" )); + System.out.println( "Document opened successfully from a string" ); + } + catch( java.lang.RuntimeException e ) + { + System.out.println( e.getMessage( )); + }
+ catch( java.io.UnsupportedEncodingException e )
+ {
+ System.out.println( e.getMessage( ));
+ } + + /* Open a document from a URI */ + try + { + doc2 = foo.OpenDocumentFromURI( "test.html" ); + System.out.println( "Document opened successfully from a URI" ); + } + catch( java.lang.RuntimeException e ) + { + System.out.println( e.getMessage( )); + } + + /* Try both machines on doc 1 */ + if( doc1 != 0 ) + { + if( m1 != 0 ) + { + try + { + String result = foo.SearchDocument( doc1, "foo is \\1", m1 ); + System.out.println( "Expression 1 on doc 1: " + result ); + } + catch( java.lang.RuntimeException e ) + { + System.out.println( e.getMessage( )); + } + catch( java.lang.OutOfMemoryError e ) + { + System.out.println( e.getMessage( )); + } + } + + if( m2 != 0 ) + { + try + { + String result = foo.SearchDocument( doc1, "bar is \\1", m2 ); + System.out.println( "Expression 2 on doc 1: " + result ); + } + catch( java.lang.RuntimeException e ) + { + System.out.println( "This error is ok: " + e.getMessage( )); + } + catch( java.lang.OutOfMemoryError e ) + { + System.out.println( e.getMessage( )); + } + } + + /* Free it now that we're finished */ + foo.FreeDocument( doc1 ); + } + + /* Try both machines on doc 2 */ + if( doc2 != 0 ) + { + if( m1 != 0 ) + { + try + { + String result = foo.SearchDocument( doc2, "foo is \\1", m1 ); + System.out.println( "Expression 1 on doc 2: " + result ); + } + catch( java.lang.RuntimeException e ) + { + System.out.println( e.getMessage( )); + } + catch( java.lang.OutOfMemoryError e ) + { + System.out.println( e.getMessage( )); + } + } + + if( m2 != 0 ) + { + try + { + String result = foo.SearchDocument( doc2, "bar is \\1", m2 ); + System.out.println( "Expression 2 on doc 2: " + result ); + } + catch( java.lang.RuntimeException e ) + { + System.out.println( e.getMessage( )); + } + catch( java.lang.OutOfMemoryError e ) + { + System.out.println( e.getMessage( )); + } + } + + /* Free it now that we're finished */ + foo.FreeDocument( doc2 ); + } + + /* Free the machines */ + if( m1 != 0 ) + foo.FreeMachine( m1 ); + if( m2 != 0 ) + foo.FreeMachine( m2 ); + } +}
\ No newline at end of file diff --git a/regex/COPYRIGHT b/regex/COPYRIGHT new file mode 100644 index 0000000..30c1f7a --- /dev/null +++ b/regex/COPYRIGHT @@ -0,0 +1,20 @@ +Copyright 1992, 1993, 1994, 1997 Henry Spencer. All rights reserved. +This software is not subject to any license of the American Telephone +and Telegraph Company or of the Regents of the University of California. + +Permission is granted to anyone to use this software for any purpose on +any computer system, and to alter it and redistribute it, subject +to the following restrictions: + +1. The author is not responsible for the consequences of use of this + software, no matter how awful, even if they arise from flaws in it. + +2. The origin of this software must not be misrepresented, either by + explicit claim or by omission. Since few users ever read sources, + credits must appear in the documentation. + +3. Altered versions must be plainly marked as such, and must not be + misrepresented as being the original software. Since few users + ever read sources, credits must appear in the documentation. + +4. This notice may not be removed or altered. diff --git a/regex/Makefile b/regex/Makefile new file mode 100644 index 0000000..3882b37 --- /dev/null +++ b/regex/Makefile @@ -0,0 +1,130 @@ +# You probably want to take -DREDEBUG out of CFLAGS, and put something like +# -O in, *after* testing (-DREDEBUG strengthens testing by enabling a lot of +# internal assertion checking and some debugging facilities). +# Put -Dconst= in for a pre-ANSI compiler. +# Do not take -DPOSIX_MISTAKE out. +# REGCFLAGS isn't important to you (it's for my use in some special contexts). +CFLAGS=-I. -DPOSIX_MISTAKE -DREDEBUG $(REGCFLAGS) + +# If you have a pre-ANSI compiler, put -o into MKHFLAGS. If you want +# the Berkeley __P macro, put -b in. +MKHFLAGS= + +# Flags for linking but not compiling, if any. +LDFLAGS= + +# Extra libraries for linking, if any. +LIBS= + +# Internal stuff, should not need changing. +OBJPRODN=regcomp.o regexec.o regerror.o regfree.o +OBJS=$(OBJPRODN) split.o debug.o main.o +H=cclass.h cname.h regex2.h utils.h +REGSRC=regcomp.c regerror.c regexec.c regfree.c +ALLSRC=$(REGSRC) engine.c debug.c main.c split.c + +# Stuff that matters only if you're trying to lint the package. +LINTFLAGS=-I. -Dstatic= -Dconst= -DREDEBUG +LINTC=regcomp.c regexec.c regerror.c regfree.c debug.c main.c +JUNKLINT=possible pointer alignment|null effect + +# arrangements to build forward-reference header files +.SUFFIXES: .ih .h +.c.ih: + sh ./mkh $(MKHFLAGS) -p $< >$@ + +default: r + +lib: purge $(OBJPRODN) + rm -f libregex.a + ar crv libregex.a $(OBJPRODN) + +purge: + rm -f *.o + +# stuff to build regex.h +REGEXH=regex.h +REGEXHSRC=regex2.h $(REGSRC) +$(REGEXH): $(REGEXHSRC) mkh + sh ./mkh $(MKHFLAGS) -i _REGEX_H_ $(REGEXHSRC) >regex.tmp + cmp -s regex.tmp regex.h 2>/dev/null || cp regex.tmp regex.h + rm -f regex.tmp + +# dependencies +$(OBJPRODN) debug.o: utils.h regex.h regex2.h +regcomp.o: cclass.h cname.h regcomp.ih +regexec.o: engine.c engine.ih +regerror.o: regerror.ih +debug.o: debug.ih +main.o: main.ih + +# tester +re: $(OBJS) + $(CC) $(CFLAGS) $(LDFLAGS) $(OBJS) $(LIBS) -o $@ + +# regression test +r: re tests + ./re <tests + ./re -el <tests + ./re -er <tests + +# 57 variants, and other stuff, for development use -- not useful to you +ra: ./re tests + -./re <tests + -./re -el <tests + -./re -er <tests + +rx: ./re tests + ./re -x <tests + ./re -x -el <tests + ./re -x -er <tests + +t: ./re tests + -time ./re <tests + -time ./re -cs <tests + -time ./re -el <tests + -time ./re -cs -el <tests + +l: $(LINTC) + lint $(LINTFLAGS) -h $(LINTC) 2>&1 | egrep -v '$(JUNKLINT)' | tee lint + +fullprint: + ti README WHATSNEW notes todo | list + ti *.h | list + list *.c + list regex.3 regex.7 + +print: + ti README WHATSNEW notes todo | list + ti *.h | list + list reg*.c engine.c + + +mf.tmp: Makefile + sed '/^REGEXH=/s/=.*/=regex.h/' Makefile | sed '/#DEL$$/d' >$@ + +DTRH=cclass.h cname.h regex2.h utils.h +PRE=COPYRIGHT README WHATSNEW +POST=mkh regex.3 regex.7 tests $(DTRH) $(ALLSRC) fake/*.[ch] +FILES=$(PRE) Makefile $(POST) +DTR=$(PRE) Makefile=mf.tmp $(POST) +dtr: $(FILES) mf.tmp + makedtr $(DTR) >$@ + rm mf.tmp + +cio: $(FILES) + cio $(FILES) + +rdf: $(FILES) + rcsdiff -c $(FILES) 2>&1 | p + +# various forms of cleanup +tidy: + rm -f junk* core core.* *.core dtr *.tmp lint + +clean: tidy + rm -f *.o *.s *.ih re libregex.a + +# don't do this one unless you know what you're doing +spotless: clean + rm -f mkh regex.h diff --git a/regex/README b/regex/README new file mode 100644 index 0000000..e6ce373 --- /dev/null +++ b/regex/README @@ -0,0 +1,32 @@ +alpha3.8 release. +Tue Aug 10 15:51:48 EDT 1999 +henry@spsystems.net (formerly henry@zoo.toronto.edu) + +See WHATSNEW for change listing. + +installation notes: +-------- +Read the comments at the beginning of Makefile before running. + +Utils.h contains some things that just might have to be modified on +some systems, as well as a nested include (ugh) of <assert.h>. + +The "fake" directory contains quick-and-dirty fakes for some header +files and routines that old systems may not have. Note also that +-DUSEBCOPY will make utils.h substitute bcopy() for memmove(). + +After that, "make r" will build regcomp.o, regexec.o, regfree.o, +and regerror.o (the actual routines), bundle them together into a test +program, and run regression tests on them. No output is good output. + +"make lib" builds just the .o files for the actual routines (when +you're happy with testing and have adjusted CFLAGS for production), +and puts them together into libregex.a. You can pick up either the +library or *.o ("make lib" makes sure there are no other .o files left +around to confuse things). + +Main.c, debug.c, split.c are used for regression testing but are not part +of the RE routines themselves. + +Regex.h goes in /usr/include. All other .h files are internal only. +-------- diff --git a/regex/WHATSNEW b/regex/WHATSNEW new file mode 100644 index 0000000..1295343 --- /dev/null +++ b/regex/WHATSNEW @@ -0,0 +1,108 @@ +New in alpha3.8: Bug fix for signed/unsigned mixup, found and fixed +by the FreeBSD folks. + +New in alpha3.7: A bit of cleanup aimed at maximizing portability, +possibly at slight cost in efficiency. "ul" suffixes and "unsigned long" +no longer appear, in particular. + +New in alpha3.6: A couple more portability glitches fixed. + +New in alpha3.5: Active development of this code has been stopped -- +I'm working on a complete reimplementation -- but folks have found some +minor portability glitches and the like, hence this release to fix them. +One penalty: slightly reduced compatibility with old compilers, because +the ANSI C `unsigned long' type and `ul' constant suffix are used in a +few places (I could avoid this but it would be considerably more work). + +New in alpha3.4: The complex bug alluded to below has been fixed (in a +slightly kludgey temporary way that may hurt efficiency a bit; this is +another "get it out the door for 4.4" release). The tests at the end of +the tests file have accordingly been uncommented. The primary sign of +the bug was that something like a?b matching ab matched b rather than ab. +(The bug was essentially specific to this exact situation, else it would +have shown up earlier.) + +New in alpha3.3: The definition of word boundaries has been altered +slightly, to more closely match the usual programming notion that "_" +is an alphabetic. Stuff used for pre-ANSI systems is now in a subdir, +and the makefile no longer alludes to it in mysterious ways. The +makefile has generally been cleaned up some. Fixes have been made +(again!) so that the regression test will run without -DREDEBUG, at +the cost of weaker checking. A workaround for a bug in some folks' +<assert.h> has been added. And some more things have been added to +tests, including a couple right at the end which are commented out +because the code currently flunks them (complex bug; fix coming). +Plus the usual minor cleanup. + +New in alpha3.2: Assorted bits of cleanup and portability improvement +(the development base is now a BSDI system using GCC instead of an ancient +Sun system, and the newer compiler exposed some glitches). Fix for a +serious bug that affected REs using many [] (including REG_ICASE REs +because of the way they are implemented), *sometimes*, depending on +memory-allocation patterns. The header-file prototypes no longer name +the parameters, avoiding possible name conflicts. The possibility that +some clot has defined CHAR_MIN as (say) `-128' instead of `(-128)' is +now handled gracefully. "uchar" is no longer used as an internal type +name (too many people have the same idea). Still the same old lousy +performance, alas. + +New in alpha3.1: Basically nothing, this release is just a bookkeeping +convenience. Stay tuned. + +New in alpha3.0: Performance is no better, alas, but some fixes have been +made and some functionality has been added. (This is basically the "get +it out the door in time for 4.4" release.) One bug fix: regfree() didn't +free the main internal structure (how embarrassing). It is now possible +to put NULs in either the RE or the target string, using (resp.) a new +REG_PEND flag and the old REG_STARTEND flag. The REG_NOSPEC flag to +regcomp() makes all characters ordinary, so you can match a literal +string easily (this will become more useful when performance improves!). +There are now primitives to match beginnings and ends of words, although +the syntax is disgusting and so is the implementation. The REG_ATOI +debugging interface has changed a bit. And there has been considerable +internal cleanup of various kinds. + +New in alpha2.3: Split change list out of README, and moved flags notes +into Makefile. Macro-ized the name of regex(7) in regex(3), since it has +to change for 4.4BSD. Cleanup work in engine.c, and some new regression +tests to catch tricky cases thereof. + +New in alpha2.2: Out-of-date manpages updated. Regerror() acquires two +small extensions -- REG_ITOA and REG_ATOI -- which avoid debugging kludges +in my own test program and might be useful to others for similar purposes. +The regression test will now compile (and run) without REDEBUG. The +BRE \$ bug is fixed. Most uses of "uchar" are gone; it's all chars now. +Char/uchar parameters are now written int/unsigned, to avoid possible +portability problems with unpromoted parameters. Some unsigned casts have +been introduced to minimize portability problems with shifting into sign +bits. + +New in alpha2.1: Lots of little stuff, cleanup and fixes. The one big +thing is that regex.h is now generated, using mkh, rather than being +supplied in the distribution; due to circularities in dependencies, +you have to build regex.h explicitly by "make h". The two known bugs +have been fixed (and the regression test now checks for them), as has a +problem with assertions not being suppressed in the absence of REDEBUG. +No performance work yet. + +New in alpha2: Backslash-anything is an ordinary character, not an +error (except, of course, for the handful of backslashed metacharacters +in BREs), which should reduce script breakage. The regression test +checks *where* null strings are supposed to match, and has generally +been tightened up somewhat. Small bug fixes in parameter passing (not +harmful, but technically errors) and some other areas. Debugging +invoked by defining REDEBUG rather than not defining NDEBUG. + +New in alpha+3: full prototyping for internal routines, using a little +helper program, mkh, which extracts prototypes given in stylized comments. +More minor cleanup. Buglet fix: it's CHAR_BIT, not CHAR_BITS. Simple +pre-screening of input when a literal string is known to be part of the +RE; this does wonders for performance. + +New in alpha+2: minor bits of cleanup. Notably, the number "32" for the +word width isn't hardwired into regexec.c any more, the public header +file prototypes the functions if __STDC__ is defined, and some small typos +in the manpages have been fixed. + +New in alpha+1: improvements to the manual pages, and an important +extension, the REG_STARTEND option to regexec(). diff --git a/regex/cclass.h b/regex/cclass.h new file mode 100644 index 0000000..d892103 --- /dev/null +++ b/regex/cclass.h @@ -0,0 +1,27 @@ +/* character-class table */ +static struct cclass { + char *name; + char *chars; + char *multis; +} cclasses[] = { + {"alnum", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", ""}, + {"alpha", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", + ""}, + {"blank", " \t", ""}, + {"cntrl", "\007\b\t\n\v\f\r\1\2\3\4\5\6\16\17\20\21\22\23\24\25\26\27\30\31\32\33\34\35\36\37\177", ""}, + {"digit", "0123456789", ""}, + {"graph", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~", + ""}, + {"lower", "abcdefghijklmnopqrstuvwxyz", + ""}, + {"print", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ ", + ""}, + {"punct", "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~", + ""}, + {"space", "\t\n\v\f\r ", ""}, + {"upper", "ABCDEFGHIJKLMNOPQRSTUVWXYZ", + ""}, + {"xdigit", "0123456789ABCDEFabcdef", + ""}, + {NULL, 0, ""} +}; diff --git a/regex/cname.h b/regex/cname.h new file mode 100644 index 0000000..a4af252 --- /dev/null +++ b/regex/cname.h @@ -0,0 +1,102 @@ +/* character-name table */ +static struct cname { + char *name; + char code; +} cnames[] = { + {"NUL", '\0'}, + {"SOH", '\001'}, + {"STX", '\002'}, + {"ETX", '\003'}, + {"EOT", '\004'}, + {"ENQ", '\005'}, + {"ACK", '\006'}, + {"BEL", '\007'}, + {"alert", '\007'}, + {"BS", '\010'}, + {"backspace", '\b'}, + {"HT", '\011'}, + {"tab", '\t'}, + {"LF", '\012'}, + {"newline", '\n'}, + {"VT", '\013'}, + {"vertical-tab", '\v'}, + {"FF", '\014'}, + {"form-feed", '\f'}, + {"CR", '\015'}, + {"carriage-return", '\r'}, + {"SO", '\016'}, + {"SI", '\017'}, + {"DLE", '\020'}, + {"DC1", '\021'}, + {"DC2", '\022'}, + {"DC3", '\023'}, + {"DC4", '\024'}, + {"NAK", '\025'}, + {"SYN", '\026'}, + {"ETB", '\027'}, + {"CAN", '\030'}, + {"EM", '\031'}, + {"SUB", '\032'}, + {"ESC", '\033'}, + {"IS4", '\034'}, + {"FS", '\034'}, + {"IS3", '\035'}, + {"GS", '\035'}, + {"IS2", '\036'}, + {"RS", '\036'}, + {"IS1", '\037'}, + {"US", '\037'}, + {"space", ' '}, + {"exclamation-mark", '!'}, + {"quotation-mark", '"'}, + {"number-sign", '#'}, + {"dollar-sign", '$'}, + {"percent-sign", '%'}, + {"ampersand", '&'}, + {"apostrophe", '\''}, + {"left-parenthesis", '('}, + {"right-parenthesis", ')'}, + {"asterisk", '*'}, + {"plus-sign", '+'}, + {"comma", ','}, + {"hyphen", '-'}, + {"hyphen-minus", '-'}, + {"period", '.'}, + {"full-stop", '.'}, + {"slash", '/'}, + {"solidus", '/'}, + {"zero", '0'}, + {"one", '1'}, + {"two", '2'}, + {"three", '3'}, + {"four", '4'}, + {"five", '5'}, + {"six", '6'}, + {"seven", '7'}, + {"eight", '8'}, + {"nine", '9'}, + {"colon", ':'}, + {"semicolon", ';'}, + {"less-than-sign", '<'}, + {"equals-sign", '='}, + {"greater-than-sign", '>'}, + {"question-mark", '?'}, + {"commercial-at", '@'}, + {"left-square-bracket", '['}, + {"backslash", '\\'}, + {"reverse-solidus", '\\'}, + {"right-square-bracket", ']'}, + {"circumflex", '^'}, + {"circumflex-accent", '^'}, + {"underscore", '_'}, + {"low-line", '_'}, + {"grave-accent", '`'}, + {"left-brace", '{'}, + {"left-curly-bracket", '{'}, + {"vertical-line", '|'}, + {"right-brace", '}'}, + {"right-curly-bracket", '}'}, + {"tilde", '~'}, + {"DEL", '\177'}, + {NULL, 0} +}; diff --git a/regex/debug.c b/regex/debug.c new file mode 100644 index 0000000..99ce7da --- /dev/null +++ b/regex/debug.c @@ -0,0 +1,242 @@ +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#include <limits.h> +#include <stdlib.h> +#include <sys/types.h> +#include <regex.h> + +#include "utils.h" +#include "regex2.h" +#include "debug.ih" + +/* + - regprint - print a regexp for debugging + == void regprint(regex_t *r, FILE *d); + */ +void +regprint(r, d) +regex_t *r; +FILE *d; +{ + register struct re_guts *g = r->re_g; + register int i; + register int c; + register int last; + int nincat[NC]; + + fprintf(d, "%ld states, %d categories", (long)g->nstates, + g->ncategories); + fprintf(d, ", first %ld last %ld", (long)g->firststate, + (long)g->laststate); + if (g->iflags&USEBOL) + fprintf(d, ", USEBOL"); + if (g->iflags&USEEOL) + fprintf(d, ", USEEOL"); + if (g->iflags&BAD) + fprintf(d, ", BAD"); + if (g->nsub > 0) + fprintf(d, ", nsub=%ld", (long)g->nsub); + if (g->must != NULL) + fprintf(d, ", must(%ld) `%*s'", (long)g->mlen, (int)g->mlen, + g->must); + if (g->backrefs) + fprintf(d, ", backrefs"); + if (g->nplus > 0) + fprintf(d, ", nplus %ld", (long)g->nplus); + fprintf(d, "\n"); + s_print(g, d); + for (i = 0; i < g->ncategories; i++) { + nincat[i] = 0; + for (c = CHAR_MIN; c <= CHAR_MAX; c++) + if (g->categories[c] == i) + nincat[i]++; + } + fprintf(d, "cc0#%d", nincat[0]); + for (i = 1; i < g->ncategories; i++) + if (nincat[i] == 1) { + for (c = CHAR_MIN; c <= CHAR_MAX; c++) + if (g->categories[c] == i) + break; + fprintf(d, ", %d=%s", i, regchar(c)); + } + fprintf(d, "\n"); + for (i = 1; i < g->ncategories; i++) + if (nincat[i] != 1) { + fprintf(d, "cc%d\t", i); + last = -1; + for (c = CHAR_MIN; c <= CHAR_MAX+1; c++) /* +1 does flush */ + if (c <= CHAR_MAX && g->categories[c] == i) { + if (last < 0) { + fprintf(d, "%s", regchar(c)); + last = c; + } + } else { + if (last >= 0) { + if (last != c-1) + fprintf(d, "-%s", + regchar(c-1)); + last = -1; + } + } + fprintf(d, "\n"); + } +} + +/* + - s_print - print the strip for debugging + == static void s_print(register struct re_guts *g, FILE *d); + */ +static void +s_print(g, d) +register struct re_guts *g; +FILE *d; +{ + register sop *s; + register cset *cs; + register int i; + register int done = 0; + register sop opnd; + register int col = 0; + register int last; + register sopno offset = 2; +# define GAP() { if (offset % 5 == 0) { \ + if (col > 40) { \ + fprintf(d, "\n\t"); \ + col = 0; \ + } else { \ + fprintf(d, " "); \ + col++; \ + } \ + } else \ + col++; \ + offset++; \ + } + + if (OP(g->strip[0]) != OEND) + fprintf(d, "missing initial OEND!\n"); + for (s = &g->strip[1]; !done; s++) { + opnd = OPND(*s); + switch (OP(*s)) { + case OEND: + fprintf(d, "\n"); + done = 1; + break; + case OCHAR: + if (strchr("\\|()^$.[+*?{}!<> ", (char)opnd) != NULL) + fprintf(d, "\\%c", (char)opnd); + else + fprintf(d, "%s", regchar((char)opnd)); + break; + case OBOL: + fprintf(d, "^"); + break; + case OEOL: + fprintf(d, "$"); + break; + case OBOW: + fprintf(d, "\\{"); + break; + case OEOW: + fprintf(d, "\\}"); + break; + case OANY: + fprintf(d, "."); + break; + case OANYOF: + fprintf(d, "[(%ld)", (long)opnd); + cs = &g->sets[opnd]; + last = -1; + for (i = 0; i < g->csetsize+1; i++) /* +1 flushes */ + if (CHIN(cs, i) && i < g->csetsize) { + if (last < 0) { + fprintf(d, "%s", regchar(i)); + last = i; + } + } else { + if (last >= 0) { + if (last != i-1) + fprintf(d, "-%s", + regchar(i-1)); + last = -1; + } + } + fprintf(d, "]"); + break; + case OBACK_: + fprintf(d, "(\\<%ld>", (long)opnd); + break; + case O_BACK: + fprintf(d, "<%ld>\\)", (long)opnd); + break; + case OPLUS_: + fprintf(d, "(+"); + if (OP(*(s+opnd)) != O_PLUS) + fprintf(d, "<%ld>", (long)opnd); + break; + case O_PLUS: + if (OP(*(s-opnd)) != OPLUS_) + fprintf(d, "<%ld>", (long)opnd); + fprintf(d, "+)"); + break; + case OQUEST_: + fprintf(d, "(?"); + if (OP(*(s+opnd)) != O_QUEST) + fprintf(d, "<%ld>", (long)opnd); + break; + case O_QUEST: + if (OP(*(s-opnd)) != OQUEST_) + fprintf(d, "<%ld>", (long)opnd); + fprintf(d, "?)"); + break; + case OLPAREN: + fprintf(d, "((<%ld>", (long)opnd); + break; + case ORPAREN: + fprintf(d, "<%ld>))", (long)opnd); + break; + case OCH_: + fprintf(d, "<"); + if (OP(*(s+opnd)) != OOR2) + fprintf(d, "<%ld>", (long)opnd); + break; + case OOR1: + if (OP(*(s-opnd)) != OOR1 && OP(*(s-opnd)) != OCH_) + fprintf(d, "<%ld>", (long)opnd); + fprintf(d, "|"); + break; + case OOR2: + fprintf(d, "|"); + if (OP(*(s+opnd)) != OOR2 && OP(*(s+opnd)) != O_CH) + fprintf(d, "<%ld>", (long)opnd); + break; + case O_CH: + if (OP(*(s-opnd)) != OOR1) + fprintf(d, "<%ld>", (long)opnd); + fprintf(d, ">"); + break; + default: + fprintf(d, "!%d(%d)!", OP(*s), opnd); + break; + } + if (!done) + GAP(); + } +} + +/* + - regchar - make a character printable + == static char *regchar(int ch); + */ +static char * /* -> representation */ +regchar(ch) +int ch; +{ + static char buf[10]; + + if (isprint(ch) || ch == ' ') + sprintf(buf, "%c", ch); + else + sprintf(buf, "\\%o", ch); + return(buf); +} diff --git a/regex/debug.ih b/regex/debug.ih new file mode 100644 index 0000000..5f40ff7 --- /dev/null +++ b/regex/debug.ih @@ -0,0 +1,14 @@ +/* ========= begin header generated by ./mkh ========= */ +#ifdef __cplusplus +extern "C" { +#endif + +/* === debug.c === */ +void regprint(regex_t *r, FILE *d); +static void s_print(register struct re_guts *g, FILE *d); +static char *regchar(int ch); + +#ifdef __cplusplus +} +#endif +/* ========= end header generated by ./mkh ========= */ diff --git a/regex/engine.c b/regex/engine.c new file mode 100644 index 0000000..919fe3f --- /dev/null +++ b/regex/engine.c @@ -0,0 +1,1019 @@ +/* + * The matching engine and friends. This file is #included by regexec.c + * after suitable #defines of a variety of macros used herein, so that + * different state representations can be used without duplicating masses + * of code. + */ + +#ifdef SNAMES +#define matcher smatcher +#define fast sfast +#define slow sslow +#define dissect sdissect +#define backref sbackref +#define step sstep +#define print sprint +#define at sat +#define match smat +#endif +#ifdef LNAMES +#define matcher lmatcher +#define fast lfast +#define slow lslow +#define dissect ldissect +#define backref lbackref +#define step lstep +#define print lprint +#define at lat +#define match lmat +#endif + +/* another structure passed up and down to avoid zillions of parameters */ +struct match { + struct re_guts *g; + int eflags; + regmatch_t *pmatch; /* [nsub+1] (0 element unused) */ + char *offp; /* offsets work from here */ + char *beginp; /* start of string -- virtual NUL precedes */ + char *endp; /* end of string -- virtual NUL here */ + char *coldp; /* can be no match starting before here */ + char **lastpos; /* [nplus+1] */ + STATEVARS; + states st; /* current states */ + states fresh; /* states for a fresh start */ + states tmp; /* temporary */ + states empty; /* empty set of states */ +}; + +#include "engine.ih" + +#ifdef REDEBUG +#define SP(t, s, c) print(m, t, s, c, stdout) +#define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2) +#define NOTE(str) { if (m->eflags®_TRACE) printf("=%s\n", (str)); } +#else +#define SP(t, s, c) /* nothing */ +#define AT(t, p1, p2, s1, s2) /* nothing */ +#define NOTE(s) /* nothing */ +#endif + +/* + - matcher - the actual matching engine + == static int matcher(register struct re_guts *g, char *string, \ + == size_t nmatch, regmatch_t pmatch[], int eflags); + */ +static int /* 0 success, REG_NOMATCH failure */ +matcher(g, string, nmatch, pmatch, eflags) +register struct re_guts *g; +char *string; +size_t nmatch; +regmatch_t pmatch[]; +int eflags; +{ + register char *endp; + register int i; + struct match mv; + register struct match *m = &mv; + register char *dp; + const register sopno gf = g->firststate+1; /* +1 for OEND */ + const register sopno gl = g->laststate; + char *start; + char *stop; + + /* simplify the situation where possible */ + if (g->cflags®_NOSUB) + nmatch = 0; + if (eflags®_STARTEND) { + start = string + pmatch[0].rm_so; + stop = string + pmatch[0].rm_eo; + } else { + start = string; + stop = start + strlen(start); + } + if (stop < start) + return(REG_INVARG); + + /* prescreening; this does wonders for this rather slow code */ + if (g->must != NULL) { + for (dp = start; dp < stop; dp++) + if (*dp == g->must[0] && stop - dp >= g->mlen && + memcmp(dp, g->must, (size_t)g->mlen) == 0) + break; + if (dp == stop) /* we didn't find g->must */ + return(REG_NOMATCH); + } + + /* match struct setup */ + m->g = g; + m->eflags = eflags; + m->pmatch = NULL; + m->lastpos = NULL; + m->offp = string; + m->beginp = start; + m->endp = stop; + STATESETUP(m, 4); + SETUP(m->st); + SETUP(m->fresh); + SETUP(m->tmp); + SETUP(m->empty); + CLEAR(m->empty); + + /* this loop does only one repetition except for backrefs */ + for (;;) { + endp = fast(m, start, stop, gf, gl); + if (endp == NULL) { /* a miss */ + STATETEARDOWN(m); + return(REG_NOMATCH); + } + if (nmatch == 0 && !g->backrefs) + break; /* no further info needed */ + + /* where? */ + assert(m->coldp != NULL); + for (;;) { + NOTE("finding start"); + endp = slow(m, m->coldp, stop, gf, gl); + if (endp != NULL) + break; + assert(m->coldp < m->endp); + m->coldp++; + } + if (nmatch == 1 && !g->backrefs) + break; /* no further info needed */ + + /* oh my, he wants the subexpressions... */ + if (m->pmatch == NULL) + m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) * + sizeof(regmatch_t)); + if (m->pmatch == NULL) { + STATETEARDOWN(m); + return(REG_ESPACE); + } + for (i = 1; i <= m->g->nsub; i++) + m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1; + if (!g->backrefs && !(m->eflags®_BACKR)) { + NOTE("dissecting"); + dp = dissect(m, m->coldp, endp, gf, gl); + } else { + if (g->nplus > 0 && m->lastpos == NULL) + m->lastpos = (char **)malloc((g->nplus+1) * + sizeof(char *)); + if (g->nplus > 0 && m->lastpos == NULL) { + free(m->pmatch); + STATETEARDOWN(m); + return(REG_ESPACE); + } + NOTE("backref dissect"); + dp = backref(m, m->coldp, endp, gf, gl, (sopno)0); + } + if (dp != NULL) + break; + + /* uh-oh... we couldn't find a subexpression-level match */ + assert(g->backrefs); /* must be back references doing it */ + assert(g->nplus == 0 || m->lastpos != NULL); + for (;;) { + if (dp != NULL || endp <= m->coldp) + break; /* defeat */ + NOTE("backoff"); + endp = slow(m, m->coldp, endp-1, gf, gl); + if (endp == NULL) + break; /* defeat */ + /* try it on a shorter possibility */ +#ifndef NDEBUG + for (i = 1; i <= m->g->nsub; i++) { + assert(m->pmatch[i].rm_so == -1); + assert(m->pmatch[i].rm_eo == -1); + } +#endif + NOTE("backoff dissect"); + dp = backref(m, m->coldp, endp, gf, gl, (sopno)0); + } + assert(dp == NULL || dp == endp); + if (dp != NULL) /* found a shorter one */ + break; + + /* despite initial appearances, there is no match here */ + NOTE("false alarm"); + start = m->coldp + 1; /* recycle starting later */ + assert(start <= stop); + } + + /* fill in the details if requested */ + if (nmatch > 0) { + pmatch[0].rm_so = m->coldp - m->offp; + pmatch[0].rm_eo = endp - m->offp; + } + if (nmatch > 1) { + assert(m->pmatch != NULL); + for (i = 1; i < nmatch; i++) + if (i <= m->g->nsub) + pmatch[i] = m->pmatch[i]; + else { + pmatch[i].rm_so = -1; + pmatch[i].rm_eo = -1; + } + } + + if (m->pmatch != NULL) + free((char *)m->pmatch); + if (m->lastpos != NULL) + free((char *)m->lastpos); + STATETEARDOWN(m); + return(0); +} + +/* + - dissect - figure out what matched what, no back references + == static char *dissect(register struct match *m, char *start, \ + == char *stop, sopno startst, sopno stopst); + */ +static char * /* == stop (success) always */ +dissect(m, start, stop, startst, stopst) +register struct match *m; +char *start; +char *stop; +sopno startst; +sopno stopst; +{ + register int i; + register sopno ss; /* start sop of current subRE */ + register sopno es; /* end sop of current subRE */ + register char *sp; /* start of string matched by it */ + register char *stp; /* string matched by it cannot pass here */ + register char *rest; /* start of rest of string */ + register char *tail; /* string unmatched by rest of RE */ + register sopno ssub; /* start sop of subsubRE */ + register sopno esub; /* end sop of subsubRE */ + register char *ssp; /* start of string matched by subsubRE */ + register char *sep; /* end of string matched by subsubRE */ + register char *oldssp; /* previous ssp */ + register char *dp; + + AT("diss", start, stop, startst, stopst); + sp = start; + for (ss = startst; ss < stopst; ss = es) { + /* identify end of subRE */ + es = ss; + switch (OP(m->g->strip[es])) { + case OPLUS_: + case OQUEST_: + es += OPND(m->g->strip[es]); + break; + case OCH_: + while (OP(m->g->strip[es]) != O_CH) + es += OPND(m->g->strip[es]); + break; + } + es++; + + /* figure out what it matched */ + switch (OP(m->g->strip[ss])) { + case OEND: + assert(nope); + break; + case OCHAR: + sp++; + break; + case OBOL: + case OEOL: + case OBOW: + case OEOW: + break; + case OANY: + case OANYOF: + sp++; + break; + case OBACK_: + case O_BACK: + assert(nope); + break; + /* cases where length of match is hard to find */ + case OQUEST_: + stp = stop; + for (;;) { + /* how long could this one be? */ + rest = slow(m, sp, stp, ss, es); + assert(rest != NULL); /* it did match */ + /* could the rest match the rest? */ + tail = slow(m, rest, stop, es, stopst); + if (tail == stop) + break; /* yes! */ + /* no -- try a shorter match for this one */ + stp = rest - 1; + assert(stp >= sp); /* it did work */ + } + ssub = ss + 1; + esub = es - 1; + /* did innards match? */ + if (slow(m, sp, rest, ssub, esub) != NULL) { + dp = dissect(m, sp, rest, ssub, esub); + assert(dp == rest); + } else /* no */ + assert(sp == rest); + sp = rest; + break; + case OPLUS_: + stp = stop; + for (;;) { + /* how long could this one be? */ + rest = slow(m, sp, stp, ss, es); + assert(rest != NULL); /* it did match */ + /* could the rest match the rest? */ + tail = slow(m, rest, stop, es, stopst); + if (tail == stop) + break; /* yes! */ + /* no -- try a shorter match for this one */ + stp = rest - 1; + assert(stp >= sp); /* it did work */ + } + ssub = ss + 1; + esub = es - 1; + ssp = sp; + oldssp = ssp; + for (;;) { /* find last match of innards */ + sep = slow(m, ssp, rest, ssub, esub); + if (sep == NULL || sep == ssp) + break; /* failed or matched null */ + oldssp = ssp; /* on to next try */ + ssp = sep; + } + if (sep == NULL) { + /* last successful match */ + sep = ssp; + ssp = oldssp; + } + assert(sep == rest); /* must exhaust substring */ + assert(slow(m, ssp, sep, ssub, esub) == rest); + dp = dissect(m, ssp, sep, ssub, esub); + assert(dp == sep); + sp = rest; + break; + case OCH_: + stp = stop; + for (;;) { + /* how long could this one be? */ + rest = slow(m, sp, stp, ss, es); + assert(rest != NULL); /* it did match */ + /* could the rest match the rest? */ + tail = slow(m, rest, stop, es, stopst); + if (tail == stop) + break; /* yes! */ + /* no -- try a shorter match for this one */ + stp = rest - 1; + assert(stp >= sp); /* it did work */ + } + ssub = ss + 1; + esub = ss + OPND(m->g->strip[ss]) - 1; + assert(OP(m->g->strip[esub]) == OOR1); + for (;;) { /* find first matching branch */ + if (slow(m, sp, rest, ssub, esub) == rest) + break; /* it matched all of it */ + /* that one missed, try next one */ + assert(OP(m->g->strip[esub]) == OOR1); + esub++; + assert(OP(m->g->strip[esub]) == OOR2); + ssub = esub + 1; + esub += OPND(m->g->strip[esub]); + if (OP(m->g->strip[esub]) == OOR2) + esub--; + else + assert(OP(m->g->strip[esub]) == O_CH); + } + dp = dissect(m, sp, rest, ssub, esub); + assert(dp == rest); + sp = rest; + break; + case O_PLUS: + case O_QUEST: + case OOR1: + case OOR2: + case O_CH: + assert(nope); + break; + case OLPAREN: + i = OPND(m->g->strip[ss]); + assert(0 < i && i <= m->g->nsub); + m->pmatch[i].rm_so = sp - m->offp; + break; + case ORPAREN: + i = OPND(m->g->strip[ss]); + assert(0 < i && i <= m->g->nsub); + m->pmatch[i].rm_eo = sp - m->offp; + break; + default: /* uh oh */ + assert(nope); + break; + } + } + + assert(sp == stop); + return(sp); +} + +/* + - backref - figure out what matched what, figuring in back references + == static char *backref(register struct match *m, char *start, \ + == char *stop, sopno startst, sopno stopst, sopno lev); + */ +static char * /* == stop (success) or NULL (failure) */ +backref(m, start, stop, startst, stopst, lev) +register struct match *m; +char *start; +char *stop; +sopno startst; +sopno stopst; +sopno lev; /* PLUS nesting level */ +{ + register int i; + register sopno ss; /* start sop of current subRE */ + register char *sp; /* start of string matched by it */ + register sopno ssub; /* start sop of subsubRE */ + register sopno esub; /* end sop of subsubRE */ + register char *ssp; /* start of string matched by subsubRE */ + register char *dp; + register size_t len; + register int hard; + register sop s; + register regoff_t offsave; + register cset *cs; + + AT("back", start, stop, startst, stopst); + sp = start; + + /* get as far as we can with easy stuff */ + hard = 0; + for (ss = startst; !hard && ss < stopst; ss++) + switch (OP(s = m->g->strip[ss])) { + case OCHAR: + if (sp == stop || *sp++ != (char)OPND(s)) + return(NULL); + break; + case OANY: + if (sp == stop) + return(NULL); + sp++; + break; + case OANYOF: + cs = &m->g->sets[OPND(s)]; + if (sp == stop || !CHIN(cs, *sp++)) + return(NULL); + break; + case OBOL: + if ( (sp == m->beginp && !(m->eflags®_NOTBOL)) || + (sp < m->endp && *(sp-1) == '\n' && + (m->g->cflags®_NEWLINE)) ) + { /* yes */ } + else + return(NULL); + break; + case OEOL: + if ( (sp == m->endp && !(m->eflags®_NOTEOL)) || + (sp < m->endp && *sp == '\n' && + (m->g->cflags®_NEWLINE)) ) + { /* yes */ } + else + return(NULL); + break; + case OBOW: + if (( (sp == m->beginp && !(m->eflags®_NOTBOL)) || + (sp < m->endp && *(sp-1) == '\n' && + (m->g->cflags®_NEWLINE)) || + (sp > m->beginp && + !ISWORD(*(sp-1))) ) && + (sp < m->endp && ISWORD(*sp)) ) + { /* yes */ } + else + return(NULL); + break; + case OEOW: + if (( (sp == m->endp && !(m->eflags®_NOTEOL)) || + (sp < m->endp && *sp == '\n' && + (m->g->cflags®_NEWLINE)) || + (sp < m->endp && !ISWORD(*sp)) ) && + (sp > m->beginp && ISWORD(*(sp-1))) ) + { /* yes */ } + else + return(NULL); + break; + case O_QUEST: + break; + case OOR1: /* matches null but needs to skip */ + ss++; + s = m->g->strip[ss]; + do { + assert(OP(s) == OOR2); + ss += OPND(s); + } while (OP(s = m->g->strip[ss]) != O_CH); + /* note that the ss++ gets us past the O_CH */ + break; + default: /* have to make a choice */ + hard = 1; + break; + } + if (!hard) { /* that was it! */ + if (sp != stop) + return(NULL); + return(sp); + } + ss--; /* adjust for the for's final increment */ + + /* the hard stuff */ + AT("hard", sp, stop, ss, stopst); + s = m->g->strip[ss]; + switch (OP(s)) { + case OBACK_: /* the vilest depths */ + i = OPND(s); + assert(0 < i && i <= m->g->nsub); + if (m->pmatch[i].rm_eo == -1) + return(NULL); + assert(m->pmatch[i].rm_so != -1); + len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so; + assert(stop - m->beginp >= len); + if (sp > stop - len) + return(NULL); /* not enough left to match */ + ssp = m->offp + m->pmatch[i].rm_so; + if (memcmp(sp, ssp, len) != 0) + return(NULL); + while (m->g->strip[ss] != SOP(O_BACK, i)) + ss++; + return(backref(m, sp+len, stop, ss+1, stopst, lev)); + break; + case OQUEST_: /* to null or not */ + dp = backref(m, sp, stop, ss+1, stopst, lev); + if (dp != NULL) + return(dp); /* not */ + return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev)); + break; + case OPLUS_: + assert(m->lastpos != NULL); + assert(lev+1 <= m->g->nplus); + m->lastpos[lev+1] = sp; + return(backref(m, sp, stop, ss+1, stopst, lev+1)); + break; + case O_PLUS: + if (sp == m->lastpos[lev]) /* last pass matched null */ + return(backref(m, sp, stop, ss+1, stopst, lev-1)); + /* try another pass */ + m->lastpos[lev] = sp; + dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev); + if (dp == NULL) + return(backref(m, sp, stop, ss+1, stopst, lev-1)); + else + return(dp); + break; + case OCH_: /* find the right one, if any */ + ssub = ss + 1; + esub = ss + OPND(s) - 1; + assert(OP(m->g->strip[esub]) == OOR1); + for (;;) { /* find first matching branch */ + dp = backref(m, sp, stop, ssub, esub, lev); + if (dp != NULL) + return(dp); + /* that one missed, try next one */ + if (OP(m->g->strip[esub]) == O_CH) + return(NULL); /* there is none */ + esub++; + assert(OP(m->g->strip[esub]) == OOR2); + ssub = esub + 1; + esub += OPND(m->g->strip[esub]); + if (OP(m->g->strip[esub]) == OOR2) + esub--; + else + assert(OP(m->g->strip[esub]) == O_CH); + } + break; + case OLPAREN: /* must undo assignment if rest fails */ + i = OPND(s); + assert(0 < i && i <= m->g->nsub); + offsave = m->pmatch[i].rm_so; + m->pmatch[i].rm_so = sp - m->offp; + dp = backref(m, sp, stop, ss+1, stopst, lev); + if (dp != NULL) + return(dp); + m->pmatch[i].rm_so = offsave; + return(NULL); + break; + case ORPAREN: /* must undo assignment if rest fails */ + i = OPND(s); + assert(0 < i && i <= m->g->nsub); + offsave = m->pmatch[i].rm_eo; + m->pmatch[i].rm_eo = sp - m->offp; + dp = backref(m, sp, stop, ss+1, stopst, lev); + if (dp != NULL) + return(dp); + m->pmatch[i].rm_eo = offsave; + return(NULL); + break; + default: /* uh oh */ + assert(nope); + break; + } + + /* "can't happen" */ + assert(nope); + /* NOTREACHED */ + return((char *)NULL); /* dummy */ +} + +/* + - fast - step through the string at top speed + == static char *fast(register struct match *m, char *start, \ + == char *stop, sopno startst, sopno stopst); + */ +static char * /* where tentative match ended, or NULL */ +fast(m, start, stop, startst, stopst) +register struct match *m; +char *start; +char *stop; +sopno startst; +sopno stopst; +{ + register states st = m->st; + register states fresh = m->fresh; + register states tmp = m->tmp; + register char *p = start; + register int c = (start == m->beginp) ? OUT : *(start-1); + register int lastc; /* previous c */ + register int flagch; + register int i; + register char *coldp; /* last p after which no match was underway */ + + CLEAR(st); + SET1(st, startst); + st = step(m->g, startst, stopst, st, NOTHING, st); + ASSIGN(fresh, st); + SP("start", st, *p); + coldp = NULL; + for (;;) { + /* next character */ + lastc = c; + c = (p == m->endp) ? OUT : *p; + if (EQ(st, fresh)) + coldp = p; + + /* is there an EOL and/or BOL between lastc and c? */ + flagch = '\0'; + i = 0; + if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || + (lastc == OUT && !(m->eflags®_NOTBOL)) ) { + flagch = BOL; + i = m->g->nbol; + } + if ( (c == '\n' && m->g->cflags®_NEWLINE) || + (c == OUT && !(m->eflags®_NOTEOL)) ) { + flagch = (flagch == BOL) ? BOLEOL : EOL; + i += m->g->neol; + } + if (i != 0) { + for (; i > 0; i--) + st = step(m->g, startst, stopst, st, flagch, st); + SP("boleol", st, c); + } + + /* how about a word boundary? */ + if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) && + (c != OUT && ISWORD(c)) ) { + flagch = BOW; + } + if ( (lastc != OUT && ISWORD(lastc)) && + (flagch == EOL || (c != OUT && !ISWORD(c))) ) { + flagch = EOW; + } + if (flagch == BOW || flagch == EOW) { + st = step(m->g, startst, stopst, st, flagch, st); + SP("boweow", st, c); + } + + /* are we done? */ + if (ISSET(st, stopst) || p == stop) + break; /* NOTE BREAK OUT */ + + /* no, we must deal with this character */ + ASSIGN(tmp, st); + ASSIGN(st, fresh); + assert(c != OUT); + st = step(m->g, startst, stopst, tmp, c, st); + SP("aft", st, c); + assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st)); + p++; + } + + assert(coldp != NULL); + m->coldp = coldp; + if (ISSET(st, stopst)) + return(p+1); + else + return(NULL); +} + +/* + - slow - step through the string more deliberately + == static char *slow(register struct match *m, char *start, \ + == char *stop, sopno startst, sopno stopst); + */ +static char * /* where it ended */ +slow(m, start, stop, startst, stopst) +register struct match *m; +char *start; +char *stop; +sopno startst; +sopno stopst; +{ + register states st = m->st; + register states empty = m->empty; + register states tmp = m->tmp; + register char *p = start; + register int c = (start == m->beginp) ? OUT : *(start-1); + register int lastc; /* previous c */ + register int flagch; + register int i; + register char *matchp; /* last p at which a match ended */ + + AT("slow", start, stop, startst, stopst); + CLEAR(st); + SET1(st, startst); + SP("sstart", st, *p); + st = step(m->g, startst, stopst, st, NOTHING, st); + matchp = NULL; + for (;;) { + /* next character */ + lastc = c; + c = (p == m->endp) ? OUT : *p; + + /* is there an EOL and/or BOL between lastc and c? */ + flagch = '\0'; + i = 0; + if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || + (lastc == OUT && !(m->eflags®_NOTBOL)) ) { + flagch = BOL; + i = m->g->nbol; + } + if ( (c == '\n' && m->g->cflags®_NEWLINE) || + (c == OUT && !(m->eflags®_NOTEOL)) ) { + flagch = (flagch == BOL) ? BOLEOL : EOL; + i += m->g->neol; + } + if (i != 0) { + for (; i > 0; i--) + st = step(m->g, startst, stopst, st, flagch, st); + SP("sboleol", st, c); + } + + /* how about a word boundary? */ + if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) && + (c != OUT && ISWORD(c)) ) { + flagch = BOW; + } + if ( (lastc != OUT && ISWORD(lastc)) && + (flagch == EOL || (c != OUT && !ISWORD(c))) ) { + flagch = EOW; + } + if (flagch == BOW || flagch == EOW) { + st = step(m->g, startst, stopst, st, flagch, st); + SP("sboweow", st, c); + } + + /* are we done? */ + if (ISSET(st, stopst)) + matchp = p; + if (EQ(st, empty) || p == stop) + break; /* NOTE BREAK OUT */ + + /* no, we must deal with this character */ + ASSIGN(tmp, st); + ASSIGN(st, empty); + assert(c != OUT); + st = step(m->g, startst, stopst, tmp, c, st); + SP("saft", st, c); + assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st)); + p++; + } + + return(matchp); +} + + +/* + - step - map set of states reachable before char to set reachable after + == static states step(register struct re_guts *g, sopno start, sopno stop, \ + == register states bef, int ch, register states aft); + == #define BOL (OUT+1) + == #define EOL (BOL+1) + == #define BOLEOL (BOL+2) + == #define NOTHING (BOL+3) + == #define BOW (BOL+4) + == #define EOW (BOL+5) + == #define CODEMAX (BOL+5) // highest code used + == #define NONCHAR(c) ((c) > CHAR_MAX) + == #define NNONCHAR (CODEMAX-CHAR_MAX) + */ +static states +step(g, start, stop, bef, ch, aft) +register struct re_guts *g; +sopno start; /* start state within strip */ +sopno stop; /* state after stop state within strip */ +register states bef; /* states reachable before */ +int ch; /* character or NONCHAR code */ +register states aft; /* states already known reachable after */ +{ + register cset *cs; + register sop s; + register sopno pc; + register onestate here; /* note, macros know this name */ + register sopno look; + register long i; + + for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) { + s = g->strip[pc]; + switch (OP(s)) { + case OEND: + assert(pc == stop-1); + break; + case OCHAR: + /* only characters can match */ + assert(!NONCHAR(ch) || ch != (char)OPND(s)); + if (ch == (char)OPND(s)) + FWD(aft, bef, 1); + break; + case OBOL: + if (ch == BOL || ch == BOLEOL) + FWD(aft, bef, 1); + break; + case OEOL: + if (ch == EOL || ch == BOLEOL) + FWD(aft, bef, 1); + break; + case OBOW: + if (ch == BOW) + FWD(aft, bef, 1); + break; + case OEOW: + if (ch == EOW) + FWD(aft, bef, 1); + break; + case OANY: + if (!NONCHAR(ch)) + FWD(aft, bef, 1); + break; + case OANYOF: + cs = &g->sets[OPND(s)]; + if (!NONCHAR(ch) && CHIN(cs, ch)) + FWD(aft, bef, 1); + break; + case OBACK_: /* ignored here */ + case O_BACK: + FWD(aft, aft, 1); + break; + case OPLUS_: /* forward, this is just an empty */ + FWD(aft, aft, 1); + break; + case O_PLUS: /* both forward and back */ + FWD(aft, aft, 1); + i = ISSETBACK(aft, OPND(s)); + BACK(aft, aft, OPND(s)); + if (!i && ISSETBACK(aft, OPND(s))) { + /* oho, must reconsider loop body */ + pc -= OPND(s) + 1; + INIT(here, pc); + } + break; + case OQUEST_: /* two branches, both forward */ + FWD(aft, aft, 1); + FWD(aft, aft, OPND(s)); + break; + case O_QUEST: /* just an empty */ + FWD(aft, aft, 1); + break; + case OLPAREN: /* not significant here */ + case ORPAREN: + FWD(aft, aft, 1); + break; + case OCH_: /* mark the first two branches */ + FWD(aft, aft, 1); + assert(OP(g->strip[pc+OPND(s)]) == OOR2); + FWD(aft, aft, OPND(s)); + break; + case OOR1: /* done a branch, find the O_CH */ + if (ISSTATEIN(aft, here)) { + for (look = 1; + OP(s = g->strip[pc+look]) != O_CH; + look += OPND(s)) + assert(OP(s) == OOR2); + FWD(aft, aft, look); + } + break; + case OOR2: /* propagate OCH_'s marking */ + FWD(aft, aft, 1); + if (OP(g->strip[pc+OPND(s)]) != O_CH) { + assert(OP(g->strip[pc+OPND(s)]) == OOR2); + FWD(aft, aft, OPND(s)); + } + break; + case O_CH: /* just empty */ + FWD(aft, aft, 1); + break; + default: /* ooooops... */ + assert(nope); + break; + } + } + + return(aft); +} + +#ifdef REDEBUG +/* + - print - print a set of states + == #ifdef REDEBUG + == static void print(struct match *m, char *caption, states st, \ + == int ch, FILE *d); + == #endif + */ +static void +print(m, caption, st, ch, d) +struct match *m; +char *caption; +states st; +int ch; +FILE *d; +{ + register struct re_guts *g = m->g; + register int i; + register int first = 1; + + if (!(m->eflags®_TRACE)) + return; + + fprintf(d, "%s", caption); + if (ch != '\0') + fprintf(d, " %s", pchar(ch)); + for (i = 0; i < g->nstates; i++) + if (ISSET(st, i)) { + fprintf(d, "%s%d", (first) ? "\t" : ", ", i); + first = 0; + } + fprintf(d, "\n"); +} + +/* + - at - print current situation + == #ifdef REDEBUG + == static void at(struct match *m, char *title, char *start, char *stop, \ + == sopno startst, sopno stopst); + == #endif + */ +static void +at(m, title, start, stop, startst, stopst) +struct match *m; +char *title; +char *start; +char *stop; +sopno startst; +sopno stopst; +{ + if (!(m->eflags®_TRACE)) + return; + + printf("%s %s-", title, pchar(*start)); + printf("%s ", pchar(*stop)); + printf("%ld-%ld\n", (long)startst, (long)stopst); +} + +#ifndef PCHARDONE +#define PCHARDONE /* never again */ +/* + - pchar - make a character printable + == #ifdef REDEBUG + == static char *pchar(int ch); + == #endif + * + * Is this identical to regchar() over in debug.c? Well, yes. But a + * duplicate here avoids having a debugging-capable regexec.o tied to + * a matching debug.o, and this is convenient. It all disappears in + * the non-debug compilation anyway, so it doesn't matter much. + */ +static char * /* -> representation */ +pchar(ch) +int ch; +{ + static char pbuf[10]; + + if (isprint(ch) || ch == ' ') + sprintf(pbuf, "%c", ch); + else + sprintf(pbuf, "\\%o", ch); + return(pbuf); +} +#endif +#endif + +#undef matcher +#undef fast +#undef slow +#undef dissect +#undef backref +#undef step +#undef print +#undef at +#undef match diff --git a/regex/engine.ih b/regex/engine.ih new file mode 100644 index 0000000..cc98334 --- /dev/null +++ b/regex/engine.ih @@ -0,0 +1,35 @@ +/* ========= begin header generated by ./mkh ========= */ +#ifdef __cplusplus +extern "C" { +#endif + +/* === engine.c === */ +static int matcher(register struct re_guts *g, char *string, size_t nmatch, regmatch_t pmatch[], int eflags); +static char *dissect(register struct match *m, char *start, char *stop, sopno startst, sopno stopst); +static char *backref(register struct match *m, char *start, char *stop, sopno startst, sopno stopst, sopno lev); +static char *fast(register struct match *m, char *start, char *stop, sopno startst, sopno stopst); +static char *slow(register struct match *m, char *start, char *stop, sopno startst, sopno stopst); +static states step(register struct re_guts *g, sopno start, sopno stop, register states bef, int ch, register states aft); +#define BOL (OUT+1) +#define EOL (BOL+1) +#define BOLEOL (BOL+2) +#define NOTHING (BOL+3) +#define BOW (BOL+4) +#define EOW (BOL+5) +#define CODEMAX (BOL+5) /* highest code used */ +#define NONCHAR(c) ((c) > CHAR_MAX) +#define NNONCHAR (CODEMAX-CHAR_MAX) +#ifdef REDEBUG +static void print(struct match *m, char *caption, states st, int ch, FILE *d); +#endif +#ifdef REDEBUG +static void at(struct match *m, char *title, char *start, char *stop, sopno startst, sopno stopst); +#endif +#ifdef REDEBUG +static char *pchar(int ch); +#endif + +#ifdef __cplusplus +} +#endif +/* ========= end header generated by ./mkh ========= */ diff --git a/regex/main.c b/regex/main.c new file mode 100644 index 0000000..0221e77 --- /dev/null +++ b/regex/main.c @@ -0,0 +1,510 @@ +#include <stdio.h> +#include <string.h> +#include <sys/types.h> +#include <regex.h> +#include <assert.h> + +#include "main.ih" + +char *progname; +int debug = 0; +int line = 0; +int status = 0; + +int copts = REG_EXTENDED; +int eopts = 0; +regoff_t startoff = 0; +regoff_t endoff = 0; + + +extern int split(); +extern void regprint(); + +/* + - main - do the simple case, hand off to regress() for regression + */ +main(argc, argv) +int argc; +char *argv[]; +{ + regex_t re; +# define NS 10 + regmatch_t subs[NS]; + char erbuf[100]; + int err; + size_t len; + int c; + int errflg = 0; + register int i; + extern int optind; + extern char *optarg; + + progname = argv[0]; + + while ((c = getopt(argc, argv, "c:e:S:E:x")) != EOF) + switch (c) { + case 'c': /* compile options */ + copts = options('c', optarg); + break; + case 'e': /* execute options */ + eopts = options('e', optarg); + break; + case 'S': /* start offset */ + startoff = (regoff_t)atoi(optarg); + break; + case 'E': /* end offset */ + endoff = (regoff_t)atoi(optarg); + break; + case 'x': /* Debugging. */ + debug++; + break; + case '?': + default: + errflg++; + break; + } + if (errflg) { + fprintf(stderr, "usage: %s ", progname); + fprintf(stderr, "[-c copt][-C][-d] [re]\n"); + exit(2); + } + + if (optind >= argc) { + regress(stdin); + exit(status); + } + + err = regcomp(&re, argv[optind++], copts); + if (err) { + len = regerror(err, &re, erbuf, sizeof(erbuf)); + fprintf(stderr, "error %s, %d/%d `%s'\n", + eprint(err), len, sizeof(erbuf), erbuf); + exit(status); + } + regprint(&re, stdout); + + if (optind >= argc) { + regfree(&re); + exit(status); + } + + if (eopts®_STARTEND) { + subs[0].rm_so = startoff; + subs[0].rm_eo = strlen(argv[optind]) - endoff; + } + err = regexec(&re, argv[optind], (size_t)NS, subs, eopts); + if (err) { + len = regerror(err, &re, erbuf, sizeof(erbuf)); + fprintf(stderr, "error %s, %d/%d `%s'\n", + eprint(err), len, sizeof(erbuf), erbuf); + exit(status); + } + if (!(copts®_NOSUB)) { + len = (int)(subs[0].rm_eo - subs[0].rm_so); + if (subs[0].rm_so != -1) { + if (len != 0) + printf("match `%.*s'\n", len, + argv[optind] + subs[0].rm_so); + else + printf("match `'@%.1s\n", + argv[optind] + subs[0].rm_so); + } + for (i = 1; i < NS; i++) + if (subs[i].rm_so != -1) + printf("(%d) `%.*s'\n", i, + (int)(subs[i].rm_eo - subs[i].rm_so), + argv[optind] + subs[i].rm_so); + } + exit(status); +} + +/* + - regress - main loop of regression test + == void regress(FILE *in); + */ +void +regress(in) +FILE *in; +{ + char inbuf[1000]; +# define MAXF 10 + char *f[MAXF]; + int nf; + int i; + char erbuf[100]; + size_t ne; + char *badpat = "invalid regular expression"; +# define SHORT 10 + char *bpname = "REG_BADPAT"; + regex_t re; + + while (fgets(inbuf, sizeof(inbuf), in) != NULL) { + line++; + if (inbuf[0] == '#' || inbuf[0] == '\n') + continue; /* NOTE CONTINUE */ + inbuf[strlen(inbuf)-1] = '\0'; /* get rid of stupid \n */ + if (debug) + fprintf(stdout, "%d:\n", line); + nf = split(inbuf, f, MAXF, "\t\t"); + if (nf < 3) { + fprintf(stderr, "bad input, line %d\n", line); + exit(1); + } + for (i = 0; i < nf; i++) + if (strcmp(f[i], "\"\"") == 0) + f[i] = ""; + if (nf <= 3) + f[3] = NULL; + if (nf <= 4) + f[4] = NULL; + try(f[0], f[1], f[2], f[3], f[4], options('c', f[1])); + if (opt('&', f[1])) /* try with either type of RE */ + try(f[0], f[1], f[2], f[3], f[4], + options('c', f[1]) &~ REG_EXTENDED); + } + + ne = regerror(REG_BADPAT, (regex_t *)NULL, erbuf, sizeof(erbuf)); + if (strcmp(erbuf, badpat) != 0 || ne != strlen(badpat)+1) { + fprintf(stderr, "end: regerror() test gave `%s' not `%s'\n", + erbuf, badpat); + status = 1; + } + ne = regerror(REG_BADPAT, (regex_t *)NULL, erbuf, (size_t)SHORT); + if (strncmp(erbuf, badpat, SHORT-1) != 0 || erbuf[SHORT-1] != '\0' || + ne != strlen(badpat)+1) { + fprintf(stderr, "end: regerror() short test gave `%s' not `%.*s'\n", + erbuf, SHORT-1, badpat); + status = 1; + } + ne = regerror(REG_ITOA|REG_BADPAT, (regex_t *)NULL, erbuf, sizeof(erbuf)); + if (strcmp(erbuf, bpname) != 0 || ne != strlen(bpname)+1) { + fprintf(stderr, "end: regerror() ITOA test gave `%s' not `%s'\n", + erbuf, bpname); + status = 1; + } + re.re_endp = bpname; + ne = regerror(REG_ATOI, &re, erbuf, sizeof(erbuf)); + if (atoi(erbuf) != (int)REG_BADPAT) { + fprintf(stderr, "end: regerror() ATOI test gave `%s' not `%ld'\n", + erbuf, (long)REG_BADPAT); + status = 1; + } else if (ne != strlen(erbuf)+1) { + fprintf(stderr, "end: regerror() ATOI test len(`%s') = %ld\n", + erbuf, (long)REG_BADPAT); + status = 1; + } +} + +/* + - try - try it, and report on problems + == void try(char *f0, char *f1, char *f2, char *f3, char *f4, int opts); + */ +void +try(f0, f1, f2, f3, f4, opts) +char *f0; +char *f1; +char *f2; +char *f3; +char *f4; +int opts; /* may not match f1 */ +{ + regex_t re; +# define NSUBS 10 + regmatch_t subs[NSUBS]; +# define NSHOULD 15 + char *should[NSHOULD]; + int nshould; + char erbuf[100]; + int err; + int len; + char *type = (opts & REG_EXTENDED) ? "ERE" : "BRE"; + register int i; + char *grump; + char f0copy[1000]; + char f2copy[1000]; + + strcpy(f0copy, f0); + re.re_endp = (opts®_PEND) ? f0copy + strlen(f0copy) : NULL; + fixstr(f0copy); + err = regcomp(&re, f0copy, opts); + if (err != 0 && (!opt('C', f1) || err != efind(f2))) { + /* unexpected error or wrong error */ + len = regerror(err, &re, erbuf, sizeof(erbuf)); + fprintf(stderr, "%d: %s error %s, %d/%d `%s'\n", + line, type, eprint(err), len, + sizeof(erbuf), erbuf); + status = 1; + } else if (err == 0 && opt('C', f1)) { + /* unexpected success */ + fprintf(stderr, "%d: %s should have given REG_%s\n", + line, type, f2); + status = 1; + err = 1; /* so we won't try regexec */ + } + + if (err != 0) { + regfree(&re); + return; + } + + strcpy(f2copy, f2); + fixstr(f2copy); + + if (options('e', f1)®_STARTEND) { + if (strchr(f2, '(') == NULL || strchr(f2, ')') == NULL) + fprintf(stderr, "%d: bad STARTEND syntax\n", line); + subs[0].rm_so = strchr(f2, '(') - f2 + 1; + subs[0].rm_eo = strchr(f2, ')') - f2; + } + err = regexec(&re, f2copy, NSUBS, subs, options('e', f1)); + + if (err != 0 && (f3 != NULL || err != REG_NOMATCH)) { + /* unexpected error or wrong error */ + len = regerror(err, &re, erbuf, sizeof(erbuf)); + fprintf(stderr, "%d: %s exec error %s, %d/%d `%s'\n", + line, type, eprint(err), len, + sizeof(erbuf), erbuf); + status = 1; + } else if (err != 0) { + /* nothing more to check */ + } else if (f3 == NULL) { + /* unexpected success */ + fprintf(stderr, "%d: %s exec should have failed\n", + line, type); + status = 1; + err = 1; /* just on principle */ + } else if (opts®_NOSUB) { + /* nothing more to check */ + } else if ((grump = check(f2, subs[0], f3)) != NULL) { + fprintf(stderr, "%d: %s %s\n", line, type, grump); + status = 1; + err = 1; + } + + if (err != 0 || f4 == NULL) { + regfree(&re); + return; + } + + for (i = 1; i < NSHOULD; i++) + should[i] = NULL; + nshould = split(f4, should+1, NSHOULD-1, ","); + if (nshould == 0) { + nshould = 1; + should[1] = ""; + } + for (i = 1; i < NSUBS; i++) { + grump = check(f2, subs[i], should[i]); + if (grump != NULL) { + fprintf(stderr, "%d: %s $%d %s\n", line, + type, i, grump); + status = 1; + err = 1; + } + } + + regfree(&re); +} + +/* + - options - pick options out of a regression-test string + == int options(int type, char *s); + */ +int +options(type, s) +int type; /* 'c' compile, 'e' exec */ +char *s; +{ + register char *p; + register int o = (type == 'c') ? copts : eopts; + register char *legal = (type == 'c') ? "bisnmp" : "^$#tl"; + + for (p = s; *p != '\0'; p++) + if (strchr(legal, *p) != NULL) + switch (*p) { + case 'b': + o &= ~REG_EXTENDED; + break; + case 'i': + o |= REG_ICASE; + break; + case 's': + o |= REG_NOSUB; + break; + case 'n': + o |= REG_NEWLINE; + break; + case 'm': + o &= ~REG_EXTENDED; + o |= REG_NOSPEC; + break; + case 'p': + o |= REG_PEND; + break; + case '^': + o |= REG_NOTBOL; + break; + case '$': + o |= REG_NOTEOL; + break; + case '#': + o |= REG_STARTEND; + break; + case 't': /* trace */ + o |= REG_TRACE; + break; + case 'l': /* force long representation */ + o |= REG_LARGE; + break; + case 'r': /* force backref use */ + o |= REG_BACKR; + break; + } + return(o); +} + +/* + - opt - is a particular option in a regression string? + == int opt(int c, char *s); + */ +int /* predicate */ +opt(c, s) +int c; +char *s; +{ + return(strchr(s, c) != NULL); +} + +/* + - fixstr - transform magic characters in strings + == void fixstr(register char *p); + */ +void +fixstr(p) +register char *p; +{ + if (p == NULL) + return; + + for (; *p != '\0'; p++) + if (*p == 'N') + *p = '\n'; + else if (*p == 'T') + *p = '\t'; + else if (*p == 'S') + *p = ' '; + else if (*p == 'Z') + *p = '\0'; +} + +/* + - check - check a substring match + == char *check(char *str, regmatch_t sub, char *should); + */ +char * /* NULL or complaint */ +check(str, sub, should) +char *str; +regmatch_t sub; +char *should; +{ + register int len; + register int shlen; + register char *p; + static char grump[500]; + register char *at = NULL; + + if (should != NULL && strcmp(should, "-") == 0) + should = NULL; + if (should != NULL && should[0] == '@') { + at = should + 1; + should = ""; + } + + /* check rm_so and rm_eo for consistency */ + if (sub.rm_so > sub.rm_eo || (sub.rm_so == -1 && sub.rm_eo != -1) || + (sub.rm_so != -1 && sub.rm_eo == -1) || + (sub.rm_so != -1 && sub.rm_so < 0) || + (sub.rm_eo != -1 && sub.rm_eo < 0) ) { + sprintf(grump, "start %ld end %ld", (long)sub.rm_so, + (long)sub.rm_eo); + return(grump); + } + + /* check for no match */ + if (sub.rm_so == -1 && should == NULL) + return(NULL); + if (sub.rm_so == -1) + return("did not match"); + + /* check for in range */ + if (sub.rm_eo > strlen(str)) { + sprintf(grump, "start %ld end %ld, past end of string", + (long)sub.rm_so, (long)sub.rm_eo); + return(grump); + } + + len = (int)(sub.rm_eo - sub.rm_so); + shlen = (int)strlen(should); + p = str + sub.rm_so; + + /* check for not supposed to match */ + if (should == NULL) { + sprintf(grump, "matched `%.*s'", len, p); + return(grump); + } + + /* check for wrong match */ + if (len != shlen || strncmp(p, should, (size_t)shlen) != 0) { + sprintf(grump, "matched `%.*s' instead", len, p); + return(grump); + } + if (shlen > 0) + return(NULL); + + /* check null match in right place */ + if (at == NULL) + return(NULL); + shlen = strlen(at); + if (shlen == 0) + shlen = 1; /* force check for end-of-string */ + if (strncmp(p, at, shlen) != 0) { + sprintf(grump, "matched null at `%.20s'", p); + return(grump); + } + return(NULL); +} + +/* + - eprint - convert error number to name + == static char *eprint(int err); + */ +static char * +eprint(err) +int err; +{ + static char epbuf[100]; + size_t len; + + len = regerror(REG_ITOA|err, (regex_t *)NULL, epbuf, sizeof(epbuf)); + assert(len <= sizeof(epbuf)); + return(epbuf); +} + +/* + - efind - convert error name to number + == static int efind(char *name); + */ +static int +efind(name) +char *name; +{ + static char efbuf[100]; + size_t n; + regex_t re; + + sprintf(efbuf, "REG_%s", name); + assert(strlen(efbuf) < sizeof(efbuf)); + re.re_endp = efbuf; + (void) regerror(REG_ATOI, &re, efbuf, sizeof(efbuf)); + return(atoi(efbuf)); +} diff --git a/regex/main.ih b/regex/main.ih new file mode 100644 index 0000000..5a0118a --- /dev/null +++ b/regex/main.ih @@ -0,0 +1,19 @@ +/* ========= begin header generated by ./mkh ========= */ +#ifdef __cplusplus +extern "C" { +#endif + +/* === main.c === */ +void regress(FILE *in); +void try(char *f0, char *f1, char *f2, char *f3, char *f4, int opts); +int options(int type, char *s); +int opt(int c, char *s); +void fixstr(register char *p); +char *check(char *str, regmatch_t sub, char *should); +static char *eprint(int err); +static int efind(char *name); + +#ifdef __cplusplus +} +#endif +/* ========= end header generated by ./mkh ========= */ diff --git a/regex/mkh b/regex/mkh new file mode 100755 index 0000000..252b246 --- /dev/null +++ b/regex/mkh @@ -0,0 +1,76 @@ +#! /bin/sh +# mkh - pull headers out of C source +PATH=/bin:/usr/bin ; export PATH + +# egrep pattern to pick out marked lines +egrep='^ =([ ]|$)' + +# Sed program to process marked lines into lines for the header file. +# The markers have already been removed. Two things are done here: removal +# of backslashed newlines, and some fudging of comments. The first is done +# because -o needs to have prototypes on one line to strip them down. +# Getting comments into the output is tricky; we turn C++-style // comments +# into /* */ comments, after altering any existing */'s to avoid trouble. +peel=' /\\$/N + /\\\n[ ]*/s///g + /\/\//s;\*/;* /;g + /\/\//s;//\(.*\);/*\1 */;' + +for a +do + case "$a" in + -o) # old (pre-function-prototype) compiler + # add code to comment out argument lists + peel="$peel + "'/^\([^#\/][^\/]*[a-zA-Z0-9_)]\)(\(.*\))/s;;\1(/*\2*/);' + shift + ;; + -b) # funny Berkeley __P macro + peel="$peel + "'/^\([^#\/][^\/]*[a-zA-Z0-9_)]\)(\(.*\))/s;;\1 __P((\2));' + shift + ;; + -s) # compiler doesn't like `static foo();' + # add code to get rid of the `static' + peel="$peel + "'/^static[ ][^\/]*[a-zA-Z0-9_)](.*)/s;static.;;' + shift + ;; + -p) # private declarations + egrep='^ ==([ ]|$)' + shift + ;; + -i) # wrap in #ifndef, argument is name + ifndef="$2" + shift ; shift + ;; + *) break + ;; + esac +done + +if test " $ifndef" != " " +then + echo "#ifndef $ifndef" + echo "#define $ifndef /* never again */" +fi +echo "/* ========= begin header generated by $0 ========= */" +echo '#ifdef __cplusplus' +echo 'extern "C" {' +echo '#endif' +for f +do + echo + echo "/* === $f === */" + egrep "$egrep" $f | sed 's/^ ==*[ ]//;s/^ ==*$//' | sed "$peel" + echo +done +echo '#ifdef __cplusplus' +echo '}' +echo '#endif' +echo "/* ========= end header generated by $0 ========= */" +if test " $ifndef" != " " +then + echo "#endif" +fi +exit 0 diff --git a/regex/regcomp.c b/regex/regcomp.c new file mode 100644 index 0000000..27c5303 --- /dev/null +++ b/regex/regcomp.c @@ -0,0 +1,1603 @@ +#include <sys/types.h> +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#include <limits.h> +#include <stdlib.h> +#include <regex.h> + +#include "utils.h" +#include "regex2.h" + +#include "cclass.h" +#include "cname.h" + +/* + * parse structure, passed up and down to avoid global variables and + * other clumsinesses + */ +struct parse { + char *next; /* next character in RE */ + char *end; /* end of string (-> NUL normally) */ + int error; /* has an error been seen? */ + sop *strip; /* malloced strip */ + sopno ssize; /* malloced strip size (allocated) */ + sopno slen; /* malloced strip length (used) */ + int ncsalloc; /* number of csets allocated */ + struct re_guts *g; +# define NPAREN 10 /* we need to remember () 1-9 for back refs */ + sopno pbegin[NPAREN]; /* -> ( ([0] unused) */ + sopno pend[NPAREN]; /* -> ) ([0] unused) */ +}; + +#include "regcomp.ih" + +static char nuls[10]; /* place to point scanner in event of error */ + +/* + * macros for use with parse structure + * BEWARE: these know that the parse structure is named `p' !!! + */ +#define PEEK() (*p->next) +#define PEEK2() (*(p->next+1)) +#define MORE() (p->next < p->end) +#define MORE2() (p->next+1 < p->end) +#define SEE(c) (MORE() && PEEK() == (c)) +#define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b)) +#define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0) +#define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0) +#define NEXT() (p->next++) +#define NEXT2() (p->next += 2) +#define NEXTn(n) (p->next += (n)) +#define GETNEXT() (*p->next++) +#define SETERROR(e) seterr(p, (e)) +#define REQUIRE(co, e) ((co) || SETERROR(e)) +#define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e)) +#define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e)) +#define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e)) +#define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd)) +#define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos) +#define AHEAD(pos) dofwd(p, pos, HERE()-(pos)) +#define ASTERN(sop, pos) EMIT(sop, HERE()-pos) +#define HERE() (p->slen) +#define THERE() (p->slen - 1) +#define THERETHERE() (p->slen - 2) +#define DROP(n) (p->slen -= (n)) + +#ifndef NDEBUG +static int never = 0; /* for use in asserts; shuts lint up */ +#else +#define never 0 /* some <assert.h>s have bugs too */ +#endif + +/* + - regcomp - interface for parser and compilation + = extern int notbuiltin_regcomp(regex_t *, const char *, int); + = #define REG_BASIC 0000 + = #define REG_EXTENDED 0001 + = #define REG_ICASE 0002 + = #define REG_NOSUB 0004 + = #define REG_NEWLINE 0010 + = #define REG_NOSPEC 0020 + = #define REG_PEND 0040 + = #define REG_DUMP 0200 + */ +int /* 0 success, otherwise REG_something */ +notbuiltin_regcomp(preg, pattern, cflags) +regex_t *preg; +const char *pattern; +int cflags; +{ + struct parse pa; + register struct re_guts *g; + register struct parse *p = &pa; + register int i; + register size_t len; +#ifdef REDEBUG +# define GOODFLAGS(f) (f) +#else +# define GOODFLAGS(f) ((f)&~REG_DUMP) +#endif + + cflags = GOODFLAGS(cflags); + if ((cflags®_EXTENDED) && (cflags®_NOSPEC)) + return(REG_INVARG); + + if (cflags®_PEND) { + if (preg->re_endp < pattern) + return(REG_INVARG); + len = preg->re_endp - pattern; + } else + len = strlen((char *)pattern); + + /* do the mallocs early so failure handling is easy */ + g = (struct re_guts *)malloc(sizeof(struct re_guts) + + (NC-1)*sizeof(cat_t)); + if (g == NULL) + return(REG_ESPACE); + p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */ + p->strip = (sop *)malloc(p->ssize * sizeof(sop)); + p->slen = 0; + if (p->strip == NULL) { + free((char *)g); + return(REG_ESPACE); + } + + /* set things up */ + p->g = g; + p->next = (char *)pattern; /* convenience; we do not modify it */ + p->end = p->next + len; + p->error = 0; + p->ncsalloc = 0; + for (i = 0; i < NPAREN; i++) { + p->pbegin[i] = 0; + p->pend[i] = 0; + } + g->csetsize = NC; + g->sets = NULL; + g->setbits = NULL; + g->ncsets = 0; + g->cflags = cflags; + g->iflags = 0; + g->nbol = 0; + g->neol = 0; + g->must = NULL; + g->mlen = 0; + g->nsub = 0; + g->ncategories = 1; /* category 0 is "everything else" */ + g->categories = &g->catspace[-(CHAR_MIN)]; + (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t)); + g->backrefs = 0; + + /* do it */ + EMIT(OEND, 0); + g->firststate = THERE(); + if (cflags®_EXTENDED) + p_ere(p, OUT); + else if (cflags®_NOSPEC) + p_str(p); + else + p_bre(p, OUT, OUT); + EMIT(OEND, 0); + g->laststate = THERE(); + + /* tidy up loose ends and fill things in */ + categorize(p, g); + stripsnug(p, g); + findmust(p, g); + g->nplus = pluscount(p, g); + g->magic = MAGIC2; + preg->re_nsub = g->nsub; + preg->re_g = g; + preg->re_magic = MAGIC1; +#ifndef REDEBUG + /* not debugging, so can't rely on the assert() in regexec() */ + if (g->iflags&BAD) + SETERROR(REG_ASSERT); +#endif + + /* win or lose, we're done */ + if (p->error != 0) /* lose */ + notbuiltin_regfree(preg); + return(p->error); +} + +/* + - p_ere - ERE parser top level, concatenation and alternation + == static void p_ere(register struct parse *p, int stop); + */ +static void +p_ere(p, stop) +register struct parse *p; +int stop; /* character this ERE should end at */ +{ + register char c; + register sopno prevback; + register sopno prevfwd; + register sopno conc; + register int first = 1; /* is this the first alternative? */ + + for (;;) { + /* do a bunch of concatenated expressions */ + conc = HERE(); + while (MORE() && (c = PEEK()) != '|' && c != stop) + p_ere_exp(p); + REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */ + + if (!EAT('|')) + break; /* NOTE BREAK OUT */ + + if (first) { + INSERT(OCH_, conc); /* offset is wrong */ + prevfwd = conc; + prevback = conc; + first = 0; + } + ASTERN(OOR1, prevback); + prevback = THERE(); + AHEAD(prevfwd); /* fix previous offset */ + prevfwd = HERE(); + EMIT(OOR2, 0); /* offset is very wrong */ + } + + if (!first) { /* tail-end fixups */ + AHEAD(prevfwd); + ASTERN(O_CH, prevback); + } + + assert(!MORE() || SEE(stop)); +} + +/* + - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op + == static void p_ere_exp(register struct parse *p); + */ +static void +p_ere_exp(p) +register struct parse *p; +{ + register char c; + register sopno pos; + register int count; + register int count2; + register sopno subno; + int wascaret = 0; + + assert(MORE()); /* caller should have ensured this */ + c = GETNEXT(); + + pos = HERE(); + switch (c) { + case '(': + REQUIRE(MORE(), REG_EPAREN); + p->g->nsub++; + subno = p->g->nsub; + if (subno < NPAREN) + p->pbegin[subno] = HERE(); + EMIT(OLPAREN, subno); + if (!SEE(')')) + p_ere(p, ')'); + if (subno < NPAREN) { + p->pend[subno] = HERE(); + assert(p->pend[subno] != 0); + } + EMIT(ORPAREN, subno); + MUSTEAT(')', REG_EPAREN); + break; +#ifndef POSIX_MISTAKE + case ')': /* happens only if no current unmatched ( */ + /* + * You may ask, why the ifndef? Because I didn't notice + * this until slightly too late for 1003.2, and none of the + * other 1003.2 regular-expression reviewers noticed it at + * all. So an unmatched ) is legal POSIX, at least until + * we can get it fixed. + */ + SETERROR(REG_EPAREN); + break; +#endif + case '^': + EMIT(OBOL, 0); + p->g->iflags |= USEBOL; + p->g->nbol++; + wascaret = 1; + break; + case '$': + EMIT(OEOL, 0); + p->g->iflags |= USEEOL; + p->g->neol++; + break; + case '|': + SETERROR(REG_EMPTY); + break; + case '*': + case '+': + case '?': + SETERROR(REG_BADRPT); + break; + case '.': + if (p->g->cflags®_NEWLINE) + nonnewline(p); + else + EMIT(OANY, 0); + break; + case '[': + p_bracket(p); + break; + case '\\': + REQUIRE(MORE(), REG_EESCAPE); + c = GETNEXT(); + ordinary(p, c); + break; + case '{': /* okay as ordinary except if digit follows */ + REQUIRE(!MORE() || !isdigit(PEEK()), REG_BADRPT); + /* FALLTHROUGH */ + default: + ordinary(p, c); + break; + } + + if (!MORE()) + return; + c = PEEK(); + /* we call { a repetition if followed by a digit */ + if (!( c == '*' || c == '+' || c == '?' || + (c == '{' && MORE2() && isdigit(PEEK2())) )) + return; /* no repetition, we're done */ + NEXT(); + + REQUIRE(!wascaret, REG_BADRPT); + switch (c) { + case '*': /* implemented as +? */ + /* this case does not require the (y|) trick, noKLUDGE */ + INSERT(OPLUS_, pos); + ASTERN(O_PLUS, pos); + INSERT(OQUEST_, pos); + ASTERN(O_QUEST, pos); + break; + case '+': + INSERT(OPLUS_, pos); + ASTERN(O_PLUS, pos); + break; + case '?': + /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ + INSERT(OCH_, pos); /* offset slightly wrong */ + ASTERN(OOR1, pos); /* this one's right */ + AHEAD(pos); /* fix the OCH_ */ + EMIT(OOR2, 0); /* offset very wrong... */ + AHEAD(THERE()); /* ...so fix it */ + ASTERN(O_CH, THERETHERE()); + break; + case '{': + count = p_count(p); + if (EAT(',')) { + if (isdigit(PEEK())) { + count2 = p_count(p); + REQUIRE(count <= count2, REG_BADBR); + } else /* single number with comma */ + count2 = INFINITY; + } else /* just a single number */ + count2 = count; + repeat(p, pos, count, count2); + if (!EAT('}')) { /* error heuristics */ + while (MORE() && PEEK() != '}') + NEXT(); + REQUIRE(MORE(), REG_EBRACE); + SETERROR(REG_BADBR); + } + break; + } + + if (!MORE()) + return; + c = PEEK(); + if (!( c == '*' || c == '+' || c == '?' || + (c == '{' && MORE2() && isdigit(PEEK2())) ) ) + return; + SETERROR(REG_BADRPT); +} + +/* + - p_str - string (no metacharacters) "parser" + == static void p_str(register struct parse *p); + */ +static void +p_str(p) +register struct parse *p; +{ + REQUIRE(MORE(), REG_EMPTY); + while (MORE()) + ordinary(p, GETNEXT()); +} + +/* + - p_bre - BRE parser top level, anchoring and concatenation + == static void p_bre(register struct parse *p, register int end1, \ + == register int end2); + * Giving end1 as OUT essentially eliminates the end1/end2 check. + * + * This implementation is a bit of a kludge, in that a trailing $ is first + * taken as an ordinary character and then revised to be an anchor. The + * only undesirable side effect is that '$' gets included as a character + * category in such cases. This is fairly harmless; not worth fixing. + * The amount of lookahead needed to avoid this kludge is excessive. + */ +static void +p_bre(p, end1, end2) +register struct parse *p; +register int end1; /* first terminating character */ +register int end2; /* second terminating character */ +{ + register sopno start = HERE(); + register int first = 1; /* first subexpression? */ + register int wasdollar = 0; + + if (EAT('^')) { + EMIT(OBOL, 0); + p->g->iflags |= USEBOL; + p->g->nbol++; + } + while (MORE() && !SEETWO(end1, end2)) { + wasdollar = p_simp_re(p, first); + first = 0; + } + if (wasdollar) { /* oops, that was a trailing anchor */ + DROP(1); + EMIT(OEOL, 0); + p->g->iflags |= USEEOL; + p->g->neol++; + } + + REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */ +} + +/* + - p_simp_re - parse a simple RE, an atom possibly followed by a repetition + == static int p_simp_re(register struct parse *p, int starordinary); + */ +static int /* was the simple RE an unbackslashed $? */ +p_simp_re(p, starordinary) +register struct parse *p; +int starordinary; /* is a leading * an ordinary character? */ +{ + register int c; + register int count; + register int count2; + register sopno pos; + register int i; + register sopno subno; +# define BACKSL (1<<CHAR_BIT) + + pos = HERE(); /* repetion op, if any, covers from here */ + + assert(MORE()); /* caller should have ensured this */ + c = GETNEXT(); + if (c == '\\') { + REQUIRE(MORE(), REG_EESCAPE); + c = BACKSL | (unsigned char)GETNEXT(); + } + switch (c) { + case '.': + if (p->g->cflags®_NEWLINE) + nonnewline(p); + else + EMIT(OANY, 0); + break; + case '[': + p_bracket(p); + break; + case BACKSL|'{': + SETERROR(REG_BADRPT); + break; + case BACKSL|'(': + p->g->nsub++; + subno = p->g->nsub; + if (subno < NPAREN) + p->pbegin[subno] = HERE(); + EMIT(OLPAREN, subno); + /* the MORE here is an error heuristic */ + if (MORE() && !SEETWO('\\', ')')) + p_bre(p, '\\', ')'); + if (subno < NPAREN) { + p->pend[subno] = HERE(); + assert(p->pend[subno] != 0); + } + EMIT(ORPAREN, subno); + REQUIRE(EATTWO('\\', ')'), REG_EPAREN); + break; + case BACKSL|')': /* should not get here -- must be user */ + case BACKSL|'}': + SETERROR(REG_EPAREN); + break; + case BACKSL|'1': + case BACKSL|'2': + case BACKSL|'3': + case BACKSL|'4': + case BACKSL|'5': + case BACKSL|'6': + case BACKSL|'7': + case BACKSL|'8': + case BACKSL|'9': + i = (c&~BACKSL) - '0'; + assert(i < NPAREN); + if (p->pend[i] != 0) { + assert(i <= p->g->nsub); + EMIT(OBACK_, i); + assert(p->pbegin[i] != 0); + assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); + assert(OP(p->strip[p->pend[i]]) == ORPAREN); + (void) dupl(p, p->pbegin[i]+1, p->pend[i]); + EMIT(O_BACK, i); + } else + SETERROR(REG_ESUBREG); + p->g->backrefs = 1; + break; + case '*': + REQUIRE(starordinary, REG_BADRPT); + /* FALLTHROUGH */ + default: + ordinary(p, (char)c); /* takes off BACKSL, if any */ + break; + } + + if (EAT('*')) { /* implemented as +? */ + /* this case does not require the (y|) trick, noKLUDGE */ + INSERT(OPLUS_, pos); + ASTERN(O_PLUS, pos); + INSERT(OQUEST_, pos); + ASTERN(O_QUEST, pos); + } else if (EATTWO('\\', '{')) { + count = p_count(p); + if (EAT(',')) { + if (MORE() && isdigit(PEEK())) { + count2 = p_count(p); + REQUIRE(count <= count2, REG_BADBR); + } else /* single number with comma */ + count2 = INFINITY; + } else /* just a single number */ + count2 = count; + repeat(p, pos, count, count2); + if (!EATTWO('\\', '}')) { /* error heuristics */ + while (MORE() && !SEETWO('\\', '}')) + NEXT(); + REQUIRE(MORE(), REG_EBRACE); + SETERROR(REG_BADBR); + } + } else if (c == (unsigned char)'$') /* $ (but not \$) ends it */ + return(1); + + return(0); +} + +/* + - p_count - parse a repetition count + == static int p_count(register struct parse *p); + */ +static int /* the value */ +p_count(p) +register struct parse *p; +{ + register int count = 0; + register int ndigits = 0; + + while (MORE() && isdigit(PEEK()) && count <= DUPMAX) { + count = count*10 + (GETNEXT() - '0'); + ndigits++; + } + + REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR); + return(count); +} + +/* + - p_bracket - parse a bracketed character list + == static void p_bracket(register struct parse *p); + * + * Note a significant property of this code: if the allocset() did SETERROR, + * no set operations are done. + */ +static void +p_bracket(p) +register struct parse *p; +{ + register cset *cs = allocset(p); + register int invert = 0; + + /* Dept of Truly Sickening Special-Case Kludges */ + if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) { + EMIT(OBOW, 0); + NEXTn(6); + return; + } + if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) { + EMIT(OEOW, 0); + NEXTn(6); + return; + } + + if (EAT('^')) + invert++; /* make note to invert set at end */ + if (EAT(']')) + CHadd(cs, ']'); + else if (EAT('-')) + CHadd(cs, '-'); + while (MORE() && PEEK() != ']' && !SEETWO('-', ']')) + p_b_term(p, cs); + if (EAT('-')) + CHadd(cs, '-'); + MUSTEAT(']', REG_EBRACK); + + if (p->error != 0) /* don't mess things up further */ + return; + + if (p->g->cflags®_ICASE) { + register int i; + register int ci; + + for (i = p->g->csetsize - 1; i >= 0; i--) + if (CHIN(cs, i) && isalpha(i)) { + ci = othercase(i); + if (ci != i) + CHadd(cs, ci); + } + if (cs->multis != NULL) + mccase(p, cs); + } + if (invert) { + register int i; + + for (i = p->g->csetsize - 1; i >= 0; i--) + if (CHIN(cs, i)) + CHsub(cs, i); + else + CHadd(cs, i); + if (p->g->cflags®_NEWLINE) + CHsub(cs, '\n'); + if (cs->multis != NULL) + mcinvert(p, cs); + } + + assert(cs->multis == NULL); /* xxx */ + + if (nch(p, cs) == 1) { /* optimize singleton sets */ + ordinary(p, firstch(p, cs)); + freeset(p, cs); + } else + EMIT(OANYOF, freezeset(p, cs)); +} + +/* + - p_b_term - parse one term of a bracketed character list + == static void p_b_term(register struct parse *p, register cset *cs); + */ +static void +p_b_term(p, cs) +register struct parse *p; +register cset *cs; +{ + register char c; + register char start, finish; + register int i; + + /* classify what we've got */ + switch ((MORE()) ? PEEK() : '\0') { + case '[': + c = (MORE2()) ? PEEK2() : '\0'; + break; + case '-': + SETERROR(REG_ERANGE); + return; /* NOTE RETURN */ + break; + default: + c = '\0'; + break; + } + + switch (c) { + case ':': /* character class */ + NEXT2(); + REQUIRE(MORE(), REG_EBRACK); + c = PEEK(); + REQUIRE(c != '-' && c != ']', REG_ECTYPE); + p_b_cclass(p, cs); + REQUIRE(MORE(), REG_EBRACK); + REQUIRE(EATTWO(':', ']'), REG_ECTYPE); + break; + case '=': /* equivalence class */ + NEXT2(); + REQUIRE(MORE(), REG_EBRACK); + c = PEEK(); + REQUIRE(c != '-' && c != ']', REG_ECOLLATE); + p_b_eclass(p, cs); + REQUIRE(MORE(), REG_EBRACK); + REQUIRE(EATTWO('=', ']'), REG_ECOLLATE); + break; + default: /* symbol, ordinary character, or range */ +/* xxx revision needed for multichar stuff */ + start = p_b_symbol(p); + if (SEE('-') && MORE2() && PEEK2() != ']') { + /* range */ + NEXT(); + if (EAT('-')) + finish = '-'; + else + finish = p_b_symbol(p); + } else + finish = start; +/* xxx what about signed chars here... */ + REQUIRE(start <= finish, REG_ERANGE); + for (i = start; i <= finish; i++) + CHadd(cs, i); + break; + } +} + +/* + - p_b_cclass - parse a character-class name and deal with it + == static void p_b_cclass(register struct parse *p, register cset *cs); + */ +static void +p_b_cclass(p, cs) +register struct parse *p; +register cset *cs; +{ + register char *sp = p->next; + register struct cclass *cp; + register size_t len; + register char *u; + register char c; + + while (MORE() && isalpha(PEEK())) + NEXT(); + len = p->next - sp; + for (cp = cclasses; cp->name != NULL; cp++) + if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0') + break; + if (cp->name == NULL) { + /* oops, didn't find it */ + SETERROR(REG_ECTYPE); + return; + } + + u = cp->chars; + while ((c = *u++) != '\0') + CHadd(cs, c); + for (u = cp->multis; *u != '\0'; u += strlen(u) + 1) + MCadd(p, cs, u); +} + +/* + - p_b_eclass - parse an equivalence-class name and deal with it + == static void p_b_eclass(register struct parse *p, register cset *cs); + * + * This implementation is incomplete. xxx + */ +static void +p_b_eclass(p, cs) +register struct parse *p; +register cset *cs; +{ + register char c; + + c = p_b_coll_elem(p, '='); + CHadd(cs, c); +} + +/* + - p_b_symbol - parse a character or [..]ed multicharacter collating symbol + == static char p_b_symbol(register struct parse *p); + */ +static char /* value of symbol */ +p_b_symbol(p) +register struct parse *p; +{ + register char value; + + REQUIRE(MORE(), REG_EBRACK); + if (!EATTWO('[', '.')) + return(GETNEXT()); + + /* collating symbol */ + value = p_b_coll_elem(p, '.'); + REQUIRE(EATTWO('.', ']'), REG_ECOLLATE); + return(value); +} + +/* + - p_b_coll_elem - parse a collating-element name and look it up + == static char p_b_coll_elem(register struct parse *p, int endc); + */ +static char /* value of collating element */ +p_b_coll_elem(p, endc) +register struct parse *p; +int endc; /* name ended by endc,']' */ +{ + register char *sp = p->next; + register struct cname *cp; + register int len; + + while (MORE() && !SEETWO(endc, ']')) + NEXT(); + if (!MORE()) { + SETERROR(REG_EBRACK); + return(0); + } + len = p->next - sp; + for (cp = cnames; cp->name != NULL; cp++) + if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0') + return(cp->code); /* known name */ + if (len == 1) + return(*sp); /* single character */ + SETERROR(REG_ECOLLATE); /* neither */ + return(0); +} + +/* + - othercase - return the case counterpart of an alphabetic + == static char othercase(int ch); + */ +static char /* if no counterpart, return ch */ +othercase(ch) +int ch; +{ + assert(isalpha(ch)); + if (isupper(ch)) + return(tolower(ch)); + else if (islower(ch)) + return(toupper(ch)); + else /* peculiar, but could happen */ + return(ch); +} + +/* + - bothcases - emit a dualcase version of a two-case character + == static void bothcases(register struct parse *p, int ch); + * + * Boy, is this implementation ever a kludge... + */ +static void +bothcases(p, ch) +register struct parse *p; +int ch; +{ + register char *oldnext = p->next; + register char *oldend = p->end; + char bracket[3]; + + assert(othercase(ch) != ch); /* p_bracket() would recurse */ + p->next = bracket; + p->end = bracket+2; + bracket[0] = ch; + bracket[1] = ']'; + bracket[2] = '\0'; + p_bracket(p); + assert(p->next == bracket+2); + p->next = oldnext; + p->end = oldend; +} + +/* + - ordinary - emit an ordinary character + == static void ordinary(register struct parse *p, register int ch); + */ +static void +ordinary(p, ch) +register struct parse *p; +register int ch; +{ + register cat_t *cap = p->g->categories; + + if ((p->g->cflags®_ICASE) && isalpha(ch) && othercase(ch) != ch) + bothcases(p, ch); + else { + EMIT(OCHAR, (unsigned char)ch); + if (cap[ch] == 0) + cap[ch] = p->g->ncategories++; + } +} + +/* + - nonnewline - emit REG_NEWLINE version of OANY + == static void nonnewline(register struct parse *p); + * + * Boy, is this implementation ever a kludge... + */ +static void +nonnewline(p) +register struct parse *p; +{ + register char *oldnext = p->next; + register char *oldend = p->end; + char bracket[4]; + + p->next = bracket; + p->end = bracket+3; + bracket[0] = '^'; + bracket[1] = '\n'; + bracket[2] = ']'; + bracket[3] = '\0'; + p_bracket(p); + assert(p->next == bracket+3); + p->next = oldnext; + p->end = oldend; +} + +/* + - repeat - generate code for a bounded repetition, recursively if needed + == static void repeat(register struct parse *p, sopno start, int from, int to); + */ +static void +repeat(p, start, from, to) +register struct parse *p; +sopno start; /* operand from here to end of strip */ +int from; /* repeated from this number */ +int to; /* to this number of times (maybe INFINITY) */ +{ + register sopno finish = HERE(); +# define N 2 +# define INF 3 +# define REP(f, t) ((f)*8 + (t)) +# define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N) + register sopno copy; + + if (p->error != 0) /* head off possible runaway recursion */ + return; + + assert(from <= to); + + switch (REP(MAP(from), MAP(to))) { + case REP(0, 0): /* must be user doing this */ + DROP(finish-start); /* drop the operand */ + break; + case REP(0, 1): /* as x{1,1}? */ + case REP(0, N): /* as x{1,n}? */ + case REP(0, INF): /* as x{1,}? */ + /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ + INSERT(OCH_, start); /* offset is wrong... */ + repeat(p, start+1, 1, to); + ASTERN(OOR1, start); + AHEAD(start); /* ... fix it */ + EMIT(OOR2, 0); + AHEAD(THERE()); + ASTERN(O_CH, THERETHERE()); + break; + case REP(1, 1): /* trivial case */ + /* done */ + break; + case REP(1, N): /* as x?x{1,n-1} */ + /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ + INSERT(OCH_, start); + ASTERN(OOR1, start); + AHEAD(start); + EMIT(OOR2, 0); /* offset very wrong... */ + AHEAD(THERE()); /* ...so fix it */ + ASTERN(O_CH, THERETHERE()); + copy = dupl(p, start+1, finish+1); + assert(copy == finish+4); + repeat(p, copy, 1, to-1); + break; + case REP(1, INF): /* as x+ */ + INSERT(OPLUS_, start); + ASTERN(O_PLUS, start); + break; + case REP(N, N): /* as xx{m-1,n-1} */ + copy = dupl(p, start, finish); + repeat(p, copy, from-1, to-1); + break; + case REP(N, INF): /* as xx{n-1,INF} */ + copy = dupl(p, start, finish); + repeat(p, copy, from-1, to); + break; + default: /* "can't happen" */ + SETERROR(REG_ASSERT); /* just in case */ + break; + } +} + +/* + - seterr - set an error condition + == static int seterr(register struct parse *p, int e); + */ +static int /* useless but makes type checking happy */ +seterr(p, e) +register struct parse *p; +int e; +{ + if (p->error == 0) /* keep earliest error condition */ + p->error = e; + p->next = nuls; /* try to bring things to a halt */ + p->end = nuls; + return(0); /* make the return value well-defined */ +} + +/* + - allocset - allocate a set of characters for [] + == static cset *allocset(register struct parse *p); + */ +static cset * +allocset(p) +register struct parse *p; +{ + register int no = p->g->ncsets++; + register size_t nc; + register size_t nbytes; + register cset *cs; + register size_t css = (size_t)p->g->csetsize; + register int i; + + if (no >= p->ncsalloc) { /* need another column of space */ + p->ncsalloc += CHAR_BIT; + nc = p->ncsalloc; + assert(nc % CHAR_BIT == 0); + nbytes = nc / CHAR_BIT * css; + if (p->g->sets == NULL) + p->g->sets = (cset *)malloc(nc * sizeof(cset)); + else + p->g->sets = (cset *)realloc((char *)p->g->sets, + nc * sizeof(cset)); + if (p->g->setbits == NULL) + p->g->setbits = (uch *)malloc(nbytes); + else { + p->g->setbits = (uch *)realloc((char *)p->g->setbits, + nbytes); + /* xxx this isn't right if setbits is now NULL */ + for (i = 0; i < no; i++) + p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT); + } + if (p->g->sets != NULL && p->g->setbits != NULL) + (void) memset((char *)p->g->setbits + (nbytes - css), + 0, css); + else { + no = 0; + SETERROR(REG_ESPACE); + /* caller's responsibility not to do set ops */ + } + } + + assert(p->g->sets != NULL); /* xxx */ + cs = &p->g->sets[no]; + cs->ptr = p->g->setbits + css*((no)/CHAR_BIT); + cs->mask = 1 << ((no) % CHAR_BIT); + cs->hash = 0; + cs->smultis = 0; + cs->multis = NULL; + + return(cs); +} + +/* + - freeset - free a now-unused set + == static void freeset(register struct parse *p, register cset *cs); + */ +static void +freeset(p, cs) +register struct parse *p; +register cset *cs; +{ + register int i; + register cset *top = &p->g->sets[p->g->ncsets]; + register size_t css = (size_t)p->g->csetsize; + + for (i = 0; i < css; i++) + CHsub(cs, i); + if (cs == top-1) /* recover only the easy case */ + p->g->ncsets--; +} + +/* + - freezeset - final processing on a set of characters + == static int freezeset(register struct parse *p, register cset *cs); + * + * The main task here is merging identical sets. This is usually a waste + * of time (although the hash code minimizes the overhead), but can win + * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash + * is done using addition rather than xor -- all ASCII [aA] sets xor to + * the same value! + */ +static int /* set number */ +freezeset(p, cs) +register struct parse *p; +register cset *cs; +{ + register uch h = cs->hash; + register int i; + register cset *top = &p->g->sets[p->g->ncsets]; + register cset *cs2; + register size_t css = (size_t)p->g->csetsize; + + /* look for an earlier one which is the same */ + for (cs2 = &p->g->sets[0]; cs2 < top; cs2++) + if (cs2->hash == h && cs2 != cs) { + /* maybe */ + for (i = 0; i < css; i++) + if (!!CHIN(cs2, i) != !!CHIN(cs, i)) + break; /* no */ + if (i == css) + break; /* yes */ + } + + if (cs2 < top) { /* found one */ + freeset(p, cs); + cs = cs2; + } + + return((int)(cs - p->g->sets)); +} + +/* + - firstch - return first character in a set (which must have at least one) + == static int firstch(register struct parse *p, register cset *cs); + */ +static int /* character; there is no "none" value */ +firstch(p, cs) +register struct parse *p; +register cset *cs; +{ + register int i; + register size_t css = (size_t)p->g->csetsize; + + for (i = 0; i < css; i++) + if (CHIN(cs, i)) + return((char)i); + assert(never); + return(0); /* arbitrary */ +} + +/* + - nch - number of characters in a set + == static int nch(register struct parse *p, register cset *cs); + */ +static int +nch(p, cs) +register struct parse *p; +register cset *cs; +{ + register int i; + register size_t css = (size_t)p->g->csetsize; + register int n = 0; + + for (i = 0; i < css; i++) + if (CHIN(cs, i)) + n++; + return(n); +} + +/* + - mcadd - add a collating element to a cset + == static void mcadd(register struct parse *p, register cset *cs, \ + == register char *cp); + */ +static void +mcadd(p, cs, cp) +register struct parse *p; +register cset *cs; +register char *cp; +{ + register size_t oldend = cs->smultis; + + cs->smultis += strlen(cp) + 1; + if (cs->multis == NULL) + cs->multis = malloc(cs->smultis); + else + cs->multis = realloc(cs->multis, cs->smultis); + if (cs->multis == NULL) { + SETERROR(REG_ESPACE); + return; + } + + (void) strcpy(cs->multis + oldend - 1, cp); + cs->multis[cs->smultis - 1] = '\0'; +} + +/* + - mcsub - subtract a collating element from a cset + == static void mcsub(register cset *cs, register char *cp); + */ +static void +mcsub(cs, cp) +register cset *cs; +register char *cp; +{ + register char *fp = mcfind(cs, cp); + register size_t len = strlen(fp); + + assert(fp != NULL); + (void) memmove(fp, fp + len + 1, + cs->smultis - (fp + len + 1 - cs->multis)); + cs->smultis -= len; + + if (cs->smultis == 0) { + free(cs->multis); + cs->multis = NULL; + return; + } + + cs->multis = realloc(cs->multis, cs->smultis); + assert(cs->multis != NULL); +} + +/* + - mcin - is a collating element in a cset? + == static int mcin(register cset *cs, register char *cp); + */ +static int +mcin(cs, cp) +register cset *cs; +register char *cp; +{ + return(mcfind(cs, cp) != NULL); +} + +/* + - mcfind - find a collating element in a cset + == static char *mcfind(register cset *cs, register char *cp); + */ +static char * +mcfind(cs, cp) +register cset *cs; +register char *cp; +{ + register char *p; + + if (cs->multis == NULL) + return(NULL); + for (p = cs->multis; *p != '\0'; p += strlen(p) + 1) + if (strcmp(cp, p) == 0) + return(p); + return(NULL); +} + +/* + - mcinvert - invert the list of collating elements in a cset + == static void mcinvert(register struct parse *p, register cset *cs); + * + * This would have to know the set of possibilities. Implementation + * is deferred. + */ +static void +mcinvert(p, cs) +register struct parse *p; +register cset *cs; +{ + assert(cs->multis == NULL); /* xxx */ +} + +/* + - mccase - add case counterparts of the list of collating elements in a cset + == static void mccase(register struct parse *p, register cset *cs); + * + * This would have to know the set of possibilities. Implementation + * is deferred. + */ +static void +mccase(p, cs) +register struct parse *p; +register cset *cs; +{ + assert(cs->multis == NULL); /* xxx */ +} + +/* + - isinsets - is this character in any sets? + == static int isinsets(register struct re_guts *g, int c); + */ +static int /* predicate */ +isinsets(g, c) +register struct re_guts *g; +int c; +{ + register uch *col; + register int i; + register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT; + register unsigned uc = (unsigned char)c; + + for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize) + if (col[uc] != 0) + return(1); + return(0); +} + +/* + - samesets - are these two characters in exactly the same sets? + == static int samesets(register struct re_guts *g, int c1, int c2); + */ +static int /* predicate */ +samesets(g, c1, c2) +register struct re_guts *g; +int c1; +int c2; +{ + register uch *col; + register int i; + register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT; + register unsigned uc1 = (unsigned char)c1; + register unsigned uc2 = (unsigned char)c2; + + for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize) + if (col[uc1] != col[uc2]) + return(0); + return(1); +} + +/* + - categorize - sort out character categories + == static void categorize(struct parse *p, register struct re_guts *g); + */ +static void +categorize(p, g) +struct parse *p; +register struct re_guts *g; +{ + register cat_t *cats = g->categories; + register int c; + register int c2; + register cat_t cat; + + /* avoid making error situations worse */ + if (p->error != 0) + return; + + for (c = CHAR_MIN; c <= CHAR_MAX; c++) + if (cats[c] == 0 && isinsets(g, c)) { + cat = g->ncategories++; + cats[c] = cat; + for (c2 = c+1; c2 <= CHAR_MAX; c2++) + if (cats[c2] == 0 && samesets(g, c, c2)) + cats[c2] = cat; + } +} + +/* + - dupl - emit a duplicate of a bunch of sops + == static sopno dupl(register struct parse *p, sopno start, sopno finish); + */ +static sopno /* start of duplicate */ +dupl(p, start, finish) +register struct parse *p; +sopno start; /* from here */ +sopno finish; /* to this less one */ +{ + register sopno ret = HERE(); + register sopno len = finish - start; + + assert(finish >= start); + if (len == 0) + return(ret); + enlarge(p, p->ssize + len); /* this many unexpected additions */ + assert(p->ssize >= p->slen + len); + (void) memcpy((char *)(p->strip + p->slen), + (char *)(p->strip + start), (size_t)len*sizeof(sop)); + p->slen += len; + return(ret); +} + +/* + - doemit - emit a strip operator + == static void doemit(register struct parse *p, sop op, size_t opnd); + * + * It might seem better to implement this as a macro with a function as + * hard-case backup, but it's just too big and messy unless there are + * some changes to the data structures. Maybe later. + */ +static void +doemit(p, op, opnd) +register struct parse *p; +sop op; +size_t opnd; +{ + /* avoid making error situations worse */ + if (p->error != 0) + return; + + /* deal with oversize operands ("can't happen", more or less) */ + assert(opnd < 1<<OPSHIFT); + + /* deal with undersized strip */ + if (p->slen >= p->ssize) + enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */ + assert(p->slen < p->ssize); + + /* finally, it's all reduced to the easy case */ + p->strip[p->slen++] = SOP(op, opnd); +} + +/* + - doinsert - insert a sop into the strip + == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos); + */ +static void +doinsert(p, op, opnd, pos) +register struct parse *p; +sop op; +size_t opnd; +sopno pos; +{ + register sopno sn; + register sop s; + register int i; + + /* avoid making error situations worse */ + if (p->error != 0) + return; + + sn = HERE(); + EMIT(op, opnd); /* do checks, ensure space */ + assert(HERE() == sn+1); + s = p->strip[sn]; + + /* adjust paren pointers */ + assert(pos > 0); + for (i = 1; i < NPAREN; i++) { + if (p->pbegin[i] >= pos) { + p->pbegin[i]++; + } + if (p->pend[i] >= pos) { + p->pend[i]++; + } + } + + memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos], + (HERE()-pos-1)*sizeof(sop)); + p->strip[pos] = s; +} + +/* + - dofwd - complete a forward reference + == static void dofwd(register struct parse *p, sopno pos, sop value); + */ +static void +dofwd(p, pos, value) +register struct parse *p; +register sopno pos; +sop value; +{ + /* avoid making error situations worse */ + if (p->error != 0) + return; + + assert(value < 1<<OPSHIFT); + p->strip[pos] = OP(p->strip[pos]) | value; +} + +/* + - enlarge - enlarge the strip + == static void enlarge(register struct parse *p, sopno size); + */ +static void +enlarge(p, size) +register struct parse *p; +register sopno size; +{ + register sop *sp; + + if (p->ssize >= size) + return; + + sp = (sop *)realloc(p->strip, size*sizeof(sop)); + if (sp == NULL) { + SETERROR(REG_ESPACE); + return; + } + p->strip = sp; + p->ssize = size; +} + +/* + - stripsnug - compact the strip + == static void stripsnug(register struct parse *p, register struct re_guts *g); + */ +static void +stripsnug(p, g) +register struct parse *p; +register struct re_guts *g; +{ + g->nstates = p->slen; + g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop)); + if (g->strip == NULL) { + SETERROR(REG_ESPACE); + g->strip = p->strip; + } +} + +/* + - findmust - fill in must and mlen with longest mandatory literal string + == static void findmust(register struct parse *p, register struct re_guts *g); + * + * This algorithm could do fancy things like analyzing the operands of | + * for common subsequences. Someday. This code is simple and finds most + * of the interesting cases. + * + * Note that must and mlen got initialized during setup. + */ +static void +findmust(p, g) +struct parse *p; +register struct re_guts *g; +{ + register sop *scan; + sop *start; + register sop *newstart; + register sopno newlen; + register sop s; + register char *cp; + register sopno i; + + /* avoid making error situations worse */ + if (p->error != 0) + return; + + /* find the longest OCHAR sequence in strip */ + newlen = 0; + scan = g->strip + 1; + do { + s = *scan++; + switch (OP(s)) { + case OCHAR: /* sequence member */ + if (newlen == 0) /* new sequence */ + newstart = scan - 1; + newlen++; + break; + case OPLUS_: /* things that don't break one */ + case OLPAREN: + case ORPAREN: + break; + case OQUEST_: /* things that must be skipped */ + case OCH_: + scan--; + do { + scan += OPND(s); + s = *scan; + /* assert() interferes w debug printouts */ + if (OP(s) != O_QUEST && OP(s) != O_CH && + OP(s) != OOR2) { + g->iflags |= BAD; + return; + } + } while (OP(s) != O_QUEST && OP(s) != O_CH); + /* fallthrough */ + default: /* things that break a sequence */ + if (newlen > g->mlen) { /* ends one */ + start = newstart; + g->mlen = newlen; + } + newlen = 0; + break; + } + } while (OP(s) != OEND); + + if (g->mlen == 0) /* there isn't one */ + return; + + /* turn it into a character string */ + g->must = malloc((size_t)g->mlen + 1); + if (g->must == NULL) { /* argh; just forget it */ + g->mlen = 0; + return; + } + cp = g->must; + scan = start; + for (i = g->mlen; i > 0; i--) { + while (OP(s = *scan++) != OCHAR) + continue; + assert(cp < g->must + g->mlen); + *cp++ = (char)OPND(s); + } + assert(cp == g->must + g->mlen); + *cp++ = '\0'; /* just on general principles */ +} + +/* + - pluscount - count + nesting + == static sopno pluscount(register struct parse *p, register struct re_guts *g); + */ +static sopno /* nesting depth */ +pluscount(p, g) +struct parse *p; +register struct re_guts *g; +{ + register sop *scan; + register sop s; + register sopno plusnest = 0; + register sopno maxnest = 0; + + if (p->error != 0) + return(0); /* there may not be an OEND */ + + scan = g->strip + 1; + do { + s = *scan++; + switch (OP(s)) { + case OPLUS_: + plusnest++; + break; + case O_PLUS: + if (plusnest > maxnest) + maxnest = plusnest; + plusnest--; + break; + } + } while (OP(s) != OEND); + if (plusnest != 0) + g->iflags |= BAD; + return(maxnest); +} diff --git a/regex/regcomp.ih b/regex/regcomp.ih new file mode 100644 index 0000000..0776e71 --- /dev/null +++ b/regex/regcomp.ih @@ -0,0 +1,51 @@ +/* ========= begin header generated by ./mkh ========= */ +#ifdef __cplusplus +extern "C" { +#endif + +/* === regcomp.c === */ +static void p_ere(register struct parse *p, int stop); +static void p_ere_exp(register struct parse *p); +static void p_str(register struct parse *p); +static void p_bre(register struct parse *p, register int end1, register int end2); +static int p_simp_re(register struct parse *p, int starordinary); +static int p_count(register struct parse *p); +static void p_bracket(register struct parse *p); +static void p_b_term(register struct parse *p, register cset *cs); +static void p_b_cclass(register struct parse *p, register cset *cs); +static void p_b_eclass(register struct parse *p, register cset *cs); +static char p_b_symbol(register struct parse *p); +static char p_b_coll_elem(register struct parse *p, int endc); +static char othercase(int ch); +static void bothcases(register struct parse *p, int ch); +static void ordinary(register struct parse *p, register int ch); +static void nonnewline(register struct parse *p); +static void repeat(register struct parse *p, sopno start, int from, int to); +static int seterr(register struct parse *p, int e); +static cset *allocset(register struct parse *p); +static void freeset(register struct parse *p, register cset *cs); +static int freezeset(register struct parse *p, register cset *cs); +static int firstch(register struct parse *p, register cset *cs); +static int nch(register struct parse *p, register cset *cs); +static void mcadd(register struct parse *p, register cset *cs, register char *cp); +static void mcsub(register cset *cs, register char *cp); +static int mcin(register cset *cs, register char *cp); +static char *mcfind(register cset *cs, register char *cp); +static void mcinvert(register struct parse *p, register cset *cs); +static void mccase(register struct parse *p, register cset *cs); +static int isinsets(register struct re_guts *g, int c); +static int samesets(register struct re_guts *g, int c1, int c2); +static void categorize(struct parse *p, register struct re_guts *g); +static sopno dupl(register struct parse *p, sopno start, sopno finish); +static void doemit(register struct parse *p, sop op, size_t opnd); +static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos); +static void dofwd(register struct parse *p, sopno pos, sop value); +static void enlarge(register struct parse *p, sopno size); +static void stripsnug(register struct parse *p, register struct re_guts *g); +static void findmust(register struct parse *p, register struct re_guts *g); +static sopno pluscount(register struct parse *p, register struct re_guts *g); + +#ifdef __cplusplus +} +#endif +/* ========= end header generated by ./mkh ========= */ diff --git a/regex/regerror.c b/regex/regerror.c new file mode 100644 index 0000000..b9238c8 --- /dev/null +++ b/regex/regerror.c @@ -0,0 +1,126 @@ +#include <sys/types.h> +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#include <limits.h> +#include <stdlib.h> +#include <regex.h> + +#include "utils.h" +#include "regerror.ih" + +/* + = #define REG_OKAY 0 + = #define REG_NOMATCH 1 + = #define REG_BADPAT 2 + = #define REG_ECOLLATE 3 + = #define REG_ECTYPE 4 + = #define REG_EESCAPE 5 + = #define REG_ESUBREG 6 + = #define REG_EBRACK 7 + = #define REG_EPAREN 8 + = #define REG_EBRACE 9 + = #define REG_BADBR 10 + = #define REG_ERANGE 11 + = #define REG_ESPACE 12 + = #define REG_BADRPT 13 + = #define REG_EMPTY 14 + = #define REG_ASSERT 15 + = #define REG_INVARG 16 + = #define REG_ATOI 255 // convert name to number (!) + = #define REG_ITOA 0400 // convert number to name (!) + */ +static struct rerr { + int code; + char *name; + char *explain; +} rerrs[] = { + {REG_OKAY, "REG_OKAY", "no errors detected"}, + {REG_NOMATCH, "REG_NOMATCH", "regexec() failed to match"}, + {REG_BADPAT, "REG_BADPAT", "invalid regular expression"}, + {REG_ECOLLATE, "REG_ECOLLATE", "invalid collating element"}, + {REG_ECTYPE, "REG_ECTYPE", "invalid character class"}, + {REG_EESCAPE, "REG_EESCAPE", "trailing backslash (\\)"}, + {REG_ESUBREG, "REG_ESUBREG", "invalid backreference number"}, + {REG_EBRACK, "REG_EBRACK", "brackets ([ ]) not balanced"}, + {REG_EPAREN, "REG_EPAREN", "parentheses not balanced"}, + {REG_EBRACE, "REG_EBRACE", "braces not balanced"}, + {REG_BADBR, "REG_BADBR", "invalid repetition count(s)"}, + {REG_ERANGE, "REG_ERANGE", "invalid character range"}, + {REG_ESPACE, "REG_ESPACE", "out of memory"}, + {REG_BADRPT, "REG_BADRPT", "repetition-operator operand invalid"}, + {REG_EMPTY, "REG_EMPTY", "empty (sub)expression"}, + {REG_ASSERT, "REG_ASSERT", "\"can't happen\" -- you found a bug"}, + {REG_INVARG, "REG_INVARG", "invalid argument to regex routine"}, + {-1, "", "*** unknown regexp error code ***"} +}; + +/* + - regerror - the interface to error numbers + = extern size_t notbuiltin_regerror(int, const regex_t *, char *, size_t); + */ +/* ARGSUSED */ +size_t +notbuiltin_regerror(errcode, preg, errbuf, errbuf_size) +int errcode; +const regex_t *preg; +char *errbuf; +size_t errbuf_size; +{ + register struct rerr *r; + register size_t len; + register int target = errcode &~ REG_ITOA; + register char *s; + char convbuf[50]; + + if (errcode == REG_ATOI) + s = regatoi(preg, convbuf); + else { + for (r = rerrs; r->code >= 0; r++) + if (r->code == target) + break; + + if (errcode®_ITOA) { + if (r->code >= 0) + (void) strcpy(convbuf, r->name); + else + sprintf(convbuf, "REG_0x%x", target); + assert(strlen(convbuf) < sizeof(convbuf)); + s = convbuf; + } else + s = r->explain; + } + + len = strlen(s) + 1; + if (errbuf_size > 0) { + if (errbuf_size > len) + (void) strcpy(errbuf, s); + else { + (void) strncpy(errbuf, s, errbuf_size-1); + errbuf[errbuf_size-1] = '\0'; + } + } + + return(len); +} + +/* + - regatoi - internal routine to implement REG_ATOI + == static char *regatoi(const regex_t *preg, char *localbuf); + */ +static char * +regatoi(preg, localbuf) +const regex_t *preg; +char *localbuf; +{ + register struct rerr *r; + + for (r = rerrs; r->code >= 0; r++) + if (strcmp(r->name, preg->re_endp) == 0) + break; + if (r->code < 0) + return("0"); + + sprintf(localbuf, "%d", r->code); + return(localbuf); +} diff --git a/regex/regerror.ih b/regex/regerror.ih new file mode 100644 index 0000000..2cb668c --- /dev/null +++ b/regex/regerror.ih @@ -0,0 +1,12 @@ +/* ========= begin header generated by ./mkh ========= */ +#ifdef __cplusplus +extern "C" { +#endif + +/* === regerror.c === */ +static char *regatoi(const regex_t *preg, char *localbuf); + +#ifdef __cplusplus +} +#endif +/* ========= end header generated by ./mkh ========= */ diff --git a/regex/regex.3 b/regex/regex.3 new file mode 100644 index 0000000..bc74709 --- /dev/null +++ b/regex/regex.3 @@ -0,0 +1,509 @@ +.TH REGEX 3 "25 Sept 1997" +.BY "Henry Spencer" +.de ZR +.\" one other place knows this name: the SEE ALSO section +.IR regex (7) \\$1 +.. +.SH NAME +regcomp, regexec, regerror, regfree \- regular-expression library +.SH SYNOPSIS +.ft B +.\".na +#include <sys/types.h> +.br +#include <regex.h> +.HP 10 +int regcomp(regex_t\ *preg, const\ char\ *pattern, int\ cflags); +.HP +int\ regexec(const\ regex_t\ *preg, const\ char\ *string, +size_t\ nmatch, regmatch_t\ pmatch[], int\ eflags); +.HP +size_t\ regerror(int\ errcode, const\ regex_t\ *preg, +char\ *errbuf, size_t\ errbuf_size); +.HP +void\ regfree(regex_t\ *preg); +.\".ad +.ft +.SH DESCRIPTION +These routines implement POSIX 1003.2 regular expressions (``RE''s); +see +.ZR . +.I Regcomp +compiles an RE written as a string into an internal form, +.I regexec +matches that internal form against a string and reports results, +.I regerror +transforms error codes from either into human-readable messages, +and +.I regfree +frees any dynamically-allocated storage used by the internal form +of an RE. +.PP +The header +.I <regex.h> +declares two structure types, +.I regex_t +and +.IR regmatch_t , +the former for compiled internal forms and the latter for match reporting. +It also declares the four functions, +a type +.IR regoff_t , +and a number of constants with names starting with ``REG_''. +.PP +.I Regcomp +compiles the regular expression contained in the +.I pattern +string, +subject to the flags in +.IR cflags , +and places the results in the +.I regex_t +structure pointed to by +.IR preg . +.I Cflags +is the bitwise OR of zero or more of the following flags: +.IP REG_EXTENDED \w'REG_EXTENDED'u+2n +Compile modern (``extended'') REs, +rather than the obsolete (``basic'') REs that +are the default. +.IP REG_BASIC +This is a synonym for 0, +provided as a counterpart to REG_EXTENDED to improve readability. +This is an extension, +compatible with but not specified by POSIX 1003.2, +and should be used with +caution in software intended to be portable to other systems. +.IP REG_NOSPEC +Compile with recognition of all special characters turned off. +All characters are thus considered ordinary, +so the ``RE'' is a literal string. +This is an extension, +compatible with but not specified by POSIX 1003.2, +and should be used with +caution in software intended to be portable to other systems. +REG_EXTENDED and REG_NOSPEC may not be used +in the same call to +.IR regcomp . +.IP REG_ICASE +Compile for matching that ignores upper/lower case distinctions. +See +.ZR . +.IP REG_NOSUB +Compile for matching that need only report success or failure, +not what was matched. +.IP REG_NEWLINE +Compile for newline-sensitive matching. +By default, newline is a completely ordinary character with no special +meaning in either REs or strings. +With this flag, +`[^' bracket expressions and `.' never match newline, +a `^' anchor matches the null string after any newline in the string +in addition to its normal function, +and the `$' anchor matches the null string before any newline in the +string in addition to its normal function. +.IP REG_PEND +The regular expression ends, +not at the first NUL, +but just before the character pointed to by the +.I re_endp +member of the structure pointed to by +.IR preg . +The +.I re_endp +member is of type +.IR const\ char\ * . +This flag permits inclusion of NULs in the RE; +they are considered ordinary characters. +This is an extension, +compatible with but not specified by POSIX 1003.2, +and should be used with +caution in software intended to be portable to other systems. +.PP +When successful, +.I regcomp +returns 0 and fills in the structure pointed to by +.IR preg . +One member of that structure +(other than +.IR re_endp ) +is publicized: +.IR re_nsub , +of type +.IR size_t , +contains the number of parenthesized subexpressions within the RE +(except that the value of this member is undefined if the +REG_NOSUB flag was used). +If +.I regcomp +fails, it returns a non-zero error code; +see DIAGNOSTICS. +.PP +.I Regexec +matches the compiled RE pointed to by +.I preg +against the +.IR string , +subject to the flags in +.IR eflags , +and reports results using +.IR nmatch , +.IR pmatch , +and the returned value. +The RE must have been compiled by a previous invocation of +.IR regcomp . +The compiled form is not altered during execution of +.IR regexec , +so a single compiled RE can be used simultaneously by multiple threads. +.PP +By default, +the NUL-terminated string pointed to by +.I string +is considered to be the text of an entire line, +with the NUL indicating the end of the line. +(That is, +any other end-of-line marker is considered to have been removed +and replaced by the NUL.) +The +.I eflags +argument is the bitwise OR of zero or more of the following flags: +.IP REG_NOTBOL \w'REG_STARTEND'u+2n +The first character of +the string +is not the beginning of a line, so the `^' anchor should not match before it. +This does not affect the behavior of newlines under REG_NEWLINE. +.IP REG_NOTEOL +The NUL terminating +the string +does not end a line, so the `$' anchor should not match before it. +This does not affect the behavior of newlines under REG_NEWLINE. +.IP REG_STARTEND +The string is considered to start at +\fIstring\fR\ + \fIpmatch\fR[0].\fIrm_so\fR +and to have a terminating NUL located at +\fIstring\fR\ + \fIpmatch\fR[0].\fIrm_eo\fR +(there need not actually be a NUL at that location), +regardless of the value of +.IR nmatch . +See below for the definition of +.IR pmatch +and +.IR nmatch . +This is an extension, +compatible with but not specified by POSIX 1003.2, +and should be used with +caution in software intended to be portable to other systems. +Note that a non-zero \fIrm_so\fR does not imply REG_NOTBOL; +REG_STARTEND affects only the location of the string, +not how it is matched. +.PP +See +.ZR +for a discussion of what is matched in situations where an RE or a +portion thereof could match any of several substrings of +.IR string . +.PP +Normally, +.I regexec +returns 0 for success and the non-zero code REG_NOMATCH for failure. +Other non-zero error codes may be returned in exceptional situations; +see DIAGNOSTICS. +.PP +If REG_NOSUB was specified in the compilation of the RE, +or if +.I nmatch +is 0, +.I regexec +ignores the +.I pmatch +argument (but see below for the case where REG_STARTEND is specified). +Otherwise, +.I pmatch +points to an array of +.I nmatch +structures of type +.IR regmatch_t . +Such a structure has at least the members +.I rm_so +and +.IR rm_eo , +both of type +.I regoff_t +(a signed arithmetic type at least as large as an +.I off_t +and a +.IR ssize_t ), +containing respectively the offset of the first character of a substring +and the offset of the first character after the end of the substring. +Offsets are measured from the beginning of the +.I string +argument given to +.IR regexec . +An empty substring is denoted by equal offsets, +both indicating the character following the empty substring. +.PP +The 0th member of the +.I pmatch +array is filled in to indicate what substring of +.I string +was matched by the entire RE. +Remaining members report what substring was matched by parenthesized +subexpressions within the RE; +member +.I i +reports subexpression +.IR i , +with subexpressions counted (starting at 1) by the order of their opening +parentheses in the RE, left to right. +Unused entries in the array\(emcorresponding either to subexpressions that +did not participate in the match at all, or to subexpressions that do not +exist in the RE (that is, \fIi\fR\ > \fIpreg\fR\->\fIre_nsub\fR)\(emhave both +.I rm_so +and +.I rm_eo +set to \-1. +If a subexpression participated in the match several times, +the reported substring is the last one it matched. +(Note, as an example in particular, that when the RE `(b*)+' matches `bbb', +the parenthesized subexpression matches the three `b's and then +an infinite number of empty strings following the last `b', +so the reported substring is one of the empties.) +.PP +If REG_STARTEND is specified, +.I pmatch +must point to at least one +.I regmatch_t +(even if +.I nmatch +is 0 or REG_NOSUB was specified), +to hold the input offsets for REG_STARTEND. +Use for output is still entirely controlled by +.IR nmatch ; +if +.I nmatch +is 0 or REG_NOSUB was specified, +the value of +.IR pmatch [0] +will not be changed by a successful +.IR regexec . +.PP +.I Regerror +maps a non-zero +.I errcode +from either +.I regcomp +or +.I regexec +to a human-readable, printable message. +If +.I preg +is non-NULL, +the error code should have arisen from use of +the +.I regex_t +pointed to by +.IR preg , +and if the error code came from +.IR regcomp , +it should have been the result from the most recent +.I regcomp +using that +.IR regex_t . +.RI ( Regerror +may be able to supply a more detailed message using information +from the +.IR regex_t .) +.I Regerror +places the NUL-terminated message into the buffer pointed to by +.IR errbuf , +limiting the length (including the NUL) to at most +.I errbuf_size +bytes. +If the whole message won't fit, +as much of it as will fit before the terminating NUL is supplied. +In any case, +the returned value is the size of buffer needed to hold the whole +message (including terminating NUL). +If +.I errbuf_size +is 0, +.I errbuf +is ignored but the return value is still correct. +.PP +If the +.I errcode +given to +.I regerror +is first ORed with REG_ITOA, +the ``message'' that results is the printable name of the error code, +e.g. ``REG_NOMATCH'', +rather than an explanation thereof. +If +.I errcode +is REG_ATOI, +then +.I preg +shall be non-NULL and the +.I re_endp +member of the structure it points to +must point to the printable name of an error code; +in this case, the result in +.I errbuf +is the decimal digits of +the numeric value of the error code +(0 if the name is not recognized). +REG_ITOA and REG_ATOI are intended primarily as debugging facilities; +they are extensions, +compatible with but not specified by POSIX 1003.2, +and should be used with +caution in software intended to be portable to other systems. +Be warned also that they are considered experimental and changes are possible. +.PP +.I Regfree +frees any dynamically-allocated storage associated with the compiled RE +pointed to by +.IR preg . +The remaining +.I regex_t +is no longer a valid compiled RE +and the effect of supplying it to +.I regexec +or +.I regerror +is undefined. +.PP +None of these functions references global variables except for tables +of constants; +all are safe for use from multiple threads if the arguments are safe. +.SH IMPLEMENTATION CHOICES +There are a number of decisions that 1003.2 leaves up to the implementor, +either by explicitly saying ``undefined'' or by virtue of them being +forbidden by the RE grammar. +This implementation treats them as follows. +.PP +See +.ZR +for a discussion of the definition of case-independent matching. +.PP +There is no particular limit on the length of REs, +except insofar as memory is limited. +Memory usage is approximately linear in RE size, and largely insensitive +to RE complexity, except for bounded repetitions. +See BUGS for one short RE using them +that will run almost any system out of memory. +.PP +A backslashed character other than one specifically given a magic meaning +by 1003.2 (such magic meanings occur only in obsolete [``basic''] REs) +is taken as an ordinary character. +.PP +Any unmatched [ is a REG_EBRACK error. +.PP +Equivalence classes cannot begin or end bracket-expression ranges. +The endpoint of one range cannot begin another. +.PP +RE_DUP_MAX, the limit on repetition counts in bounded repetitions, is 255. +.PP +A repetition operator (?, *, +, or bounds) cannot follow another +repetition operator. +A repetition operator cannot begin an expression or subexpression +or follow `^' or `|'. +.PP +`|' cannot appear first or last in a (sub)expression or after another `|', +i.e. an operand of `|' cannot be an empty subexpression. +An empty parenthesized subexpression, `()', is legal and matches an +empty (sub)string. +An empty string is not a legal RE. +.PP +A `{' followed by a digit is considered the beginning of bounds for a +bounded repetition, which must then follow the syntax for bounds. +A `{' \fInot\fR followed by a digit is considered an ordinary character. +.PP +`^' and `$' beginning and ending subexpressions in obsolete (``basic'') +REs are anchors, not ordinary characters. +.SH SEE ALSO +grep(1), regex(7) +.PP +POSIX 1003.2, sections 2.8 (Regular Expression Notation) +and +B.5 (C Binding for Regular Expression Matching). +.SH DIAGNOSTICS +Non-zero error codes from +.I regcomp +and +.I regexec +include the following: +.PP +.nf +.ta \w'REG_ECOLLATE'u+3n +REG_NOMATCH regexec() failed to match +REG_BADPAT invalid regular expression +REG_ECOLLATE invalid collating element +REG_ECTYPE invalid character class +REG_EESCAPE \e applied to unescapable character +REG_ESUBREG invalid backreference number +REG_EBRACK brackets [ ] not balanced +REG_EPAREN parentheses ( ) not balanced +REG_EBRACE braces { } not balanced +REG_BADBR invalid repetition count(s) in { } +REG_ERANGE invalid character range in [ ] +REG_ESPACE ran out of memory +REG_BADRPT ?, *, or + operand invalid +REG_EMPTY empty (sub)expression +REG_ASSERT ``can't happen''\(emyou found a bug +REG_INVARG invalid argument, e.g. negative-length string +.fi +.SH HISTORY +Written by Henry Spencer, +henry@zoo.toronto.edu. +.SH BUGS +This is an alpha release with known defects. +Please report problems. +.PP +There is one known functionality bug. +The implementation of internationalization is incomplete: +the locale is always assumed to be the default one of 1003.2, +and only the collating elements etc. of that locale are available. +.PP +The back-reference code is subtle and doubts linger about its correctness +in complex cases. +.PP +.I Regexec +performance is poor. +This will improve with later releases. +.I Nmatch +exceeding 0 is expensive; +.I nmatch +exceeding 1 is worse. +.I Regexec +is largely insensitive to RE complexity \fIexcept\fR that back +references are massively expensive. +RE length does matter; in particular, there is a strong speed bonus +for keeping RE length under about 30 characters, +with most special characters counting roughly double. +.PP +.I Regcomp +implements bounded repetitions by macro expansion, +which is costly in time and space if counts are large +or bounded repetitions are nested. +An RE like, say, +`((((a{1,100}){1,100}){1,100}){1,100}){1,100}' +will (eventually) run almost any existing machine out of swap space. +.PP +There are suspected problems with response to obscure error conditions. +Notably, +certain kinds of internal overflow, +produced only by truly enormous REs or by multiply nested bounded repetitions, +are probably not handled well. +.PP +Due to a mistake in 1003.2, things like `a)b' are legal REs because `)' is +a special character only in the presence of a previous unmatched `('. +This can't be fixed until the spec is fixed. +.PP +The standard's definition of back references is vague. +For example, does +`a\e(\e(b\e)*\e2\e)*d' match `abbbd'? +Until the standard is clarified, +behavior in such cases should not be relied on. +.PP +The implementation of word-boundary matching is a bit of a kludge, +and bugs may lurk in combinations of word-boundary matching and anchoring. diff --git a/regex/regex.7 b/regex/regex.7 new file mode 100644 index 0000000..0fa1802 --- /dev/null +++ b/regex/regex.7 @@ -0,0 +1,235 @@ +.TH REGEX 7 "25 Oct 1995" +.BY "Henry Spencer" +.SH NAME +regex \- POSIX 1003.2 regular expressions +.SH DESCRIPTION +Regular expressions (``RE''s), +as defined in POSIX 1003.2, come in two forms: +modern REs (roughly those of +.IR egrep ; +1003.2 calls these ``extended'' REs) +and obsolete REs (roughly those of +.IR ed ; +1003.2 ``basic'' REs). +Obsolete REs mostly exist for backward compatibility in some old programs; +they will be discussed at the end. +1003.2 leaves some aspects of RE syntax and semantics open; +`\(dg' marks decisions on these aspects that +may not be fully portable to other 1003.2 implementations. +.PP +A (modern) RE is one\(dg or more non-empty\(dg \fIbranches\fR, +separated by `|'. +It matches anything that matches one of the branches. +.PP +A branch is one\(dg or more \fIpieces\fR, concatenated. +It matches a match for the first, followed by a match for the second, etc. +.PP +A piece is an \fIatom\fR possibly followed +by a single\(dg `*', `+', `?', or \fIbound\fR. +An atom followed by `*' matches a sequence of 0 or more matches of the atom. +An atom followed by `+' matches a sequence of 1 or more matches of the atom. +An atom followed by `?' matches a sequence of 0 or 1 matches of the atom. +.PP +A \fIbound\fR is `{' followed by an unsigned decimal integer, +possibly followed by `,' +possibly followed by another unsigned decimal integer, +always followed by `}'. +The integers must lie between 0 and RE_DUP_MAX (255\(dg) inclusive, +and if there are two of them, the first may not exceed the second. +An atom followed by a bound containing one integer \fIi\fR +and no comma matches +a sequence of exactly \fIi\fR matches of the atom. +An atom followed by a bound +containing one integer \fIi\fR and a comma matches +a sequence of \fIi\fR or more matches of the atom. +An atom followed by a bound +containing two integers \fIi\fR and \fIj\fR matches +a sequence of \fIi\fR through \fIj\fR (inclusive) matches of the atom. +.PP +An atom is a regular expression enclosed in `()' (matching a match for the +regular expression), +an empty set of `()' (matching the null string)\(dg, +a \fIbracket expression\fR (see below), `.' +(matching any single character), `^' (matching the null string at the +beginning of a line), `$' (matching the null string at the +end of a line), a `\e' followed by one of the characters +`^.[$()|*+?{\e' +(matching that character taken as an ordinary character), +a `\e' followed by any other character\(dg +(matching that character taken as an ordinary character, +as if the `\e' had not been present\(dg), +or a single character with no other significance (matching that character). +A `{' followed by a character other than a digit is an ordinary +character, not the beginning of a bound\(dg. +It is illegal to end an RE with `\e'. +.PP +A \fIbracket expression\fR is a list of characters enclosed in `[]'. +It normally matches any single character from the list (but see below). +If the list begins with `^', +it matches any single character +(but see below) \fInot\fR from the rest of the list. +If two characters in the list are separated by `\-', this is shorthand +for the full \fIrange\fR of characters between those two (inclusive) in the +collating sequence, +e.g. `[0\-9]' in ASCII matches any decimal digit. +It is illegal\(dg for two ranges to share an +endpoint, e.g. `a\-c\-e'. +Ranges are very collating-sequence-dependent, +and portable programs should avoid relying on them. +.PP +To include a literal `]' in the list, make it the first character +(following a possible `^'). +To include a literal `\-', make it the first or last character, +or the second endpoint of a range. +To use a literal `\-' as the first endpoint of a range, +enclose it in `[.' and `.]' to make it a collating element (see below). +With the exception of these and some combinations using `[' (see next +paragraphs), all other special characters, including `\e', lose their +special significance within a bracket expression. +.PP +Within a bracket expression, a collating element (a character, +a multi-character sequence that collates as if it were a single character, +or a collating-sequence name for either) +enclosed in `[.' and `.]' stands for the +sequence of characters of that collating element. +The sequence is a single element of the bracket expression's list. +A bracket expression containing a multi-character collating element +can thus match more than one character, +e.g. if the collating sequence includes a `ch' collating element, +then the RE `[[.ch.]]*c' matches the first five characters +of `chchcc'. +.PP +Within a bracket expression, a collating element enclosed in `[=' and +`=]' is an equivalence class, standing for the sequences of characters +of all collating elements equivalent to that one, including itself. +(If there are no other equivalent collating elements, +the treatment is as if the enclosing delimiters were `[.' and `.]'.) +For example, if o and \o'o^' are the members of an equivalence class, +then `[[=o=]]', `[[=\o'o^'=]]', and `[o\o'o^']' are all synonymous. +An equivalence class may not\(dg be an endpoint +of a range. +.PP +Within a bracket expression, the name of a \fIcharacter class\fR enclosed +in `[:' and `:]' stands for the list of all characters belonging to that +class. +Standard character class names are: +.PP +.RS +.nf +.ta 3c 6c 9c +alnum digit punct +alpha graph space +blank lower upper +cntrl print xdigit +.fi +.RE +.PP +These stand for the character classes defined in +.IR ctype (3). +A locale may provide others. +A character class may not be used as an endpoint of a range. +.PP +There are two special cases\(dg of bracket expressions: +the bracket expressions `[[:<:]]' and `[[:>:]]' match the null string at +the beginning and end of a word respectively. +A word is defined as a sequence of +word characters +which is neither preceded nor followed by +word characters. +A word character is an +.I alnum +character (as defined by +.IR ctype (3)) +or an underscore. +This is an extension, +compatible with but not specified by POSIX 1003.2, +and should be used with +caution in software intended to be portable to other systems. +.PP +In the event that an RE could match more than one substring of a given +string, +the RE matches the one starting earliest in the string. +If the RE could match more than one substring starting at that point, +it matches the longest. +Subexpressions also match the longest possible substrings, subject to +the constraint that the whole match be as long as possible, +with subexpressions starting earlier in the RE taking priority over +ones starting later. +Note that higher-level subexpressions thus take priority over +their lower-level component subexpressions. +.PP +Match lengths are measured in characters, not collating elements. +A null string is considered longer than no match at all. +For example, +`bb*' matches the three middle characters of `abbbc', +`(wee|week)(knights|nights)' matches all ten characters of `weeknights', +when `(.*).*' is matched against `abc' the parenthesized subexpression +matches all three characters, and +when `(a*)*' is matched against `bc' both the whole RE and the parenthesized +subexpression match the null string. +.PP +If case-independent matching is specified, +the effect is much as if all case distinctions had vanished from the +alphabet. +When an alphabetic that exists in multiple cases appears as an +ordinary character outside a bracket expression, it is effectively +transformed into a bracket expression containing both cases, +e.g. `x' becomes `[xX]'. +When it appears inside a bracket expression, all case counterparts +of it are added to the bracket expression, so that (e.g.) `[x]' +becomes `[xX]' and `[^x]' becomes `[^xX]'. +.PP +No particular limit is imposed on the length of REs\(dg. +Programs intended to be portable should not employ REs longer +than 256 bytes, +as an implementation can refuse to accept such REs and remain +POSIX-compliant. +.PP +Obsolete (``basic'') regular expressions differ in several respects. +`|', `+', and `?' are ordinary characters and there is no equivalent +for their functionality. +The delimiters for bounds are `\e{' and `\e}', +with `{' and `}' by themselves ordinary characters. +The parentheses for nested subexpressions are `\e(' and `\e)', +with `(' and `)' by themselves ordinary characters. +`^' is an ordinary character except at the beginning of the +RE or\(dg the beginning of a parenthesized subexpression, +`$' is an ordinary character except at the end of the +RE or\(dg the end of a parenthesized subexpression, +and `*' is an ordinary character if it appears at the beginning of the +RE or the beginning of a parenthesized subexpression +(after a possible leading `^'). +Finally, there is one new type of atom, a \fIback reference\fR: +`\e' followed by a non-zero decimal digit \fId\fR +matches the same sequence of characters +matched by the \fId\fRth parenthesized subexpression +(numbering subexpressions by the positions of their opening parentheses, +left to right), +so that (e.g.) `\e([bc]\e)\e1' matches `bb' or `cc' but not `bc'. +.SH SEE ALSO +regex(3) +.PP +POSIX 1003.2, section 2.8 (Regular Expression Notation). +.SH HISTORY +Written by Henry Spencer, based on the 1003.2 spec. +.SH BUGS +Having two kinds of REs is a botch. +.PP +The current 1003.2 spec says that `)' is an ordinary character in +the absence of an unmatched `('; +this was an unintentional result of a wording error, +and change is likely. +Avoid relying on it. +.PP +Back references are a dreadful botch, +posing major problems for efficient implementations. +They are also somewhat vaguely defined +(does +`a\e(\e(b\e)*\e2\e)*d' match `abbbd'?). +Avoid using them. +.PP +1003.2's specification of case-independent matching is vague. +The ``one case implies all cases'' definition given above +is current consensus among implementors as to the right interpretation. +.PP +The syntax for word boundaries is incredibly ugly. diff --git a/regex/regex.h b/regex/regex.h new file mode 100644 index 0000000..e3f81bf --- /dev/null +++ b/regex/regex.h @@ -0,0 +1,74 @@ +#ifndef _REGEX_H_ +#define _REGEX_H_ /* never again */ +/* ========= begin header generated by ./mkh ========= */ +#ifdef __cplusplus +extern "C" { +#endif + +/* === regex2.h === */ +typedef off_t regoff_t; +typedef struct { + int re_magic; + size_t re_nsub; /* number of parenthesized subexpressions */ + const char *re_endp; /* end pointer for REG_PEND */ + struct re_guts *re_g; /* none of your business :-) */ +} regex_t; +typedef struct { + regoff_t rm_so; /* start of match */ + regoff_t rm_eo; /* end of match */ +} regmatch_t; + + +/* === regcomp.c === */ +extern int notbuiltin_regcomp(regex_t *, const char *, int); +#define REG_BASIC 0000 +#define REG_EXTENDED 0001 +#define REG_ICASE 0002 +#define REG_NOSUB 0004 +#define REG_NEWLINE 0010 +#define REG_NOSPEC 0020 +#define REG_PEND 0040 +#define REG_DUMP 0200 + + +/* === regerror.c === */ +#define REG_OKAY 0 +#define REG_NOMATCH 1 +#define REG_BADPAT 2 +#define REG_ECOLLATE 3 +#define REG_ECTYPE 4 +#define REG_EESCAPE 5 +#define REG_ESUBREG 6 +#define REG_EBRACK 7 +#define REG_EPAREN 8 +#define REG_EBRACE 9 +#define REG_BADBR 10 +#define REG_ERANGE 11 +#define REG_ESPACE 12 +#define REG_BADRPT 13 +#define REG_EMPTY 14 +#define REG_ASSERT 15 +#define REG_INVARG 16 +#define REG_ATOI 255 /* convert name to number (!) */ +#define REG_ITOA 0400 /* convert number to name (!) */ +extern size_t notbuiltin_regerror(int, const regex_t *, char *, size_t); + + +/* === regexec.c === */ +extern int notbuiltin_regexec(const regex_t *, const char *, size_t, regmatch_t [], int); +#define REG_NOTBOL 00001 +#define REG_NOTEOL 00002 +#define REG_STARTEND 00004 +#define REG_TRACE 00400 /* tracing of execution */ +#define REG_LARGE 01000 /* force large representation */ +#define REG_BACKR 02000 /* force use of backref code */ + + +/* === regfree.c === */ +extern void notbuiltin_regfree(regex_t *); + +#ifdef __cplusplus +} +#endif +/* ========= end header generated by ./mkh ========= */ +#endif diff --git a/regex/regex2.h b/regex/regex2.h new file mode 100644 index 0000000..58fd8d8 --- /dev/null +++ b/regex/regex2.h @@ -0,0 +1,134 @@ +/* + * First, the stuff that ends up in the outside-world include file + = typedef off_t regoff_t; + = typedef struct { + = int re_magic; + = size_t re_nsub; // number of parenthesized subexpressions + = const char *re_endp; // end pointer for REG_PEND + = struct re_guts *re_g; // none of your business :-) + = } regex_t; + = typedef struct { + = regoff_t rm_so; // start of match + = regoff_t rm_eo; // end of match + = } regmatch_t; + */ +/* + * internals of regex_t + */ +#define MAGIC1 ((('r'^0200)<<8) | 'e') + +/* + * The internal representation is a *strip*, a sequence of + * operators ending with an endmarker. (Some terminology etc. is a + * historical relic of earlier versions which used multiple strips.) + * Certain oddities in the representation are there to permit running + * the machinery backwards; in particular, any deviation from sequential + * flow must be marked at both its source and its destination. Some + * fine points: + * + * - OPLUS_ and O_PLUS are *inside* the loop they create. + * - OQUEST_ and O_QUEST are *outside* the bypass they create. + * - OCH_ and O_CH are *outside* the multi-way branch they create, while + * OOR1 and OOR2 are respectively the end and the beginning of one of + * the branches. Note that there is an implicit OOR2 following OCH_ + * and an implicit OOR1 preceding O_CH. + * + * In state representations, an operator's bit is on to signify a state + * immediately *preceding* "execution" of that operator. + */ +typedef long sop; /* strip operator */ +typedef long sopno; +#define OPRMASK 0x7c000000 +#define OPDMASK 0x03ffffff +#define OPSHIFT (26) +#define OP(n) ((n)&OPRMASK) +#define OPND(n) ((n)&OPDMASK) +#define SOP(op, opnd) ((op)|(opnd)) +/* operators meaning operand */ +/* (back, fwd are offsets) */ +#define OEND (1<<OPSHIFT) /* endmarker - */ +#define OCHAR (2<<OPSHIFT) /* character unsigned char */ +#define OBOL (3<<OPSHIFT) /* left anchor - */ +#define OEOL (4<<OPSHIFT) /* right anchor - */ +#define OANY (5<<OPSHIFT) /* . - */ +#define OANYOF (6<<OPSHIFT) /* [...] set number */ +#define OBACK_ (7<<OPSHIFT) /* begin \d paren number */ +#define O_BACK (8<<OPSHIFT) /* end \d paren number */ +#define OPLUS_ (9<<OPSHIFT) /* + prefix fwd to suffix */ +#define O_PLUS (10<<OPSHIFT) /* + suffix back to prefix */ +#define OQUEST_ (11<<OPSHIFT) /* ? prefix fwd to suffix */ +#define O_QUEST (12<<OPSHIFT) /* ? suffix back to prefix */ +#define OLPAREN (13<<OPSHIFT) /* ( fwd to ) */ +#define ORPAREN (14<<OPSHIFT) /* ) back to ( */ +#define OCH_ (15<<OPSHIFT) /* begin choice fwd to OOR2 */ +#define OOR1 (16<<OPSHIFT) /* | pt. 1 back to OOR1 or OCH_ */ +#define OOR2 (17<<OPSHIFT) /* | pt. 2 fwd to OOR2 or O_CH */ +#define O_CH (18<<OPSHIFT) /* end choice back to OOR1 */ +#define OBOW (19<<OPSHIFT) /* begin word - */ +#define OEOW (20<<OPSHIFT) /* end word - */ + +/* + * Structure for [] character-set representation. Character sets are + * done as bit vectors, grouped 8 to a byte vector for compactness. + * The individual set therefore has both a pointer to the byte vector + * and a mask to pick out the relevant bit of each byte. A hash code + * simplifies testing whether two sets could be identical. + * + * This will get trickier for multicharacter collating elements. As + * preliminary hooks for dealing with such things, we also carry along + * a string of multi-character elements, and decide the size of the + * vectors at run time. + */ +typedef struct { + uch *ptr; /* -> uch [csetsize] */ + uch mask; /* bit within array */ + uch hash; /* hash code */ + size_t smultis; + char *multis; /* -> char[smulti] ab\0cd\0ef\0\0 */ +} cset; +/* note that CHadd and CHsub are unsafe, and CHIN doesn't yield 0/1 */ +#define CHadd(cs, c) ((cs)->ptr[(uch)(c)] |= (cs)->mask, (cs)->hash += (c)) +#define CHsub(cs, c) ((cs)->ptr[(uch)(c)] &= ~(cs)->mask, (cs)->hash -= (c)) +#define CHIN(cs, c) ((cs)->ptr[(uch)(c)] & (cs)->mask) +#define MCadd(p, cs, cp) mcadd(p, cs, cp) /* regcomp() internal fns */ +#define MCsub(p, cs, cp) mcsub(p, cs, cp) +#define MCin(p, cs, cp) mcin(p, cs, cp) + +/* stuff for character categories */ +typedef unsigned char cat_t; + +/* + * main compiled-expression structure + */ +struct re_guts { + int magic; +# define MAGIC2 ((('R'^0200)<<8)|'E') + sop *strip; /* malloced area for strip */ + int csetsize; /* number of bits in a cset vector */ + int ncsets; /* number of csets in use */ + cset *sets; /* -> cset [ncsets] */ + uch *setbits; /* -> uch[csetsize][ncsets/CHAR_BIT] */ + int cflags; /* copy of regcomp() cflags argument */ + sopno nstates; /* = number of sops */ + sopno firststate; /* the initial OEND (normally 0) */ + sopno laststate; /* the final OEND */ + int iflags; /* internal flags */ +# define USEBOL 01 /* used ^ */ +# define USEEOL 02 /* used $ */ +# define BAD 04 /* something wrong */ + int nbol; /* number of ^ used */ + int neol; /* number of $ used */ + int ncategories; /* how many character categories */ + cat_t *categories; /* ->catspace[-CHAR_MIN] */ + char *must; /* match must contain this string */ + int mlen; /* length of must */ + size_t nsub; /* copy of re_nsub */ + int backrefs; /* does it use back references? */ + sopno nplus; /* how deep does it nest +s? */ + /* catspace must be last */ + cat_t catspace[1]; /* actually [NC] */ +}; + +/* misc utilities */ +#define OUT (CHAR_MAX+1) /* a non-character value */ +#define ISWORD(c) (isalnum(c) || (c) == '_') diff --git a/regex/regexec.c b/regex/regexec.c new file mode 100644 index 0000000..6ab320e --- /dev/null +++ b/regex/regexec.c @@ -0,0 +1,138 @@ +/* + * the outer shell of regexec() + * + * This file includes engine.c *twice*, after muchos fiddling with the + * macros that code uses. This lets the same code operate on two different + * representations for state sets. + */ +#include <sys/types.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <limits.h> +#include <ctype.h> +#include <regex.h> + +#include "utils.h" +#include "regex2.h" + +static int nope = 0; /* for use in asserts; shuts lint up */ + +/* macros for manipulating states, small version */ +#define states unsigned +#define states1 unsigned /* for later use in regexec() decision */ +#define CLEAR(v) ((v) = 0) +#define SET0(v, n) ((v) &= ~((unsigned)1 << (n))) +#define SET1(v, n) ((v) |= (unsigned)1 << (n)) +#define ISSET(v, n) ((v) & ((unsigned)1 << (n))) +#define ASSIGN(d, s) ((d) = (s)) +#define EQ(a, b) ((a) == (b)) +#define STATEVARS int dummy /* dummy version */ +#define STATESETUP(m, n) /* nothing */ +#define STATETEARDOWN(m) /* nothing */ +#define SETUP(v) ((v) = 0) +#define onestate unsigned +#define INIT(o, n) ((o) = (unsigned)1 << (n)) +#define INC(o) ((o) <<= 1) +#define ISSTATEIN(v, o) ((v) & (o)) +/* some abbreviations; note that some of these know variable names! */ +/* do "if I'm here, I can also be there" etc without branches */ +#define FWD(dst, src, n) ((dst) |= ((unsigned)(src)&(here)) << (n)) +#define BACK(dst, src, n) ((dst) |= ((unsigned)(src)&(here)) >> (n)) +#define ISSETBACK(v, n) ((v) & ((unsigned)here >> (n))) +/* function names */ +#define SNAMES /* engine.c looks after details */ + +#include "engine.c" + +/* now undo things */ +#undef states +#undef CLEAR +#undef SET0 +#undef SET1 +#undef ISSET +#undef ASSIGN +#undef EQ +#undef STATEVARS +#undef STATESETUP +#undef STATETEARDOWN +#undef SETUP +#undef onestate +#undef INIT +#undef INC +#undef ISSTATEIN +#undef FWD +#undef BACK +#undef ISSETBACK +#undef SNAMES + +/* macros for manipulating states, large version */ +#define states char * +#define CLEAR(v) memset(v, 0, m->g->nstates) +#define SET0(v, n) ((v)[n] = 0) +#define SET1(v, n) ((v)[n] = 1) +#define ISSET(v, n) ((v)[n]) +#define ASSIGN(d, s) memcpy(d, s, m->g->nstates) +#define EQ(a, b) (memcmp(a, b, m->g->nstates) == 0) +#define STATEVARS int vn; char *space +#define STATESETUP(m, nv) { (m)->space = malloc((nv)*(m)->g->nstates); \ + if ((m)->space == NULL) return(REG_ESPACE); \ + (m)->vn = 0; } +#define STATETEARDOWN(m) { free((m)->space); } +#define SETUP(v) ((v) = &m->space[m->vn++ * m->g->nstates]) +#define onestate int +#define INIT(o, n) ((o) = (n)) +#define INC(o) ((o)++) +#define ISSTATEIN(v, o) ((v)[o]) +/* some abbreviations; note that some of these know variable names! */ +/* do "if I'm here, I can also be there" etc without branches */ +#define FWD(dst, src, n) ((dst)[here+(n)] |= (src)[here]) +#define BACK(dst, src, n) ((dst)[here-(n)] |= (src)[here]) +#define ISSETBACK(v, n) ((v)[here - (n)]) +/* function names */ +#define LNAMES /* flag */ + +#include "engine.c" + +/* + - regexec - interface for matching + = extern int notbuiltin_regexec(const regex_t *, const char *, size_t, \ + = regmatch_t [], int); + = #define REG_NOTBOL 00001 + = #define REG_NOTEOL 00002 + = #define REG_STARTEND 00004 + = #define REG_TRACE 00400 // tracing of execution + = #define REG_LARGE 01000 // force large representation + = #define REG_BACKR 02000 // force use of backref code + * + * We put this here so we can exploit knowledge of the state representation + * when choosing which matcher to call. Also, by this point the matchers + * have been prototyped. + */ +int /* 0 success, REG_NOMATCH failure */ +notbuiltin_regexec(preg, string, nmatch, pmatch, eflags) +const regex_t *preg; +const char *string; +size_t nmatch; +regmatch_t pmatch[]; +int eflags; +{ + register struct re_guts *g = preg->re_g; +#ifdef REDEBUG +# define GOODFLAGS(f) (f) +#else +# define GOODFLAGS(f) ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND)) +#endif + + if (preg->re_magic != MAGIC1 || g->magic != MAGIC2) + return(REG_BADPAT); + assert(!(g->iflags&BAD)); + if (g->iflags&BAD) /* backstop for no-debug case */ + return(REG_BADPAT); + eflags = GOODFLAGS(eflags); + + if (g->nstates <= CHAR_BIT*sizeof(states1) && !(eflags®_LARGE)) + return(smatcher(g, (char *)string, nmatch, pmatch, eflags)); + else + return(lmatcher(g, (char *)string, nmatch, pmatch, eflags)); +} diff --git a/regex/regfree.c b/regex/regfree.c new file mode 100644 index 0000000..bfcde53 --- /dev/null +++ b/regex/regfree.c @@ -0,0 +1,37 @@ +#include <sys/types.h> +#include <stdio.h> +#include <stdlib.h> +#include <regex.h> + +#include "utils.h" +#include "regex2.h" + +/* + - regfree - free everything + = extern void notbuiltin_regfree(regex_t *); + */ +void +notbuiltin_regfree(preg) +regex_t *preg; +{ + register struct re_guts *g; + + if (preg->re_magic != MAGIC1) /* oops */ + return; /* nice to complain, but hard */ + + g = preg->re_g; + if (g == NULL || g->magic != MAGIC2) /* oops again */ + return; + preg->re_magic = 0; /* mark it invalid */ + g->magic = 0; /* mark it invalid */ + + if (g->strip != NULL) + free((char *)g->strip); + if (g->sets != NULL) + free((char *)g->sets); + if (g->setbits != NULL) + free((char *)g->setbits); + if (g->must != NULL) + free(g->must); + free((char *)g); +} diff --git a/regex/split.c b/regex/split.c new file mode 100644 index 0000000..188bdb7 --- /dev/null +++ b/regex/split.c @@ -0,0 +1,316 @@ +#include <stdio.h> +#include <string.h> + +/* + - split - divide a string into fields, like awk split() + = int split(char *string, char *fields[], int nfields, char *sep); + */ +int /* number of fields, including overflow */ +split(string, fields, nfields, sep) +char *string; +char *fields[]; /* list is not NULL-terminated */ +int nfields; /* number of entries available in fields[] */ +char *sep; /* "" white, "c" single char, "ab" [ab]+ */ +{ + register char *p = string; + register char c; /* latest character */ + register char sepc = sep[0]; + register char sepc2; + register int fn; + register char **fp = fields; + register char *sepp; + register int trimtrail; + + /* white space */ + if (sepc == '\0') { + while ((c = *p++) == ' ' || c == '\t') + continue; + p--; + trimtrail = 1; + sep = " \t"; /* note, code below knows this is 2 long */ + sepc = ' '; + } else + trimtrail = 0; + sepc2 = sep[1]; /* now we can safely pick this up */ + + /* catch empties */ + if (*p == '\0') + return(0); + + /* single separator */ + if (sepc2 == '\0') { + fn = nfields; + for (;;) { + *fp++ = p; + fn--; + if (fn == 0) + break; + while ((c = *p++) != sepc) + if (c == '\0') + return(nfields - fn); + *(p-1) = '\0'; + } + /* we have overflowed the fields vector -- just count them */ + fn = nfields; + for (;;) { + while ((c = *p++) != sepc) + if (c == '\0') + return(fn); + fn++; + } + /* not reached */ + } + + /* two separators */ + if (sep[2] == '\0') { + fn = nfields; + for (;;) { + *fp++ = p; + fn--; + while ((c = *p++) != sepc && c != sepc2) + if (c == '\0') { + if (trimtrail && **(fp-1) == '\0') + fn++; + return(nfields - fn); + } + if (fn == 0) + break; + *(p-1) = '\0'; + while ((c = *p++) == sepc || c == sepc2) + continue; + p--; + } + /* we have overflowed the fields vector -- just count them */ + fn = nfields; + while (c != '\0') { + while ((c = *p++) == sepc || c == sepc2) + continue; + p--; + fn++; + while ((c = *p++) != '\0' && c != sepc && c != sepc2) + continue; + } + /* might have to trim trailing white space */ + if (trimtrail) { + p--; + while ((c = *--p) == sepc || c == sepc2) + continue; + p++; + if (*p != '\0') { + if (fn == nfields+1) + *p = '\0'; + fn--; + } + } + return(fn); + } + + /* n separators */ + fn = 0; + for (;;) { + if (fn < nfields) + *fp++ = p; + fn++; + for (;;) { + c = *p++; + if (c == '\0') + return(fn); + sepp = sep; + while ((sepc = *sepp++) != '\0' && sepc != c) + continue; + if (sepc != '\0') /* it was a separator */ + break; + } + if (fn < nfields) + *(p-1) = '\0'; + for (;;) { + c = *p++; + sepp = sep; + while ((sepc = *sepp++) != '\0' && sepc != c) + continue; + if (sepc == '\0') /* it wasn't a separator */ + break; + } + p--; + } + + /* not reached */ +} + +#ifdef TEST_SPLIT + + +/* + * test program + * pgm runs regression + * pgm sep splits stdin lines by sep + * pgm str sep splits str by sep + * pgm str sep n splits str by sep n times + */ +int +main(argc, argv) +int argc; +char *argv[]; +{ + char buf[512]; + register int n; +# define MNF 10 + char *fields[MNF]; + + if (argc > 4) + for (n = atoi(argv[3]); n > 0; n--) { + (void) strcpy(buf, argv[1]); + } + else if (argc > 3) + for (n = atoi(argv[3]); n > 0; n--) { + (void) strcpy(buf, argv[1]); + (void) split(buf, fields, MNF, argv[2]); + } + else if (argc > 2) + dosplit(argv[1], argv[2]); + else if (argc > 1) + while (fgets(buf, sizeof(buf), stdin) != NULL) { + buf[strlen(buf)-1] = '\0'; /* stomp newline */ + dosplit(buf, argv[1]); + } + else + regress(); + + exit(0); +} + +dosplit(string, seps) +char *string; +char *seps; +{ +# define NF 5 + char *fields[NF]; + register int nf; + + nf = split(string, fields, NF, seps); + print(nf, NF, fields); +} + +print(nf, nfp, fields) +int nf; +int nfp; +char *fields[]; +{ + register int fn; + register int bound; + + bound = (nf > nfp) ? nfp : nf; + printf("%d:\t", nf); + for (fn = 0; fn < bound; fn++) + printf("\"%s\"%s", fields[fn], (fn+1 < nf) ? ", " : "\n"); +} + +#define RNF 5 /* some table entries know this */ +struct { + char *str; + char *seps; + int nf; + char *fi[RNF]; +} tests[] = { + "", " ", 0, { "" }, + " ", " ", 2, { "", "" }, + "x", " ", 1, { "x" }, + "xy", " ", 1, { "xy" }, + "x y", " ", 2, { "x", "y" }, + "abc def g ", " ", 5, { "abc", "def", "", "g", "" }, + " a bcd", " ", 4, { "", "", "a", "bcd" }, + "a b c d e f", " ", 6, { "a", "b", "c", "d", "e f" }, + " a b c d ", " ", 6, { "", "a", "b", "c", "d " }, + + "", " _", 0, { "" }, + " ", " _", 2, { "", "" }, + "x", " _", 1, { "x" }, + "x y", " _", 2, { "x", "y" }, + "ab _ cd", " _", 2, { "ab", "cd" }, + " a_b c ", " _", 5, { "", "a", "b", "c", "" }, + "a b c_d e f", " _", 6, { "a", "b", "c", "d", "e f" }, + " a b c d ", " _", 6, { "", "a", "b", "c", "d " }, + + "", " _~", 0, { "" }, + " ", " _~", 2, { "", "" }, + "x", " _~", 1, { "x" }, + "x y", " _~", 2, { "x", "y" }, + "ab _~ cd", " _~", 2, { "ab", "cd" }, + " a_b c~", " _~", 5, { "", "a", "b", "c", "" }, + "a b_c d~e f", " _~", 6, { "a", "b", "c", "d", "e f" }, + "~a b c d ", " _~", 6, { "", "a", "b", "c", "d " }, + + "", " _~-", 0, { "" }, + " ", " _~-", 2, { "", "" }, + "x", " _~-", 1, { "x" }, + "x y", " _~-", 2, { "x", "y" }, + "ab _~- cd", " _~-", 2, { "ab", "cd" }, + " a_b c~", " _~-", 5, { "", "a", "b", "c", "" }, + "a b_c-d~e f", " _~-", 6, { "a", "b", "c", "d", "e f" }, + "~a-b c d ", " _~-", 6, { "", "a", "b", "c", "d " }, + + "", " ", 0, { "" }, + " ", " ", 2, { "", "" }, + "x", " ", 1, { "x" }, + "xy", " ", 1, { "xy" }, + "x y", " ", 2, { "x", "y" }, + "abc def g ", " ", 4, { "abc", "def", "g", "" }, + " a bcd", " ", 3, { "", "a", "bcd" }, + "a b c d e f", " ", 6, { "a", "b", "c", "d", "e f" }, + " a b c d ", " ", 6, { "", "a", "b", "c", "d " }, + + "", "", 0, { "" }, + " ", "", 0, { "" }, + "x", "", 1, { "x" }, + "xy", "", 1, { "xy" }, + "x y", "", 2, { "x", "y" }, + "abc def g ", "", 3, { "abc", "def", "g" }, + "\t a bcd", "", 2, { "a", "bcd" }, + " a \tb\t c ", "", 3, { "a", "b", "c" }, + "a b c d e ", "", 5, { "a", "b", "c", "d", "e" }, + "a b\tc d e f", "", 6, { "a", "b", "c", "d", "e f" }, + " a b c d e f ", "", 6, { "a", "b", "c", "d", "e f " }, + + NULL, NULL, 0, { NULL }, +}; + +regress() +{ + char buf[512]; + register int n; + char *fields[RNF+1]; + register int nf; + register int i; + register int printit; + register char *f; + + for (n = 0; tests[n].str != NULL; n++) { + (void) strcpy(buf, tests[n].str); + fields[RNF] = NULL; + nf = split(buf, fields, RNF, tests[n].seps); + printit = 0; + if (nf != tests[n].nf) { + printf("split `%s' by `%s' gave %d fields, not %d\n", + tests[n].str, tests[n].seps, nf, tests[n].nf); + printit = 1; + } else if (fields[RNF] != NULL) { + printf("split() went beyond array end\n"); + printit = 1; + } else { + for (i = 0; i < nf && i < RNF; i++) { + f = fields[i]; + if (f == NULL) + f = "(NULL)"; + if (strcmp(f, tests[n].fi[i]) != 0) { + printf("split `%s' by `%s', field %d is `%s', not `%s'\n", + tests[n].str, tests[n].seps, + i, fields[i], tests[n].fi[i]); + printit = 1; + } + } + } + if (printit) + print(nf, RNF, fields); + } +} +#endif diff --git a/regex/tests b/regex/tests new file mode 100644 index 0000000..e4d928d --- /dev/null +++ b/regex/tests @@ -0,0 +1,477 @@ +# regular expression test set +# Lines are at least three fields, separated by one or more tabs. "" stands +# for an empty field. First field is an RE. Second field is flags. If +# C flag given, regcomp() is expected to fail, and the third field is the +# error name (minus the leading REG_). +# +# Otherwise it is expected to succeed, and the third field is the string to +# try matching it against. If there is no fourth field, the match is +# expected to fail. If there is a fourth field, it is the substring that +# the RE is expected to match. If there is a fifth field, it is a comma- +# separated list of what the subexpressions should match, with - indicating +# no match for that one. In both the fourth and fifth fields, a (sub)field +# starting with @ indicates that the (sub)expression is expected to match +# a null string followed by the stuff after the @; this provides a way to +# test where null strings match. The character `N' in REs and strings +# is newline, `S' is space, `T' is tab, `Z' is NUL. +# +# The full list of flags: +# - placeholder, does nothing +# b RE is a BRE, not an ERE +# & try it as both an ERE and a BRE +# C regcomp() error expected, third field is error name +# i REG_ICASE +# m ("mundane") REG_NOSPEC +# s REG_NOSUB (not really testable) +# n REG_NEWLINE +# ^ REG_NOTBOL +# $ REG_NOTEOL +# # REG_STARTEND (see below) +# p REG_PEND +# +# For REG_STARTEND, the start/end offsets are those of the substring +# enclosed in (). + +# basics +a & a a +abc & abc abc +abc|de - abc abc +a|b|c - abc a + +# parentheses and perversions thereof +a(b)c - abc abc +a\(b\)c b abc abc +a( C EPAREN +a( b a( a( +a\( - a( a( +a\( bC EPAREN +a\(b bC EPAREN +a(b C EPAREN +a(b b a(b a(b +# gag me with a right parenthesis -- 1003.2 goofed here (my fault, partly) +a) - a) a) +) - ) ) +# end gagging (in a just world, those *should* give EPAREN) +a) b a) a) +a\) bC EPAREN +\) bC EPAREN +a()b - ab ab +a\(\)b b ab ab + +# anchoring and REG_NEWLINE +^abc$ & abc abc +a^b - a^b +a^b b a^b a^b +a$b - a$b +a$b b a$b a$b +^ & abc @abc +$ & abc @ +^$ & "" @ +$^ - "" @ +\($\)\(^\) b "" @ +# stop retching, those are legitimate (although disgusting) +^^ - "" @ +$$ - "" @ +b$ & abNc +b$ &n abNc b +^b$ & aNbNc +^b$ &n aNbNc b +^$ &n aNNb @Nb +^$ n abc +^$ n abcN @ +$^ n aNNb @Nb +\($\)\(^\) bn aNNb @Nb +^^ n^ aNNb @Nb +$$ n aNNb @NN +^a ^ a +a$ $ a +^a ^n aNb +^b ^n aNb b +a$ $n bNa +b$ $n bNa b +a*(^b$)c* - b b +a*\(^b$\)c* b b b + +# certain syntax errors and non-errors +| C EMPTY +| b | | +* C BADRPT +* b * * ++ C BADRPT +? C BADRPT +"" &C EMPTY +() - abc @abc +\(\) b abc @abc +a||b C EMPTY +|ab C EMPTY +ab| C EMPTY +(|a)b C EMPTY +(a|)b C EMPTY +(*a) C BADRPT +(+a) C BADRPT +(?a) C BADRPT +({1}a) C BADRPT +\(\{1\}a\) bC BADRPT +(a|*b) C BADRPT +(a|+b) C BADRPT +(a|?b) C BADRPT +(a|{1}b) C BADRPT +^* C BADRPT +^* b * * +^+ C BADRPT +^? C BADRPT +^{1} C BADRPT +^\{1\} bC BADRPT + +# metacharacters, backslashes +a.c & abc abc +a[bc]d & abd abd +a\*c & a*c a*c +a\\b & a\b a\b +a\\\*b & a\*b a\*b +a\bc & abc abc +a\ &C EESCAPE +a\\bc & a\bc a\bc +\{ bC BADRPT +a\[b & a[b a[b +a[b &C EBRACK +# trailing $ is a peculiar special case for the BRE code +a$ & a a +a$ & a$ +a\$ & a +a\$ & a$ a$ +a\\$ & a +a\\$ & a$ +a\\$ & a\$ +a\\$ & a\ a\ + +# back references, ugh +a\(b\)\2c bC ESUBREG +a\(b\1\)c bC ESUBREG +a\(b*\)c\1d b abbcbbd abbcbbd bb +a\(b*\)c\1d b abbcbd +a\(b*\)c\1d b abbcbbbd +^\(.\)\1 b abc +a\([bc]\)\1d b abcdabbd abbd b +a\(\([bc]\)\2\)*d b abbccd abbccd +a\(\([bc]\)\2\)*d b abbcbd +# actually, this next one probably ought to fail, but the spec is unclear +a\(\(b\)*\2\)*d b abbbd abbbd +# here is a case that no NFA implementation does right +\(ab*\)[ab]*\1 b ababaaa ababaaa a +# check out normal matching in the presence of back refs +\(a\)\1bcd b aabcd aabcd +\(a\)\1bc*d b aabcd aabcd +\(a\)\1bc*d b aabd aabd +\(a\)\1bc*d b aabcccd aabcccd +\(a\)\1bc*[ce]d b aabcccd aabcccd +^\(a\)\1b\(c\)*cd$ b aabcccd aabcccd + +# ordinary repetitions +ab*c & abc abc +ab+c - abc abc +ab?c - abc abc +a\(*\)b b a*b a*b +a\(**\)b b ab ab +a\(***\)b bC BADRPT +*a b *a *a +**a b a a +***a bC BADRPT + +# the dreaded bounded repetitions +{ & { { +{abc & {abc {abc +{1 C BADRPT +{1} C BADRPT +a{b & a{b a{b +a{1}b - ab ab +a\{1\}b b ab ab +a{1,}b - ab ab +a\{1,\}b b ab ab +a{1,2}b - aab aab +a\{1,2\}b b aab aab +a{1 C EBRACE +a\{1 bC EBRACE +a{1a C EBRACE +a\{1a bC EBRACE +a{1a} C BADBR +a\{1a\} bC BADBR +a{,2} - a{,2} a{,2} +a\{,2\} bC BADBR +a{,} - a{,} a{,} +a\{,\} bC BADBR +a{1,x} C BADBR +a\{1,x\} bC BADBR +a{1,x C EBRACE +a\{1,x bC EBRACE +a{300} C BADBR +a\{300\} bC BADBR +a{1,0} C BADBR +a\{1,0\} bC BADBR +ab{0,0}c - abcac ac +ab\{0,0\}c b abcac ac +ab{0,1}c - abcac abc +ab\{0,1\}c b abcac abc +ab{0,3}c - abbcac abbc +ab\{0,3\}c b abbcac abbc +ab{1,1}c - acabc abc +ab\{1,1\}c b acabc abc +ab{1,3}c - acabc abc +ab\{1,3\}c b acabc abc +ab{2,2}c - abcabbc abbc +ab\{2,2\}c b abcabbc abbc +ab{2,4}c - abcabbc abbc +ab\{2,4\}c b abcabbc abbc +((a{1,10}){1,10}){1,10} - a a a,a + +# multiple repetitions +a** &C BADRPT +a++ C BADRPT +a?? C BADRPT +a*+ C BADRPT +a*? C BADRPT +a+* C BADRPT +a+? C BADRPT +a?* C BADRPT +a?+ C BADRPT +a{1}{1} C BADRPT +a*{1} C BADRPT +a+{1} C BADRPT +a?{1} C BADRPT +a{1}* C BADRPT +a{1}+ C BADRPT +a{1}? C BADRPT +a*{b} - a{b} a{b} +a\{1\}\{1\} bC BADRPT +a*\{1\} bC BADRPT +a\{1\}* bC BADRPT + +# brackets, and numerous perversions thereof +a[b]c & abc abc +a[ab]c & abc abc +a[^ab]c & adc adc +a[]b]c & a]c a]c +a[[b]c & a[c a[c +a[-b]c & a-c a-c +a[^]b]c & adc adc +a[^-b]c & adc adc +a[b-]c & a-c a-c +a[b &C EBRACK +a[] &C EBRACK +a[1-3]c & a2c a2c +a[3-1]c &C ERANGE +a[1-3-5]c &C ERANGE +a[[.-.]--]c & a-c a-c +a[1- &C ERANGE +a[[. &C EBRACK +a[[.x &C EBRACK +a[[.x. &C EBRACK +a[[.x.] &C EBRACK +a[[.x.]] & ax ax +a[[.x,.]] &C ECOLLATE +a[[.one.]]b & a1b a1b +a[[.notdef.]]b &C ECOLLATE +a[[.].]]b & a]b a]b +a[[:alpha:]]c & abc abc +a[[:notdef:]]c &C ECTYPE +a[[: &C EBRACK +a[[:alpha &C EBRACK +a[[:alpha:] &C EBRACK +a[[:alpha,:] &C ECTYPE +a[[:]:]]b &C ECTYPE +a[[:-:]]b &C ECTYPE +a[[:alph:]] &C ECTYPE +a[[:alphabet:]] &C ECTYPE +[[:alnum:]]+ - -%@a0X- a0X +[[:alpha:]]+ - -%@aX0- aX +[[:blank:]]+ - aSSTb SST +[[:cntrl:]]+ - aNTb NT +[[:digit:]]+ - a019b 019 +[[:graph:]]+ - Sa%bS a%b +[[:lower:]]+ - AabC ab +[[:print:]]+ - NaSbN aSb +[[:punct:]]+ - S%-&T %-& +[[:space:]]+ - aSNTb SNT +[[:upper:]]+ - aBCd BC +[[:xdigit:]]+ - p0f3Cq 0f3C +a[[=b=]]c & abc abc +a[[= &C EBRACK +a[[=b &C EBRACK +a[[=b= &C EBRACK +a[[=b=] &C EBRACK +a[[=b,=]] &C ECOLLATE +a[[=one=]]b & a1b a1b + +# complexities +a(((b)))c - abc abc +a(b|(c))d - abd abd +a(b*|c)d - abbd abbd +# just gotta have one DFA-buster, of course +a[ab]{20} - aaaaabaaaabaaaabaaaab aaaaabaaaabaaaabaaaab +# and an inline expansion in case somebody gets tricky +a[ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab] - aaaaabaaaabaaaabaaaab aaaaabaaaabaaaabaaaab +# and in case somebody just slips in an NFA... +a[ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab][ab](wee|week)(knights|night) - aaaaabaaaabaaaabaaaabweeknights aaaaabaaaabaaaabaaaabweeknights +# fish for anomalies as the number of states passes 32 +12345678901234567890123456789 - a12345678901234567890123456789b 12345678901234567890123456789 +123456789012345678901234567890 - a123456789012345678901234567890b 123456789012345678901234567890 +1234567890123456789012345678901 - a1234567890123456789012345678901b 1234567890123456789012345678901 +12345678901234567890123456789012 - a12345678901234567890123456789012b 12345678901234567890123456789012 +123456789012345678901234567890123 - a123456789012345678901234567890123b 123456789012345678901234567890123 +# and one really big one, beyond any plausible word width +1234567890123456789012345678901234567890123456789012345678901234567890 - a1234567890123456789012345678901234567890123456789012345678901234567890b 1234567890123456789012345678901234567890123456789012345678901234567890 +# fish for problems as brackets go past 8 +[ab][cd][ef][gh][ij][kl][mn] - xacegikmoq acegikm +[ab][cd][ef][gh][ij][kl][mn][op] - xacegikmoq acegikmo +[ab][cd][ef][gh][ij][kl][mn][op][qr] - xacegikmoqy acegikmoq +[ab][cd][ef][gh][ij][kl][mn][op][q] - xacegikmoqy acegikmoq + +# subtleties of matching +abc & xabcy abc +a\(b\)?c\1d b acd +aBc i Abc Abc +a[Bc]*d i abBCcd abBCcd +0[[:upper:]]1 &i 0a1 0a1 +0[[:lower:]]1 &i 0A1 0A1 +a[^b]c &i abc +a[^b]c &i aBc +a[^b]c &i adc adc +[a]b[c] - abc abc +[a]b[a] - aba aba +[abc]b[abc] - abc abc +[abc]b[abd] - abd abd +a(b?c)+d - accd accd +(wee|week)(knights|night) - weeknights weeknights +(we|wee|week|frob)(knights|night|day) - weeknights weeknights +a[bc]d - xyzaaabcaababdacd abd +a[ab]c - aaabc abc +abc s abc abc +a* & b @b + +# Let's have some fun -- try to match a C comment. +# first the obvious, which looks okay at first glance... +/\*.*\*/ - /*x*/ /*x*/ +# but... +/\*.*\*/ - /*x*/y/*z*/ /*x*/y/*z*/ +# okay, we must not match */ inside; try to do that... +/\*([^*]|\*[^/])*\*/ - /*x*/ /*x*/ +/\*([^*]|\*[^/])*\*/ - /*x*/y/*z*/ /*x*/ +# but... +/\*([^*]|\*[^/])*\*/ - /*x**/y/*z*/ /*x**/y/*z*/ +# and a still fancier version, which does it right (I think)... +/\*([^*]|\*+[^*/])*\*+/ - /*x*/ /*x*/ +/\*([^*]|\*+[^*/])*\*+/ - /*x*/y/*z*/ /*x*/ +/\*([^*]|\*+[^*/])*\*+/ - /*x**/y/*z*/ /*x**/ +/\*([^*]|\*+[^*/])*\*+/ - /*x****/y/*z*/ /*x****/ +/\*([^*]|\*+[^*/])*\*+/ - /*x**x*/y/*z*/ /*x**x*/ +/\*([^*]|\*+[^*/])*\*+/ - /*x***x/y/*z*/ /*x***x/y/*z*/ + +# subexpressions +.* - abc abc - +a(b)(c)d - abcd abcd b,c +a(((b)))c - abc abc b,b,b +a(b|(c))d - abd abd b,- +a(b*|c|e)d - abbd abbd bb +a(b*|c|e)d - acd acd c +a(b*|c|e)d - ad ad @d +a(b?)c - abc abc b +a(b?)c - ac ac @c +a(b+)c - abc abc b +a(b+)c - abbbc abbbc bbb +a(b*)c - ac ac @c +(a|ab)(bc([de]+)f|cde) - abcdef abcdef a,bcdef,de +# the regression tester only asks for 9 subexpressions +a(b)(c)(d)(e)(f)(g)(h)(i)(j)k - abcdefghijk abcdefghijk b,c,d,e,f,g,h,i,j +a(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)l - abcdefghijkl abcdefghijkl b,c,d,e,f,g,h,i,j,k +a([bc]?)c - abc abc b +a([bc]?)c - ac ac @c +a([bc]+)c - abc abc b +a([bc]+)c - abcc abcc bc +a([bc]+)bc - abcbc abcbc bc +a(bb+|b)b - abb abb b +a(bbb+|bb+|b)b - abb abb b +a(bbb+|bb+|b)b - abbb abbb bb +a(bbb+|bb+|b)bb - abbb abbb b +(.*).* - abcdef abcdef abcdef +(a*)* - bc @b @b + +# do we get the right subexpression when it is used more than once? +a(b|c)*d - ad ad - +a(b|c)*d - abcd abcd c +a(b|c)+d - abd abd b +a(b|c)+d - abcd abcd c +a(b|c?)+d - ad ad @d +a(b|c?)+d - abcd abcd @d +a(b|c){0,0}d - ad ad - +a(b|c){0,1}d - ad ad - +a(b|c){0,1}d - abd abd b +a(b|c){0,2}d - ad ad - +a(b|c){0,2}d - abcd abcd c +a(b|c){0,}d - ad ad - +a(b|c){0,}d - abcd abcd c +a(b|c){1,1}d - abd abd b +a(b|c){1,1}d - acd acd c +a(b|c){1,2}d - abd abd b +a(b|c){1,2}d - abcd abcd c +a(b|c){1,}d - abd abd b +a(b|c){1,}d - abcd abcd c +a(b|c){2,2}d - acbd acbd b +a(b|c){2,2}d - abcd abcd c +a(b|c){2,4}d - abcd abcd c +a(b|c){2,4}d - abcbd abcbd b +a(b|c){2,4}d - abcbcd abcbcd c +a(b|c){2,}d - abcd abcd c +a(b|c){2,}d - abcbd abcbd b +a(b+|((c)*))+d - abd abd @d,@d,- +a(b+|((c)*))+d - abcd abcd @d,@d,- + +# check out the STARTEND option +[abc] &# a(b)c b +[abc] &# a(d)c +[abc] &# a(bc)d b +[abc] &# a(dc)d c +. &# a()c +b.*c &# b(bc)c bc +b.* &# b(bc)c bc +.*c &# b(bc)c bc + +# plain strings, with the NOSPEC flag +abc m abc abc +abc m xabcy abc +abc m xyz +a*b m aba*b a*b +a*b m ab +"" mC EMPTY + +# cases involving NULs +aZb & a a +aZb &p a +aZb &p# (aZb) aZb +aZ*b &p# (ab) ab +a.b &# (aZb) aZb +a.* &# (aZb)c aZb + +# word boundaries (ick) +[[:<:]]a & a a +[[:<:]]a & ba +[[:<:]]a & -a a +a[[:>:]] & a a +a[[:>:]] & ab +a[[:>:]] & a- a +[[:<:]]a.c[[:>:]] & axcd-dayc-dazce-abc abc +[[:<:]]a.c[[:>:]] & axcd-dayc-dazce-abc-q abc +[[:<:]]a.c[[:>:]] & axc-dayc-dazce-abc axc +[[:<:]]b.c[[:>:]] & a_bxc-byc_d-bzc-q bzc +[[:<:]].x..[[:>:]] & y_xa_-_xb_y-_xc_-axdc _xc_ +[[:<:]]a_b[[:>:]] & x_a_b + +# past problems, and suspected problems +(A[1])|(A[2])|(A[3])|(A[4])|(A[5])|(A[6])|(A[7])|(A[8])|(A[9])|(A[A]) - A1 A1 +abcdefghijklmnop i abcdefghijklmnop abcdefghijklmnop +abcdefghijklmnopqrstuv i abcdefghijklmnopqrstuv abcdefghijklmnopqrstuv +(ALAK)|(ALT[AB])|(CC[123]1)|(CM[123]1)|(GAMC)|(LC[23][EO ])|(SEM[1234])|(SL[ES][12])|(SLWW)|(SLF )|(SLDT)|(VWH[12])|(WH[34][EW])|(WP1[ESN]) - CC11 CC11 +CC[13]1|a{21}[23][EO][123][Es][12]a{15}aa[34][EW]aaaaaaa[X]a - CC11 CC11 +Char \([a-z0-9_]*\)\[.* b Char xyz[k Char xyz[k xyz +a?b - ab ab +-\{0,1\}[0-9]*$ b -5 -5 +a*a*a*a*a*a*a* & aaaaaa aaaaaa diff --git a/regex/utils.h b/regex/utils.h new file mode 100644 index 0000000..1a997ac --- /dev/null +++ b/regex/utils.h @@ -0,0 +1,22 @@ +/* utility definitions */ +#ifdef _POSIX2_RE_DUP_MAX +#define DUPMAX _POSIX2_RE_DUP_MAX +#else +#define DUPMAX 255 +#endif +#define INFINITY (DUPMAX + 1) +#define NC (CHAR_MAX - CHAR_MIN + 1) +typedef unsigned char uch; + +/* switch off assertions (if not already off) if no REDEBUG */ +#ifndef REDEBUG +#ifndef NDEBUG +#define NDEBUG /* no assertions please */ +#endif +#endif +#include <assert.h> + +/* for old systems with bcopy() but no memmove() */ +#ifdef USEBCOPY +#define memmove(d, s, c) bcopy(s, d, c) +#endif diff --git a/test.html b/test.html new file mode 100644 index 0000000..09865dc --- /dev/null +++ b/test.html @@ -0,0 +1,11 @@ +<html> +<head> + <title>GrokHtml Test Document</title> +</head> +<body> + <table> + <tr><td>foo = baz</td></tr> + <tr><td>bar = quux</td></tr> + </table> +</body> +</html>
\ No newline at end of file diff --git a/treexpr.c b/treexpr.c new file mode 100644 index 0000000..eb68f2e --- /dev/null +++ b/treexpr.c @@ -0,0 +1,1145 @@ +/* treexpr.c - Tree expression language source file + + Copyright (C) 2005 Dell, Inc. + + Authors: David Barksdale <amatus@ocgnet.org> + + + + This library is free software; you can redistribute it and/or + + modify it under the terms of the GNU Lesser General Public + + License as published by the Free Software Foundation; either + + version 2.1 of the License, or (at your option) any later version. + + + + This library is distributed in the hope that it will be useful, + + but WITHOUT ANY WARRANTY; without even the implied warranty of + + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + + Lesser General Public License for more details. + + + + You should have received a copy of the GNU Lesser General Public + + License along with this library; if not, write to the Free Software + + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +-- Syntax -- + Expr ::= Term | Expr "|" Term + Term ::= Factor | Term Factor + Factor ::= Symbol | Symbol "*" | "~" | "(" Expr ")" | "(" Expr ")" "*" + | Symbol "->" Expr | Symbol ":" String | Symbol Attrs | Symbol Attrs "->" Expr + Attrs ::= "<" Attr* ">" + Attr ::= Symbol | Symbol "=" String + Symbol ::= any alphanumeric string with '_' and '-' + String ::= quoted string (skips over \") + +-- Semantics -- +A tree can be thought of as a hierarchical list, each element of the list can have a list of +children. Consider the following tree: + + html + / \ + head body + / / \ +title h1 p + +root list: html +list of html's children: head body +list of head's children: title +list of body's children: h1 p +list of h1's chlidren: ~ (where ~ denotes the empty list) +list of p's children: ~ + +By the same token, a tree expression can be thought of as a hierarchical regular expression, +each symbol in the expression can have a child expression. The "->" operator binds a child +expression to a symbol in the parent expression. If a symbol has no child expression it is +equivalent to having a child expression that matches everything. In other words the children +of a symbol are ignored if there is no child expression. It can also be said that "->" adds +a restriction to the symbol on it's left-hand side: the symbol will only be matched if the +symbol's children match the child expression. Other restriction operators are discussed later to +improve matching of HTML. Consider the following expressions: + + These match the tree above: + html - matches the root list and ignores html's children + html -> head body - also matches html's children and ignores head and body's children + html -> (head -> title) body - also matches head's children and ignores title's children + html -> (head -> title -> ~) body - also matches title's children + html -> (head -> title -> ~) (body -> h1 p) - also matches body's children + html -> (head -> title -> ~) (body -> (h1 -> ~) (p -> ~)) - matches the tree exactly + + These do not match the tree above: + body - does not match root list + html -> body - matches root list but does not match html's children (must match all) + html -> body head - matches root list but html's children are out of order + +Note the grouping around "->". In the second expression "->" binds the symbol "html" to the +expression "head body". In the third expression we want the symbol "head" to be bound to the +expression "title" and not "title body" so we must group them together using parenthesis. + +Tree expressions use the alternation "|" and closure "*" operators from reqular expressions. +Consider the following expressions: + html* - matches the root list because it consists of zero or more "html" symbols + html | xml - matches the root list because it consists of "html" or "xml" + html -> (head -> title | title meta) body - matches + +In addition to the "~" special symbol there is "." which matches any symbol: + html -> .* - matches the root list and html's children because html has zero or more + html -> .* (body -> .* p .*) .* - matches a tree that has "html" at the root, html has + atleast one child named "body", and body has atleast + one child named "p". + +-- Extra restriction operators for HTML matching -- + +The ":" operator binds a regular expression to a symbol, the symbol matches only if it's +contents matches the regular expression. In HTML the only tags that have contents are "text" +and "comment". So most of the time it will be used like: + p -> text:"ab*c" - matches the HTML '<p>abbbbbc</p>' + +The "<", "=", and ">" operators are used together to bind a symbol to an attribute list, +the symbol matches only if every attribute matches an attribute of the HTML tag. An attribute +restriction is a list of name and value pairs. A name without a value is matched only if it +appears in the HTML without a value. Consider the following: + table <bgcolor="blue"> - matches the HTML '<table bgcolor="blue">' + and also the HTML '<table bgcolor="blue" border="1">' + foo <bar> - matches the HTML '<foo bar>' but not '<foo bar="">' or '<foo bar="baz">' + foo <bar> | foo <bar=".*"> - matches all three + +It is possible to combine the attribute restriction operators with the "->" operator (for example +option <selected> -> text:"blue"), but it is not possible to combine the content restriction +operator with the "->" operator (for example text:"blue" -> br) because "text" and "comment" +symbols never have children. + +-- Extracting values from an HTML page -- +This section has been up for debate because it can be very confusing. The way we extract strings +from the tree expressions is from the contents and attribute rescrictions. These restrictions +contain regular expressions that match against some of the data contained in an HTML page. Most +regular expression libraries allow you to use something called back references where each +parenthasized sub-expression is given a number and the string matching that sub-expression can be +referenced later. For example the expression "foo" has no sub-expressions, the expression "fo(o*)" +has one sub-expression, namely "o*". When "fo(o*)" is matched against "fooo", the fist +sub-expression references the string "oo". The sub-expressions are numbered by the position of +their open parenthesis. For example "(b(a)(r))" has three sub-expressions, 1. "b(a)(r)" 2. "a" +3. "r". If a sub-expression matches multiple strings then the last match is what is referenced. +For example "(ab|ac)*" matches "ababac" and the string referenced will be "ac". + +A tree expression can have several regular expressions embedded in it. In order to find a specific +sub-expression they are numbered in the order they appear in the tree expression. For example: + form -> input<value="([0-9]+)"> text:"." + input<value="([0-9]+)"> text:"." + input<value="([0-9]+)"> text:"." + input<value="([0-9]+)"> input +has four sub-expressions. This tree expression would match against an HTML form that might be used +for changing an IP address: +<form method="POST" action="/cgi-bin/setip"> + <input type="text" name="first" value="192"> . + <input type="text" name="second" value="168"> . + <input type="text" name="third" value="1"> . + <input type="text" name="fourth" value="42"> <input type="submit" value="Set IP"> +</form> +In this case the extracted values will be: +1: "192" +2: "168" +3: "1" +4: "42" +It's simple to specify a method for combining the strings together to form a usefull output. +For example something like "\1.\2.\3.\4" would produce "192.168.1.42". +*/ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <ctype.h> +#include <libxml/tree.h> +#include <sys/types.h> +#include "regex.h" +#include "treexpr.h" + +#ifdef _WINDOWS +#define strcasecmp stricmp +#endif + +// allocator that never returns NULL, cheap hack to make code shorter +void *zalloc( size_t size ) +{ + void *p; + + do { p = calloc( size, 1 ); + } while( p == NULL ); + return p; +} + +// builds a machine that matches a symbol +struct machine *symbol( char *name ) +{ + struct machine *m; + struct state *start, *final; + struct trans *tr; + + // alloc stuff + m = zalloc( sizeof( struct machine )); + start = zalloc( sizeof( struct state )); + final = zalloc( sizeof( struct state )); + tr = zalloc( sizeof( struct trans )); + + // insert transition + tr->name = name; + tr->st = final; + start->tr = tr; + + // maintain linked list + start->next = final; + + // finish machine + m->start = start; + m->final = final; + return m; +} + +// builds a machine that matches the empty string +struct machine *epsilon( void ) +{ + struct machine *m; + struct state *start, *final; + struct epsilon *cat; + + // alloc stuff + m = zalloc( sizeof( struct machine )); + start = zalloc( sizeof( struct state )); + final = zalloc( sizeof( struct state )); + cat = zalloc( sizeof( struct epsilon )); + + // insert epsilon transition + cat->st = final; + start->ep = cat; + + // maintain liked list + start->next = final; + + // finish machine + m->start = start; + m->final = final; + return m; +} + +// builds a machine that matches nothing (not used at present, but here for completeness) +struct machine *null( void ) +{ + struct machine *m; + struct state *start, *final; + + // alloc stuff + m = zalloc( sizeof( struct machine )); + start = zalloc( sizeof( struct state )); + final = zalloc( sizeof( struct state )); + + // maintain linked list + start->next = final; + + // finish machine + m->start = start; + m->final = final; + return m; +} + +// concatanates two machines +struct machine *concat( struct machine *a, struct machine *b ) +{ + struct epsilon *cat; + + if( a == NULL || b == NULL ) + return NULL; + + // alloc stuff + cat = zalloc( sizeof( struct epsilon )); + + // insert epsilon transition + cat->st = b->start; + cat->next = a->final->ep; + a->final->ep = cat; + + // maintain linked list + a->final->next = b->start; + + // use machine 'a' as our new machine and free 'b' + a->final = b->final; + free( b ); + return a; +} + +// alternates two machines (spike) +struct machine *alternate( struct machine *a, struct machine *b ) +{ + struct state *start, *final; + struct epsilon *s1, *s2, *f1, *f2; + + if( a == NULL || b == NULL ) + return NULL; + + // alloc stuff + start = zalloc( sizeof( struct state )); + final = zalloc( sizeof( struct state )); + s1 = zalloc( sizeof( struct epsilon )); + s2 = zalloc( sizeof( struct epsilon )); + f1 = zalloc( sizeof( struct epsilon )); + f2 = zalloc( sizeof( struct epsilon )); + + // insert epsilon transitions from our new start state + // to the start states of the two machines + s1->st = a->start; + s2->st = b->start; + s1->next = s2; + start->ep = s1; + + // insert epsilon transitions from the final states of the + // new machines to our new final state + f1->st = final; + f2->st = final; + f1->next = a->final->ep; + a->final->ep = f1; + f2->next = b->final->ep; + b->final->ep = f2; + + // maintain linked list + start->next = a->start; + a->final->next = b->start; + b->final->next = final; + + // use machine 'a' as our new machine and free 'b' + a->start = start; + a->final = final; + free( b ); + return a; +} + +// creates the closure of a machine (splat) +struct machine *closure( struct machine *a ) +{ + struct state *start, *final; + struct epsilon *s1, *s2, *f1, *f2; + + if( a == NULL ) + return NULL; + + // alloc stuff + start = zalloc( sizeof( struct state )); + final = zalloc( sizeof( struct state )); + s1 = zalloc( sizeof( struct epsilon )); + s2 = zalloc( sizeof( struct epsilon )); + f1 = zalloc( sizeof( struct epsilon )); + f2 = zalloc( sizeof( struct epsilon )); + + // insert epsilon transitions from our new start state to + // the machine's start state and to our new final state + s1->st = final; + s2->st = a->start; + s1->next = s2; + start->ep = s1; + + // insert epsilon transitions from the machine's final state + // to the machine's start state and our new final state + f1->st = a->start; + f2->st = final; + f1->next = f2; + f2->next = a->final->ep; + a->final->ep = f1; + + // maintain linked list + start->next = a->start; + a->final->next = final; + + // use 'a' as our new machine + a->start = start; + a->final = final; + return a; +} + +void free_machine( struct machine *m ); + +// free each state in a linked list +void free_states( struct state *sl ) +{ + struct trans *tr; + struct epsilon *ep, *epn; + struct state *next; + struct attribute *at, *atn; + + for( ; sl != NULL; sl = next ) + { + next = sl->next; + + // free each transition off this state + tr = sl->tr; + if( tr != NULL ) + { + // free all the junk that can hang off of a transition + free_machine( tr->ptr ); + free( tr->name ); + if( tr->re.re_magic != 0 ) + notbuiltin_regfree( &tr->re ); + for( at = tr->attrs; at != NULL; at = atn ) + { + atn = at->next; + free( at->name ); + if( at->re.re_magic != 0 ) + notbuiltin_regfree( &at->re ); + free( at ); + } + free( tr ); + } + + // free each epsilon transition (easy) + for( ep = sl->ep; ep != NULL; ep = epn ) + { + epn = ep->next; + free( ep ); + } + + // finally free the state + free( sl ); + } +} + +void free_machine( struct machine *m ) +{ + int i; + + if( m == NULL ) + return; + + // free every state in the machine + free_states( m->start ); + + // if we have an E function free it + if( m->E != NULL ) + { + for( i = 0; i < m->states; i++ ) + free( m->E[i] ); + free( m->E ); + } + + // free bitmasks + if( m->cur_state != NULL ) + free( m->cur_state ); + if( m->next_state != NULL ) + free( m->next_state ); + + // finally free the machine + free( m ); +} + +/* + * Tokenizer + */ +struct token +{ + int t; + char *name; +}; + +#define T_EOL ( -2 ) // not really paid attention to +#define T_ERROR ( -1 ) // tokenizing error, look at token->error and token->buf +#define T_SYMBOL ( 0 ) // symbol +#define T_SQUIGGLE ( 1 ) // ~ +#define T_WAX ( 2 ) // ( +#define T_WANE ( 3 ) // ) +#define T_SPIKE ( 4 ) // | +#define T_SPLAT ( 5 ) // * +#define T_PTR ( 6 ) // -> +#define T_TWOSPOT ( 7 ) // : +#define T_ANGLE ( 8 ) // < +#define T_RIGHTANGLE ( 9 ) // > +#define T_HALFMESH ( 10 ) // = +#define T_STRING ( 11 ) // quoted string + +// parse the next token in a string and return a pointer into the string were we stoped +const char *get_tok( const char *str, struct token *tk ) +{ + static char *name; + const char *p; + int i, len = 0; + + if( str == NULL ) + { + tk->t = T_ERROR; + return NULL; + } + + // skip whitespace + for( p = str; *p != 0 && isspace( *p ); p++ ); + + switch( *p ) + { + case 0: + tk->t = T_EOL; + return p; + case '~': + tk->t = T_SQUIGGLE; + return p + 1; + case '(': + tk->t = T_WAX; + return p + 1; + case ')': + tk->t = T_WANE; + return p + 1; + case '|': + tk->t = T_SPIKE; + return p + 1; + case '*': + tk->t = T_SPLAT; + return p + 1; + case '-': + if( p[1] == '>' ) + { + tk->t = T_PTR; + return p + 2; + } + tk->t = T_ERROR; + return p; + case ':': + tk->t = T_TWOSPOT; + return p + 1; + case '<': + tk->t = T_ANGLE; + return p + 1; + case '>': + tk->t = T_RIGHTANGLE; + return p + 1; + case '=': + tk->t = T_HALFMESH; + return p + 1; + case '\"': + p++; + len = 16; + name = zalloc( len ); + for( i = 0; p[i] != 0 && p[i] != '\"'; i++ ) + { + if( i + 1 >= len ) + name = realloc( name, len *= 2 ); + if( p[i] == '\\' && p[i + 1] == '\"' && i < 254 ) + { + name[i] = p[i]; + i++; + } + name[i] = p[i]; + } + name[i] = 0; + tk->t = p[i] == 0 ? T_ERROR : T_STRING; + tk->name = name; + return p + i + ( p[i] == '\"' ? 1 : 0 ); + case '.': + name = zalloc( 2 ); + name[0] = '.'; + name[1] = 0; + tk->t = T_SYMBOL; + tk->name = name; + return p + 1; + default: + len = 16; + name = zalloc( len ); + for( i = 0; isalnum( p[i] ) || p[i] == '_' || p[i] == '-'; i++ ) + { + if( i + 1 >= len ) + name = realloc( name, len *= 2 ); + name[i] = p[i]; + } + name[i] = 0; + tk->t = i > 0 ? T_SYMBOL : T_ERROR; + tk->name = name; + return p + i; + } +} + +const char *parse_treexpr( const char *expr, struct machine **m ); + +// parses an attribute construction: <foo="bar" baz="quux" quuux> +// the opening angle has already been consumed +const char *parse_attrs( const char *expr, struct attribute **a ) +{ + struct token tk; + struct attribute *prev = NULL, *attr; + const char *next; + + // build a list of attributes in order + for( next = get_tok( expr, &tk ); tk.t == T_SYMBOL; ) + { + // fist we grab the name + attr = zalloc( sizeof( struct attribute )); + if( prev == NULL ) + prev = *a = attr; + else + prev = prev->next = attr; + attr->name = tk.name; + + // check for optional = + next = get_tok( next, &tk ); + if( tk.t != T_HALFMESH ) + continue; + + // grab regex and compile it + next = get_tok( next, &tk ); + if( tk.t != T_STRING ) + return NULL; + if( notbuiltin_regcomp( &attr->re, tk.name, REG_EXTENDED + | REG_ICASE ) != 0 ) + { + notbuiltin_regfree( &attr->re ); + attr->re.re_magic = 0; + return NULL; + } + free( tk.name ); + next = get_tok( next, &tk ); + } + if( tk.t == T_RIGHTANGLE ) + return next; + return NULL; +} + +// parse a tree expression "factor" +// a factor is what I'm calling the operands to concatenation +// so it's either a symbol (with optional restrictions), a parenthasized expression +// or a factor with a * +// this does not allow foolishness like "foo**" (equivalent to "foo*") or "~*" (equivalent to "~") +// even though they are technically valid +const char *parse_factor( const char *expr, struct machine **m ) +{ + struct token tk; + struct machine *r; + const char *next, *cur; + + // this token should either be a symbol, a ~, or a ( + cur = get_tok( expr, &tk ); + if( tk.t == T_ERROR ) + { + *m = zalloc( sizeof( struct machine )); + ( *m )->error = "Tokenizing error"; + ( *m )->buf = expr; + return NULL; + } + if( tk.t == T_SYMBOL ) + { + // build a machine to match the symbol + *m = symbol( tk.name ); + next = get_tok( cur, &tk ); + if( tk.t == T_ERROR ) + { + ( *m )->error = "Tokenizing error"; + ( *m )->buf = cur; + return NULL; + } + + // if there's a * build the closure + if( tk.t == T_SPLAT ) + { + *m = closure( *m ); + return next; + } + + // if there's a -> then parse the expression on the rhs and add it as a restriction + if( tk.t == T_PTR ) + { + next = parse_treexpr( next, &r ); + ( *m )->start->tr->ptr = r; + if( next == NULL ) + { + ( *m )->error = r->error; + ( *m )->buf = r->buf; + return NULL; + } + return next; + } + + // if there's a : then compile the regex and add it as a restriction + if( tk.t == T_TWOSPOT ) + { + cur = next; + next = get_tok( cur, &tk ); + if( tk.t == T_ERROR ) + { + ( *m )->error = "Tokenizing error"; + ( *m )->buf = cur; + return NULL; + } + if( tk.t != T_STRING ) + { + ( *m )->error = "Expecting a \"-delimited string"; + ( *m )->buf = cur; + return NULL; + } + if( notbuiltin_regcomp( &( *m )->start->tr->re, tk.name, + REG_EXTENDED | REG_ICASE ) != 0 ) + { + notbuiltin_regfree( &( *m )->start->tr->re ); + ( *m )->start->tr->re.re_magic = 0; + ( *m )->error = "Error parsing regular expression"; + ( *m )->buf = cur; + } + free( tk.name ); + return next; + } + + // if there's a < then parse attributes and add it as a restriction + if( tk.t == T_ANGLE ) + { + next = parse_attrs( next, &( *m )->start->tr->attrs ); + if( next == NULL ) + { + ( *m )->error = "Expecting attribute list, ie <name=\"value\" name2=\"value2\">"; + ( *m )->buf = cur; + return NULL; + } + cur = next; + + // we also allow a -> restriction in this case + next = get_tok( cur, &tk ); + if( tk.t == T_PTR ) + { + next = parse_treexpr( next, &r ); + ( *m )->start->tr->ptr = r; + if( next == NULL ) + { + ( *m )->error = r->error; + ( *m )->buf = r->buf; + return NULL; + } + return next; + } + return cur; + } + return cur; + } + if( tk.t == T_SQUIGGLE ) + { + // build epsilon machine + *m = epsilon( ); + return cur; + } + if( tk.t == T_WAX ) + { + // parse expression + cur = parse_treexpr( cur, m ); + if( cur == NULL ) + return NULL; + + // make sure we end in ) + next = get_tok( cur, &tk ); + if( tk.t == T_ERROR ) + { + ( *m )->error = "Tokenizing error"; + ( *m )->buf = cur; + return NULL; + } + if( tk.t != T_WANE ) + { + ( *m )->error = "Expected ')'"; + ( *m )->buf = cur; + return NULL; + } + + // check for * and build closure + cur = next; + next = get_tok( cur, &tk ); + if( tk.t == T_ERROR ) + { + ( *m )->error = "Tokenizing error"; + ( *m )->buf = cur; + return NULL; + } + if( tk.t == T_SPLAT ) + { + *m = closure( *m ); + return next; + } + return cur; + } + + // invalid symbol + *m = zalloc( sizeof( struct machine )); + ( *m )->error = "Expected symbol or '~' or '('"; + ( *m )->buf = expr; + return NULL; +} + +// parse a tree expression "term" +// a term is what I'm calling the operands to alternation +// a term is either a factor, or a list of factors concatenated together +const char *parse_term( const char *expr, struct machine **m ) +{ + struct token tk; + struct machine *r; + const char *cur; + + // grab the first factor + cur = parse_factor( expr, m ); + if( cur == NULL ) + return NULL; + + // grab zero or more factors + for( get_tok( cur, &tk ); tk.t == T_SYMBOL || tk.t == T_WAX || tk.t == T_SQUIGGLE; + get_tok( cur, &tk )) + { + cur = parse_factor( cur, &r ); + if( cur == NULL ) + { + ( *m )->error = r->error; + ( *m )->buf = r->buf; + free_machine( r ); + return NULL; + } + + // concatenate the factors + *m = concat( *m, r ); + } + if( tk.t == T_ERROR ) + { + ( *m )->error = "Tokenizing error"; + ( *m )->buf = cur; + return NULL; + } + return cur; +} + +// parse a tree expression +// an expression is just a term or a list of terms seperated by | +// this looks almost exactly like parse_term() +const char *parse_treexpr( const char *expr, struct machine **m ) +{ + struct token tk; + const char *next, *cur; + struct machine *r; + + // grab the first term + cur = parse_term( expr, m ); + if( cur == NULL ) + return NULL; + + // grab zero or more terms + for( next = get_tok( cur, &tk ); tk.t == T_SPIKE; next = get_tok( cur, &tk )) + { + cur = parse_term( next, &r ); + if( cur == NULL ) + { + ( *m )->error = r->error; + ( *m )->buf = r->buf; + free_machine( r ); + return NULL; + } + + // combine the terms using alternation + *m = alternate( *m, r ); + } + if( tk.t == T_ERROR ) + { + ( *m )->error = "Tokenizing error"; + ( *m )->buf = cur; + return NULL; + } + return cur; +} + + +// process a regex restriction (basically just executes the regex) +int regex_process( struct trans *tr, char *content ) +{ + if( content == NULL ) + return 0; + if( notbuiltin_regexec( &tr->re, content, RESUBR, tr->match, 0 ) == 0 ) + { + tr->str = content; + return 1; + } + tr->str = NULL; + return 0; +} + +// process an attribute restriction +// it's important that we don't save the matches for all regexes until we know all of them +// match. otherwise if you were trying to match <foo="bar" bar="baz"> and you had a list like +// <foo="bar" bar="baz"> (both regexes match) +// <foo="barr" bar="quux"> (the first one matches and overwrites the previous match for foo) +// then you would be left with foo="barr" bar="baz" as your matches +int attrs_process( struct trans *tr, struct _xmlAttr *properties ) +{ + struct attribute *attr; + struct _xmlAttr *cur; + regmatch_t match[RESUBR]; + + // first pass makes sure each attribute matches + for( attr = tr->attrs; attr != NULL; attr = attr->next ) + { + for( cur = properties; cur != NULL; cur = cur->next ) + { + if( strcasecmp( attr->name, (char *)cur->name ) == 0 ) + { + // if there's no value it will only match if we didn't specify a regex + if( cur->children == NULL ) + { + if( attr->re.re_magic == 0 ) + break; + return 0; + } + // otherwise the regex has to match the value + if( notbuiltin_regexec( &attr->re, + (char *)cur->children->content, RESUBR, + match, 0 ) == 0 ) + break; + else + attr->str = NULL; + return 0; + } + } + if( cur == NULL ) + return 0; + } + // second pass saves the matches + for( attr = tr->attrs; attr != NULL; attr = attr->next ) + { + for( cur = properties; cur != NULL; cur = cur->next ) + { + if( strcasecmp( attr->name, (char *)cur->name ) == 0 ) + { + // if there's no value it will only match if we didn't specify a regex + if( cur->children == NULL ) + { + if( attr->re.re_magic == 0 ) + break; + return 0; + } + // otherwise the regex has to match the value + if( notbuiltin_regexec( &attr->re, + (char *)cur->children->content, RESUBR, + attr->match, 0 ) == 0 ) + { + attr->str = (char *)cur->children->content; + break; + } + else + attr->str = NULL; + return 0; + } + } + if( cur == NULL ) + return 0; + } + return 1; +} + +// some handy macros: +// number of bits in type pointed to by x +#define B( x ) (sizeof(*(x))*8) + +// number of elements in array pointed to by x in order to contain n bits +#define N( x, n ) (((n)+B(x)-1)/B(x)) + +// test bit b of array pointed to by x +#define TEST_BIT( x, b ) (((x)[(b)/B(x)]>>((b)%B(x)))&1) + +// set bit b of array pointed to by x +#define SET_BIT( x, b ) ((x)[(b)/B(x)]|=1<<((b)%B(x))) + +// compute the disjunction of two bitfields of n bits +#define OR( x, y, n ) {unsigned int _i;for(_i=0;_i<N(x,n);(x)[_i]|=(y)[_i],_i++);} + +// applies a machine to an xml tree +// returns true iff the machine accepts +// all matches to regexes are contained within the machine +int tree_process( struct machine *m, xmlNodePtr node ) +{ + int *e, done; + struct state *cur, *cur2; + struct trans *tr; + struct epsilon *ep; + + if( m == NULL ) + return 1; + if( m->E == NULL ) + { + // Generate E function + // the E function is an array of bitmasks indexed by state number + // the bitmask represents the states you can reach by epsilon transitions + + // number states + m->states = 0; + for( cur = m->start; cur != NULL; cur = cur->next ) + cur->num = m->states++; + + // fill E + m->E = zalloc( sizeof( *m->E ) * m->states ); + for( cur = m->start; cur != NULL; cur = cur->next ) + { + e = m->E[cur->num] = zalloc( N( *m->E, m->states ) * sizeof( **m->E )); + + // we can reach ourself + SET_BIT( e, cur->num ); + + // try to add new states until an iteration of this loop makes no progress + done = 0; + while( !done ) + { + done = 1; + // for each state that is already in the bitmask, add states you can reach + // by epsilon transitions + for( cur2 = m->start; cur2 != NULL; cur2 = cur2->next ) + if( TEST_BIT( e, cur2->num )) + for( ep = cur2->ep; ep != NULL; ep = ep->next ) + if( !TEST_BIT( e, ep->st->num )) + { + SET_BIT( e, ep->st->num ); + done = 0; + } + } + } + } + + // allocate current state and next state bitmasks + if( m->cur_state == NULL ) + m->cur_state = zalloc( N( m->cur_state, m->states ) * sizeof( *m->cur_state )); + if( m->next_state == NULL ) + m->next_state = zalloc( N( m->next_state, m->states ) * sizeof( *m->next_state )); + + // our inital current state is E(start) + OR( m->cur_state, m->E[m->start->num], m->states ); + + // main loop, terminate when we run out of input or when there's no states in the cur_state bitmask + while( node != NULL ) + { + unsigned int i; + int sum = 0; + + // are we still alive? + for( i = 0; i < N( m->cur_state, m->states ); i++ ) + sum |= m->cur_state[i]; + if( sum == 0 ) break; + + // zero out next_state and start adding states we can reach by normal transitions + memset( m->next_state, 0, N( m->next_state, m->states ) * sizeof( *m->next_state )); + + // for each state in the cur_state bitmask we try a transition + for( cur = m->start; cur != NULL; cur = cur->next ) + if( TEST_BIT( m->cur_state, cur->num )) + { + tr = cur->tr; + if( tr != NULL ) + { + // first we must match the name and attributes + if( strcmp( tr->name, "." ) != 0 && + ( node->name == NULL || strcasecmp( tr->name, (char *)node->name ) != 0 )) + continue; + if( tr->attrs != NULL && !attrs_process( tr, node->properties )) + continue; + // second we can match a machine and regexp + if( tr->ptr != NULL && !tree_process( tr->ptr, node->children )) + continue; + if( tr->re.re_magic != 0 && !regex_process( tr, (char *)node->content )) + continue; + // we have a winner! add E(st) to the next state bitmap + OR( m->next_state, m->E[tr->st->num], m->states ); + } + } + // advance input + node = node->next; + + // swap cur_state and next_state pointers, saves us a copy operation + e = m->cur_state; + m->cur_state = m->next_state; + m->next_state = e; + } + + // the machine accepts the input if we end up in the final state + done = TEST_BIT( m->cur_state, m->final->num ); + return done; +} + +// extracts regex matches from a machine after it has been run +struct regex_match *find_matches( struct state *s, struct regex_match *m ) +{ + struct regex_match *cur, *head; + struct trans *tr; + struct attribute *attr; + int i; + + if( s == NULL ) + return m; + + // recurse to next state first, so we can add the matches in the current state to the + // front of the list + m = find_matches( s->next, m ); + + // grab matches in this state + tr = s->tr; + if( tr != NULL ) + { + // the -> comes after <foo> in the expression, so search it first + if( tr->ptr != NULL ) + m = find_matches( tr->ptr->start, m ); + + // next search : "foo" + if( tr->str != NULL ) + { + // loop backwards so that list builds forwards + for( i = RESUBR - 1; i > 0; i-- ) + if( tr->match[i].rm_eo != -1 ) + { + cur = zalloc( sizeof( struct regex_match )); + cur->match = tr->match[i]; + cur->str = tr->str; + cur->next = m; + m = cur; + } + } + + // last search <foo> + // loop forwards because we have no choice, but build list backwards + head = NULL; + cur = NULL; + for( attr = tr->attrs; attr != NULL; attr = attr->next ) + { + if( attr->str == NULL ) + continue; + for( i = 1; i < RESUBR; i++ ) + if( attr->match[i].rm_eo != -1 ) + { + if( head == NULL ) + cur = head = zalloc( sizeof( struct regex_match )); + else + cur = cur->next = zalloc( sizeof( struct regex_match )); + cur->match = attr->match[i]; + cur->str = attr->str; + cur->next = NULL; + } + } + if( head != NULL ) + { + cur->next = m; + m = head; + } + } + return m; +} + +// runs machine m on each xml node at this level, then recurses to it's children, building a +// list of matches +struct match *node_recurse( struct machine *m, xmlNodePtr node, struct match *n ) +{ + xmlNodePtr cur, next; + struct match *xml; + + if( node == NULL ) + return n; + for( cur = node; cur != NULL; cur = cur->next ) + { + // this will consider each node by itself (without siblings) + next = cur->next; + cur->next = NULL; + if( tree_process( m, cur )) + { + xml = zalloc( sizeof( struct match )); + xml->next = n; + xml->node = cur; + xml->re = find_matches( m->start, NULL ); + n = xml; + } + cur->next = next; + // recurse to children + n = node_recurse( m, cur->children, n ); + } + return n; +} + +// run a machine on each node in an xml document and return a list of matches +struct match *document_process( struct machine *m, xmlDocPtr doc ) +{ + return node_recurse( m, doc->children->next, NULL ); +} diff --git a/treexpr.h b/treexpr.h new file mode 100644 index 0000000..c424a54 --- /dev/null +++ b/treexpr.h @@ -0,0 +1,107 @@ +/* treexpr.h - Tree expression language header + + Copyright (C) 2005 David Barksdale + + + + This library is free software; you can redistribute it and/or + + modify it under the terms of the GNU Lesser General Public + + License as published by the Free Software Foundation; either + + version 2.1 of the License, or (at your option) any later version. + + + + This library is distributed in the hope that it will be useful, + + but WITHOUT ANY WARRANTY; without even the implied warranty of + + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + + Lesser General Public License for more details. + + + + You should have received a copy of the GNU Lesser General Public + + License along with this library; if not, write to the Free Software + + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef _TREEXPR_H_ +#define _TREEXPR_H_ + +#include <libxml/tree.h> +#include <sys/types.h> +#include "regex.h" + +/* + * State machines + */ + +struct state; + +struct epsilon +{ + struct epsilon *next; + struct state *st; +}; + +#define RESUBR ( 10 ) + +struct attribute +{ + struct attribute *next; + char *name; // name of attribute to match + regex_t re; // compiled regular expression to match + regmatch_t match[RESUBR]; // matches + char *str; // string containing matches +}; + +struct trans +{ + struct state *st; // state we transition to upon match + // stuff to match + char *name; // name of tag to match against + regex_t re; // compiled regular expression to match against contents + regmatch_t match[RESUBR]; // matches + char *str; // string containing matches + struct attribute *attrs; // attributes to match against + struct machine *ptr; // machine to match children +}; + +struct state +{ + struct trans *tr; // optional transition + struct epsilon *ep; // list of epsilon transitions + int num; // state number (generated at run time) + // graph traversal + struct state *next; // internal list of states for a machine +}; + +struct machine +{ + struct state *start; // start state + struct state *final; // final state (yes, only one) + // parse errors + const char *error, *buf; + // execution + int states; // number of states + int **E; // arrays of bit masks for E function + // I moved these here to make repeated execution a little faster + // we alloc these buffers on the first execution and then reuse them + int *cur_state; + int *next_state; +}; + +/* Matches */ + +struct regex_match +{ + struct regex_match *next; + regmatch_t match; // match + char *str; // string containing match +}; + +struct match +{ + struct match *next; + xmlNodePtr node; // root node of tree match + struct regex_match *re; // list of regular expression matches +}; + +/* Public functions */ + +const char *parse_treexpr( const char *expr, struct machine **m ); +void free_machine( struct machine *m ); +struct match *document_process( struct machine *m, xmlDocPtr doc ); + +#endif |