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