granicus.if.org Git - postgresql/blob - src/include/regex/regguts.h

   1 /*
   2  * Internal interface definitions, etc., for the reg package
   3  *
   4  * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
   5  *
   6  * Development of this software was funded, in part, by Cray Research Inc.,
   7  * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
   8  * Corporation, none of whom are responsible for the results.  The author
   9  * thanks all of them.
  10  *
  11  * Redistribution and use in source and binary forms -- with or without
  12  * modification -- are permitted for any purpose, provided that
  13  * redistributions in source form retain this entire copyright notice and
  14  * indicate the origin and nature of any modifications.
  15  *
  16  * I'd appreciate being given credit for this package in the documentation
  17  * of software which uses it, but that is not a requirement.
  18  *
  19  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  21  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
  22  * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  23  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  24  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  25  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  26  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  27  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  28  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  * src/include/regex/regguts.h
  31  */
  32
  33
  34
  35 /*
  36  * Environmental customization.  It should not (I hope) be necessary to
  37  * alter the file you are now reading -- regcustom.h should handle it all,
  38  * given care here and elsewhere.
  39  */
  40 #include "regcustom.h"
  41
  42
  43
  44 /*
  45  * Things that regcustom.h might override.
  46  */
  47
  48 /* assertions */
  49 #ifndef assert
  50 #ifndef REG_DEBUG
  51 #define  NDEBUG                                 /* no assertions */
  52 #endif
  53 #include <assert.h>
  54 #endif
  55
  56 /* voids */
  57 #ifndef DISCARD
  58 #define DISCARD void                    /* for throwing values away */
  59 #endif
  60 #ifndef VS
  61 #define VS(x)   ((void *)(x))   /* cast something to generic ptr */
  62 #endif
  63
  64 /* function-pointer declarator */
  65 #ifndef FUNCPTR
  66 #define FUNCPTR(name, args) (*(name)) args
  67 #endif
  68
  69 /* memory allocation */
  70 #ifndef MALLOC
  71 #define MALLOC(n)       malloc(n)
  72 #endif
  73 #ifndef REALLOC
  74 #define REALLOC(p, n)   realloc(VS(p), n)
  75 #endif
  76 #ifndef FREE
  77 #define FREE(p)         free(VS(p))
  78 #endif
  79
  80 /* want size of a char in bits, and max value in bounded quantifiers */
  81 #ifndef _POSIX2_RE_DUP_MAX
  82 #define _POSIX2_RE_DUP_MAX      255 /* normally from <limits.h> */
  83 #endif
  84
  85
  86
  87 /*
  88  * misc
  89  */
  90
  91 #define NOTREACHED      0
  92 #define xxx             1
  93
  94 #define DUPMAX  _POSIX2_RE_DUP_MAX
  95 #define DUPINF  (DUPMAX+1)
  96
  97 #define REMAGIC 0xfed7                  /* magic number for main struct */
  98
  99
 100
 101 /*
 102  * debugging facilities
 103  */
 104 #ifdef REG_DEBUG
 105 /* FDEBUG does finite-state tracing */
 106 #define FDEBUG(arglist) { if (v->eflags&REG_FTRACE) printf arglist; }
 107 /* MDEBUG does higher-level tracing */
 108 #define MDEBUG(arglist) { if (v->eflags&REG_MTRACE) printf arglist; }
 109 #else
 110 #define FDEBUG(arglist) {}
 111 #define MDEBUG(arglist) {}
 112 #endif
 113
 114
 115
 116 /*
 117  * bitmap manipulation
 118  */
 119 #define UBITS   (CHAR_BIT * sizeof(unsigned))
 120 #define BSET(uv, sn)    ((uv)[(sn)/UBITS] |= (unsigned)1 << ((sn)%UBITS))
 121 #define ISBSET(uv, sn)  ((uv)[(sn)/UBITS] & ((unsigned)1 << ((sn)%UBITS)))
 122
 123
 124
 125 /*
 126  * We dissect a chr into byts for colormap table indexing.  Here we define
 127  * a byt, which will be the same as a byte on most machines...  The exact
 128  * size of a byt is not critical, but about 8 bits is good, and extraction
 129  * of 8-bit chunks is sometimes especially fast.
 130  */
 131 #ifndef BYTBITS
 132 #define BYTBITS 8                               /* bits in a byt */
 133 #endif
 134 #define BYTTAB  (1<<BYTBITS)    /* size of table with one entry per byt value */
 135 #define BYTMASK (BYTTAB-1)              /* bit mask for byt */
 136 #define NBYTS   ((CHRBITS+BYTBITS-1)/BYTBITS)
 137 /* the definition of GETCOLOR(), below, assumes NBYTS <= 4 */
 138
 139
 140
 141 /*
 142  * As soon as possible, we map chrs into equivalence classes -- "colors" --
 143  * which are of much more manageable number.
 144  */
 145 typedef short color;                    /* colors of characters */
 146 typedef int pcolor;                             /* what color promotes to */
 147
 148 #define MAX_COLOR       32767           /* max color (must fit in 'color' datatype) */
 149 #define COLORLESS       (-1)            /* impossible color */
 150 #define WHITE           0                       /* default color, parent of all others */
 151
 152
 153
 154 /*
 155  * A colormap is a tree -- more precisely, a DAG -- indexed at each level
 156  * by a byt of the chr, to map the chr to a color efficiently.  Because
 157  * lower sections of the tree can be shared, it can exploit the usual
 158  * sparseness of such a mapping table.  The tree is always NBYTS levels
 159  * deep (in the past it was shallower during construction but was "filled"
 160  * to full depth at the end of that); areas that are unaltered as yet point
 161  * to "fill blocks" which are entirely WHITE in color.
 162  *
 163  * Leaf-level tree blocks are of type "struct colors", while upper-level
 164  * blocks are of type "struct ptrs".  Pointers into the tree are generally
 165  * declared as "union tree *" to be agnostic about what level they point to.
 166  */
 167
 168 /* the tree itself */
 169 struct colors
 170 {
 171         color           ccolor[BYTTAB];
 172 };
 173 struct ptrs
 174 {
 175         union tree *pptr[BYTTAB];
 176 };
 177 union tree
 178 {
 179         struct colors colors;
 180         struct ptrs ptrs;
 181 };
 182
 183 /* use these pseudo-field names when dereferencing a "union tree" pointer */
 184 #define tcolor  colors.ccolor
 185 #define tptr    ptrs.pptr
 186
 187 /*
 188  * Per-color data structure for the compile-time color machinery
 189  *
 190  * If "sub" is not NOSUB then it is the number of the color's current
 191  * subcolor, i.e. we are in process of dividing this color (character
 192  * equivalence class) into two colors.  See src/backend/regex/README for
 193  * discussion of subcolors.
 194  *
 195  * Currently-unused colors have the FREECOL bit set and are linked into a
 196  * freelist using their "sub" fields, but only if their color numbers are
 197  * less than colormap.max.  Any array entries beyond "max" are just garbage.
 198  */
 199 struct colordesc
 200 {
 201         uchr            nchrs;                  /* number of chars of this color */
 202         color           sub;                    /* open subcolor, if any; or free-chain ptr */
 203 #define  NOSUB   COLORLESS              /* value of "sub" when no open subcolor */
 204         struct arc *arcs;                       /* chain of all arcs of this color */
 205         chr                     firstchr;               /* char first assigned to this color */
 206         int                     flags;                  /* bit values defined next */
 207 #define  FREECOL 01                             /* currently free */
 208 #define  PSEUDO  02                             /* pseudocolor, no real chars */
 209 #define  UNUSEDCOLOR(cd) ((cd)->flags & FREECOL)
 210         union tree *block;                      /* block of solid color, if any */
 211 };
 212
 213 /*
 214  * The color map itself
 215  *
 216  * Much of the data in the colormap struct is only used at compile time.
 217  * However, the bulk of the space usage is in the "tree" structure, so it's
 218  * not clear that there's much point in converting the rest to a more compact
 219  * form when compilation is finished.
 220  */
 221 struct colormap
 222 {
 223         int                     magic;
 224 #define  CMMAGIC 0x876
 225         struct vars *v;                         /* for compile error reporting */
 226         size_t          ncds;                   /* allocated length of colordescs array */
 227         size_t          max;                    /* highest color number currently in use */
 228         color           free;                   /* beginning of free chain (if non-0) */
 229         struct colordesc *cd;           /* pointer to array of colordescs */
 230 #define  CDEND(cm)       (&(cm)->cd[(cm)->max + 1])
 231         /* If we need up to NINLINECDS, we store them here to save a malloc */
 232 #define  NINLINECDS  ((size_t)10)
 233         struct colordesc cdspace[NINLINECDS];
 234         union tree      tree[NBYTS];    /* tree top, plus lower-level fill blocks */
 235 };
 236
 237 /* optimization magic to do fast chr->color mapping */
 238 #define B0(c)   ((c) & BYTMASK)
 239 #define B1(c)   (((c)>>BYTBITS) & BYTMASK)
 240 #define B2(c)   (((c)>>(2*BYTBITS)) & BYTMASK)
 241 #define B3(c)   (((c)>>(3*BYTBITS)) & BYTMASK)
 242 #if NBYTS == 1
 243 #define GETCOLOR(cm, c) ((cm)->tree->tcolor[B0(c)])
 244 #endif
 245 /* beware, for NBYTS>1, GETCOLOR() is unsafe -- 2nd arg used repeatedly */
 246 #if NBYTS == 2
 247 #define GETCOLOR(cm, c) ((cm)->tree->tptr[B1(c)]->tcolor[B0(c)])
 248 #endif
 249 #if NBYTS == 4
 250 #define GETCOLOR(cm, c) ((cm)->tree->tptr[B3(c)]->tptr[B2(c)]->tptr[B1(c)]->tcolor[B0(c)])
 251 #endif
 252
 253
 254 /*
 255  * Interface definitions for locale-interface functions in regc_locale.c.
 256  */
 257
 258 /*
 259  * Representation of a set of characters.  chrs[] represents individual
 260  * code points, ranges[] represents ranges in the form min..max inclusive.
 261  *
 262  * Note that in cvecs gotten from newcvec() and intended to be freed by
 263  * freecvec(), both arrays of chrs are after the end of the struct, not
 264  * separately malloc'd; so chrspace and rangespace are effectively immutable.
 265  */
 266 struct cvec
 267 {
 268         int                     nchrs;                  /* number of chrs */
 269         int                     chrspace;               /* number of chrs allocated in chrs[] */
 270         chr                *chrs;                       /* pointer to vector of chrs */
 271         int                     nranges;                /* number of ranges (chr pairs) */
 272         int                     rangespace;             /* number of ranges allocated in ranges[] */
 273         chr                *ranges;                     /* pointer to vector of chr pairs */
 274 };
 275
 276
 277 /*
 278  * definitions for NFA internal representation
 279  *
 280  * Having a "from" pointer within each arc may seem redundant, but it
 281  * saves a lot of hassle.
 282  */
 283 struct state;
 284
 285 struct arc
 286 {
 287         int                     type;                   /* 0 if free, else an NFA arc type code */
 288         color           co;
 289         struct state *from;                     /* where it's from (and contained within) */
 290         struct state *to;                       /* where it's to */
 291         struct arc *outchain;           /* link in *from's outs chain or free chain */
 292 #define  freechain       outchain
 293         struct arc *inchain;            /* link in *to's ins chain */
 294         struct arc *colorchain;         /* link in color's arc chain */
 295         struct arc *colorchainRev;      /* back-link in color's arc chain */
 296 };
 297
 298 struct arcbatch
 299 {                                                               /* for bulk allocation of arcs */
 300         struct arcbatch *next;
 301 #define  ABSIZE  10
 302         struct arc      a[ABSIZE];
 303 };
 304
 305 struct state
 306 {
 307         int                     no;
 308 #define  FREESTATE       (-1)
 309         char            flag;                   /* marks special states */
 310         int                     nins;                   /* number of inarcs */
 311         struct arc *ins;                        /* chain of inarcs */
 312         int                     nouts;                  /* number of outarcs */
 313         struct arc *outs;                       /* chain of outarcs */
 314         struct arc *free;                       /* chain of free arcs */
 315         struct state *tmp;                      /* temporary for traversal algorithms */
 316         struct state *next;                     /* chain for traversing all */
 317         struct state *prev;                     /* back chain */
 318         struct arcbatch oas;            /* first arcbatch, avoid malloc in easy case */
 319         int                     noas;                   /* number of arcs used in first arcbatch */
 320 };
 321
 322 struct nfa
 323 {
 324         struct state *pre;                      /* pre-initial state */
 325         struct state *init;                     /* initial state */
 326         struct state *final;            /* final state */
 327         struct state *post;                     /* post-final state */
 328         int                     nstates;                /* for numbering states */
 329         struct state *states;           /* state-chain header */
 330         struct state *slast;            /* tail of the chain */
 331         struct state *free;                     /* free list */
 332         struct colormap *cm;            /* the color map */
 333         color           bos[2];                 /* colors, if any, assigned to BOS and BOL */
 334         color           eos[2];                 /* colors, if any, assigned to EOS and EOL */
 335         size_t          size;                   /* Current NFA size; differs from nstates as
 336                                                                  * it also counts the number of states in
 337                                                                  * children of this NFA. */
 338         struct vars *v;                         /* simplifies compile error reporting */
 339         struct nfa *parent;                     /* parent NFA, if any */
 340 };
 341
 342
 343
 344 /*
 345  * definitions for compacted NFA
 346  *
 347  * The main space savings in a compacted NFA is from making the arcs as small
 348  * as possible.  We store only the transition color and next-state number for
 349  * each arc.  The list of out arcs for each state is an array beginning at
 350  * cnfa.states[statenumber], and terminated by a dummy carc struct with
 351  * co == COLORLESS.
 352  *
 353  * The non-dummy carc structs are of two types: plain arcs and LACON arcs.
 354  * Plain arcs just store the transition color number as "co".  LACON arcs
 355  * store the lookahead constraint number plus cnfa.ncolors as "co".  LACON
 356  * arcs can be distinguished from plain by testing for co >= cnfa.ncolors.
 357  */
 358 struct carc
 359 {
 360         color           co;                             /* COLORLESS is list terminator */
 361         int                     to;                             /* next-state number */
 362 };
 363
 364 struct cnfa
 365 {
 366         int                     nstates;                /* number of states */
 367         int                     ncolors;                /* number of colors (max color in use + 1) */
 368         int                     flags;
 369 #define  HASLACONS      01                      /* uses lookahead constraints */
 370         int                     pre;                    /* setup state number */
 371         int                     post;                   /* teardown state number */
 372         color           bos[2];                 /* colors, if any, assigned to BOS and BOL */
 373         color           eos[2];                 /* colors, if any, assigned to EOS and EOL */
 374         char       *stflags;            /* vector of per-state flags bytes */
 375 #define  CNFA_NOPROGRESS        01      /* flag bit for a no-progress state */
 376         struct carc **states;           /* vector of pointers to outarc lists */
 377         /* states[n] are pointers into a single malloc'd array of arcs */
 378         struct carc *arcs;                      /* the area for the lists */
 379 };
 380
 381 #define ZAPCNFA(cnfa)   ((cnfa).nstates = 0)
 382 #define NULLCNFA(cnfa)  ((cnfa).nstates == 0)
 383
 384 /*
 385  * Used to limit the maximum NFA size to something sane. [Tcl Bug 1810264]
 386  */
 387 #ifndef REG_MAX_STATES
 388 #define REG_MAX_STATES  100000
 389 #endif
 390
 391 /*
 392  * subexpression tree
 393  *
 394  * "op" is one of:
 395  *              '='  plain regex without interesting substructure (implemented as DFA)
 396  *              'b'  back-reference (has no substructure either)
 397  *              '('  capture node: captures the match of its single child
 398  *              '.'  concatenation: matches a match for left, then a match for right
 399  *              '|'  alternation: matches a match for left or a match for right
 400  *              '*'  iteration: matches some number of matches of its single child
 401  *
 402  * Note: the right child of an alternation must be another alternation or
 403  * NULL; hence, an N-way branch requires N alternation nodes, not N-1 as you
 404  * might expect.  This could stand to be changed.  Actually I'd rather see
 405  * a single alternation node with N children, but that will take revising
 406  * the representation of struct subre.
 407  *
 408  * Note: when a backref is directly quantified, we stick the min/max counts
 409  * into the backref rather than plastering an iteration node on top.  This is
 410  * for efficiency: there is no need to search for possible division points.
 411  */
 412 struct subre
 413 {
 414         char            op;                             /* see type codes above */
 415         char            flags;
 416 #define  LONGER  01                             /* prefers longer match */
 417 #define  SHORTER 02                             /* prefers shorter match */
 418 #define  MIXED   04                             /* mixed preference below */
 419 #define  CAP     010                    /* capturing parens below */
 420 #define  BACKR   020                    /* back reference below */
 421 #define  INUSE   0100                   /* in use in final tree */
 422 #define  NOPROP  03                             /* bits which may not propagate up */
 423 #define  LMIX(f) ((f)<<2)               /* LONGER -> MIXED */
 424 #define  SMIX(f) ((f)<<1)               /* SHORTER -> MIXED */
 425 #define  UP(f)   (((f)&~NOPROP) | (LMIX(f) & SMIX(f) & MIXED))
 426 #define  MESSY(f)        ((f)&(MIXED|CAP|BACKR))
 427 #define  PREF(f) ((f)&NOPROP)
 428 #define  PREF2(f1, f2)   ((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
 429 #define  COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2))
 430         short           id;                             /* ID of subre (1..ntree-1) */
 431         int                     subno;                  /* subexpression number (for 'b' and '(') */
 432         short           min;                    /* min repetitions for iteration or backref */
 433         short           max;                    /* max repetitions for iteration or backref */
 434         struct subre *left;                     /* left child, if any (also freelist chain) */
 435         struct subre *right;            /* right child, if any */
 436         struct state *begin;            /* outarcs from here... */
 437         struct state *end;                      /* ...ending in inarcs here */
 438         struct cnfa cnfa;                       /* compacted NFA, if any */
 439         struct subre *chain;            /* for bookkeeping and error cleanup */
 440 };
 441
 442
 443
 444 /*
 445  * table of function pointers for generic manipulation functions
 446  * A regex_t's re_fns points to one of these.
 447  */
 448 struct fns
 449 {
 450         void            FUNCPTR(free, (regex_t *));
 451         int                     FUNCPTR(cancel_requested, (void));
 452 };
 453
 454 #define CANCEL_REQUESTED(re)  \
 455         ((*((struct fns *) (re)->re_fns)->cancel_requested) ())
 456
 457
 458 /*
 459  * the insides of a regex_t, hidden behind a void *
 460  */
 461 struct guts
 462 {
 463         int                     magic;
 464 #define  GUTSMAGIC       0xfed9
 465         int                     cflags;                 /* copy of compile flags */
 466         long            info;                   /* copy of re_info */
 467         size_t          nsub;                   /* copy of re_nsub */
 468         struct subre *tree;
 469         struct cnfa search;                     /* for fast preliminary search */
 470         int                     ntree;                  /* number of subre's, less one */
 471         struct colormap cmap;
 472         int                     FUNCPTR(compare, (const chr *, const chr *, size_t));
 473         struct subre *lacons;           /* lookahead-constraint vector */
 474         int                     nlacons;                /* size of lacons */
 475 };