src/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
  31
  32
  33 /*
  34  * Environmental customization.  It should not (I hope) be necessary to
  35  * alter the file you are now reading -- regcustom.h should handle it all,
  36  * given care here and elsewhere.
  37  */
  38 #include "regcustom.h"
  39
  40
  41
  42 /*
  43  * Things that regcustom.h might override.
  44  */
  45
  46 /* standard header files (NULL is a reasonable indicator for them) */
  47 #ifndef NULL
  48 #include <stdio.h>
  49 #include <stdlib.h>
  50 #include <ctype.h>
  51 #include <limits.h>
  52 #include <string.h>
  53 #endif
  54
  55 /* assertions */
  56 #ifndef assert
  57 #       ifndef REG_DEBUG
  58 #       define  NDEBUG          /* no assertions */
  59 #       endif
  60 #include <assert.h>
  61 #endif
  62
  63 /* voids */
  64 #ifndef VOID
  65 #define VOID    void                    /* for function return values */
  66 #endif
  67 #ifndef DISCARD
  68 #define DISCARD VOID                    /* for throwing values away */
  69 #endif
  70 #ifndef PVOID
  71 #define PVOID   VOID *                  /* generic pointer */
  72 #endif
  73 #ifndef VS
  74 #define VS(x)   ((PVOID)(x))            /* cast something to generic ptr */
  75 #endif
  76 #ifndef NOPARMS
  77 #define NOPARMS VOID                    /* for empty parm lists */
  78 #endif
  79
  80 /* const */
  81 #ifndef CONST
  82 #define CONST   const                   /* for old compilers, might be empty */
  83 #endif
  84
  85 /* function-pointer declarator */
  86 #ifndef FUNCPTR
  87 #if __STDC__ >= 1
  88 #define FUNCPTR(name, args)     (*name)args
  89 #else
  90 #define FUNCPTR(name, args)     (*name)()
  91 #endif
  92 #endif
  93
  94 /* memory allocation */
  95 #ifndef MALLOC
  96 #define MALLOC(n)       malloc(n)
  97 #endif
  98 #ifndef REALLOC
  99 #define REALLOC(p, n)   realloc(VS(p), n)
 100 #endif
 101 #ifndef FREE
 102 #define FREE(p)         free(VS(p))
 103 #endif
 104
 105 /* want size of a char in bits, and max value in bounded quantifiers */
 106 #ifndef CHAR_BIT
 107 #include <limits.h>
 108 #endif
 109 #ifndef _POSIX2_RE_DUP_MAX
 110 #define _POSIX2_RE_DUP_MAX      255     /* normally from <limits.h> */
 111 #endif
 112
 113
 114
 115 /*
 116  * misc
 117  */
 118
 119 #define NOTREACHED      0
 120 #define xxx             1
 121
 122 #define DUPMAX  _POSIX2_RE_DUP_MAX
 123 #define INFINITY        (DUPMAX+1)
 124
 125 #define REMAGIC 0xfed7          /* magic number for main struct */
 126
 127
 128
 129 /*
 130  * debugging facilities
 131  */
 132 #ifdef REG_DEBUG
 133 /* FDEBUG does finite-state tracing */
 134 #define FDEBUG(arglist) { if (v->eflags&REG_FTRACE) printf arglist; }
 135 /* MDEBUG does higher-level tracing */
 136 #define MDEBUG(arglist) { if (v->eflags&REG_MTRACE) printf arglist; }
 137 #else
 138 #define FDEBUG(arglist) {}
 139 #define MDEBUG(arglist) {}
 140 #endif
 141
 142
 143
 144 /*
 145  * bitmap manipulation
 146  */
 147 #define UBITS   (CHAR_BIT * sizeof(unsigned))
 148 #define BSET(uv, sn)    ((uv)[(sn)/UBITS] |= (unsigned)1 << ((sn)%UBITS))
 149 #define ISBSET(uv, sn)  ((uv)[(sn)/UBITS] & ((unsigned)1 << ((sn)%UBITS)))
 150
 151
 152
 153 /*
 154  * We dissect a chr into byts for colormap table indexing.  Here we define
 155  * a byt, which will be the same as a byte on most machines...  The exact
 156  * size of a byt is not critical, but about 8 bits is good, and extraction
 157  * of 8-bit chunks is sometimes especially fast.
 158  */
 159 #ifndef BYTBITS
 160 #define BYTBITS 8               /* bits in a byt */
 161 #endif
 162 #define BYTTAB  (1<<BYTBITS)    /* size of table with one entry per byt value */
 163 #define BYTMASK (BYTTAB-1)      /* bit mask for byt */
 164 #define NBYTS   ((CHRBITS+BYTBITS-1)/BYTBITS)
 165 /* the definition of GETCOLOR(), below, assumes NBYTS <= 4 */
 166
 167
 168
 169 /*
 170  * As soon as possible, we map chrs into equivalence classes -- "colors" --
 171  * which are of much more manageable number.
 172  */
 173 typedef short color;            /* colors of characters */
 174 typedef int pcolor;             /* what color promotes to */
 175 #define COLORLESS       (-1)    /* impossible color */
 176 #define WHITE           0       /* default color, parent of all others */
 177
 178
 179
 180 /*
 181  * A colormap is a tree -- more precisely, a DAG -- indexed at each level
 182  * by a byt of the chr, to map the chr to a color efficiently.  Because
 183  * lower sections of the tree can be shared, it can exploit the usual
 184  * sparseness of such a mapping table.  The tree is always NBYTS levels
 185  * deep (in the past it was shallower during construction but was "filled"
 186  * to full depth at the end of that); areas that are unaltered as yet point
 187  * to "fill blocks" which are entirely WHITE in color.
 188  */
 189
 190 /* the tree itself */
 191 struct colors {
 192         color ccolor[BYTTAB];
 193 };
 194 struct ptrs {
 195         union tree *pptr[BYTTAB];
 196 };
 197 union tree {
 198         struct colors colors;
 199         struct ptrs ptrs;
 200 };
 201 #define tcolor  colors.ccolor
 202 #define tptr    ptrs.pptr
 203
 204 /* internal per-color structure for the color machinery */
 205 struct colordesc {
 206         uchr nchrs;             /* number of chars of this color */
 207         color sub;              /* open subcolor (if any); free chain ptr */
 208 #               define  NOSUB   COLORLESS
 209         struct arc *arcs;       /* color chain */
 210         int flags;
 211 #               define  FREECOL 01      /* currently free */
 212 #               define  PSEUDO  02      /* pseudocolor, no real chars */
 213 #       define  UNUSEDCOLOR(cd) ((cd)->flags&FREECOL)
 214         union tree *block;      /* block of solid color, if any */
 215 };
 216
 217 /* the color map itself */
 218 struct colormap {
 219         int magic;
 220 #               define  CMMAGIC 0x876
 221         struct vars *v;                 /* for compile error reporting */
 222         size_t ncds;                    /* number of colordescs */
 223         size_t max;                     /* highest in use */
 224         color free;                     /* beginning of free chain (if non-0) */
 225         struct colordesc *cd;
 226 #       define  CDEND(cm)       (&(cm)->cd[(cm)->max + 1])
 227 #               define  NINLINECDS      ((size_t)10)
 228         struct colordesc cdspace[NINLINECDS];
 229         union tree tree[NBYTS];         /* tree top, plus fill blocks */
 230 };
 231
 232 /* optimization magic to do fast chr->color mapping */
 233 #define B0(c)   ((c) & BYTMASK)
 234 #define B1(c)   (((c)>>BYTBITS) & BYTMASK)
 235 #define B2(c)   (((c)>>(2*BYTBITS)) & BYTMASK)
 236 #define B3(c)   (((c)>>(3*BYTBITS)) & BYTMASK)
 237 #if NBYTS == 1
 238 #define GETCOLOR(cm, c) ((cm)->tree->tcolor[B0(c)])
 239 #endif
 240 /* beware, for NBYTS>1, GETCOLOR() is unsafe -- 2nd arg used repeatedly */
 241 #if NBYTS == 2
 242 #define GETCOLOR(cm, c) ((cm)->tree->tptr[B1(c)]->tcolor[B0(c)])
 243 #endif
 244 #if NBYTS == 4
 245 #define GETCOLOR(cm, c) ((cm)->tree->tptr[B3(c)]->tptr[B2(c)]->tptr[B1(c)]->tcolor[B0(c)])
 246 #endif
 247
 248
 249
 250 /*
 251  * Interface definitions for locale-interface functions in locale.c.
 252  * Multi-character collating elements (MCCEs) cause most of the trouble.
 253  */
 254 struct cvec {
 255         int nchrs;              /* number of chrs */
 256         int chrspace;           /* number of chrs possible */
 257         chr *chrs;              /* pointer to vector of chrs */
 258         int nranges;            /* number of ranges (chr pairs) */
 259         int rangespace;         /* number of chrs possible */
 260         chr *ranges;            /* pointer to vector of chr pairs */
 261         int nmcces;             /* number of MCCEs */
 262         int mccespace;          /* number of MCCEs possible */
 263         int nmccechrs;          /* number of chrs used for MCCEs */
 264         chr *mcces[1];          /* pointers to 0-terminated MCCEs */
 265                                 /* and both batches of chrs are on the end */
 266 };
 267
 268 /* caution:  this value cannot be changed easily */
 269 #define MAXMCCE 2               /* length of longest MCCE */
 270
 271
 272
 273 /*
 274  * definitions for NFA internal representation
 275  *
 276  * Having a "from" pointer within each arc may seem redundant, but it
 277  * saves a lot of hassle.
 278  */
 279 struct state;
 280
 281 struct arc {
 282         int type;
 283 #               define  ARCFREE '\0'
 284         color co;
 285         struct state *from;     /* where it's from (and contained within) */
 286         struct state *to;       /* where it's to */
 287         struct arc *outchain;   /* *from's outs chain or free chain */
 288 #       define  freechain       outchain
 289         struct arc *inchain;    /* *to's ins chain */
 290         struct arc *colorchain; /* color's arc chain */
 291 };
 292
 293 struct arcbatch {               /* for bulk allocation of arcs */
 294         struct arcbatch *next;
 295 #       define  ABSIZE  10
 296         struct arc a[ABSIZE];
 297 };
 298
 299 struct state {
 300         int no;
 301 #               define  FREESTATE       (-1)
 302         char flag;              /* marks special states */
 303         int nins;               /* number of inarcs */
 304         struct arc *ins;        /* chain of inarcs */
 305         int nouts;              /* number of outarcs */
 306         struct arc *outs;       /* chain of outarcs */
 307         struct arc *free;       /* chain of free arcs */
 308         struct state *tmp;      /* temporary for traversal algorithms */
 309         struct state *next;     /* chain for traversing all */
 310         struct state *prev;     /* back chain */
 311         struct arcbatch oas;    /* first arcbatch, avoid malloc in easy case */
 312         int noas;               /* number of arcs used in first arcbatch */
 313 };
 314
 315 struct nfa {
 316         struct state *pre;      /* pre-initial state */
 317         struct state *init;     /* initial state */
 318         struct state *final;    /* final state */
 319         struct state *post;     /* post-final state */
 320         int nstates;            /* for numbering states */
 321         struct state *states;   /* state-chain header */
 322         struct state *slast;    /* tail of the chain */
 323         struct state *free;     /* free list */
 324         struct colormap *cm;    /* the color map */
 325         color bos[2];           /* colors, if any, assigned to BOS and BOL */
 326         color eos[2];           /* colors, if any, assigned to EOS and EOL */
 327         struct vars *v;         /* simplifies compile error reporting */
 328         struct nfa *parent;     /* parent NFA, if any */
 329 };
 330
 331
 332
 333 /*
 334  * definitions for compacted NFA
 335  */
 336 struct carc {
 337         color co;               /* COLORLESS is list terminator */
 338         int to;                 /* state number */
 339 };
 340
 341 struct cnfa {
 342         int nstates;            /* number of states */
 343         int ncolors;            /* number of colors */
 344         int flags;
 345 #               define  HASLACONS       01      /* uses lookahead constraints */
 346         int pre;                /* setup state number */
 347         int post;               /* teardown state number */
 348         color bos[2];           /* colors, if any, assigned to BOS and BOL */
 349         color eos[2];           /* colors, if any, assigned to EOS and EOL */
 350         struct carc **states;   /* vector of pointers to outarc lists */
 351         struct carc *arcs;      /* the area for the lists */
 352 };
 353 #define ZAPCNFA(cnfa)   ((cnfa).nstates = 0)
 354 #define NULLCNFA(cnfa)  ((cnfa).nstates == 0)
 355
 356
 357
 358 /*
 359  * subexpression tree
 360  */
 361 struct subre {
 362         char op;                /* '|', '.' (concat), 'b' (backref), '(', '=' */
 363         char flags;
 364 #               define  LONGER  01      /* prefers longer match */
 365 #               define  SHORTER 02      /* prefers shorter match */
 366 #               define  MIXED   04      /* mixed preference below */
 367 #               define  CAP     010     /* capturing parens below */
 368 #               define  BACKR   020     /* back reference below */
 369 #               define  INUSE   0100    /* in use in final tree */
 370 #               define  LOCAL   03      /* bits which may not propagate up */
 371 #               define  LMIX(f) ((f)<<2)        /* LONGER -> MIXED */
 372 #               define  SMIX(f) ((f)<<1)        /* SHORTER -> MIXED */
 373 #               define  UP(f)   (((f)&~LOCAL) | (LMIX(f) & SMIX(f) & MIXED))
 374 #               define  MESSY(f)        ((f)&(MIXED|CAP|BACKR))
 375 #               define  PREF(f) ((f)&LOCAL)
 376 #               define  PREF2(f1, f2)   ((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
 377 #               define  COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2))
 378         short retry;            /* index into retry memory */
 379         int subno;              /* subexpression number (for 'b' and '(') */
 380         short min;              /* min repetitions, for backref only */
 381         short max;              /* max repetitions, for backref only */
 382         struct subre *left;     /* left child, if any (also freelist chain) */
 383         struct subre *right;    /* right child, if any */
 384         struct state *begin;    /* outarcs from here... */
 385         struct state *end;      /* ...ending in inarcs here */
 386         struct cnfa cnfa;       /* compacted NFA, if any */
 387         struct subre *chain;    /* for bookkeeping and error cleanup */
 388 };
 389
 390
 391
 392 /*
 393  * table of function pointers for generic manipulation functions
 394  * A regex_t's re_fns points to one of these.
 395  */
 396 struct fns {
 397         VOID FUNCPTR(free, (regex_t *));
 398 };
 399
 400
 401
 402 /*
 403  * the insides of a regex_t, hidden behind a void *
 404  */
 405 struct guts {
 406         int magic;
 407 #               define  GUTSMAGIC       0xfed9
 408         int cflags;             /* copy of compile flags */
 409         long info;              /* copy of re_info */
 410         size_t nsub;            /* copy of re_nsub */
 411         struct subre *tree;
 412         struct cnfa search;     /* for fast preliminary search */
 413         int ntree;
 414         struct colormap cmap;
 415         int FUNCPTR(compare, (CONST chr *, CONST chr *, size_t));
 416         struct subre *lacons;   /* lookahead-constraint vector */
 417         int nlacons;            /* size of lacons */
 418 };