Merge from vendor branch LIBPCAP:
[dragonfly.git] / lib / libc / regex / regex.3
1 .\" Copyright (c) 1992, 1993, 1994 Henry Spencer.
2 .\" Copyright (c) 1992, 1993, 1994
3 .\"     The Regents of the University of California.  All rights reserved.
4 .\"
5 .\" This code is derived from software contributed to Berkeley by
6 .\" Henry Spencer.
7 .\"
8 .\" Redistribution and use in source and binary forms, with or without
9 .\" modification, are permitted provided that the following conditions
10 .\" are met:
11 .\" 1. Redistributions of source code must retain the above copyright
12 .\"    notice, this list of conditions and the following disclaimer.
13 .\" 2. Redistributions in binary form must reproduce the above copyright
14 .\"    notice, this list of conditions and the following disclaimer in the
15 .\"    documentation and/or other materials provided with the distribution.
16 .\" 3. All advertising materials mentioning features or use of this software
17 .\"    must display the following acknowledgement:
18 .\"     This product includes software developed by the University of
19 .\"     California, Berkeley and its contributors.
20 .\" 4. Neither the name of the University nor the names of its contributors
21 .\"    may be used to endorse or promote products derived from this software
22 .\"    without specific prior written permission.
23 .\"
24 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 .\" SUCH DAMAGE.
35 .\"
36 .\"     @(#)regex.3     8.4 (Berkeley) 3/20/94
37 .\" $FreeBSD: src/lib/libc/regex/regex.3,v 1.4.2.4 2001/12/14 18:33:56 ru Exp $
38 .\" $DragonFly: src/lib/libc/regex/regex.3,v 1.2 2003/06/17 04:26:44 dillon Exp $
39 .\"
40 .Dd March 20, 1994
41 .Dt REGEX 3
42 .Os
43 .Sh NAME
44 .Nm regcomp ,
45 .Nm regexec ,
46 .Nm regerror ,
47 .Nm regfree
48 .Nd regular-expression library
49 .Sh LIBRARY
50 .Lb libc
51 .Sh SYNOPSIS
52 .In sys/types.h
53 .In regex.h
54 .Ft int
55 .Fn regcomp "regex_t *preg" "const char *pattern" "int cflags"
56 .Ft int
57 .Fo regexec
58 .Fa "const regex_t *preg" "const char *string"
59 .Fa "size_t nmatch" "regmatch_t pmatch[]" "int eflags"
60 .Fc
61 .Ft size_t
62 .Fo regerror
63 .Fa "int errcode" "const regex_t *preg"
64 .Fa "char *errbuf" "size_t errbuf_size"
65 .Fc
66 .Ft void
67 .Fn regfree "regex_t *preg"
68 .Sh DESCRIPTION
69 These routines implement
70 .St -p1003.2
71 regular expressions
72 .Pq Do RE Dc Ns s ;
73 see
74 .Xr re_format 7 .
75 .Fn Regcomp
76 compiles an RE written as a string into an internal form,
77 .Fn regexec
78 matches that internal form against a string and reports results,
79 .Fn regerror
80 transforms error codes from either into human-readable messages,
81 and
82 .Fn regfree
83 frees any dynamically-allocated storage used by the internal form
84 of an RE.
85 .Pp
86 The header
87 .Aq Pa regex.h
88 declares two structure types,
89 .Ft regex_t
90 and
91 .Ft regmatch_t ,
92 the former for compiled internal forms and the latter for match reporting.
93 It also declares the four functions,
94 a type
95 .Ft regoff_t ,
96 and a number of constants with names starting with
97 .Dq Dv REG_ .
98 .Pp
99 .Fn Regcomp
100 compiles the regular expression contained in the
101 .Fa pattern
102 string,
103 subject to the flags in
104 .Fa cflags ,
105 and places the results in the
106 .Ft regex_t
107 structure pointed to by
108 .Fa preg .
109 .Fa Cflags
110 is the bitwise OR of zero or more of the following flags:
111 .Bl -tag -width REG_EXTENDED
112 .It Dv REG_EXTENDED
113 Compile modern
114 .Pq Dq extended
115 REs,
116 rather than the obsolete
117 .Pq Dq basic
118 REs that
119 are the default.
120 .It Dv REG_BASIC
121 This is a synonym for 0,
122 provided as a counterpart to
123 .Dv REG_EXTENDED
124 to improve readability.
125 .It Dv REG_NOSPEC
126 Compile with recognition of all special characters turned off.
127 All characters are thus considered ordinary,
128 so the
129 .Dq RE
130 is a literal string.
131 This is an extension,
132 compatible with but not specified by
133 .St -p1003.2 ,
134 and should be used with
135 caution in software intended to be portable to other systems.
136 .Dv REG_EXTENDED
137 and
138 .Dv REG_NOSPEC
139 may not be used
140 in the same call to
141 .Fn regcomp .
142 .It Dv REG_ICASE
143 Compile for matching that ignores upper/lower case distinctions.
144 See
145 .Xr re_format 7 .
146 .It Dv REG_NOSUB
147 Compile for matching that need only report success or failure,
148 not what was matched.
149 .It Dv REG_NEWLINE
150 Compile for newline-sensitive matching.
151 By default, newline is a completely ordinary character with no special
152 meaning in either REs or strings.
153 With this flag,
154 .Ql [^
155 bracket expressions and
156 .Ql .\&
157 never match newline,
158 a
159 .Ql ^\&
160 anchor matches the null string after any newline in the string
161 in addition to its normal function,
162 and the
163 .Ql $\&
164 anchor matches the null string before any newline in the
165 string in addition to its normal function.
166 .It Dv REG_PEND
167 The regular expression ends,
168 not at the first NUL,
169 but just before the character pointed to by the
170 .Va re_endp
171 member of the structure pointed to by
172 .Fa preg .
173 The
174 .Va re_endp
175 member is of type
176 .Ft "const char *" .
177 This flag permits inclusion of NULs in the RE;
178 they are considered ordinary characters.
179 This is an extension,
180 compatible with but not specified by
181 .St -p1003.2 ,
182 and should be used with
183 caution in software intended to be portable to other systems.
184 .El
185 .Pp
186 When successful,
187 .Fn regcomp
188 returns 0 and fills in the structure pointed to by
189 .Fa preg .
190 One member of that structure
191 (other than
192 .Va re_endp )
193 is publicized:
194 .Va re_nsub ,
195 of type
196 .Ft size_t ,
197 contains the number of parenthesized subexpressions within the RE
198 (except that the value of this member is undefined if the
199 .Dv REG_NOSUB
200 flag was used).
201 If
202 .Fn regcomp
203 fails, it returns a non-zero error code;
204 see
205 .Sx DIAGNOSTICS .
206 .Pp
207 .Fn Regexec
208 matches the compiled RE pointed to by
209 .Fa preg
210 against the
211 .Fa string ,
212 subject to the flags in
213 .Fa eflags ,
214 and reports results using
215 .Fa nmatch ,
216 .Fa pmatch ,
217 and the returned value.
218 The RE must have been compiled by a previous invocation of
219 .Fn regcomp .
220 The compiled form is not altered during execution of
221 .Fn regexec ,
222 so a single compiled RE can be used simultaneously by multiple threads.
223 .Pp
224 By default,
225 the NUL-terminated string pointed to by
226 .Fa string
227 is considered to be the text of an entire line, minus any terminating
228 newline.
229 The
230 .Fa eflags
231 argument is the bitwise OR of zero or more of the following flags:
232 .Bl -tag -width REG_STARTEND
233 .It Dv REG_NOTBOL
234 The first character of
235 the string
236 is not the beginning of a line, so the
237 .Ql ^\&
238 anchor should not match before it.
239 This does not affect the behavior of newlines under
240 .Dv REG_NEWLINE .
241 .It Dv REG_NOTEOL
242 The NUL terminating
243 the string
244 does not end a line, so the
245 .Ql $\&
246 anchor should not match before it.
247 This does not affect the behavior of newlines under
248 .Dv REG_NEWLINE .
249 .It Dv REG_STARTEND
250 The string is considered to start at
251 .Fa string
252 +
253 .Fa pmatch Ns [0]. Ns Va rm_so
254 and to have a terminating NUL located at
255 .Fa string
256 +
257 .Fa pmatch Ns [0]. Ns Va rm_eo
258 (there need not actually be a NUL at that location),
259 regardless of the value of
260 .Fa nmatch .
261 See below for the definition of
262 .Fa pmatch
263 and
264 .Fa nmatch .
265 This is an extension,
266 compatible with but not specified by
267 .St -p1003.2 ,
268 and should be used with
269 caution in software intended to be portable to other systems.
270 Note that a non-zero
271 .Va rm_so
272 does not imply
273 .Dv REG_NOTBOL ;
274 .Dv REG_STARTEND
275 affects only the location of the string,
276 not how it is matched.
277 .El
278 .Pp
279 See
280 .Xr re_format 7
281 for a discussion of what is matched in situations where an RE or a
282 portion thereof could match any of several substrings of
283 .Fa string .
284 .Pp
285 Normally,
286 .Fn regexec
287 returns 0 for success and the non-zero code
288 .Dv REG_NOMATCH
289 for failure.
290 Other non-zero error codes may be returned in exceptional situations;
291 see
292 .Sx DIAGNOSTICS .
293 .Pp
294 If
295 .Dv REG_NOSUB
296 was specified in the compilation of the RE,
297 or if
298 .Fa nmatch
299 is 0,
300 .Fn regexec
301 ignores the
302 .Fa pmatch
303 argument (but see below for the case where
304 .Dv REG_STARTEND
305 is specified).
306 Otherwise,
307 .Fa pmatch
308 points to an array of
309 .Fa nmatch
310 structures of type
311 .Ft regmatch_t .
312 Such a structure has at least the members
313 .Va rm_so
314 and
315 .Va rm_eo ,
316 both of type
317 .Ft regoff_t
318 (a signed arithmetic type at least as large as an
319 .Ft off_t
320 and a
321 .Ft ssize_t ) ,
322 containing respectively the offset of the first character of a substring
323 and the offset of the first character after the end of the substring.
324 Offsets are measured from the beginning of the
325 .Fa string
326 argument given to
327 .Fn regexec .
328 An empty substring is denoted by equal offsets,
329 both indicating the character following the empty substring.
330 .Pp
331 The 0th member of the
332 .Fa pmatch
333 array is filled in to indicate what substring of
334 .Fa string
335 was matched by the entire RE.
336 Remaining members report what substring was matched by parenthesized
337 subexpressions within the RE;
338 member
339 .Va i
340 reports subexpression
341 .Va i ,
342 with subexpressions counted (starting at 1) by the order of their opening
343 parentheses in the RE, left to right.
344 Unused entries in the array (corresponding either to subexpressions that
345 did not participate in the match at all, or to subexpressions that do not
346 exist in the RE (that is,
347 .Va i
348 >
349 .Fa preg Ns -> Ns Va re_nsub ) )
350 have both
351 .Va rm_so
352 and
353 .Va rm_eo
354 set to -1.
355 If a subexpression participated in the match several times,
356 the reported substring is the last one it matched.
357 (Note, as an example in particular, that when the RE
358 .Ql "(b*)+"
359 matches
360 .Ql bbb ,
361 the parenthesized subexpression matches each of the three
362 .So Li b Sc Ns s
363 and then
364 an infinite number of empty strings following the last
365 .Ql b ,
366 so the reported substring is one of the empties.)
367 .Pp
368 If
369 .Dv REG_STARTEND
370 is specified,
371 .Fa pmatch
372 must point to at least one
373 .Ft regmatch_t
374 (even if
375 .Fa nmatch
376 is 0 or
377 .Dv REG_NOSUB
378 was specified),
379 to hold the input offsets for
380 .Dv REG_STARTEND .
381 Use for output is still entirely controlled by
382 .Fa nmatch ;
383 if
384 .Fa nmatch
385 is 0 or
386 .Dv REG_NOSUB
387 was specified,
388 the value of
389 .Fa pmatch Ns [0]
390 will not be changed by a successful
391 .Fn regexec .
392 .Pp
393 .Fn Regerror
394 maps a non-zero
395 .Fa errcode
396 from either
397 .Fn regcomp
398 or
399 .Fn regexec
400 to a human-readable, printable message.
401 If
402 .Fa preg
403 is
404 .No non\- Ns Dv NULL ,
405 the error code should have arisen from use of
406 the
407 .Ft regex_t
408 pointed to by
409 .Fa preg ,
410 and if the error code came from
411 .Fn regcomp ,
412 it should have been the result from the most recent
413 .Fn regcomp
414 using that
415 .Ft regex_t .
416 .No ( Fn Regerror
417 may be able to supply a more detailed message using information
418 from the
419 .Ft regex_t . )
420 .Fn Regerror
421 places the NUL-terminated message into the buffer pointed to by
422 .Fa errbuf ,
423 limiting the length (including the NUL) to at most
424 .Fa errbuf_size
425 bytes.
426 If the whole message won't fit,
427 as much of it as will fit before the terminating NUL is supplied.
428 In any case,
429 the returned value is the size of buffer needed to hold the whole
430 message (including terminating NUL).
431 If
432 .Fa errbuf_size
433 is 0,
434 .Fa errbuf
435 is ignored but the return value is still correct.
436 .Pp
437 If the
438 .Fa errcode
439 given to
440 .Fn regerror
441 is first ORed with
442 .Dv REG_ITOA ,
443 the
444 .Dq message
445 that results is the printable name of the error code,
446 e.g.\&
447 .Dq Dv REG_NOMATCH ,
448 rather than an explanation thereof.
449 If
450 .Fa errcode
451 is
452 .Dv REG_ATOI ,
453 then
454 .Fa preg
455 shall be
456 .No non\- Ns Dv NULL
457 and the
458 .Va re_endp
459 member of the structure it points to
460 must point to the printable name of an error code;
461 in this case, the result in
462 .Fa errbuf
463 is the decimal digits of
464 the numeric value of the error code
465 (0 if the name is not recognized).
466 .Dv REG_ITOA
467 and
468 .Dv REG_ATOI
469 are intended primarily as debugging facilities;
470 they are extensions,
471 compatible with but not specified by
472 .St -p1003.2 ,
473 and should be used with
474 caution in software intended to be portable to other systems.
475 Be warned also that they are considered experimental and changes are possible.
476 .Pp
477 .Fn Regfree
478 frees any dynamically-allocated storage associated with the compiled RE
479 pointed to by
480 .Fa preg .
481 The remaining
482 .Ft regex_t
483 is no longer a valid compiled RE
484 and the effect of supplying it to
485 .Fn regexec
486 or
487 .Fn regerror
488 is undefined.
489 .Pp
490 None of these functions references global variables except for tables
491 of constants;
492 all are safe for use from multiple threads if the arguments are safe.
493 .Sh IMPLEMENTATION CHOICES
494 There are a number of decisions that
495 .St -p1003.2
496 leaves up to the implementor,
497 either by explicitly saying
498 .Dq undefined
499 or by virtue of them being
500 forbidden by the RE grammar.
501 This implementation treats them as follows.
502 .Pp
503 See
504 .Xr re_format 7
505 for a discussion of the definition of case-independent matching.
506 .Pp
507 There is no particular limit on the length of REs,
508 except insofar as memory is limited.
509 Memory usage is approximately linear in RE size, and largely insensitive
510 to RE complexity, except for bounded repetitions.
511 See
512 .Sx BUGS
513 for one short RE using them
514 that will run almost any system out of memory.
515 .Pp
516 A backslashed character other than one specifically given a magic meaning
517 by
518 .St -p1003.2
519 (such magic meanings occur only in obsolete
520 .Bq Dq basic
521 REs)
522 is taken as an ordinary character.
523 .Pp
524 Any unmatched
525 .Ql [\&
526 is a
527 .Dv REG_EBRACK
528 error.
529 .Pp
530 Equivalence classes cannot begin or end bracket-expression ranges.
531 The endpoint of one range cannot begin another.
532 .Pp
533 .Dv RE_DUP_MAX ,
534 the limit on repetition counts in bounded repetitions, is 255.
535 .Pp
536 A repetition operator
537 .Ql ( ?\& ,
538 .Ql *\& ,
539 .Ql +\& ,
540 or bounds)
541 cannot follow another
542 repetition operator.
543 A repetition operator cannot begin an expression or subexpression
544 or follow
545 .Ql ^\&
546 or
547 .Ql |\& .
548 .Pp
549 .Ql |\&
550 cannot appear first or last in a (sub)expression or after another
551 .Ql |\& ,
552 i.e. an operand of
553 .Ql |\&
554 cannot be an empty subexpression.
555 An empty parenthesized subexpression,
556 .Ql "()" ,
557 is legal and matches an
558 empty (sub)string.
559 An empty string is not a legal RE.
560 .Pp
561 A
562 .Ql {\&
563 followed by a digit is considered the beginning of bounds for a
564 bounded repetition, which must then follow the syntax for bounds.
565 A
566 .Ql {\&
567 .Em not
568 followed by a digit is considered an ordinary character.
569 .Pp
570 .Ql ^\&
571 and
572 .Ql $\&
573 beginning and ending subexpressions in obsolete
574 .Pq Dq basic
575 REs are anchors, not ordinary characters.
576 .Sh SEE ALSO
577 .Xr grep 1 ,
578 .Xr re_format 7
579 .Pp
580 .St -p1003.2 ,
581 sections 2.8 (Regular Expression Notation)
582 and
583 B.5 (C Binding for Regular Expression Matching).
584 .Sh DIAGNOSTICS
585 Non-zero error codes from
586 .Fn regcomp
587 and
588 .Fn regexec
589 include the following:
590 .Pp
591 .Bl -tag -width REG_ECOLLATE -compact
592 .It Dv REG_NOMATCH
593 .Fn regexec
594 failed to match
595 .It Dv REG_BADPAT
596 invalid regular expression
597 .It Dv REG_ECOLLATE
598 invalid collating element
599 .It Dv REG_ECTYPE
600 invalid character class
601 .It Dv REG_EESCAPE
602 .Ql \e
603 applied to unescapable character
604 .It Dv REG_ESUBREG
605 invalid backreference number
606 .It Dv REG_EBRACK
607 brackets
608 .Ql "[ ]"
609 not balanced
610 .It Dv REG_EPAREN
611 parentheses
612 .Ql "( )"
613 not balanced
614 .It Dv REG_EBRACE
615 braces
616 .Ql "{ }"
617 not balanced
618 .It Dv REG_BADBR
619 invalid repetition count(s) in
620 .Ql "{ }"
621 .It Dv REG_ERANGE
622 invalid character range in
623 .Ql "[ ]"
624 .It Dv REG_ESPACE
625 ran out of memory
626 .It Dv REG_BADRPT
627 .Ql ?\& ,
628 .Ql *\& ,
629 or
630 .Ql +\&
631 operand invalid
632 .It Dv REG_EMPTY
633 empty (sub)expression
634 .It Dv REG_ASSERT
635 can't happen - you found a bug
636 .It Dv REG_INVARG
637 invalid argument, e.g. negative-length string
638 .El
639 .Sh HISTORY
640 Originally written by
641 .An Henry Spencer .
642 Altered for inclusion in the
643 .Bx 4.4
644 distribution.
645 .Sh BUGS
646 This is an alpha release with known defects.
647 Please report problems.
648 .Pp
649 The back-reference code is subtle and doubts linger about its correctness
650 in complex cases.
651 .Pp
652 .Fn Regexec
653 performance is poor.
654 This will improve with later releases.
655 .Fa Nmatch
656 exceeding 0 is expensive;
657 .Fa nmatch
658 exceeding 1 is worse.
659 .Fn Regexec
660 is largely insensitive to RE complexity
661 .Em except
662 that back
663 references are massively expensive.
664 RE length does matter; in particular, there is a strong speed bonus
665 for keeping RE length under about 30 characters,
666 with most special characters counting roughly double.
667 .Pp
668 .Fn Regcomp
669 implements bounded repetitions by macro expansion,
670 which is costly in time and space if counts are large
671 or bounded repetitions are nested.
672 An RE like, say,
673 .Ql "((((a{1,100}){1,100}){1,100}){1,100}){1,100}"
674 will (eventually) run almost any existing machine out of swap space.
675 .Pp
676 There are suspected problems with response to obscure error conditions.
677 Notably,
678 certain kinds of internal overflow,
679 produced only by truly enormous REs or by multiply nested bounded repetitions,
680 are probably not handled well.
681 .Pp
682 Due to a mistake in
683 .St -p1003.2 ,
684 things like
685 .Ql "a)b"
686 are legal REs because
687 .Ql )\&
688 is
689 a special character only in the presence of a previous unmatched
690 .Ql (\& .
691 This can't be fixed until the spec is fixed.
692 .Pp
693 The standard's definition of back references is vague.
694 For example, does
695 .Ql "a\e(\e(b\e)*\e2\e)*d"
696 match
697 .Ql "abbbd" ?
698 Until the standard is clarified,
699 behavior in such cases should not be relied on.
700 .Pp
701 The implementation of word-boundary matching is a bit of a kludge,
702 and bugs may lurk in combinations of word-boundary matching and anchoring.