usr/src/lib/libast/common/regex/reglib.h

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
   5 *                      and is licensed under the                       *
   6 *                  Common Public License, Version 1.0                  *
   7 *                    by AT&T Intellectual Property                     *
   8 *                                                                      *
   9 *                A copy of the License is available at                 *
  10 *            http://www.opensource.org/licenses/cpl1.0.txt             *
  11 *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
  12 *                                                                      *
  13 *              Information and Software Systems Research               *
  14 *                            AT&T Research                             *
  15 *                           Florham Park NJ                            *
  16 *                                                                      *
  17 *                 Glenn Fowler <gsf@research.att.com>                  *
  18 *                  David Korn <dgk@research.att.com>                   *
  19 *                   Phong Vo <kpv@research.att.com>                    *
  20 *                                                                      *
  21 ***********************************************************************/
  22 #pragma prototyped
  23
  24 /*
  25  * posix regex implementation
  26  *
  27  * based on Doug McIlroy's C++ implementation
  28  * Knuth-Morris-Pratt adapted from Corman-Leiserson-Rivest
  29  * Boyer-Moore from conversations with David Korn, Phong Vo, Andrew Hume
  30  */
  31
  32 #ifndef _REGLIB_H
  33 #define _REGLIB_H
  34
  35 #define REG_VERSION_EXEC        20020509L
  36 #define REG_VERSION_MAP         20030916L       /* regdisc_t.re_map     */
  37
  38 #define re_info         env
  39
  40 #define alloc           _reg_alloc
  41 #define classfun        _reg_classfun
  42 #define drop            _reg_drop
  43 #define fatal           _reg_fatal
  44 #define state           _reg_state
  45
  46 typedef struct regsubop_s
  47 {
  48         int             op;             /* REG_SUB_LOWER,REG_SUB_UPPER  */
  49         int             off;            /* re_rhs or match[] offset     */
  50         int             len;            /* re_rhs len or len==0 match[] */
  51 } regsubop_t;
  52
  53 #define _REG_SUB_PRIVATE_ \
  54         char*           re_cur;         /* re_buf cursor                */ \
  55         char*           re_end;         /* re_buf end                   */ \
  56         regsubop_t*     re_ops;         /* rhs ops                      */ \
  57         char            re_rhs[1];      /* substitution rhs             */
  58
  59 #include <ast.h>
  60 #include <cdt.h>
  61 #include <stk.h>
  62
  63 #include "regex.h"
  64
  65 #include <ctype.h>
  66 #include <errno.h>
  67
  68 #if _BLD_DEBUG && !defined(_AST_REGEX_DEBUG)
  69 #define _AST_REGEX_DEBUG        1
  70 #endif
  71
  72 #define MBSIZE(p)       ((ast.tmp_int=mbsize(p))>0?ast.tmp_int:1)
  73
  74 #undef  RE_DUP_MAX                      /* posix puts this in limits.h! */
  75 #define RE_DUP_MAX      (INT_MAX/2-1)   /* 2*RE_DUP_MAX won't overflow  */
  76 #define RE_DUP_INF      (RE_DUP_MAX+1)  /* infinity, for *              */
  77 #define BACK_REF_MAX    9
  78
  79 #define REG_COMP        (REG_DELIMITED|REG_ESCAPE|REG_EXTENDED|REG_FIRST|REG_ICASE|REG_NOSUB|REG_NEWLINE|REG_SHELL|REG_AUGMENTED|REG_LEFT|REG_LITERAL|REG_MINIMAL|REG_MULTIREF|REG_NULL|REG_RIGHT|REG_LENIENT|REG_MUSTDELIM)
  80 #define REG_EXEC        (REG_ADVANCE|REG_INVERT|REG_NOTBOL|REG_NOTEOL|REG_STARTEND)
  81
  82 #define REX_NULL                0       /* null string (internal)       */
  83 #define REX_ALT                 1       /* a|b                          */
  84 #define REX_ALT_CATCH           2       /* REX_ALT catcher              */
  85 #define REX_BACK                3       /* \1, \2, etc                  */
  86 #define REX_BEG                 4       /* initial ^                    */
  87 #define REX_BEG_STR             5       /* initial ^ w/ no newline      */
  88 #define REX_BM                  6       /* Boyer-Moore                  */
  89 #define REX_CAT                 7       /* catenation catcher           */
  90 #define REX_CLASS               8       /* [...]                        */
  91 #define REX_COLL_CLASS          9       /* collation order [...]        */
  92 #define REX_CONJ                10      /* a&b                          */
  93 #define REX_CONJ_LEFT           11      /* REX_CONJ left catcher        */
  94 #define REX_CONJ_RIGHT          12      /* REX_CONJ right catcher       */
  95 #define REX_DONE                13      /* completed match (internal)   */
  96 #define REX_DOT                 14      /* .                            */
  97 #define REX_END                 15      /* final $                      */
  98 #define REX_END_STR             16      /* final $ before tail newline  */
  99 #define REX_EXEC                17      /* call re.re_exec()            */
 100 #define REX_FIN_STR             18      /* final $ w/ no newline        */
 101 #define REX_GROUP               19      /* \(...\)                      */
 102 #define REX_GROUP_CATCH         20      /* REX_GROUP catcher            */
 103 #define REX_GROUP_AHEAD         21      /* 0-width lookahead            */
 104 #define REX_GROUP_AHEAD_CATCH   22      /* REX_GROUP_AHEAD catcher      */
 105 #define REX_GROUP_AHEAD_NOT     23      /* inverted 0-width lookahead   */
 106 #define REX_GROUP_BEHIND        24      /* 0-width lookbehind           */
 107 #define REX_GROUP_BEHIND_CATCH  25      /* REX_GROUP_BEHIND catcher     */
 108 #define REX_GROUP_BEHIND_NOT    26      /* inverted 0-width lookbehind  */
 109 #define REX_GROUP_BEHIND_NOT_CATCH 27   /* REX_GROUP_BEHIND_NOT catcher */
 110 #define REX_GROUP_COND          28      /* conditional group            */
 111 #define REX_GROUP_COND_CATCH    29      /* conditional group catcher    */
 112 #define REX_GROUP_CUT           30      /* don't backtrack over this    */
 113 #define REX_GROUP_CUT_CATCH     31      /* REX_GROUP_CUT catcher        */
 114 #define REX_KMP                 32      /* Knuth-Morris-Pratt           */
 115 #define REX_NEG                 33      /* negation                     */
 116 #define REX_NEG_CATCH           34      /* REX_NEG catcher              */
 117 #define REX_NEST                35      /* nested match                 */
 118 #define REX_ONECHAR             36      /* a single-character literal   */
 119 #define REX_REP                 37      /* Kleene closure               */
 120 #define REX_REP_CATCH           38      /* REX_REP catcher              */
 121 #define REX_STRING              39      /* some chars                   */
 122 #define REX_TRIE                40      /* alternation of strings       */
 123 #define REX_WBEG                41      /* \<                           */
 124 #define REX_WEND                42      /* \>                           */
 125 #define REX_WORD                43      /* word boundary                */
 126 #define REX_WORD_NOT            44      /* not word boundary            */
 127
 128 #define T_META          ((int)UCHAR_MAX+1)
 129 #define T_STAR          (T_META+0)
 130 #define T_PLUS          (T_META+1)
 131 #define T_QUES          (T_META+2)
 132 #define T_BANG          (T_META+3)
 133 #define T_AT            (T_META+4)
 134 #define T_TILDE         (T_META+5)
 135 #define T_PERCENT       (T_META+6)
 136 #define T_LEFT          (T_META+7)
 137 #define T_OPEN          (T_META+8)
 138 #define T_CLOSE         (T_OPEN+1)
 139 #define T_RIGHT         (T_OPEN+2)
 140 #define T_CFLX          (T_OPEN+3)
 141 #define T_DOT           (T_OPEN+4)
 142 #define T_DOTSTAR       (T_OPEN+5)
 143 #define T_END           (T_OPEN+6)
 144 #define T_BAD           (T_OPEN+7)
 145 #define T_DOLL          (T_OPEN+8)
 146 #define T_BRA           (T_OPEN+9)
 147 #define T_BAR           (T_OPEN+10)
 148 #define T_AND           (T_OPEN+11)
 149 #define T_LT            (T_OPEN+12)
 150 #define T_GT            (T_OPEN+13)
 151 #define T_SLASHPLUS     (T_OPEN+14)
 152 #define T_GROUP         (T_OPEN+15)
 153 #define T_WORD          (T_OPEN+16)
 154 #define T_WORD_NOT      (T_WORD+1)
 155 #define T_BEG_STR       (T_WORD+2)
 156 #define T_END_STR       (T_WORD+3)
 157 #define T_FIN_STR       (T_WORD+4)
 158 #define T_ESCAPE        (T_WORD+5)
 159 #define T_ALNUM         (T_WORD+6)
 160 #define T_ALNUM_NOT     (T_ALNUM+1)
 161 #define T_DIGIT         (T_ALNUM+2)
 162 #define T_DIGIT_NOT     (T_ALNUM+3)
 163 #define T_SPACE         (T_ALNUM+4)
 164 #define T_SPACE_NOT     (T_ALNUM+5)
 165 #define T_BACK          (T_ALNUM+6)
 166
 167 #define BRE             0
 168 #define ERE             3
 169 #define ARE             6
 170 #define SRE             9
 171 #define KRE             12
 172
 173 #define HIT             SSIZE_MAX
 174
 175 #define bitclr(p,c)     ((p)[((c)>>3)&037]&=(~(1<<((c)&07))))
 176 #define bitset(p,c)     ((p)[((c)>>3)&037]|=(1<<((c)&07)))
 177 #define bittst(p,c)     ((p)[((c)>>3)&037]&(1<<((c)&07)))
 178
 179 #define setadd(p,c)     bitset((p)->bits,c)
 180 #define setclr(p,c)     bitclr((p)->bits,c)
 181 #define settst(p,c)     bittst((p)->bits,c)
 182
 183 #if _hdr_wchar && _lib_wctype && _lib_iswctype
 184
 185 #include <stdio.h> /* because <wchar.h> includes it and we generate it */
 186 #include <wchar.h>
 187 #if _hdr_wctype
 188 #include <wctype.h>
 189 #endif
 190
 191 #if !defined(iswblank) && !_lib_iswblank
 192 #define _need_iswblank  1
 193 #define iswblank(x)     _reg_iswblank(x)
 194 extern int              _reg_iswblank(wint_t);
 195 #endif
 196
 197 #if !defined(towupper) && !_lib_towupper
 198 #define towupper(x)     toupper(x)
 199 #endif
 200
 201 #if !defined(towlower) && !_lib_towlower
 202 #define towlower(x)     tolower(x)
 203 #endif
 204
 205 #else
 206
 207 #undef  _lib_wctype
 208
 209 #ifndef iswalnum
 210 #define iswalnum(x)     isalnum(x)
 211 #endif
 212 #ifndef iswalpha
 213 #define iswalpha(x)     isalpha(x)
 214 #endif
 215 #ifndef iswcntrl
 216 #define iswcntrl(x)     iscntrl(x)
 217 #endif
 218 #ifndef iswdigit
 219 #define iswdigit(x)     isdigit(x)
 220 #endif
 221 #ifndef iswgraph
 222 #define iswgraph(x)     isgraph(x)
 223 #endif
 224 #ifndef iswlower
 225 #define iswlower(x)     islower(x)
 226 #endif
 227 #ifndef iswprint
 228 #define iswprint(x)     isprint(x)
 229 #endif
 230 #ifndef iswpunct
 231 #define iswpunct(x)     ispunct(x)
 232 #endif
 233 #ifndef iswspace
 234 #define iswspace(x)     isspace(x)
 235 #endif
 236 #ifndef iswupper
 237 #define iswupper(x)     isupper(x)
 238 #endif
 239 #ifndef iswxdigit
 240 #define iswxdigit(x)    isxdigit(x)
 241 #endif
 242
 243 #ifndef towlower
 244 #define towlower(x)     tolower(x)
 245 #endif
 246 #ifndef towupper
 247 #define towupper(x)     toupper(x)
 248 #endif
 249
 250 #endif
 251
 252 #ifndef iswblank
 253 #define iswblank(x)     ((x)==' '||(x)=='\t')
 254 #endif
 255
 256 #ifndef iswgraph
 257 #define iswgraph(x)     (iswprint(x)&&!iswblank(x))
 258 #endif
 259
 260 #define isword(x)       (isalnum(x)||(x)=='_')
 261
 262 /*
 263  * collation element support
 264  */
 265
 266 #define COLL_KEY_MAX    32
 267
 268 #if COLL_KEY_MAX < MB_LEN_MAX
 269 #undef  COLL_KEY_MAX
 270 #define COLL_KEY_MAX    MB_LEN_MAX
 271 #endif
 272
 273 typedef unsigned char Ckey_t[COLL_KEY_MAX+1];
 274
 275 #define COLL_end        0
 276 #define COLL_call       1
 277 #define COLL_char       2
 278 #define COLL_range      3
 279 #define COLL_range_lc   4
 280 #define COLL_range_uc   5
 281
 282 typedef struct Celt_s
 283 {
 284         short           typ;
 285         short           min;
 286         short           max;
 287         regclass_t      fun;
 288         Ckey_t          beg;
 289         Ckey_t          end;
 290 } Celt_t;
 291
 292 /*
 293  * private stuff hanging off regex_t
 294  */
 295
 296 typedef struct Stk_pos_s
 297 {
 298         off_t           offset;
 299         char*           base;
 300 } Stk_pos_t;
 301
 302 typedef struct Vector_s
 303 {
 304         Stk_t*          stk;            /* stack pointer                */
 305         char*           vec;            /* the data                     */
 306         int             inc;            /* growth increment             */
 307         int             siz;            /* element size                 */
 308         int             max;            /* max index                    */
 309         int             cur;            /* current index -- user domain */
 310 } Vector_t;
 311
 312 /*
 313  * Rex_t subtypes
 314  */
 315
 316 typedef struct Cond_s
 317 {
 318         unsigned char*  beg;            /* beginning of next match      */
 319         struct Rex_s*   next[2];        /* 0:no 1:yes next pattern      */
 320         struct Rex_s*   cont;           /* right catcher                */
 321         int             yes;            /* yes condition hit            */
 322 } Cond_t;
 323
 324 typedef struct Conj_left_s
 325 {
 326         unsigned char*  beg;            /* beginning of left match      */
 327         struct Rex_s*   right;          /* right pattern                */
 328         struct Rex_s*   cont;           /* right catcher                */
 329 } Conj_left_t;
 330
 331 typedef struct Conj_right_s
 332 {
 333         unsigned char*  end;            /* end of left match            */
 334         struct Rex_s*   cont;           /* ambient continuation         */
 335 } Conj_right_t;
 336
 337 typedef unsigned int Bm_mask_t;
 338
 339 typedef struct Bm_s
 340 {
 341         Bm_mask_t**     mask;
 342         size_t*         skip;
 343         size_t*         fail;
 344         size_t          size;
 345         ssize_t         back;
 346         ssize_t         left;
 347         ssize_t         right;
 348         size_t          complete;
 349 } Bm_t;
 350
 351 typedef struct String_s
 352 {
 353         int*            fail;
 354         unsigned char*  base;
 355         size_t          size;
 356 } String_t;
 357
 358 typedef struct Set_s
 359 {
 360         unsigned char   bits[(UCHAR_MAX+1)/CHAR_BIT];
 361 } Set_t;
 362
 363 typedef struct Collate_s
 364 {
 365         int             invert;
 366         Celt_t*         elements;
 367 } Collate_t;
 368
 369 typedef struct Binary_s
 370 {
 371         struct Rex_s*   left;
 372         struct Rex_s*   right;
 373         int             serial;
 374 } Binary_t;
 375
 376 typedef struct Group_s
 377 {
 378         int             number;         /* group number                 */
 379         int             last;           /* last contained group number  */
 380         int             size;           /* lookbehind size              */
 381         int             back;           /* backreferenced               */
 382         regflags_t      flags;          /* group flags                  */
 383         union
 384         {
 385         Binary_t        binary;
 386         struct Rex_s*   rex;
 387         }               expr;
 388 } Group_t;
 389
 390 typedef struct Exec_s
 391 {
 392         void*           data;
 393         const char*     text;
 394         size_t          size;
 395 } Exec_t;
 396
 397 #define REX_NEST_open           0x01
 398 #define REX_NEST_close          0x02
 399 #define REX_NEST_escape         0x04
 400 #define REX_NEST_quote          0x08
 401 #define REX_NEST_literal        0x10
 402 #define REX_NEST_delimiter      0x20
 403 #define REX_NEST_terminator     0x40
 404 #define REX_NEST_separator      0x80
 405
 406 #define REX_NEST_SHIFT          8
 407
 408 typedef struct Nest_s
 409 {
 410         int             primary;
 411         unsigned short  none;           /* for Nest_t.type[-1] */
 412         unsigned short  type[1];
 413 } Nest_t;
 414
 415 /*
 416  * REX_ALT catcher, solely to get control at the end of an
 417  * alternative to keep records for comparing matches.
 418  */
 419
 420 typedef struct Alt_catch_s
 421 {
 422         struct Rex_s*   cont;
 423 } Alt_catch_t;
 424
 425 typedef struct Group_catch_s
 426 {
 427         struct Rex_s*   cont;
 428         regoff_t*       eo;
 429 } Group_catch_t;
 430
 431 typedef struct Behind_catch_s
 432 {
 433         struct Rex_s*   cont;
 434         unsigned char*  beg;
 435         unsigned char*  end;
 436 } Behind_catch_t;
 437
 438 /*
 439  * REX_NEG catcher determines what string lengths can be matched,
 440  * then Neg investigates continuations of other lengths.
 441  * This is inefficient.  For !POSITIONS expressions, we can do better:
 442  * since matches to rex will be enumerated in decreasing order,
 443  * we can investigate continuations whenever a length is skipped.
 444  */
 445
 446 typedef struct Neg_catch_s
 447 {
 448         unsigned char*  beg;
 449         unsigned char*  index;
 450 } Neg_catch_t;
 451
 452 /*
 453  * REX_REP catcher.  One is created on the stack for
 454  * each iteration of a complex repetition.
 455  */
 456
 457 typedef struct Rep_catch_s
 458 {
 459         struct Rex_s*   cont;
 460         struct Rex_s*   ref;
 461         unsigned char*  beg;
 462         int             n;
 463 } Rep_catch_t;
 464
 465 /*
 466  * data structure for an alternation of pure strings
 467  * son points to a subtree of all strings with a common
 468  * prefix ending in character c.  sib links alternate
 469  * letters in the same position of a word.  end=1 if
 470  * some word ends with c.  the order of strings is
 471  * irrelevant, except long words must be investigated
 472  * before short ones.
 473  */
 474
 475 typedef struct Trie_node_s
 476 {
 477         unsigned char           c;
 478         unsigned char           end;
 479         struct Trie_node_s*     son;
 480         struct Trie_node_s*     sib;
 481 } Trie_node_t;
 482
 483 typedef struct Trie_s
 484 {
 485         Trie_node_t**   root;
 486         int             min;
 487         int             max;
 488 } Trie_t;
 489
 490 /*
 491  * Rex_t is a node in a regular expression
 492  */
 493
 494 typedef struct Rex_s
 495 {
 496         unsigned char   type;                   /* node type            */
 497         unsigned char   marked;                 /* already marked       */
 498         short           serial;                 /* subpattern number    */
 499         regflags_t      flags;                  /* scoped flags         */
 500         int             explicit;               /* scoped explicit match*/
 501         struct Rex_s*   next;                   /* remaining parts      */
 502         int             lo;                     /* lo dup count         */
 503         int             hi;                     /* hi dup count         */
 504         unsigned char*  map;                    /* fold and/or ccode map*/
 505         union
 506         {
 507         Alt_catch_t     alt_catch;              /* alt catcher          */
 508         Bm_t            bm;                     /* bm                   */
 509         Behind_catch_t  behind_catch;           /* behind catcher       */
 510         Set_t*          charclass;              /* char class           */
 511         Collate_t       collate;                /* collation class      */
 512         Cond_t          cond_catch;             /* cond catcher         */
 513         Conj_left_t     conj_left;              /* conj left catcher    */
 514         Conj_right_t    conj_right;             /* conj right catcher   */
 515         void*           data;                   /* data after Rex_t     */
 516         Exec_t          exec;                   /* re.re_exec() args    */
 517         Group_t         group;                  /* a|b or rep           */
 518         Group_catch_t   group_catch;            /* group catcher        */
 519         Neg_catch_t     neg_catch;              /* neg catcher          */
 520         Nest_t          nest;                   /* nested match         */
 521         unsigned char   onechar;                /* single char          */
 522         Rep_catch_t     rep_catch;              /* rep catcher          */
 523         String_t        string;                 /* string/kmp           */
 524         Trie_t          trie;                   /* trie                 */
 525         }               re;
 526 } Rex_t;
 527
 528 typedef struct reglib_s                 /* library private regex_t info */
 529 {
 530         struct Rex_s*   rex;            /* compiled expression          */
 531         regdisc_t*      disc;           /* REG_DISCIPLINE discipline    */
 532         const regex_t*  regex;          /* from regexec                 */
 533         unsigned char*  beg;            /* beginning of string          */
 534         unsigned char*  end;            /* end of string                */
 535         Vector_t*       pos;            /* posns of certain subpatterns */
 536         Vector_t*       bestpos;        /* ditto for best match         */
 537         regmatch_t*     match;          /* subexrs in current match     */
 538         regmatch_t*     best;           /* ditto in best match yet      */
 539         Stk_pos_t       stk;            /* exec stack pos               */
 540         size_t          min;            /* minimum match length         */
 541         size_t          nsub;           /* internal re_nsub             */
 542         regflags_t      flags;          /* flags from regcomp()         */
 543         int             error;          /* last error                   */
 544         int             explicit;       /* explicit match on this char  */
 545         int             leading;        /* leading match on this char   */
 546         int             refs;           /* regcomp()+regdup() references*/
 547         Rex_t           done;           /* the last continuation        */
 548         regstat_t       stats;          /* for regstat()                */
 549         unsigned char   fold[UCHAR_MAX+1]; /* REG_ICASE map             */
 550         unsigned char   hard;           /* hard comp                    */
 551         unsigned char   once;           /* if 1st parse fails, quit     */
 552         unsigned char   separate;       /* cannot combine               */
 553         unsigned char   stack;          /* hard comp or exec            */
 554         unsigned char   sub;            /* re_sub is valid              */
 555         unsigned char   test;           /* debug/test bitmask           */
 556 } Env_t;
 557
 558 typedef struct State_s                          /* shared state         */
 559 {
 560         regmatch_t      nomatch;
 561         struct
 562         {
 563         unsigned char   key;
 564         short           val[15];
 565         }               escape[52];
 566         short*          magic[UCHAR_MAX+1];
 567         regdisc_t       disc;
 568         int             fatal;
 569         int             initialized;
 570         Dt_t*           attrs;
 571         Dt_t*           names;
 572         Dtdisc_t        dtdisc;
 573 } State_t;
 574
 575 extern State_t          state;
 576
 577 extern void*            alloc(regdisc_t*, void*, size_t);
 578 extern regclass_t       classfun(int);
 579 extern void             drop(regdisc_t*, Rex_t*);
 580 extern int              fatal(regdisc_t*, int, const char*);
 581
 582 #endif