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