head 1.7; access; symbols; locks; strict; comment @.\" @; 1.7 date 2026.10.14.22.25.13; author agc; state dead; branches; next 1.6; commitid EvQuBHLEvZ6nMuZG; 1.6 date 2021.10.05.23.35.38; author uwe; state Exp; branches; next 1.5; commitid w6tYnouLNYJS9GbD; 1.5 date 2021.10.05.22.17.15; author agc; state Exp; branches; next 1.4; commitid 80tt23kmyDzOIFbD; 1.4 date 2021.10.05.18.56.24; author uwe; state Exp; branches; next 1.3; commitid 42XiY5WkOQu5CEbD; 1.3 date 2021.10.05.01.23.39; author agc; state Exp; branches; next 1.2; commitid iWez0YTivClGMybD; 1.2 date 2017.08.17.11.03.21; author wiz; state Exp; branches; next 1.1; commitid U3UuYEz9ype4xy3A; 1.1 date 2017.08.16.23.38.13; author agc; state Exp; branches; next ; commitid QRh3ZHtCDsbQJu3A; desc @@ 1.7 log @Remove this old code, it's been superceded - see pkgsrc/devel/libagcre and pkgsrc/textproc/agcre @ text @.\" $NetBSD: libagcre.3,v 1.6 2021/10/05 23:35:38 uwe Exp $ .\" .\" Copyright (c) 2017,2020,2021 Alistair Crooks .\" All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES .\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, .\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, .\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. .\" .Dd October 1, 2021 .Dt LIBAGCRE 3 .Os .Sh NAME .Nm agcre .Nd regular expression library .Sh LIBRARY .\"Lb agcre agcre Regular Expression Library (libagcre, \-lagcre) .Sh SYNOPSIS .In agcre.h .\" .Ft "agcre_regex_t *" .Fo agcre_new .Fa "void" .Fc .\" .Ft int .Fo agcre_regcomp .Fa "agcre_regex_t *expression" .Fa "const void *pat" .Fa "uint32_t flags" .Fc .\" .Ft int .Fo agcre_regexec .Fa "agcre_regex_t *expression" .Fa "const void *input" .Fa "size_t nmatch" .Fa "agcre_regmatch_t *matches" .Fa "uint32_t flags" .Fc .\" .Ft int .Fo agcre_rev_regexec .Fa "agcre_regex_t *expression" .Fa "const void *input" .Fa "size_t nmatch" .Fa "agcre_regmatch_t *matches" .Fa "uint32_t flags" .Fc .\" .Ft void .Fo agcre_regfree .Fa "agcre_regex_t *expression" .Fc .\" .Ft size_t .Fo agcre_regerror .Fa "int errnum" .Fa "const agcre_regex_t *expression" .Fa "char *buf" .Fa "size_t size" .Fc .\" .Ft ssize_t .Fo agcre_regnsub .Fa "char *buf" .Fa "size_t size" .Fa "const char *repl" .Fa "const agcre_regmatch_t *matches" .Fa "const char *str" .Fc .\" .Ft ssize_t .Fo agcre_regasub .Fa "char **buf" .Fa "const char *repl" .Fa "const agcre_regmatch_t *matches" .Fa "const char *str" .Fc .Sh DESCRIPTION The .Nm library is a library interface to the new regular expression functions. It will compile expressions described in .Xr agcre_format 7 , as well as some extensions. .Pp An .Vt agcre_regex_t structure can either be allocated on the stack, or it can be allocated dynamically using .Fn agcre_new function. If this function is used, storage must be freed by the caller using .Xr free 3 . .Pp A regular expression is compiled using .Fn agcre_regcomp . Various flags can be specified during compilation, which will alter the regular expression which is produced. These flags are: .Bl -tag -width Dv .It Dv AGCRE_REG_BASIC Use basic regular expressions. These are preserved for legacy reasons; no new code should use basic regular expressions. For more information on regular expression formats, please refer to .Xr agcre_format 7 . .It Dv AGCRE_REG_EXTENDED Extended regular expressions are the standard form of searching, and should be used. .It Dv AGCRE_REG_NOSUB When searching through text, the standard searches are performed, but no subexpression information will be returned. .It Dv AGCRE_REG_NEWLINE Normally newline characters are treated as a standard character. With this flag, the zero width match for .Ql \&^ before the newline character will match, as will the zero width string after the .Ql \&$ . .It Dv AGCRE_REG_NOSPEC A standard search text will be performed, and no special characters will be recognised. In the current implementation, this will be performed using a Horspool-modified Boyer\(enMoore search. .It Dv AGCRE_REG_PEND Normally, the end of the string to be compiled will be the first .Tn ASCII NUL character encountered. With this flag, the .Va re_endp field in the .Vt agcre_regex_t structure will be used to point to the last position in the string to be compiled. .It Dv AGCRE_REG_DUMP The current implementation builds a virtual machine to recognise the regular expression. This flag means that, after successful compilation of the expression, the individual virtual machine instructions will be printed on standard output. .It Dv AGCRE_REG_TRACE Traces execution of the regular expression. .It Dv AGCRE_REG_CTAGS This is used where a regular expression pattern was generated by the .Xr ctags 1 program, since the syntax generated does not conform to a standard basic regular expression. In particular, .Xr ctags 1 outputs function location patterns which contain an unescaped .Ql * character, whereas basic regular expressions will only recognise an asterisk as a standard character if it appears at the start of an expression. .\".It Dv AGCRE_IN_8BITS .\"This indicates to the .\".Fn agcre_regcomp .\"function that the string which will be parsed .\"as a regular expression has been passed as an array of bytes. .\"This is the default .\".Dq width .\"of the string expression. .\".It Dv AGCRE_IN_16BITS .\"This indicates to the .\".Fn agcre_regcomp .\"function that the string which will be parsed .\"as a regular expression has been passed as an array of 16bit .\"integers. .\".It Dv AGCRE_IN_32BITS .\"This indicates to the .\".Fn agcre_regcomp .\"function that the string which will be parsed .\"as a regular expression has been passed as an array of 32bit .\"integers. .El .Pp A regular expression, once compiled, can be executed on different input using .Fn agcre_regexec . Various flags govern the matching behavior \(em these are: .Bl -tag -width Dv .It Dv AGCRE_REG_ICASE When searching through text, a case-insensitive search will be performed. In contrast to other regular expression libraries, case insensitivity does not need to be specified at expression compile time, only at expression execution time. .It Dv AGCRE_REG_NOTBOL Normally, the sub-string passed to .Fn agcre_regexec is assumed to be the start of the whole string, and .Ql ^ matching will be performed in the standard way. With this flag, beginning of line matching will be suppressed. .It Dv AGCRE_REG_NOTEOL Normally, the sub-string passed to .Fn agcre_regexec is assumed to be the end of the whole string, and .Ql $ matching will be performed in the standard way. With this flag, end of line matching will be suppressed. .It Dv AGCRE_REG_STARTEND The string passed to .Fn agcre_regexec is normally assumed to start at the first character, and to complete at the first .Tn ASCII NUL character. With this flag, the start and end offsets to use for string matching are taken from the .Va rm_so and .Va rm_eo fields provided in the zero-th element of the .Fa matchv argument. .It Dv AGCRE_REG_ANCHOR Normally regular expressions are not assumed to start at the first character, but rather to have a lazy search at their start. Occasionally, a search anchored to the start of the string is preferred. This cannot be simulated by the .Dv AGCRE_REG_NOTBOL flag. Searches where a match needs to be found in the first character should therefore use the .Dv AGCRE_REG_ANCHOR definition. Anchoring can be specified at expression compile time, and/or at expression execution time. .\".It Dv AGCRE_IN_8BITS .\"This indicates to the .\".Fn agcre_regexec .\"function that the string which will be parsed .\"as a regular expression has been passed as an array of bytes. .\"This is the default .\".Dq width .\"of the string expression. .\".It Dv AGCRE_IN_16BITS .\"This indicates to the .\".Fn agcre_regexec .\"function that the string which will be parsed .\"as a regular expression has been passed as an array of 16bit .\"integers. .\".It Dv AGCRE_IN_32BITS .\"This indicates to the .\".Fn agcre_regexec .\"function that the string which will be parsed .\"as a regular expression has been passed as an array of 32bit .\"integers. .El .Pp Since normal expression searches take place moving forwards within a byte stream, there is not normally any need to have a function which searches a byte stream or buffer moving in reverse. However, editors frequently must implement this functionality on their own. To make reverse searching easier, the .Fn agcre_rev_regexec function is provided, which will start at the end of the sized buffer, using the .Dv AGCRE_REG_STARTEND definition, and the search will continue character by character until either a match is found or the start of the buffer is reached. This search will be done in an efficient manner, so that buffer contents which have already been searched will not be searched again. .Pp The .Fn agcre_regcomp and .Fn agcre_regexec functions both return a .Dv AGCRE_REG_SUCCESS value for a successful compilation or match, and a .Dv AGCRE_REG_FAILURE value for an unsuccessful compilation or match. In the case of an unsuccessful compilation, the .Fn agcre_regerror function can be used to identify the source of the error. Any errors encountered during compilation or execution can be displayed using .Fn agcre_regerror . .Pp The implementation is based around Rob Pike's constant-time virtual machine implementation, released in 2008 by Russ Cox with a .Tn BSD license. That implementation has been augmented to support Unicode characters, Perl escape sequences, back references, specifically-bounded repeat sequences and character sets, ranges and .Tn POSIX character classes. .Pp Because a virtual machine is used, there are no real limits to the size of regular expression which can be compiled. However, to avoid abuse, certain arbitrary limits are set: .Bl -bullet -offset indent -compact .It the maximum number of .Em tokens is set at compile-time to 65536 .It the maximum number of .Em sets is set at compile-time to 1024 .El .Pp To deallocate storage in the compiled regular expression, the .Fn agcre_regfree is used. Once the storage is deallocated, it cannot be used again without another compilation using .Fn agcre_regcomp . .Pp If storage for the regular expression was allocated using .Fn agcre_new then that storage should be deallocated using the .Xr free 3 function. .Pp The .Fn agcre_regnsub and .Fn agcre_regasub functions perform substitutions using .Xr sed 1 like syntax. They return the length of the string that would have been created if there was enough space or \-1 on error, setting .Va errno . The result is placed in .Fa buf which is user-supplied in .Fn agcre_regnsub and dynamically allocated in .Fn agcre_regasub . The .Fa repl argument contains a substitution string which might refer to the first 9 regular expression strings using .Sq Li \e Ns Ar to refer to the .Ar n\^ Ns th matched item, or .Ql \&& (which is equivalent to .Ql \e0 ) to refer to the full match. The .Fa matches array must be at least 10 elements long, and should contain the result of the matches from a previous .Fn agcre_regexec call. Only 10 elements of the .Fa matches array can be used. The .Fa str argument contains the source string in which transformations will be substituted. .Pp To show the value of constant-time execution, especially for regular expressions which may be subject to abuse, the standard .Xr grep 1 implementation takes over 30 minutes to compile and execute the following regular expression (before it was killed) .Bd -literal -offset indent % time grep -E '(a?){9999}aaaaaaaaaaaaaaaaaaaaaaaaaaaaa' 2.in load: 1.00 cmd: grep 7305 [0x1afe045d2] 1936.42u 1.28s 99% 476788k load: 1.07 cmd: grep 7305 [0x1afe045de] 2015.52u 1.28s 99% 476868k ^C2027.526u 1.332s 33:49.09 99.9% 0+0k 0+0io 0pf+0w .Ed .Pp whereas .Xr agcre 1 will execute the compilation and execution in less than 0.05 seconds .Bd -literal -offset indent % time agcre '(a?){9999}aaaaaaaaaaaaaaaaaaaaaaaaaaaaa' 2.in aaaaaaaaaaaaaaaaaaaaaaaaaaaaa 0.034u 0.011s 0:00.04 100.0% 0+0k 0+0io 0pf+0w % .Ed .Sh SEE ALSO .Xr agcre 1 , .Xr agcre_format 7 .Sh HISTORY The .Nm library first appeared in .Nx 9.0 . .Sh AUTHORS .An Alistair Crooks Aq agc@@NetBSD.org @ 1.6 log @Sprinkle more markup in previous. Sync argument names. @ text @d1 1 a1 1 .\" $NetBSD: libagcre.3,v 1.5 2021/10/05 22:17:15 agc Exp $ @ 1.5 log @add MLINKS for rev_regexec and reg[an]sub functions @ text @d1 1 a1 1 .\" $NetBSD: libagcre.3,v 1.4 2021/10/05 18:56:24 uwe Exp $ d168 1 a168 1 program, since the syntax generated does not conform to a standard d356 3 a358 1 the string that would have been created if there was enough space or -1 on error, setting errno. d360 3 a362 1 placed in buf which is user-supplied in d366 5 a370 3 The sub argument contains a substitution string which might refer to the first 9 regular expression strings using .Ql \e d372 5 a376 2 to the nth matched item, or .Ql & d380 3 a382 2 The match array must be at least 10 elements long, d387 6 a392 2 elements of the rm array can be used. The str argument contains the source string in which transformations will be substituted. @ 1.4 log @Tweak markup. @ text @d1 1 a1 1 .\" $NetBSD: libagcre.3,v 1.3 2021/10/05 01:23:39 agc Exp $ d165 12 a254 12 .It Dv AGCRE_REG_ANCHOR This is used where a regular expression pattern was generated by the .Xr ctags 1 program, since the syntax generated does not conform to a standard basic regular expression. In particular, .Xr ctags 1 outputs function location patterns which contain an unescaped .Ql * character, whereas basic regular expressions will only recognise an asterisk as a standard character if it appears at the start of an expression. d321 1 a321 1 there are no real limits top the size of regular expression d335 45 @ 1.3 log @Update agcre to version 20211001 20211001 ======== + move to a single source file, which can just be included as a single file (the library method can still be used for this as well - sometimes, it's just easier to drop in a single file to other projects) + add AGCRE_EMBED_CTAGS as a primary regular expresion type (same as basic regexps, but where a '*' occurs as a non-column 0 element of the pattern, it is assumed to be a standard character, as produced by ctags(1) output; basic regular expressions only accept '*' as a standard character as the first element of the expression). Yay. + make the version string in the program a real string, so it can be found using strings(1) + add an agcre_rev_regexec(3) function, which searches the text in an efficient, reverse manner, a la strrchr(3) or memrchr(3) fashion. + add agcre_regnsub(3) and agcre_regasub(3) functions + bump the shared lib version to 1.0 + cut version 20211001 @ text @d1 1 a1 1 .\" $NetBSD: agcre.3,v 1.2 2017/08/17 11:03:21 wiz Exp $ d27 1 a27 1 .Dt AGCRE-EMBED 3 d33 2 a34 1 .Lb agcre d37 1 d42 2 a43 1 .Ft "int" d45 3 a47 1 .Fa "agcre_regex_t *expression" "const void *pat" "uint32_t flags" d49 1 d52 5 a56 1 .Fa "agcre_regex_t *expression" "const void *input" "size_t nmatch" "agcre_regmatch_t *matches" "uint32_t flags" d58 1 d61 5 a65 1 .Fa "agcre_regex_t *expression" "const void *input" "size_t nmatch" "agcre_regmatch_t *matches" "uint32_t flags" d67 1 d72 1 d75 4 a78 1 .Fa "int errnum" "const agcre_regex_t *expression" "char *buf" "size_t size" d80 1 d83 5 a87 1 .Fa "char *buf" "size_t size" "const char *repl" "const agcre_regmatch_t *matches" "const char *str" d89 1 d92 4 a95 1 .Fa "char **buf" "const char *repl" "const agcre_regmatch_t *matches" "const char *str" d106 1 a106 1 A d121 1 a121 1 .Bl -tag -width AGCRE_REG_EXTENDEDXXX d124 1 a124 1 These are prserved for legacy reasons; no new code should use basic d132 1 a132 1 When searching through text, the standard searches are perfomed, d137 1 a137 1 .Dq ^ d140 1 a140 1 .Dq $ . d145 1 a145 1 a Horspool-modified Boyer-Moore search. d148 3 a150 1 first ASCII NUL character encountered. d152 1 a152 1 .Dv re_endp d190 2 a191 2 Various flags govern the matching behavior - these are: .Bl -tag -width AGCRE_REG_EXTENDEDXXX d202 1 a202 1 .Dq ^ d210 1 a210 1 .Dq $ d218 2 a219 1 complete at the first ASCII NUL d223 1 a223 1 .Dv rm_so d225 1 a225 1 .Dv rm_eo d246 1 a246 1 program, since the syntax generated does not conform to a standard d251 1 a251 1 .Dq * d309 3 a311 1 with a BSD license. d316 3 a318 1 and character sets, ranges and POSIX character classes. d324 9 a332 5 .Bl -tag -width characterXXX .It tokens the maximum number of tokens is set at compile-time to 65536 .It sets the maximum number of sets is set at compile-time to 1024 @ 1.2 log @Use more markup. @ text @d1 1 a1 1 .\" $NetBSD: libagcre.3,v 1.1 2017/08/16 23:38:13 agc Exp $ d3 1 a3 1 .\" Copyright (c) 2017 Alistair Crooks d26 2 a27 2 .Dd July 4, 2017 .Dt LIBAGCRE 3 d30 1 a30 1 .Nm libagcre d33 1 a33 1 .Lb libagcre d42 1 a42 1 .Fa "agcre_regex_t *expression" "const void *pat" "int flags" d46 5 a50 1 .Fa "agcre_regex_t *expression" "const void *input" "size_t nmatch" "agcre_regmatch_t *matches" "int flags" d60 8 a133 4 .It Dv AGCRE_REG_LARGE Is deprecated, and only recognised for legacy reasons. .It Dv AGCRE_REG_BACKR Is deprecated, and only recognised for legacy reasons. d197 26 d245 14 @ 1.1 log @Just what this world needs - another regexp library. However, for something I was doing, I needed a regexp library in C, BSD-licensed, and able to be exposed to a wide range of expressions, some better controlled than others. The resulting library is libagcre, which implements regular expression compilation and execution. It uses the Pike Virtual Machine approach, and features: + standard POSIX features where sane + some/most Perl escapes + lazy matching via '?' + non-capture parenthese (?:...) + in-expression case-insensitive directives are supported (?i)...(?-i) + all case-insensitivity is actioned at expression exec time. Case-insensitivity can be specified at expression compile-time, and, if so, it will be remembered. But the expression itself, once compiled, can be used to match in both a case-sensitive and insensitive manner + utf8 is supported both for expressions and for input text when matching + unicode escapes (in the Java format of \uABCD) are supported + exact multiple repetition specifiers {N}, and {N,M} are supported + backreferences are supported + utf16 (LE and BE) and utf32 (LE and BE) are supported, both for the expression and for the input being searched + at the most basic level, individual 32bit unicode characters are matched + an egrep/grep implementation for matching unicode regexps is included A simple implementation of sets is used to provide inclusion and exclusion information for unicode characters, which is taken directly from unicode.org. No bitmasks are used - ranges are specified by using an upper and a lower bound for the codepoints. Callbacks can also be added to these sets, to provide functionality similar to the ctype macros across the whole unicode character set. The standard regular expression basic3 torture test is passed with 4 known (and, I'd argue, incorrect) results flagged. As expected, the expression '(a?){9999}aaaaaaaaaaaaaaaaaaaaaaaaaaaaa' matches in linear time, as does the expression '((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))' % time agcre '(a?){9999}aaaaaaaaaaaaaaaaaaaaaaaaaaaaa' dist/tests/2.in aaaaaaaaaaaaaaaaaaaaaaaaaaaaa 0.063u 0.000s 0:00.06 100.0% 0+0k 0+0io 0pf+0w % time egrep '(a?){9999}aaaaaaaaaaaaaaaaaaaaaaaaaaaaa' dist/tests/2.in ^C88.462u 0.730s 1:29.21 99.9% 0+0k 0+0io 0pf+0w % The library and agcre utility have been run through valgrind to confirm no memory leaks. In general, the emphasis is on a modern, predictable, VM-style, well-featured regexp library, in C, with a BSD license. In particular, sljit has not been used to speed up on certain platforms, most Perl regexp features are supported, as are back references, and UTF-8, UTF-16 and UTF32. Once again, I wouldn't expect anyone to use this as the main engine in egrep. But I am always amazed at the uses for some of the things that I write. For more information about the Pike VM, and comparison to other regexp implementations, please see: https://swtch.com/~rsc/regexp/regexp2.html Alistair Crooks Tue Aug 15 07:43:34 PDT 2017 @ text @d1 1 a1 1 .\" $NetBSD: genraidconf.8,v 1.3 2011/05/17 11:23:41 wiz Exp $ d66 1 a66 1 .Dv agcre_regex_t d81 1 a81 1 .It AGCRE_REG_BASIC d85 1 a85 1 For more information on regular expression formats, please refer to d87 1 a87 1 .It AGCRE_REG_EXTENDED d90 1 a90 1 .It AGCRE_REG_NOSUB d93 1 a93 1 .It AGCRE_REG_NEWLINE d100 1 a100 1 .It AGCRE_REG_NOSPEC d105 1 a105 1 .It AGCRE_REG_PEND d111 1 a111 1 .Dv agcre_regex_t d114 1 a114 1 .It AGCRE_REG_DUMP d120 7 a126 7 .It AGCRE_REG_TRACE traces execution of the regular expression. .It AGCRE_REG_LARGE is deprecated, and only recognised for legacy reasons. .It AGCRE_REG_BACKR is deprecated, and only recognised for legacy reasons. .\".It AGCRE_IN_8BITS d134 1 a134 1 .\".It AGCRE_IN_16BITS d140 1 a140 1 .\".It AGCRE_IN_32BITS d153 1 a153 1 .It AGCRE_REG_ICASE d159 1 a159 1 .It AGCRE_REG_NOTBOL d167 1 a167 1 .It AGCRE_REG_NOTEOL d175 1 a175 1 .It AGCRE_REG_STARTEND d189 1 a189 1 .\".It AGCRE_IN_8BITS d197 1 a197 1 .\".It AGCRE_IN_16BITS d203 1 a203 1 .\".It AGCRE_IN_32BITS d242 1 a242 2 the maximum number of tokens is set at compile-time to 65536 @