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