lib/libc/tre-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. 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 .\"
  35 .Dd May 5, 2019
  36 .Dt REGEX 3
  37 .Os
  38 .Sh NAME
  39 .Nm regcomp ,
  40 .Nm regcomp_l ,
  41 .Nm regerror ,
  42 .Nm regexec ,
  43 .Nm regfree ,
  44 .Nm regncomp ,
  45 .Nm regncomp_l ,
  46 .Nm regnexec ,
  47 .Nm regwcomp ,
  48 .Nm regwcomp_l ,
  49 .Nm regwexec ,
  50 .Nm regwncomp ,
  51 .Nm regwncomp_l ,
  52 .Nm regwnexec
  53 .Nd regular-expression library
  54 .Sh LIBRARY
  55 .Lb libc
  56 .Sh SYNOPSIS
  57 .Sy (Standards-compliant APIs)
  58 .Pp
  59 .In regex.h
  60 .Ft int
  61 .Fo regcomp
  62 .Fa "regex_t *restrict preg"
  63 .Fa "const char *restrict pattern"
  64 .Fa "int cflags"
  65 .Fc
  66 .Ft size_t
  67 .Fo regerror
  68 .Fa "int errcode"
  69 .Fa "const regex_t *restrict preg"
  70 .Fa "char *restrict errbuf"
  71 .Fa "size_t errbuf_size"
  72 .Fc
  73 .Ft int
  74 .Fo regexec
  75 .Fa "const regex_t *restrict preg"
  76 .Fa "const char *restrict string"
  77 .Fa "size_t nmatch"
  78 .Fa "regmatch_t pmatch[restrict]"
  79 .Fa "int eflags"
  80 .Fc
  81 .Ft void
  82 .Fo regfree
  83 .Fa "regex_t *preg"
  84 .Fc
  85 .Pp
  86 .Sy (Non-portable extensions)
  87 .Ft int
  88 .Fo regncomp
  89 .Fa "regex_t *restrict preg"
  90 .Fa "const char *restrict pattern"
  91 .Fa "size_t len"
  92 .Fa "int cflags"
  93 .Fc
  94 .Ft int
  95 .Fo regnexec
  96 .Fa "const regex_t *restrict preg"
  97 .Fa "const char *restrict string"
  98 .Fa "size_t len"
  99 .Fa "size_t nmatch"
 100 .Fa "regmatch_t pmatch[restrict]"
 101 .Fa "int eflags"
 102 .Fc
 103 .Ft int
 104 .Fo regwcomp
 105 .Fa "regex_t *restrict preg"
 106 .Fa "const wchar_t *restrict widepat"
 107 .Fa "int cflags"
 108 .Fc
 109 .Ft int
 110 .Fo regwexec
 111 .Fa "const regex_t *restrict preg"
 112 .Fa "const wchar_t *restrict widestr"
 113 .Fa "size_t nmatch"
 114 .Fa "regmatch_t pmatch[restrict]"
 115 .Fa "int eflags"
 116 .Fc
 117 .Ft int
 118 .Fo regwncomp
 119 .Fa "regex_t *restrict preg"
 120 .Fa "const wchar_t *restrict widepat"
 121 .Fa "size_t len"
 122 .Fa "int cflags"
 123 .Fc
 124 .Ft int
 125 .Fo regwnexec
 126 .Fa "const regex_t *restrict preg"
 127 .Fa "const wchar_t *restrict widestr"
 128 .Fa "size_t len"
 129 .Fa "size_t nmatch"
 130 .Fa "regmatch_t pmatch[restrict]"
 131 .Fa "int eflags"
 132 .Fc
 133 .In regex.h
 134 .In xlocale.h
 135 .Ft int
 136 .Fo regcomp_l
 137 .Fa "regex_t *restrict preg"
 138 .Fa "const char *restrict pattern"
 139 .Fa "int cflags"
 140 .Fa "locale_t restrict"
 141 .Fc
 142 .Ft int
 143 .Fo regncomp_l
 144 .Fa "regex_t *restrict preg"
 145 .Fa "const char *restrict pattern"
 146 .Fa "size_t len"
 147 .Fa "int cflags"
 148 .Fa "locale_t restrict"
 149 .Fc
 150 .Ft int
 151 .Fo regwcomp_l
 152 .Fa "regex_t *restrict preg"
 153 .Fa "const wchar_t *restrict widepat"
 154 .Fa "int cflags"
 155 .Fa "locale_t restrict"
 156 .Fc
 157 .Ft int
 158 .Fo regwncomp_l
 159 .Fa "regex_t *restrict preg"
 160 .Fa "const wchar_t *restrict widepat"
 161 .Fa "size_t len"
 162 .Fa "int cflags"
 163 .Fa "locale_t restrict"
 164 .Fc
 165 .Sh DESCRIPTION
 166 These routines implement
 167 .St -p1003.2
 168 regular expressions
 169 .Pq Do RE Dc Ns s ;
 170 see
 171 .Xr re_format 7 .
 172 The
 173 .Fn regcomp
 174 function
 175 compiles an RE, written as a string, into an internal form.
 176 .Fn regexec
 177 matches that internal form against a string and reports results.
 178 .Fn regerror
 179 transforms error codes from either into human-readable messages.
 180 .Fn regfree
 181 frees any dynamically-allocated storage used by the internal form
 182 of an RE.
 183 .Pp
 184 The header
 185 .In regex.h
 186 declares two structure types,
 187 .Ft regex_t
 188 and
 189 .Ft regmatch_t ,
 190 the former for compiled internal forms and the latter for match reporting.
 191 It also declares the four functions,
 192 a type
 193 .Ft regoff_t ,
 194 and a number of constants with names starting with
 195 .Dq Dv REG_ .
 196 .Pp
 197 The
 198 .Fn regcomp
 199 function
 200 compiles the regular expression contained in the
 201 .Fa pattern
 202 string,
 203 subject to the flags in
 204 .Fa cflags ,
 205 and places the results in the
 206 .Ft regex_t
 207 structure pointed to by
 208 .Fa preg .
 209 The
 210 .Fa cflags
 211 argument
 212 is the bitwise OR of zero or more of the following flags:
 213 .Bl -tag -width REG_EXTENDED
 214 .It Dv REG_EXTENDED
 215 Compile modern
 216 .Pq Dq extended
 217 REs,
 218 rather than the obsolete
 219 .Pq Dq basic
 220 REs that
 221 are the default.
 222 .It Dv REG_BASIC
 223 This is a synonym for 0,
 224 provided as a counterpart to
 225 .Dv REG_EXTENDED
 226 to improve readability.
 227 .It Dv REG_NOSPEC
 228 Compile with recognition of all special characters turned off.
 229 All characters are thus considered ordinary,
 230 so the
 231 .Dq RE
 232 is a literal string.
 233 This is an extension,
 234 compatible with but not specified by
 235 .St -p1003.2 ,
 236 and should be used with
 237 caution in software intended to be portable to other systems.
 238 .Dv REG_EXTENDED
 239 and
 240 .Dv REG_NOSPEC
 241 may not be used
 242 in the same call to
 243 .Fn regcomp .
 244 .It Dv REG_LITERAL
 245 An alias of
 246 .Dv REG_NOSPEC .
 247 .It Dv REG_ICASE
 248 Compile for matching that ignores upper/lower case distinctions.
 249 See
 250 .Xr re_format 7 .
 251 .It Dv REG_NOSUB
 252 Compile for matching that need only report success or failure,
 253 not what was matched.
 254 .It Dv REG_NEWLINE
 255 Compile for newline-sensitive matching.
 256 By default, newline is a completely ordinary character with no special
 257 meaning in either REs or strings.
 258 With this flag,
 259 .Ql [^
 260 bracket expressions and
 261 .Ql .\&
 262 never match newline,
 263 a
 264 .Ql ^\&
 265 anchor matches the null string after any newline in the string
 266 in addition to its normal function,
 267 and the
 268 .Ql $\&
 269 anchor matches the null string before any newline in the
 270 string in addition to its normal function.
 271 .It Dv REG_PEND
 272 (Note that
 273 .Dv REG_PEND
 274 is not recognized by any of the wide character or
 275 .Dq Nm n
 276 variants.
 277 Besides, the
 278 .Dq Nm n
 279 variants can be used instead of
 280 .Dv REG_PEND ;
 281 see EXTENDED APIS below.)
 282 The regular expression ends,
 283 not at the first NUL,
 284 but just before the character pointed to by the
 285 .Va re_endp
 286 member of the structure pointed to by
 287 .Fa preg .
 288 The
 289 .Va re_endp
 290 member is of type
 291 .Ft "const char *" .
 292 This flag permits inclusion of NULs in the RE;
 293 they are considered ordinary characters.
 294 This is an extension,
 295 compatible with but not specified by
 296 .St -p1003.2 ,
 297 and should be used with
 298 caution in software intended to be portable to other systems.
 299 .It Dv REG_ENHANCED
 300 Recognized enhanced regular expression features; see
 301 .Xr re_format 7
 302 for details.
 303 This is an extension not specified by
 304 .St -p1003.2 ,
 305 and should be used with
 306 caution in software intended to be portable to other systems.
 307 .It Dv REG_MINIMAL
 308 Use minimal (non-greedy) repetitions instead of the normal greedy ones; see
 309 .Xr re_format 7
 310 for details.
 311 (This only applies when both
 312 .Dv REG_ENHANCED
 313 and
 314 .Dv REG_EXTENDED
 315 are also set.)
 316 This is an extension not specified by
 317 .St -p1003.2 ,
 318 and should be used with
 319 caution in software intended to be portable to other systems.
 320 .It Dv REG_UNGREEDY
 321 Alias of
 322 .Dv REG_MINIMAL .
 323 .El
 324 .Pp
 325 When successful,
 326 .Fn regcomp
 327 returns 0 and fills in the structure pointed to by
 328 .Fa preg .
 329 One member of that structure
 330 (other than
 331 .Va re_endp )
 332 is publicized:
 333 .Va re_nsub ,
 334 of type
 335 .Ft size_t ,
 336 contains the number of parenthesized subexpressions within the RE
 337 (except that the value of this member is undefined if the
 338 .Dv REG_NOSUB
 339 flag was used).
 340 If
 341 .Fn regcomp
 342 fails, it returns a non-zero error code;
 343 see
 344 .Sx RETURN VALUES .
 345 .Pp
 346 The
 347 .Fn regexec
 348 function
 349 matches the compiled RE pointed to by
 350 .Fa preg
 351 against the
 352 .Fa string ,
 353 subject to the flags in
 354 .Fa eflags ,
 355 and reports results using
 356 .Fa nmatch ,
 357 .Fa pmatch ,
 358 and the returned value.
 359 The RE must have been compiled by a previous invocation of
 360 .Fn regcomp .
 361 The compiled form is not altered during execution of
 362 .Fn regexec ,
 363 so a single compiled RE can be used simultaneously by multiple threads.
 364 .Pp
 365 By default,
 366 the NUL-terminated string pointed to by
 367 .Fa string
 368 is considered to be the text of an entire line, minus any terminating
 369 newline.
 370 The
 371 .Fa eflags
 372 argument is the bitwise OR of zero or more of the following flags:
 373 .Bl -tag -width REG_STARTEND
 374 .It Dv REG_NOTBOL
 375 The first character of
 376 the string
 377 is not the beginning of a line, so the
 378 .Ql ^\&
 379 anchor should not match before it.
 380 This does not affect the behavior of newlines under
 381 .Dv REG_NEWLINE .
 382 .It Dv REG_NOTEOL
 383 The NUL terminating
 384 the string
 385 does not end a line, so the
 386 .Ql $\&
 387 anchor should not match before it.
 388 This does not affect the behavior of newlines under
 389 .Dv REG_NEWLINE .
 390 .It Dv REG_STARTEND
 391 The string is considered to start at
 392 .Fa string
 393 +
 394 .Fa pmatch Ns [0]. Ns Va rm_so
 395 and to have a terminating NUL located at
 396 .Fa string
 397 +
 398 .Fa pmatch Ns [0]. Ns Va rm_eo
 399 (there need not actually be a NUL at that location),
 400 regardless of the value of
 401 .Fa nmatch .
 402 See below for the definition of
 403 .Fa pmatch
 404 and
 405 .Fa nmatch .
 406 This is an extension,
 407 compatible with but not specified by
 408 .St -p1003.2 ,
 409 and should be used with
 410 caution in software intended to be portable to other systems.
 411 Note that a non-zero
 412 .Va rm_so
 413 does not imply
 414 .Dv REG_NOTBOL ;
 415 .Dv REG_STARTEND
 416 affects only the location of the string,
 417 not how it is matched.
 418 .El
 419 .Pp
 420 See
 421 .Xr re_format 7
 422 for a discussion of what is matched in situations where an RE or a
 423 portion thereof could match any of several substrings of
 424 .Fa string .
 425 .Pp
 426 Normally,
 427 .Fn regexec
 428 returns 0 for success and the non-zero code
 429 .Dv REG_NOMATCH
 430 for failure.
 431 Other non-zero error codes may be returned in exceptional situations;
 432 see
 433 .Sx RETURN VALUES .
 434 .Pp
 435 If
 436 .Dv REG_NOSUB
 437 was specified in the compilation of the RE,
 438 or if
 439 .Fa nmatch
 440 is 0,
 441 .Fn regexec
 442 ignores the
 443 .Fa pmatch
 444 argument (but see below for the case where
 445 .Dv REG_STARTEND
 446 is specified).
 447 Otherwise,
 448 .Fa pmatch
 449 points to an array of
 450 .Fa nmatch
 451 structures of type
 452 .Ft regmatch_t .
 453 Such a structure has at least the members
 454 .Va rm_so
 455 and
 456 .Va rm_eo ,
 457 both of type
 458 .Ft regoff_t
 459 (a signed arithmetic type at least as large as an
 460 .Ft off_t
 461 and a
 462 .Ft ssize_t ) ,
 463 containing respectively the offset of the first character of a substring
 464 and the offset of the first character after the end of the substring.
 465 Offsets are measured from the beginning of the
 466 .Fa string
 467 argument given to
 468 .Fn regexec .
 469 An empty substring is denoted by equal offsets,
 470 both indicating the character following the empty substring.
 471 .Pp
 472 The 0th member of the
 473 .Fa pmatch
 474 array is filled in to indicate what substring of
 475 .Fa string
 476 was matched by the entire RE.
 477 Remaining members report what substring was matched by parenthesized
 478 subexpressions within the RE;
 479 member
 480 .Va i
 481 reports subexpression
 482 .Va i ,
 483 with subexpressions counted (starting at 1) by the order of their opening
 484 parentheses in the RE, left to right.
 485 Unused entries in the array (corresponding either to subexpressions that
 486 did not participate in the match at all, or to subexpressions that do not
 487 exist in the RE (that is,
 488 .Va i
 489 >
 490 .Fa preg Ns -> Ns Va re_nsub ) )
 491 have both
 492 .Va rm_so
 493 and
 494 .Va rm_eo
 495 set to -1.
 496 If a subexpression participated in the match several times,
 497 the reported substring is the last one it matched.
 498 (Note, as an example in particular, that when the RE
 499 .Ql "(b*)+"
 500 matches
 501 .Ql bbb ,
 502 the parenthesized subexpression matches each of the three
 503 .So Li b Sc Ns s
 504 and then
 505 an infinite number of empty strings following the last
 506 .Ql b ,
 507 so the reported substring is one of the empties.)
 508 .Pp
 509 If
 510 .Dv REG_STARTEND
 511 is specified,
 512 .Fa pmatch
 513 must point to at least one
 514 .Ft regmatch_t
 515 (even if
 516 .Fa nmatch
 517 is 0 or
 518 .Dv REG_NOSUB
 519 was specified),
 520 to hold the input offsets for
 521 .Dv REG_STARTEND .
 522 Use for output is still entirely controlled by
 523 .Fa nmatch ;
 524 if
 525 .Fa nmatch
 526 is 0 or
 527 .Dv REG_NOSUB
 528 was specified,
 529 the value of
 530 .Fa pmatch Ns [0]
 531 will not be changed by a successful
 532 .Fn regexec .
 533 .Pp
 534 The
 535 .Fn regerror
 536 function
 537 maps a non-zero
 538 .Fa errcode
 539 from either
 540 .Fn regcomp
 541 or
 542 .Fn regexec
 543 to a human-readable, printable message.
 544 If
 545 .Fa preg
 546 is
 547 .No non\- Ns Dv NULL ,
 548 the error code should have arisen from use of
 549 the
 550 .Ft regex_t
 551 pointed to by
 552 .Fa preg ,
 553 and if the error code came from
 554 .Fn regcomp ,
 555 it should have been the result from the most recent
 556 .Fn regcomp
 557 using that
 558 .Ft regex_t .
 559 The
 560 .Fn ( regerror
 561 may be able to supply a more detailed message using information
 562 from the
 563 .Ft regex_t . )
 564 The
 565 .Fn regerror
 566 function
 567 places the NUL-terminated message into the buffer pointed to by
 568 .Fa errbuf ,
 569 limiting the length (including the NUL) to at most
 570 .Fa errbuf_size
 571 bytes.
 572 If the whole message will not fit,
 573 as much of it as will fit before the terminating NUL is supplied.
 574 In any case,
 575 the returned value is the size of buffer needed to hold the whole
 576 message (including terminating NUL).
 577 If
 578 .Fa errbuf_size
 579 is 0,
 580 .Fa errbuf
 581 is ignored but the return value is still correct.
 582 .Pp
 583 If the
 584 .Fa errcode
 585 given to
 586 .Fn regerror
 587 is first ORed with
 588 .Dv REG_ITOA ,
 589 the
 590 .Dq message
 591 that results is the printable name of the error code,
 592 e.g.\&
 593 .Dq Dv REG_NOMATCH ,
 594 rather than an explanation thereof.
 595 If
 596 .Fa errcode
 597 is
 598 .Dv REG_ATOI ,
 599 then
 600 .Fa preg
 601 shall be
 602 .No non\- Ns Dv NULL
 603 and the
 604 .Va re_endp
 605 member of the structure it points to
 606 must point to the printable name of an error code;
 607 in this case, the result in
 608 .Fa errbuf
 609 is the decimal digits of
 610 the numeric value of the error code
 611 (0 if the name is not recognized).
 612 .Dv REG_ITOA
 613 and
 614 .Dv REG_ATOI
 615 are intended primarily as debugging facilities;
 616 they are extensions,
 617 compatible with but not specified by
 618 .St -p1003.2 ,
 619 and should be used with
 620 caution in software intended to be portable to other systems.
 621 Be warned also that they are considered experimental and changes are possible.
 622 .Pp
 623 The
 624 .Fn regfree
 625 function
 626 frees any dynamically-allocated storage associated with the compiled RE
 627 pointed to by
 628 .Fa preg .
 629 The remaining
 630 .Ft regex_t
 631 is no longer a valid compiled RE
 632 and the effect of supplying it to
 633 .Fn regexec
 634 or
 635 .Fn regerror
 636 is undefined.
 637 .Pp
 638 None of these functions references global variables except for tables
 639 of constants;
 640 all are safe for use from multiple threads if the arguments are safe.
 641 .Sh EXTENDED APIS
 642 These extended APIs are available in Mac OS X 10.8 and beyond, when the
 643 deployment target is 10.8 or later.
 644 It should also be noted that any of the
 645 .Fn regcomp
 646 variants may be used to initialize a
 647 .Ft regex_t
 648 structure, that can then be passed to any of the
 649 .Fn regexec
 650 variants.
 651 So it is quite legal to compile a wide character RE and use it to match a
 652 multibyte character string, or vice versa.
 653 .Pp
 654 The
 655 .Fn regncomp
 656 routine compiles regular expressions like
 657 .Fn regcomp ,
 658 but the length of the regular expression string is specified, allowing a string
 659 that is not NUL terminated and/or contains NUL characters.
 660 This is a modern replacement for using
 661 .Fn regcomp
 662 with the
 663 .Dv REG_PEND
 664 option.
 665 .Pp
 666 Similarly, the
 667 .Fn regnexec
 668 routine is like
 669 .Fn regexec ,
 670 but the length of the string to match is specified, allowing a string
 671 that is not NUL terminated and/or contains NUL characters.
 672 .Pp
 673 The
 674 .Fn regwcomp
 675 and
 676 .Fn regwexec
 677 variants take a wide-character
 678 .Vt ( wchar_t )
 679 string for the regular expression and string to match.
 680 And
 681 .Fn regwncomp
 682 and
 683 .Fn regwnexec
 684 are variants that allow specifying the wide character string length, and
 685 so allows wide character strings that are not NUL terminated and/or
 686 contains NUL characters.
 687 .Sh INTERACTION WITH THE LOCALE
 688 When
 689 .Fn regcomp
 690 or one of its variants is run, the regular expression is compiled into an
 691 internal form, which may include specific information about the locale currently
 692 in effect, such as equivalence classes or multi-character collation symbols.
 693 So a reference to the current locale is also stored with the internal form,
 694 so that when
 695 .Fn regexec
 696 is run, it can use the same locale (even if the locale is changed in-between
 697 the calls to
 698 .Fn regcomp
 699 and
 700 .Fn regexec ) .
 701 .Pp
 702 To provide more direct control over which locale is used,
 703 routines with
 704 .Dq Nm _l
 705 appended to their names are provided that work just like the variants
 706 without the
 707 .Dq Nm _l ,
 708 except that a locale (via a
 709 .Vt locale_t
 710 variable type) is specified directly.
 711 Note that only variants of
 712 .Fn regcomp
 713 have
 714 .Dq Nm _l
 715 variants, since the
 716 .Fn regexec
 717 variants just use the reference to the locale stored in the internal form.
 718 .Sh IMPLEMENTATION CHOICES
 719 The
 720 .Nm regex
 721 implementation in Mac OS X 10.8 and later is based on a heavily modified subset
 722 of TRE (http://laurikari.net/tre/).
 723 This provides improved performance, better conformance and additional features.
 724 However, both API and binary compatibility have been maintained with previous
 725 releases, so binaries
 726 built on previous releases should work on 10.8 and later, and binaries built on
 727 10.8 and later should be able to run on previous releases (as long as none of
 728 the new variants or new features are used.
 729 .Pp
 730 There are a number of decisions that
 731 .St -p1003.2
 732 leaves up to the implementor,
 733 either by explicitly saying
 734 .Dq undefined
 735 or by virtue of them being
 736 forbidden by the RE grammar.
 737 This implementation treats them as follows.
 738 .Pp
 739 See
 740 .Xr re_format 7
 741 for a discussion of the definition of case-independent matching.
 742 .Pp
 743 There is no particular limit on the length of REs,
 744 except insofar as memory is limited.
 745 Memory usage is approximately linear in RE size, and largely insensitive
 746 to RE complexity, except for bounded repetitions.
 747 See
 748 .Sx BUGS
 749 for one short RE using them
 750 that will run almost any system out of memory.
 751 .Pp
 752 A backslashed character other than one specifically given a magic meaning
 753 by
 754 .St -p1003.2
 755 (such magic meanings occur only in obsolete
 756 .Bq Dq basic
 757 REs)
 758 is taken as an ordinary character.
 759 .Pp
 760 Any unmatched
 761 .Ql [\&
 762 is a
 763 .Dv REG_EBRACK
 764 error.
 765 .Pp
 766 Equivalence classes cannot begin or end bracket-expression ranges.
 767 The endpoint of one range cannot begin another.
 768 .Pp
 769 .Dv RE_DUP_MAX ,
 770 the limit on repetition counts in bounded repetitions, is 255.
 771 .Pp
 772 A repetition operator
 773 .Ql ( ?\& ,
 774 .Ql *\& ,
 775 .Ql +\& ,
 776 or bounds)
 777 cannot follow another
 778 repetition operator, except for the use of
 779 .Ql ?\&
 780 for minimal repetition (for enhanced extended REs; see
 781 .Xr re_format 7
 782 for details).
 783 A repetition operator cannot begin an expression or subexpression
 784 or follow
 785 .Ql ^\&
 786 or
 787 .Ql |\& .
 788 .Pp
 789 .Ql |\&
 790 cannot appear first or last in a (sub)expression or after another
 791 .Ql |\& ,
 792 i.e., an operand of
 793 .Ql |\&
 794 cannot be an empty subexpression.
 795 An empty parenthesized subexpression,
 796 .Ql "()" ,
 797 is legal and matches an
 798 empty (sub)string.
 799 An empty string is not a legal RE.
 800 .Pp
 801 A
 802 .Ql {\&
 803 followed by a digit is considered the beginning of bounds for a
 804 bounded repetition, which must then follow the syntax for bounds.
 805 A
 806 .Ql {\&
 807 .Em not
 808 followed by a digit is considered an ordinary character.
 809 .Pp
 810 .Ql ^\&
 811 and
 812 .Ql $\&
 813 beginning and ending subexpressions in obsolete
 814 .Pq Dq basic
 815 REs are anchors, not ordinary characters.
 816 .Sh RETURN VALUES
 817 Non-zero error codes from
 818 .Fn regcomp
 819 and
 820 .Fn regexec
 821 include the following:
 822 .Pp
 823 .Bl -tag -width REG_ECOLLATE -compact
 824 .It Dv REG_NOMATCH
 825 The
 826 .Fn regexec
 827 function
 828 failed to match
 829 .It Dv REG_BADPAT
 830 invalid regular expression
 831 .It Dv REG_ECOLLATE
 832 invalid collating element
 833 .It Dv REG_ECTYPE
 834 invalid character class
 835 .It Dv REG_EESCAPE
 836 .Ql \e
 837 applied to unescapable character
 838 .It Dv REG_ESUBREG
 839 invalid backreference number
 840 .It Dv REG_EBRACK
 841 brackets
 842 .Ql "[ ]"
 843 not balanced
 844 .It Dv REG_EPAREN
 845 parentheses
 846 .Ql "( )"
 847 not balanced
 848 .It Dv REG_EBRACE
 849 braces
 850 .Ql "{ }"
 851 not balanced
 852 .It Dv REG_BADBR
 853 invalid repetition count(s) in
 854 .Ql "{ }"
 855 .It Dv REG_ERANGE
 856 invalid character range in
 857 .Ql "[ ]"
 858 .It Dv REG_ESPACE
 859 ran out of memory
 860 .It Dv REG_BADRPT
 861 .Ql ?\& ,
 862 .Ql *\& ,
 863 or
 864 .Ql +\&
 865 operand invalid
 866 .It Dv REG_EMPTY
 867 empty (sub)expression
 868 .It Dv REG_ASSERT
 869 cannot happen - you found a bug
 870 .It Dv REG_INVARG
 871 invalid argument, e.g.\& negative-length string
 872 .It Dv REG_ILLSEQ
 873 illegal byte sequence (bad multibyte character)
 874 .El
 875 .Sh SEE ALSO
 876 .Xr grep 1 ,
 877 .Xr re_format 7
 878 .Pp
 879 .St -p1003.2 ,
 880 sections 2.8 (Regular Expression Notation)
 881 and
 882 B.5 (C Binding for Regular Expression Matching).
 883 .Sh HISTORY
 884 The
 885 .Nm regex
 886 implementation is based on a heavily modified subset of TRE
 887 (http://laurikari.net/tre/), originally written by Ville Laurikari.
 888 Previous releases used an implementation originally written by
 889 .An Henry Spencer ,
 890 and altered for inclusion in the
 891 .Bx 4.4
 892 distribution.
 893 .Sh BUGS
 894 The beginning-of-line and end-of-line anchors (
 895 .Dq ^\&
 896 and
 897 .Dq $\& )
 898 are currently implemented so that repetitions can not be applied to them.
 899 The standards are unclear about whether this is legal, but other
 900 .Nm regex
 901 packages do support this case.
 902 It is best to avoid this non-portable (and not really very useful) case.
 903 .Pp
 904 The back-reference code is subtle and doubts linger about its correctness
 905 in complex cases.
 906 .Pp
 907 The
 908 .Fn regexec
 909 variants use one of two internal matching engines.
 910 The normal one is linear worst-case time in the length of the text being
 911 searched, and quadratic worst-case time in the length of the used regular
 912 expression.
 913 When back-references are used, a slower, backtracking engine is used.
 914 While all backtracking matching engines suffer from extreme slowness for certain
 915 pathological cases, the normal engines doesn't suffer from these cases.
 916 It is advised to avoid back-references whenever possible.
 917 .Pp
 918 The
 919 .Fn regcomp
 920 variants
 921 implements bounded repetitions by macro expansion,
 922 which is costly in time and space if counts are large
 923 or bounded repetitions are nested.
 924 An RE like, say,
 925 .Ql "((((a{1,100}){1,100}){1,100}){1,100}){1,100}"
 926 will (eventually) run almost any existing machine out of swap space.
 927 .Pp
 928 Due to a mistake in
 929 .St -p1003.2 ,
 930 things like
 931 .Ql "a)b"
 932 are legal REs because
 933 .Ql )\&
 934 is
 935 a special character only in the presence of a previous unmatched
 936 .Ql (\& .
 937 This cannot be fixed until the spec is fixed.
 938 .Pp
 939 The standard's definition of back references is vague.
 940 For example, does
 941 .Ql "a\e(\e(b\e)*\e2\e)*d"
 942 match
 943 .Ql "abbbd" ?
 944 Until the standard is clarified,
 945 behavior in such cases should not be relied on.