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