1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate /* Copyright (c) 1990 AT&T */ 23*0Sstevel@tonic-gate /* All Rights Reserved */ 24*0Sstevel@tonic-gate 25*0Sstevel@tonic-gate 26*0Sstevel@tonic-gate /* 27*0Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 28*0Sstevel@tonic-gate * Use is subject to license terms. 29*0Sstevel@tonic-gate */ 30*0Sstevel@tonic-gate 31*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 32*0Sstevel@tonic-gate 33*0Sstevel@tonic-gate /* 34*0Sstevel@tonic-gate * cscope - interactive C symbol or text cross-reference 35*0Sstevel@tonic-gate * 36*0Sstevel@tonic-gate * text searching functions 37*0Sstevel@tonic-gate */ 38*0Sstevel@tonic-gate 39*0Sstevel@tonic-gate #include <fcntl.h> 40*0Sstevel@tonic-gate #include <setjmp.h> 41*0Sstevel@tonic-gate #include <stdio.h> 42*0Sstevel@tonic-gate #include <string.h> 43*0Sstevel@tonic-gate #include <memory.h> 44*0Sstevel@tonic-gate #include <ctype.h> 45*0Sstevel@tonic-gate #include <unistd.h> 46*0Sstevel@tonic-gate #include "library.h" 47*0Sstevel@tonic-gate 48*0Sstevel@tonic-gate typedef enum { 49*0Sstevel@tonic-gate NO = 0, 50*0Sstevel@tonic-gate YES = 1 51*0Sstevel@tonic-gate } BOOL; 52*0Sstevel@tonic-gate 53*0Sstevel@tonic-gate typedef struct re_bm { 54*0Sstevel@tonic-gate int delta0[256]; 55*0Sstevel@tonic-gate int *delta2; 56*0Sstevel@tonic-gate uchar_t *cmap; 57*0Sstevel@tonic-gate uchar_t *bmpat; 58*0Sstevel@tonic-gate int patlen; 59*0Sstevel@tonic-gate } re_bm; 60*0Sstevel@tonic-gate 61*0Sstevel@tonic-gate typedef struct Link { 62*0Sstevel@tonic-gate uchar_t lit; 63*0Sstevel@tonic-gate struct Node *node; 64*0Sstevel@tonic-gate struct Link *next; 65*0Sstevel@tonic-gate } Link; 66*0Sstevel@tonic-gate 67*0Sstevel@tonic-gate typedef struct Node { 68*0Sstevel@tonic-gate short out; 69*0Sstevel@tonic-gate short d; 70*0Sstevel@tonic-gate short shift1; 71*0Sstevel@tonic-gate short shift2; 72*0Sstevel@tonic-gate long id; 73*0Sstevel@tonic-gate struct Node **tab; 74*0Sstevel@tonic-gate Link *alts; 75*0Sstevel@tonic-gate struct Node *fail; 76*0Sstevel@tonic-gate } Node; 77*0Sstevel@tonic-gate 78*0Sstevel@tonic-gate typedef struct re_cw { 79*0Sstevel@tonic-gate int maxdepth, mindepth; 80*0Sstevel@tonic-gate long nodeid; 81*0Sstevel@tonic-gate int step[256]; 82*0Sstevel@tonic-gate uchar_t *cmap; 83*0Sstevel@tonic-gate struct Node *root; 84*0Sstevel@tonic-gate } re_cw; 85*0Sstevel@tonic-gate 86*0Sstevel@tonic-gate typedef enum { 87*0Sstevel@tonic-gate /* lit expression types */ 88*0Sstevel@tonic-gate Literal, Dot, Charclass, EOP, 89*0Sstevel@tonic-gate 90*0Sstevel@tonic-gate /* non-lit expression types */ 91*0Sstevel@tonic-gate Cat, Alternate, Star, Plus, Quest, 92*0Sstevel@tonic-gate 93*0Sstevel@tonic-gate /* not really expression types, just helping */ 94*0Sstevel@tonic-gate Lpar, Rpar, Backslash 95*0Sstevel@tonic-gate 96*0Sstevel@tonic-gate } Exprtype; 97*0Sstevel@tonic-gate 98*0Sstevel@tonic-gate typedef int ID; 99*0Sstevel@tonic-gate 100*0Sstevel@tonic-gate typedef struct Expr { 101*0Sstevel@tonic-gate Exprtype type; /* Type of expression (in grammar) */ 102*0Sstevel@tonic-gate ID id; /* unique ID of lit expression */ 103*0Sstevel@tonic-gate int lit; /* Literal character or tag */ 104*0Sstevel@tonic-gate int flen; /* Number of following lit expressions */ 105*0Sstevel@tonic-gate ID *follow; /* Array of IDs of following lit expressions */ 106*0Sstevel@tonic-gate struct Expr *l; /* pointer to Left child (or ccl count) */ 107*0Sstevel@tonic-gate struct Expr *r; /* pointer to Right child (or ccl mask) */ 108*0Sstevel@tonic-gate struct Expr *parent; /* pointer to Parent */ 109*0Sstevel@tonic-gate } Expr; 110*0Sstevel@tonic-gate 111*0Sstevel@tonic-gate typedef struct State { 112*0Sstevel@tonic-gate struct State *tab[256]; 113*0Sstevel@tonic-gate int cnt; /* number of matched chars on full match, -1 otherwise */ 114*0Sstevel@tonic-gate int npos; /* number of IDs in position set for this state. */ 115*0Sstevel@tonic-gate int pos; /* index into posbase for beginning of IDs */ 116*0Sstevel@tonic-gate } State; 117*0Sstevel@tonic-gate 118*0Sstevel@tonic-gate typedef struct FID { 119*0Sstevel@tonic-gate ID id; /* Lit Expression id */ 120*0Sstevel@tonic-gate int fcount; /* Number of Lit exp matches before this one. */ 121*0Sstevel@tonic-gate } FID; 122*0Sstevel@tonic-gate 123*0Sstevel@tonic-gate typedef struct Positionset { 124*0Sstevel@tonic-gate int count; /* Number of lit exps in position set */ 125*0Sstevel@tonic-gate ID last; /* ID of last lit exp in position set */ 126*0Sstevel@tonic-gate FID *base; /* array of MAXID FIDS */ 127*0Sstevel@tonic-gate /* 0 means not in position set */ 128*0Sstevel@tonic-gate /* -1 means first in position set */ 129*0Sstevel@tonic-gate /* n (>0) is ID of prev member of position set. */ 130*0Sstevel@tonic-gate } Positionset; 131*0Sstevel@tonic-gate 132*0Sstevel@tonic-gate typedef struct re_re { 133*0Sstevel@tonic-gate FID *posbase; /* Array of IDs from all states */ 134*0Sstevel@tonic-gate int nposalloc; /* Allocated size of posbase */ 135*0Sstevel@tonic-gate int posnext; /* Index into free space in posbase */ 136*0Sstevel@tonic-gate int posreset; /* Index into end of IDs for initial state in posbase */ 137*0Sstevel@tonic-gate int maxid; /* Number of (also maximum ID of) lit expressions */ 138*0Sstevel@tonic-gate Expr *root; /* Pointer to root (EOP) expression */ 139*0Sstevel@tonic-gate Expr **ptr; /* Pointer to array of ptrs to lit expressions. */ 140*0Sstevel@tonic-gate uchar_t *cmap; /* Character mapping array */ 141*0Sstevel@tonic-gate Positionset firstpos; 142*0Sstevel@tonic-gate Positionset tmp; 143*0Sstevel@tonic-gate int nstates; /* Number of current states defined */ 144*0Sstevel@tonic-gate int statelim; /* Limit on number of states before flushing */ 145*0Sstevel@tonic-gate State *states; /* Array of states */ 146*0Sstevel@tonic-gate State istate; /* Initial state */ 147*0Sstevel@tonic-gate } re_re; 148*0Sstevel@tonic-gate 149*0Sstevel@tonic-gate typedef struct { 150*0Sstevel@tonic-gate uchar_t *cmap; 151*0Sstevel@tonic-gate re_re *re_ptr; 152*0Sstevel@tonic-gate re_bm *bm_ptr; 153*0Sstevel@tonic-gate re_cw *cw_ptr; 154*0Sstevel@tonic-gate BOOL fullmatch; 155*0Sstevel@tonic-gate BOOL (*procfn)(); 156*0Sstevel@tonic-gate BOOL (*succfn)(); 157*0Sstevel@tonic-gate uchar_t *loc1; 158*0Sstevel@tonic-gate uchar_t *loc2; 159*0Sstevel@tonic-gate uchar_t *expression; 160*0Sstevel@tonic-gate } PATTERN; 161*0Sstevel@tonic-gate 162*0Sstevel@tonic-gate typedef enum { 163*0Sstevel@tonic-gate BEGIN, /* File is not yet in buffer at all */ 164*0Sstevel@tonic-gate MORE, /* File is partly in buffer */ 165*0Sstevel@tonic-gate NO_MORE /* File has been completely read into buffer */ 166*0Sstevel@tonic-gate } FILE_STAT; 167*0Sstevel@tonic-gate 168*0Sstevel@tonic-gate typedef struct { 169*0Sstevel@tonic-gate uchar_t *prntbuf; /* current line of input from data file */ 170*0Sstevel@tonic-gate uchar_t *newline; /* end of line (real or sentinel \n) */ 171*0Sstevel@tonic-gate long ln; /* line number */ 172*0Sstevel@tonic-gate } LINE; 173*0Sstevel@tonic-gate 174*0Sstevel@tonic-gate #define NL '\n' 175*0Sstevel@tonic-gate 176*0Sstevel@tonic-gate #define CCL_SIZ 32 177*0Sstevel@tonic-gate #define CCL_SET(a, c) ((a)[(c) >> 3] |= bittab[(c) & 07]) 178*0Sstevel@tonic-gate #define CCL_CLR(a, c) ((a)[(c) >> 3] &= ~bittab[(c) & 07]) 179*0Sstevel@tonic-gate #define CCL_CHK(a, c) ((a)[(c) >> 3] & bittab[(c) & 07]) 180*0Sstevel@tonic-gate 181*0Sstevel@tonic-gate #define ESIZE (BUFSIZ) 182*0Sstevel@tonic-gate #define MAXBUFSIZE (64*BUFSIZ) 183*0Sstevel@tonic-gate 184*0Sstevel@tonic-gate #define MAXMALLOCS 1024 185*0Sstevel@tonic-gate #define MAXLIT 256 /* is plenty big enough */ 186*0Sstevel@tonic-gate #define LARGE MAXBUFSIZE+ESIZE+2 187*0Sstevel@tonic-gate 188*0Sstevel@tonic-gate #define CLEAR(r, rps) (void) memset((char *)(rps)->base, 0, \ 189*0Sstevel@tonic-gate (int)((r)->maxid * sizeof (FID))), \ 190*0Sstevel@tonic-gate (rps)->count = 0, (rps)->last = -1 191*0Sstevel@tonic-gate #define SET(rps, n, cnt) { \ 192*0Sstevel@tonic-gate if ((rps)->base[n].id == 0) {\ 193*0Sstevel@tonic-gate (rps)->count++;\ 194*0Sstevel@tonic-gate (rps)->base[n].fcount = (cnt);\ 195*0Sstevel@tonic-gate (rps)->base[n].id = (rps)->last;\ 196*0Sstevel@tonic-gate (rps)->last = (n);\ 197*0Sstevel@tonic-gate } else if ((cnt) > (rps)->base[n].fcount) {\ 198*0Sstevel@tonic-gate (rps)->base[n].fcount = (cnt);\ 199*0Sstevel@tonic-gate }} 200*0Sstevel@tonic-gate 201*0Sstevel@tonic-gate #define START { _p = tmp; } 202*0Sstevel@tonic-gate #define ADDL(c) { if (_p >= &tmp[MAXLIT]) _p--; *_p++ = c; } 203*0Sstevel@tonic-gate #define FINISH { ADDL(0) if ((_p-tmp) > bestlen) \ 204*0Sstevel@tonic-gate (void) memmove(best, tmp, bestlen = _p-tmp); } 205*0Sstevel@tonic-gate 206*0Sstevel@tonic-gate 207*0Sstevel@tonic-gate #define NEW(N) (froot?(t = froot, froot = froot->next, t->next = NULL, \ 208*0Sstevel@tonic-gate t->node = N, t): newlink(0, N)) 209*0Sstevel@tonic-gate #define ADD(N) if (qtail) qtail = qtail->next = NEW(N); \ 210*0Sstevel@tonic-gate else qtail = qhead = NEW(N) 211*0Sstevel@tonic-gate #define DEL() { Link *_l = qhead; if ((qhead = qhead->next) == NULL) \ 212*0Sstevel@tonic-gate qtail = NULL; _l->next = froot; froot = _l; } 213*0Sstevel@tonic-gate 214*0Sstevel@tonic-gate static uchar_t *buffer; 215*0Sstevel@tonic-gate static uchar_t *bufend; 216*0Sstevel@tonic-gate static FILE *output; 217*0Sstevel@tonic-gate static char *format; 218*0Sstevel@tonic-gate static char *file; 219*0Sstevel@tonic-gate static int file_desc; 220*0Sstevel@tonic-gate static FILE_STAT file_stat; 221*0Sstevel@tonic-gate static PATTERN match_pattern; 222*0Sstevel@tonic-gate static uchar_t char_map[2][256]; 223*0Sstevel@tonic-gate static int iflag; 224*0Sstevel@tonic-gate static Exprtype toktype; 225*0Sstevel@tonic-gate static int toklit, parno, maxid; 226*0Sstevel@tonic-gate static uchar_t tmp[MAXLIT], best[MAXLIT]; 227*0Sstevel@tonic-gate static uchar_t *_p; 228*0Sstevel@tonic-gate static int bestlen; 229*0Sstevel@tonic-gate static Node *next_node; 230*0Sstevel@tonic-gate static Link *froot, *next_link; 231*0Sstevel@tonic-gate static jmp_buf env; 232*0Sstevel@tonic-gate 233*0Sstevel@tonic-gate static int nmalloc; 234*0Sstevel@tonic-gate static uchar_t *mallocs[MAXMALLOCS]; 235*0Sstevel@tonic-gate 236*0Sstevel@tonic-gate static uchar_t bittab[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; 237*0Sstevel@tonic-gate 238*0Sstevel@tonic-gate #ifdef DEBUG 239*0Sstevel@tonic-gate #define TRACE(n) (n < debug) 240*0Sstevel@tonic-gate #define EPRINTSIZE 50000 241*0Sstevel@tonic-gate static void spr(int c, int *p, uchar_t *buf); 242*0Sstevel@tonic-gate void epr(Expr *e, uchar_t *res); 243*0Sstevel@tonic-gate static int debug = 12; 244*0Sstevel@tonic-gate #endif 245*0Sstevel@tonic-gate 246*0Sstevel@tonic-gate static void init_file(LINE *cur_ptr); 247*0Sstevel@tonic-gate static void get_line(LINE *cur_ptr, uchar_t *s); 248*0Sstevel@tonic-gate static void get_ncount(LINE *cur_ptr, uchar_t *s); 249*0Sstevel@tonic-gate static int execute(void); 250*0Sstevel@tonic-gate static State *startstate(re_re *r); 251*0Sstevel@tonic-gate static State *stateof(re_re *r, Positionset *ps); 252*0Sstevel@tonic-gate static State *nextstate(re_re *r, State *s, int a); 253*0Sstevel@tonic-gate static State *addstate(re_re *r, Positionset *ps, int cnt); 254*0Sstevel@tonic-gate static BOOL match(Expr *e, int a); 255*0Sstevel@tonic-gate static BOOL first_lit(Positionset *fpos, Expr *e); 256*0Sstevel@tonic-gate static void eptr(re_re *r, Expr *e); 257*0Sstevel@tonic-gate static void efollow(re_re *r, Positionset *fpos, Expr *e); 258*0Sstevel@tonic-gate static void follow(Positionset *fpos, Expr *e); 259*0Sstevel@tonic-gate static void followstate(re_re *r, State *s, int a, Positionset *fpos); 260*0Sstevel@tonic-gate static Expr *eall(re_re *r, PATTERN *pat); 261*0Sstevel@tonic-gate static Expr *d0(re_re *r, PATTERN *pat); 262*0Sstevel@tonic-gate static Expr *d1(re_re *r, PATTERN *pat); 263*0Sstevel@tonic-gate static Expr *d2(re_re *r, PATTERN *pat); 264*0Sstevel@tonic-gate static Expr *d3(re_re *r, PATTERN *pat); 265*0Sstevel@tonic-gate static Expr *newexpr(Exprtype t, int lit, Expr *left, Expr *right); 266*0Sstevel@tonic-gate static void lex(re_re *r, PATTERN *pat); 267*0Sstevel@tonic-gate static int re_lit(PATTERN *pat, uchar_t **b, uchar_t **e); 268*0Sstevel@tonic-gate static void traverse(PATTERN *pat, Expr *e); 269*0Sstevel@tonic-gate static int ccl(PATTERN *pat, uchar_t *tab); 270*0Sstevel@tonic-gate static BOOL altlist(), word(); 271*0Sstevel@tonic-gate static BOOL altlist(Expr *e, uchar_t *buf, re_cw *pat); 272*0Sstevel@tonic-gate static Node *newnode(re_cw *c, int d); 273*0Sstevel@tonic-gate static Link *newlink(uchar_t lit, Node *n); 274*0Sstevel@tonic-gate static void fail(Node *root); 275*0Sstevel@tonic-gate static void zeroroot(Node *root, Node *n); 276*0Sstevel@tonic-gate static void shift(re_cw *c); 277*0Sstevel@tonic-gate static void shifttab(Node *n); 278*0Sstevel@tonic-gate static void shiftprop(re_cw *c, Node *n); 279*0Sstevel@tonic-gate static void delta_2(re_bm *b); 280*0Sstevel@tonic-gate static int getstate(re_re *r, Positionset *ps); 281*0Sstevel@tonic-gate static void savestate(re_re *r); 282*0Sstevel@tonic-gate static void stateinit(re_re *r); 283*0Sstevel@tonic-gate static re_bm *re_bmcomp(uchar_t *pb, uchar_t *pe, uchar_t *cmap); 284*0Sstevel@tonic-gate static re_cw *re_cwinit(uchar_t *cmap); 285*0Sstevel@tonic-gate static re_cw *re_recw(re_re *r, uchar_t *map); 286*0Sstevel@tonic-gate static re_re *egprep(PATTERN *pat); 287*0Sstevel@tonic-gate static void re_cwadd(re_cw *c, uchar_t *s, uchar_t *e); 288*0Sstevel@tonic-gate static void re_cwcomp(re_cw *c); 289*0Sstevel@tonic-gate static void eginit(re_re *r); 290*0Sstevel@tonic-gate static BOOL re_bmexec(PATTERN *pat, uchar_t *s, uchar_t *e, uchar_t **mb, 291*0Sstevel@tonic-gate uchar_t **me); 292*0Sstevel@tonic-gate static BOOL re_cwexec(PATTERN *pat, uchar_t *rs, uchar_t *re, uchar_t **mb, 293*0Sstevel@tonic-gate uchar_t **me); 294*0Sstevel@tonic-gate static BOOL re_reexec(PATTERN *pat, uchar_t *b, uchar_t *e, uchar_t **mb, 295*0Sstevel@tonic-gate uchar_t **me); 296*0Sstevel@tonic-gate static uchar_t *egmalloc(size_t n); 297*0Sstevel@tonic-gate static void fgetfile(LINE *cur_ptr); 298*0Sstevel@tonic-gate static void dogre(PATTERN *pat); 299*0Sstevel@tonic-gate static BOOL pattern_match(PATTERN *pat, LINE *lptr); 300*0Sstevel@tonic-gate static BOOL fixloc(uchar_t **mb, uchar_t **me); 301*0Sstevel@tonic-gate static BOOL grepmatch(PATTERN *pat, uchar_t **mb, uchar_t **me); 302*0Sstevel@tonic-gate static void err(char *s); 303*0Sstevel@tonic-gate 304*0Sstevel@tonic-gate static char *message; 305*0Sstevel@tonic-gate 306*0Sstevel@tonic-gate void 307*0Sstevel@tonic-gate egrepcaseless(int i) 308*0Sstevel@tonic-gate { 309*0Sstevel@tonic-gate iflag = i; /* simulate "egrep -i" */ 310*0Sstevel@tonic-gate } 311*0Sstevel@tonic-gate 312*0Sstevel@tonic-gate char * 313*0Sstevel@tonic-gate egrepinit(char *expression) 314*0Sstevel@tonic-gate { 315*0Sstevel@tonic-gate static int firsttime = 1; 316*0Sstevel@tonic-gate int i; 317*0Sstevel@tonic-gate 318*0Sstevel@tonic-gate if (firsttime) { 319*0Sstevel@tonic-gate firsttime = 0; 320*0Sstevel@tonic-gate for (i = 0; i < 256; i++) { 321*0Sstevel@tonic-gate char_map[0][i] = (uchar_t)i; 322*0Sstevel@tonic-gate char_map[1][i] = tolower(i); 323*0Sstevel@tonic-gate } 324*0Sstevel@tonic-gate } 325*0Sstevel@tonic-gate for (i = 0; i < nmalloc; i ++) 326*0Sstevel@tonic-gate free(mallocs[i]); 327*0Sstevel@tonic-gate nmalloc = 0; 328*0Sstevel@tonic-gate message = NULL; 329*0Sstevel@tonic-gate 330*0Sstevel@tonic-gate match_pattern.expression = (uchar_t *)expression; 331*0Sstevel@tonic-gate match_pattern.cmap = char_map[iflag]; 332*0Sstevel@tonic-gate if (setjmp(env) == 0) { 333*0Sstevel@tonic-gate dogre(&match_pattern); 334*0Sstevel@tonic-gate #ifdef DEBUG 335*0Sstevel@tonic-gate { 336*0Sstevel@tonic-gate PATTERN *p = match_pattern; 337*0Sstevel@tonic-gate if (p->procfn == re_bmexec) 338*0Sstevel@tonic-gate if (!p->fullmatch) 339*0Sstevel@tonic-gate if (p->succfn == re_reexec) 340*0Sstevel@tonic-gate printf("PARTIAL BOYER_MOORE\n"); 341*0Sstevel@tonic-gate else 342*0Sstevel@tonic-gate printf("PARTIAL B_M with GREP\n"); 343*0Sstevel@tonic-gate else 344*0Sstevel@tonic-gate printf("FULL BOYER_MOORE\n"); 345*0Sstevel@tonic-gate else if (p->procfn == re_cwexec) 346*0Sstevel@tonic-gate printf("C_W\n"); 347*0Sstevel@tonic-gate else 348*0Sstevel@tonic-gate printf("GENERAL\n"); 349*0Sstevel@tonic-gate } 350*0Sstevel@tonic-gate #endif 351*0Sstevel@tonic-gate } 352*0Sstevel@tonic-gate return (message); 353*0Sstevel@tonic-gate } 354*0Sstevel@tonic-gate 355*0Sstevel@tonic-gate static void 356*0Sstevel@tonic-gate dogre(PATTERN *pat) 357*0Sstevel@tonic-gate { 358*0Sstevel@tonic-gate uchar_t *lb, *le; 359*0Sstevel@tonic-gate 360*0Sstevel@tonic-gate #ifdef DEBUG 361*0Sstevel@tonic-gate printf("PATTERN %s\n", pat->expression); 362*0Sstevel@tonic-gate #endif 363*0Sstevel@tonic-gate pat->re_ptr = egprep(pat); 364*0Sstevel@tonic-gate bestlen = re_lit(pat, &lb, &le); 365*0Sstevel@tonic-gate 366*0Sstevel@tonic-gate if (bestlen && pat->fullmatch) { /* Full Boyer Moore */ 367*0Sstevel@tonic-gate #ifdef DEBUG 368*0Sstevel@tonic-gate printf("BESTLEN %d\n", bestlen); 369*0Sstevel@tonic-gate { 370*0Sstevel@tonic-gate uchar_t *p; 371*0Sstevel@tonic-gate for (p = lb; p < le; p++) printf("%c", *p); 372*0Sstevel@tonic-gate printf("\n"); 373*0Sstevel@tonic-gate } 374*0Sstevel@tonic-gate #endif 375*0Sstevel@tonic-gate pat->bm_ptr = re_bmcomp(lb, le, pat->cmap); 376*0Sstevel@tonic-gate pat->procfn = re_bmexec; 377*0Sstevel@tonic-gate return; 378*0Sstevel@tonic-gate } 379*0Sstevel@tonic-gate if (bestlen > 1) { 380*0Sstevel@tonic-gate /* Partial Boyer Moore */ 381*0Sstevel@tonic-gate pat->bm_ptr = re_bmcomp(lb, le, pat->cmap); 382*0Sstevel@tonic-gate pat->procfn = re_bmexec; 383*0Sstevel@tonic-gate pat->fullmatch = NO; 384*0Sstevel@tonic-gate } else { 385*0Sstevel@tonic-gate pat->fullmatch = YES; 386*0Sstevel@tonic-gate if ((pat->cw_ptr = re_recw(pat->re_ptr, pat->cmap)) != NULL) { 387*0Sstevel@tonic-gate pat->procfn = re_cwexec; /* CW */ 388*0Sstevel@tonic-gate return; 389*0Sstevel@tonic-gate } 390*0Sstevel@tonic-gate } 391*0Sstevel@tonic-gate /* general egrep regular expression */ 392*0Sstevel@tonic-gate pat->succfn = re_reexec; 393*0Sstevel@tonic-gate 394*0Sstevel@tonic-gate if (pat->fullmatch) { 395*0Sstevel@tonic-gate pat->procfn = pat->succfn; 396*0Sstevel@tonic-gate pat->succfn = NULL; 397*0Sstevel@tonic-gate } 398*0Sstevel@tonic-gate } 399*0Sstevel@tonic-gate 400*0Sstevel@tonic-gate static BOOL 401*0Sstevel@tonic-gate fixloc(uchar_t **mb, uchar_t **me) 402*0Sstevel@tonic-gate { 403*0Sstevel@tonic-gate /* Handle match to null string */ 404*0Sstevel@tonic-gate 405*0Sstevel@tonic-gate while (*me <= *mb) 406*0Sstevel@tonic-gate (*me)++; 407*0Sstevel@tonic-gate 408*0Sstevel@tonic-gate if (*(*me - 1) != NL) 409*0Sstevel@tonic-gate while (**me != NL) 410*0Sstevel@tonic-gate (*me)++; 411*0Sstevel@tonic-gate 412*0Sstevel@tonic-gate /* Handle match to new-line only */ 413*0Sstevel@tonic-gate 414*0Sstevel@tonic-gate if (*mb == *me - 1 && **mb == NL) { 415*0Sstevel@tonic-gate (*me)++; 416*0Sstevel@tonic-gate } 417*0Sstevel@tonic-gate 418*0Sstevel@tonic-gate /* Handle match including beginning or ending new-line */ 419*0Sstevel@tonic-gate 420*0Sstevel@tonic-gate if (**mb == NL) 421*0Sstevel@tonic-gate (*mb)++; 422*0Sstevel@tonic-gate if (*(*me - 1) == NL) 423*0Sstevel@tonic-gate (*me)--; 424*0Sstevel@tonic-gate return (YES); 425*0Sstevel@tonic-gate } 426*0Sstevel@tonic-gate 427*0Sstevel@tonic-gate static BOOL 428*0Sstevel@tonic-gate grepmatch(PATTERN *pat, uchar_t **mb, uchar_t **me) 429*0Sstevel@tonic-gate { 430*0Sstevel@tonic-gate uchar_t *s, *f; 431*0Sstevel@tonic-gate 432*0Sstevel@tonic-gate if (pat->fullmatch) 433*0Sstevel@tonic-gate return (fixloc(mb, me)); 434*0Sstevel@tonic-gate 435*0Sstevel@tonic-gate for (f = *me - 1; *f != NL; f++) { 436*0Sstevel@tonic-gate } 437*0Sstevel@tonic-gate f++; 438*0Sstevel@tonic-gate for (s = *mb; *s != NL; s--) { 439*0Sstevel@tonic-gate } 440*0Sstevel@tonic-gate 441*0Sstevel@tonic-gate if ((*pat->succfn)(pat, s, f, mb, me)) { 442*0Sstevel@tonic-gate return (YES); 443*0Sstevel@tonic-gate } else { 444*0Sstevel@tonic-gate *mb = f; 445*0Sstevel@tonic-gate return (NO); 446*0Sstevel@tonic-gate } 447*0Sstevel@tonic-gate } 448*0Sstevel@tonic-gate 449*0Sstevel@tonic-gate static void 450*0Sstevel@tonic-gate eginit(re_re *r) 451*0Sstevel@tonic-gate { 452*0Sstevel@tonic-gate unsigned int n; 453*0Sstevel@tonic-gate 454*0Sstevel@tonic-gate r->ptr = (Expr **)egmalloc(r->maxid * sizeof (Expr *)); 455*0Sstevel@tonic-gate eptr(r, r->root); 456*0Sstevel@tonic-gate n = r->maxid * sizeof (FID); 457*0Sstevel@tonic-gate r->firstpos.base = (FID *)egmalloc(n); 458*0Sstevel@tonic-gate r->tmp.base = (FID *)egmalloc(n); 459*0Sstevel@tonic-gate CLEAR(r, &r->firstpos); 460*0Sstevel@tonic-gate if (!first_lit(&r->firstpos, r->root->l)) { 461*0Sstevel@tonic-gate /* 462*0Sstevel@tonic-gate * This expression matches the null string!!!! 463*0Sstevel@tonic-gate * Add EOP to beginning position set. 464*0Sstevel@tonic-gate */ 465*0Sstevel@tonic-gate SET(&r->firstpos, r->root->id, 0) 466*0Sstevel@tonic-gate /* (void) printf("first of root->l == 0, b=%s\n", b); */ 467*0Sstevel@tonic-gate } 468*0Sstevel@tonic-gate stateinit(r); 469*0Sstevel@tonic-gate (void) addstate(r, &r->firstpos, 0); 470*0Sstevel@tonic-gate savestate(r); 471*0Sstevel@tonic-gate } 472*0Sstevel@tonic-gate 473*0Sstevel@tonic-gate static void 474*0Sstevel@tonic-gate eptr(re_re *r, Expr *e) 475*0Sstevel@tonic-gate { 476*0Sstevel@tonic-gate if ((e->id < 0) || (e->id >= r->maxid)) { 477*0Sstevel@tonic-gate err("internal error"); 478*0Sstevel@tonic-gate } 479*0Sstevel@tonic-gate r->ptr[e->id] = e; 480*0Sstevel@tonic-gate if (e->type != Charclass) { 481*0Sstevel@tonic-gate if (e->l) eptr(r, e->l); 482*0Sstevel@tonic-gate if (e->r) eptr(r, e->r); 483*0Sstevel@tonic-gate } 484*0Sstevel@tonic-gate } 485*0Sstevel@tonic-gate 486*0Sstevel@tonic-gate static BOOL 487*0Sstevel@tonic-gate re_reexec(PATTERN *pat, uchar_t *b, uchar_t *e, uchar_t **mb, uchar_t **me) 488*0Sstevel@tonic-gate { 489*0Sstevel@tonic-gate re_re *r = pat->re_ptr; 490*0Sstevel@tonic-gate State *s, *t; 491*0Sstevel@tonic-gate 492*0Sstevel@tonic-gate #ifdef DEBUG 493*0Sstevel@tonic-gate if (TRACE(10)) { 494*0Sstevel@tonic-gate uchar_t buf[EPRINTSIZE]; 495*0Sstevel@tonic-gate epr(r->root, buf); 496*0Sstevel@tonic-gate (void) printf("expr='%s'\n", buf); 497*0Sstevel@tonic-gate } 498*0Sstevel@tonic-gate #endif 499*0Sstevel@tonic-gate s = startstate(r); 500*0Sstevel@tonic-gate 501*0Sstevel@tonic-gate for (;;) { 502*0Sstevel@tonic-gate uchar_t c; 503*0Sstevel@tonic-gate 504*0Sstevel@tonic-gate if (s->cnt >= 0) { 505*0Sstevel@tonic-gate #ifdef DEBUG 506*0Sstevel@tonic-gate if (TRACE(6)) 507*0Sstevel@tonic-gate (void) printf("match at input '%s'\n", b); 508*0Sstevel@tonic-gate #endif 509*0Sstevel@tonic-gate *mb = b - s->cnt; 510*0Sstevel@tonic-gate *me = b; 511*0Sstevel@tonic-gate if (fixloc(mb, me)) 512*0Sstevel@tonic-gate return (YES); 513*0Sstevel@tonic-gate } 514*0Sstevel@tonic-gate 515*0Sstevel@tonic-gate if (b >= e) break; 516*0Sstevel@tonic-gate c = pat->cmap[*b]; 517*0Sstevel@tonic-gate #ifdef DEBUG 518*0Sstevel@tonic-gate if (TRACE(4)) 519*0Sstevel@tonic-gate (void) printf("state %d: char '%c'\n", s-r->states, *b); 520*0Sstevel@tonic-gate #endif 521*0Sstevel@tonic-gate if ((t = s->tab[c]) != NULL) s = t; 522*0Sstevel@tonic-gate else s = nextstate(r, s, (int)c); 523*0Sstevel@tonic-gate b++; 524*0Sstevel@tonic-gate } 525*0Sstevel@tonic-gate #ifdef DEBUG 526*0Sstevel@tonic-gate if (TRACE(3)) { 527*0Sstevel@tonic-gate uchar_t buf[EPRINTSIZE]; 528*0Sstevel@tonic-gate 529*0Sstevel@tonic-gate epr(r->root, buf); 530*0Sstevel@tonic-gate (void) printf("pat = %s\n", buf); 531*0Sstevel@tonic-gate } 532*0Sstevel@tonic-gate #endif 533*0Sstevel@tonic-gate return (NO); 534*0Sstevel@tonic-gate } 535*0Sstevel@tonic-gate 536*0Sstevel@tonic-gate static BOOL 537*0Sstevel@tonic-gate match(Expr *e, int a) 538*0Sstevel@tonic-gate { 539*0Sstevel@tonic-gate switch (e->type) { 540*0Sstevel@tonic-gate case Dot: return ((BOOL)(a != NL)); 541*0Sstevel@tonic-gate case Literal: return ((BOOL)(a == e->lit)); 542*0Sstevel@tonic-gate case Charclass: return ((BOOL)(CCL_CHK((uchar_t *)e->r, a))); 543*0Sstevel@tonic-gate default: return (NO); 544*0Sstevel@tonic-gate } 545*0Sstevel@tonic-gate } 546*0Sstevel@tonic-gate 547*0Sstevel@tonic-gate /* 548*0Sstevel@tonic-gate * generates the followset for a node in fpos 549*0Sstevel@tonic-gate */ 550*0Sstevel@tonic-gate static void 551*0Sstevel@tonic-gate follow(Positionset *fpos, Expr *e) 552*0Sstevel@tonic-gate { 553*0Sstevel@tonic-gate Expr *p; 554*0Sstevel@tonic-gate 555*0Sstevel@tonic-gate if (e->type == EOP) 556*0Sstevel@tonic-gate return; 557*0Sstevel@tonic-gate else 558*0Sstevel@tonic-gate p = e->parent; 559*0Sstevel@tonic-gate switch (p->type) { 560*0Sstevel@tonic-gate case EOP: 561*0Sstevel@tonic-gate SET(fpos, p->id, 0) 562*0Sstevel@tonic-gate break; 563*0Sstevel@tonic-gate case Plus: 564*0Sstevel@tonic-gate case Star: 565*0Sstevel@tonic-gate (void) first_lit(fpos, e); 566*0Sstevel@tonic-gate follow(fpos, p); 567*0Sstevel@tonic-gate break; 568*0Sstevel@tonic-gate case Quest: 569*0Sstevel@tonic-gate case Alternate: 570*0Sstevel@tonic-gate follow(fpos, p); 571*0Sstevel@tonic-gate break; 572*0Sstevel@tonic-gate case Cat: 573*0Sstevel@tonic-gate if (e == p->r || !first_lit(fpos, p->r)) 574*0Sstevel@tonic-gate follow(fpos, p); 575*0Sstevel@tonic-gate break; 576*0Sstevel@tonic-gate default: 577*0Sstevel@tonic-gate break; 578*0Sstevel@tonic-gate } 579*0Sstevel@tonic-gate } 580*0Sstevel@tonic-gate 581*0Sstevel@tonic-gate /* 582*0Sstevel@tonic-gate * first_lit returns NO if e is nullable and in the process, 583*0Sstevel@tonic-gate * ets up fpos. 584*0Sstevel@tonic-gate */ 585*0Sstevel@tonic-gate static BOOL 586*0Sstevel@tonic-gate first_lit(Positionset *fpos, Expr *e) 587*0Sstevel@tonic-gate { 588*0Sstevel@tonic-gate BOOL k; 589*0Sstevel@tonic-gate 590*0Sstevel@tonic-gate switch (e->type) { 591*0Sstevel@tonic-gate case Literal: 592*0Sstevel@tonic-gate case Dot: 593*0Sstevel@tonic-gate case Charclass: 594*0Sstevel@tonic-gate SET(fpos, e->id, 0) 595*0Sstevel@tonic-gate return (YES); 596*0Sstevel@tonic-gate case EOP: 597*0Sstevel@tonic-gate case Star: 598*0Sstevel@tonic-gate case Quest: 599*0Sstevel@tonic-gate (void) first_lit(fpos, e->l); 600*0Sstevel@tonic-gate return (NO); 601*0Sstevel@tonic-gate case Plus: 602*0Sstevel@tonic-gate return (first_lit(fpos, e->l)); 603*0Sstevel@tonic-gate case Cat: 604*0Sstevel@tonic-gate return ((BOOL)(first_lit(fpos, e->l) || first_lit(fpos, e->r))); 605*0Sstevel@tonic-gate case Alternate: 606*0Sstevel@tonic-gate k = first_lit(fpos, e->r); 607*0Sstevel@tonic-gate return ((BOOL)(first_lit(fpos, e->l) && k)); 608*0Sstevel@tonic-gate default: 609*0Sstevel@tonic-gate err("internal error"); 610*0Sstevel@tonic-gate } 611*0Sstevel@tonic-gate return (NO); 612*0Sstevel@tonic-gate } 613*0Sstevel@tonic-gate 614*0Sstevel@tonic-gate static void 615*0Sstevel@tonic-gate efollow(re_re *r, Positionset *fpos, Expr *e) 616*0Sstevel@tonic-gate { 617*0Sstevel@tonic-gate ID i, *p; 618*0Sstevel@tonic-gate 619*0Sstevel@tonic-gate CLEAR(r, fpos); 620*0Sstevel@tonic-gate follow(fpos, e); 621*0Sstevel@tonic-gate e->flen = fpos->count; 622*0Sstevel@tonic-gate e->follow = (ID *)egmalloc(e->flen * sizeof (ID)); 623*0Sstevel@tonic-gate p = e->follow; 624*0Sstevel@tonic-gate #ifdef DEBUG 625*0Sstevel@tonic-gate printf("ID = %d LIT %c FLEN = %d\n", e->id, e->lit, e->flen); 626*0Sstevel@tonic-gate #endif 627*0Sstevel@tonic-gate for (i = fpos->last; i > 0; i = fpos->base[i].id) { 628*0Sstevel@tonic-gate *p++ = i; 629*0Sstevel@tonic-gate #ifdef DEBUG 630*0Sstevel@tonic-gate printf("FOLLOW ID = %d LIT %c\n", r->ptr[i]->id, r->ptr[i]->lit); 631*0Sstevel@tonic-gate #endif 632*0Sstevel@tonic-gate } 633*0Sstevel@tonic-gate if (p != e->follow + e->flen) { 634*0Sstevel@tonic-gate err("internal error"); 635*0Sstevel@tonic-gate } 636*0Sstevel@tonic-gate } 637*0Sstevel@tonic-gate 638*0Sstevel@tonic-gate static State * 639*0Sstevel@tonic-gate addstate(re_re *r, Positionset *ps, int cnt) 640*0Sstevel@tonic-gate { 641*0Sstevel@tonic-gate ID j; 642*0Sstevel@tonic-gate FID *p, *q; 643*0Sstevel@tonic-gate State *s; 644*0Sstevel@tonic-gate 645*0Sstevel@tonic-gate if (cnt) { 646*0Sstevel@tonic-gate s = r->states + getstate(r, ps); 647*0Sstevel@tonic-gate (void) memset((char *)s->tab, 0, sizeof (s->tab)); 648*0Sstevel@tonic-gate s->cnt = r->istate.cnt; 649*0Sstevel@tonic-gate } else { 650*0Sstevel@tonic-gate s = &r->istate; 651*0Sstevel@tonic-gate s->cnt = -1; 652*0Sstevel@tonic-gate } 653*0Sstevel@tonic-gate s->pos = r->posnext; 654*0Sstevel@tonic-gate r->posnext += ps->count; 655*0Sstevel@tonic-gate s->npos = ps->count; 656*0Sstevel@tonic-gate p = r->posbase + s->pos; 657*0Sstevel@tonic-gate for (j = ps->last; j > 0; p++, j = q->id) { 658*0Sstevel@tonic-gate q = &ps->base[j]; 659*0Sstevel@tonic-gate p->id = j; 660*0Sstevel@tonic-gate p->fcount = q->fcount; 661*0Sstevel@tonic-gate if (p->id == r->root->id && s->cnt < p->fcount) 662*0Sstevel@tonic-gate s->cnt = p->fcount; 663*0Sstevel@tonic-gate } 664*0Sstevel@tonic-gate #ifdef DEBUG 665*0Sstevel@tonic-gate if (TRACE(3)) { 666*0Sstevel@tonic-gate uchar_t buf[2000]; 667*0Sstevel@tonic-gate spr(s->npos, s->pos+r->posbase, buf); 668*0Sstevel@tonic-gate (void) printf("new state[%d] %s%s\n", s-r->states, buf, 669*0Sstevel@tonic-gate s->cnt?" cnt":""); 670*0Sstevel@tonic-gate } 671*0Sstevel@tonic-gate #endif 672*0Sstevel@tonic-gate return (s); 673*0Sstevel@tonic-gate } 674*0Sstevel@tonic-gate 675*0Sstevel@tonic-gate static State * 676*0Sstevel@tonic-gate nextstate(re_re *r, State *s, int a) 677*0Sstevel@tonic-gate { 678*0Sstevel@tonic-gate State *news; 679*0Sstevel@tonic-gate 680*0Sstevel@tonic-gate CLEAR(r, &r->tmp); 681*0Sstevel@tonic-gate followstate(r, s, a, &r->tmp); 682*0Sstevel@tonic-gate if (s != &r->istate) followstate(r, &r->istate, a, &r->tmp); 683*0Sstevel@tonic-gate 684*0Sstevel@tonic-gate #ifdef DEBUG 685*0Sstevel@tonic-gate if (TRACE(5)) { 686*0Sstevel@tonic-gate uchar_t buf[2000]; 687*0Sstevel@tonic-gate ppr(&r->tmp, buf); 688*0Sstevel@tonic-gate (void) printf("nextstate(%d, '%c'): found %s\n", s-r->states, 689*0Sstevel@tonic-gate a, buf); 690*0Sstevel@tonic-gate } 691*0Sstevel@tonic-gate #endif 692*0Sstevel@tonic-gate if (r->tmp.count == 0) 693*0Sstevel@tonic-gate news = &r->istate; 694*0Sstevel@tonic-gate else if ((news = stateof(r, &r->tmp)) == NULL) 695*0Sstevel@tonic-gate news = addstate(r, &r->tmp, 1); 696*0Sstevel@tonic-gate s->tab[a] = news; 697*0Sstevel@tonic-gate #ifdef DEBUG 698*0Sstevel@tonic-gate if (TRACE(5)) { 699*0Sstevel@tonic-gate (void) printf("nextstate(%d, '%c'): returning %ld\n", 700*0Sstevel@tonic-gate s-r->states, a, news); 701*0Sstevel@tonic-gate } 702*0Sstevel@tonic-gate #endif 703*0Sstevel@tonic-gate return (news); 704*0Sstevel@tonic-gate } 705*0Sstevel@tonic-gate 706*0Sstevel@tonic-gate static void 707*0Sstevel@tonic-gate followstate(re_re *r, State *s, int a, Positionset *fpos) 708*0Sstevel@tonic-gate { 709*0Sstevel@tonic-gate int j; 710*0Sstevel@tonic-gate ID *q, *eq; 711*0Sstevel@tonic-gate Expr *e; 712*0Sstevel@tonic-gate 713*0Sstevel@tonic-gate for (j = s->pos; j < (s->pos + s->npos); j++) { 714*0Sstevel@tonic-gate e = r->ptr[r->posbase[j].id]; 715*0Sstevel@tonic-gate if (e->type == EOP) continue; 716*0Sstevel@tonic-gate if (match(e, a)) { 717*0Sstevel@tonic-gate if (e->follow == NULL) efollow(r, &r->firstpos, e); 718*0Sstevel@tonic-gate for (q = e->follow, eq = q + e->flen; q < eq; q++) { 719*0Sstevel@tonic-gate SET(fpos, *q, r->posbase[j].fcount + 1) 720*0Sstevel@tonic-gate #ifdef DEBUG 721*0Sstevel@tonic-gate printf("CHAR %c FC %c COUNT %d\n", 722*0Sstevel@tonic-gate a, 723*0Sstevel@tonic-gate r->ptr[*q]->lit, 724*0Sstevel@tonic-gate r->posbase[j].fcount+1); 725*0Sstevel@tonic-gate #endif 726*0Sstevel@tonic-gate } 727*0Sstevel@tonic-gate } 728*0Sstevel@tonic-gate } 729*0Sstevel@tonic-gate } 730*0Sstevel@tonic-gate 731*0Sstevel@tonic-gate static uchar_t * 732*0Sstevel@tonic-gate egmalloc(size_t n) 733*0Sstevel@tonic-gate { 734*0Sstevel@tonic-gate uchar_t *x; 735*0Sstevel@tonic-gate 736*0Sstevel@tonic-gate x = (uchar_t *)mymalloc(n); 737*0Sstevel@tonic-gate mallocs[nmalloc++] = x; 738*0Sstevel@tonic-gate if (nmalloc >= MAXMALLOCS) 739*0Sstevel@tonic-gate nmalloc = MAXMALLOCS - 1; 740*0Sstevel@tonic-gate return (x); 741*0Sstevel@tonic-gate } 742*0Sstevel@tonic-gate 743*0Sstevel@tonic-gate #ifdef DEBUG 744*0Sstevel@tonic-gate void 745*0Sstevel@tonic-gate ppr(Positionse *ps, char *p) 746*0Sstevel@tonic-gate { 747*0Sstevel@tonic-gate ID n; 748*0Sstevel@tonic-gate 749*0Sstevel@tonic-gate if (ps->count < 1) { 750*0Sstevel@tonic-gate (void) sprintf(p, "{}"); 751*0Sstevel@tonic-gate return; 752*0Sstevel@tonic-gate } 753*0Sstevel@tonic-gate *p++ = '{'; 754*0Sstevel@tonic-gate for (n = ps->last; n > 0; n = ps->base[n].id) { 755*0Sstevel@tonic-gate (void) sprintf(p, "%d,", n); 756*0Sstevel@tonic-gate p = strchr(p, 0); 757*0Sstevel@tonic-gate } 758*0Sstevel@tonic-gate p[-1] = '}'; 759*0Sstevel@tonic-gate } 760*0Sstevel@tonic-gate 761*0Sstevel@tonic-gate void 762*0Sstevel@tonic-gate epr(Expr *e, uchar_t *res) 763*0Sstevel@tonic-gate { 764*0Sstevel@tonic-gate uchar_t r1[EPRINTSIZE], r2[EPRINTSIZE]; 765*0Sstevel@tonic-gate int i; 766*0Sstevel@tonic-gate 767*0Sstevel@tonic-gate if (e == NULL) { 768*0Sstevel@tonic-gate (void) sprintf(res, "!0!"); 769*0Sstevel@tonic-gate return; 770*0Sstevel@tonic-gate } 771*0Sstevel@tonic-gate switch (e->type) { 772*0Sstevel@tonic-gate case Dot: 773*0Sstevel@tonic-gate case Literal: 774*0Sstevel@tonic-gate spr(e->flen, e->follow, r1); 775*0Sstevel@tonic-gate (void) sprintf(res, "%c%s", e->lit, r1); 776*0Sstevel@tonic-gate break; 777*0Sstevel@tonic-gate case Charclass: 778*0Sstevel@tonic-gate *res++ = '['; 779*0Sstevel@tonic-gate for (i = 0; i < 256; i++) 780*0Sstevel@tonic-gate if (CCL_CHK((uchar_t *)e->r, i)) { 781*0Sstevel@tonic-gate *res++ = i; 782*0Sstevel@tonic-gate } 783*0Sstevel@tonic-gate *res++ = ']'; 784*0Sstevel@tonic-gate *res = '\0'; 785*0Sstevel@tonic-gate break; 786*0Sstevel@tonic-gate case Cat: 787*0Sstevel@tonic-gate epr(e->l, r1); 788*0Sstevel@tonic-gate epr(e->r, r2); 789*0Sstevel@tonic-gate (void) sprintf(res, "%s%s", r1, r2); 790*0Sstevel@tonic-gate break; 791*0Sstevel@tonic-gate case Alternate: 792*0Sstevel@tonic-gate epr(e->l, r1); 793*0Sstevel@tonic-gate epr(e->r, r2); 794*0Sstevel@tonic-gate (void) sprintf(res, "(%s|%s)", r1, r2); 795*0Sstevel@tonic-gate break; 796*0Sstevel@tonic-gate case Star: 797*0Sstevel@tonic-gate epr(e->l, r1); 798*0Sstevel@tonic-gate (void) sprintf(res, "(%s)*", r1); 799*0Sstevel@tonic-gate break; 800*0Sstevel@tonic-gate case Plus: 801*0Sstevel@tonic-gate epr(e->l, r1); 802*0Sstevel@tonic-gate (void) sprintf(res, "(%s)+", r1); 803*0Sstevel@tonic-gate break; 804*0Sstevel@tonic-gate case Quest: 805*0Sstevel@tonic-gate epr(e->l, r1); 806*0Sstevel@tonic-gate (void) sprintf(res, "(%s)?", r1); 807*0Sstevel@tonic-gate break; 808*0Sstevel@tonic-gate case EOP: 809*0Sstevel@tonic-gate epr(e->l, r1); 810*0Sstevel@tonic-gate (void) sprintf(res, "%s<EOP>", r1); 811*0Sstevel@tonic-gate break; 812*0Sstevel@tonic-gate default: 813*0Sstevel@tonic-gate (void) sprintf(res, "<undef type %d>", e->type); 814*0Sstevel@tonic-gate err(res); 815*0Sstevel@tonic-gate break; 816*0Sstevel@tonic-gate } 817*0Sstevel@tonic-gate } 818*0Sstevel@tonic-gate 819*0Sstevel@tonic-gate static void 820*0Sstevel@tonic-gate spr(int c, int *p, uchar_t *buf) 821*0Sstevel@tonic-gate { 822*0Sstevel@tonic-gate if (c > 0) { 823*0Sstevel@tonic-gate *buf++ = '{'; 824*0Sstevel@tonic-gate *buf = '\0'; 825*0Sstevel@tonic-gate while (--c > 0) { 826*0Sstevel@tonic-gate (void) sprintf(buf, "%d,", *p++); 827*0Sstevel@tonic-gate buf = strchr(buf, 0); 828*0Sstevel@tonic-gate } 829*0Sstevel@tonic-gate (void) sprintf(buf, "%d}", *p); 830*0Sstevel@tonic-gate } else 831*0Sstevel@tonic-gate (void) sprintf(buf, "{}"); 832*0Sstevel@tonic-gate } 833*0Sstevel@tonic-gate #endif 834*0Sstevel@tonic-gate 835*0Sstevel@tonic-gate static void 836*0Sstevel@tonic-gate stateinit(re_re *r) 837*0Sstevel@tonic-gate { 838*0Sstevel@tonic-gate /* CONSTANTCONDITION */ 839*0Sstevel@tonic-gate r->statelim = (sizeof (int) < 4 ? 32 : 128); 840*0Sstevel@tonic-gate r->states = (State *)egmalloc(r->statelim * sizeof (State)); 841*0Sstevel@tonic-gate 842*0Sstevel@tonic-gate /* CONSTANTCONDITION */ 843*0Sstevel@tonic-gate r->nposalloc = (sizeof (int) < 4 ? 2048 : 8192); 844*0Sstevel@tonic-gate r->posbase = (FID *)egmalloc(r->nposalloc * sizeof (FID)); 845*0Sstevel@tonic-gate r->nstates = r->posnext = 0; 846*0Sstevel@tonic-gate } 847*0Sstevel@tonic-gate 848*0Sstevel@tonic-gate static void 849*0Sstevel@tonic-gate clrstates(re_re *r) 850*0Sstevel@tonic-gate { 851*0Sstevel@tonic-gate r->nstates = 0; /* reclaim space for states and positions */ 852*0Sstevel@tonic-gate r->posnext = r->posreset; 853*0Sstevel@tonic-gate (void) memset((char *)r->istate.tab, 0, sizeof (r->istate.tab)); 854*0Sstevel@tonic-gate } 855*0Sstevel@tonic-gate 856*0Sstevel@tonic-gate static void 857*0Sstevel@tonic-gate savestate(re_re *r) 858*0Sstevel@tonic-gate { 859*0Sstevel@tonic-gate r->posreset = r->posnext; /* save for reset */ 860*0Sstevel@tonic-gate } 861*0Sstevel@tonic-gate 862*0Sstevel@tonic-gate static State * 863*0Sstevel@tonic-gate startstate(re_re *r) 864*0Sstevel@tonic-gate { 865*0Sstevel@tonic-gate return (&r->istate); 866*0Sstevel@tonic-gate } 867*0Sstevel@tonic-gate 868*0Sstevel@tonic-gate static int 869*0Sstevel@tonic-gate getstate(re_re *r, Positionset *ps) 870*0Sstevel@tonic-gate { 871*0Sstevel@tonic-gate if (r->nstates >= r->statelim || 872*0Sstevel@tonic-gate r->posnext + ps->count >= r->nposalloc) { 873*0Sstevel@tonic-gate clrstates(r); 874*0Sstevel@tonic-gate #ifdef DEBUG 875*0Sstevel@tonic-gate printf("%d STATES FLUSHED\n", r->statelim); 876*0Sstevel@tonic-gate #endif 877*0Sstevel@tonic-gate } 878*0Sstevel@tonic-gate return (r->nstates++); 879*0Sstevel@tonic-gate } 880*0Sstevel@tonic-gate 881*0Sstevel@tonic-gate static State * 882*0Sstevel@tonic-gate stateof(re_re *r, Positionset *ps) 883*0Sstevel@tonic-gate { 884*0Sstevel@tonic-gate State *s; 885*0Sstevel@tonic-gate int i; 886*0Sstevel@tonic-gate FID *p, *e; 887*0Sstevel@tonic-gate 888*0Sstevel@tonic-gate for (i = 0, s = r->states; i < r->nstates; i++, s++) { 889*0Sstevel@tonic-gate if (s->npos == ps->count) { 890*0Sstevel@tonic-gate for (p = s->pos+r->posbase, e = p+s->npos; p < e; p++) 891*0Sstevel@tonic-gate if (ps->base[p->id].id == 0 || 892*0Sstevel@tonic-gate ps->base[p->id].fcount != p->fcount) 893*0Sstevel@tonic-gate goto next; 894*0Sstevel@tonic-gate return (s); 895*0Sstevel@tonic-gate } 896*0Sstevel@tonic-gate next:; 897*0Sstevel@tonic-gate } 898*0Sstevel@tonic-gate return (NULL); 899*0Sstevel@tonic-gate } 900*0Sstevel@tonic-gate 901*0Sstevel@tonic-gate static re_re * 902*0Sstevel@tonic-gate egprep(PATTERN *pat) 903*0Sstevel@tonic-gate { 904*0Sstevel@tonic-gate re_re *r; 905*0Sstevel@tonic-gate 906*0Sstevel@tonic-gate r = (re_re *)egmalloc(sizeof (re_re)); 907*0Sstevel@tonic-gate (void) memset((char *)r, 0, sizeof (re_re)); 908*0Sstevel@tonic-gate 909*0Sstevel@tonic-gate pat->loc1 = pat->expression; 910*0Sstevel@tonic-gate pat->loc2 = pat->expression + strlen((char *)pat->expression); 911*0Sstevel@tonic-gate 912*0Sstevel@tonic-gate parno = 0; 913*0Sstevel@tonic-gate maxid = 1; 914*0Sstevel@tonic-gate r->cmap = pat->cmap; 915*0Sstevel@tonic-gate lex(r, pat); 916*0Sstevel@tonic-gate r->root = newexpr(EOP, '#', eall(r, pat), (Expr *)NULL); 917*0Sstevel@tonic-gate r->maxid = maxid; 918*0Sstevel@tonic-gate 919*0Sstevel@tonic-gate eginit(r); 920*0Sstevel@tonic-gate return (r); 921*0Sstevel@tonic-gate } 922*0Sstevel@tonic-gate 923*0Sstevel@tonic-gate static Expr * 924*0Sstevel@tonic-gate newexpr(Exprtype t, int lit, Expr *left, Expr *right) 925*0Sstevel@tonic-gate { 926*0Sstevel@tonic-gate Expr *e = (Expr *)egmalloc(sizeof (Expr)); 927*0Sstevel@tonic-gate 928*0Sstevel@tonic-gate e->type = t; 929*0Sstevel@tonic-gate e->parent = NULL; 930*0Sstevel@tonic-gate e->lit = lit; 931*0Sstevel@tonic-gate 932*0Sstevel@tonic-gate if (e->lit) e->id = maxid++; 933*0Sstevel@tonic-gate else e->id = 0; 934*0Sstevel@tonic-gate 935*0Sstevel@tonic-gate if ((e->l = left) != NULL) { 936*0Sstevel@tonic-gate left->parent = e; 937*0Sstevel@tonic-gate } 938*0Sstevel@tonic-gate if ((e->r = right) != NULL) { 939*0Sstevel@tonic-gate right->parent = e; 940*0Sstevel@tonic-gate } 941*0Sstevel@tonic-gate e->follow = NULL; 942*0Sstevel@tonic-gate e->flen = 0; 943*0Sstevel@tonic-gate return (e); 944*0Sstevel@tonic-gate } 945*0Sstevel@tonic-gate 946*0Sstevel@tonic-gate static void 947*0Sstevel@tonic-gate lex(re_re *r, PATTERN *pat) 948*0Sstevel@tonic-gate { 949*0Sstevel@tonic-gate if (pat->loc1 == pat->loc2) { 950*0Sstevel@tonic-gate toktype = EOP; 951*0Sstevel@tonic-gate toklit = -1; 952*0Sstevel@tonic-gate } else switch (toklit = *pat->loc1++) { 953*0Sstevel@tonic-gate case '.': toktype = Dot; break; 954*0Sstevel@tonic-gate case '*': toktype = Star; break; 955*0Sstevel@tonic-gate case '+': toktype = Plus; break; 956*0Sstevel@tonic-gate case '?': toktype = Quest; break; 957*0Sstevel@tonic-gate case '[': toktype = Charclass; break; 958*0Sstevel@tonic-gate case '|': toktype = Alternate; break; 959*0Sstevel@tonic-gate case '(': toktype = Lpar; break; 960*0Sstevel@tonic-gate case ')': toktype = Rpar; break; 961*0Sstevel@tonic-gate case '\\': toktype = Backslash; 962*0Sstevel@tonic-gate if (pat->loc1 == pat->loc2) { 963*0Sstevel@tonic-gate err("syntax error - missing character " 964*0Sstevel@tonic-gate "after \\"); 965*0Sstevel@tonic-gate } else 966*0Sstevel@tonic-gate toklit = r->cmap[*pat->loc1++]; 967*0Sstevel@tonic-gate break; 968*0Sstevel@tonic-gate case '^': case '$': toktype = Literal; toklit = NL; break; 969*0Sstevel@tonic-gate default: toktype = Literal; toklit = r->cmap[toklit]; break; 970*0Sstevel@tonic-gate } 971*0Sstevel@tonic-gate } 972*0Sstevel@tonic-gate 973*0Sstevel@tonic-gate static int 974*0Sstevel@tonic-gate ccl(PATTERN *pat, uchar_t *tab) 975*0Sstevel@tonic-gate { 976*0Sstevel@tonic-gate int i; 977*0Sstevel@tonic-gate int range = 0; 978*0Sstevel@tonic-gate int lastc = -1; 979*0Sstevel@tonic-gate int count = 0; 980*0Sstevel@tonic-gate BOOL comp = NO; 981*0Sstevel@tonic-gate 982*0Sstevel@tonic-gate (void) memset((char *)tab, 0, CCL_SIZ * sizeof (uchar_t)); 983*0Sstevel@tonic-gate if (*pat->loc1 == '^') { 984*0Sstevel@tonic-gate pat->loc1++; 985*0Sstevel@tonic-gate comp = YES; 986*0Sstevel@tonic-gate } 987*0Sstevel@tonic-gate if (*pat->loc1 == ']') { 988*0Sstevel@tonic-gate uchar_t c = pat->cmap[*pat->loc1]; 989*0Sstevel@tonic-gate CCL_SET(tab, c); 990*0Sstevel@tonic-gate lastc = *pat->loc1++; 991*0Sstevel@tonic-gate } 992*0Sstevel@tonic-gate /* scan for chars */ 993*0Sstevel@tonic-gate for (; (pat->loc1 < pat->loc2) && (*pat->loc1 != ']'); 994*0Sstevel@tonic-gate pat->loc1++) { 995*0Sstevel@tonic-gate if (*pat->loc1 == '-') { 996*0Sstevel@tonic-gate if (lastc < 0) CCL_SET(tab, pat->cmap['-']); 997*0Sstevel@tonic-gate else range = 1; 998*0Sstevel@tonic-gate continue; 999*0Sstevel@tonic-gate } 1000*0Sstevel@tonic-gate if (range) { 1001*0Sstevel@tonic-gate for (i = *pat->loc1; i >= lastc; i--) { 1002*0Sstevel@tonic-gate CCL_SET(tab, pat->cmap[i]); 1003*0Sstevel@tonic-gate } 1004*0Sstevel@tonic-gate } else { 1005*0Sstevel@tonic-gate uchar_t c = pat->cmap[*pat->loc1]; 1006*0Sstevel@tonic-gate CCL_SET(tab, c); 1007*0Sstevel@tonic-gate } 1008*0Sstevel@tonic-gate 1009*0Sstevel@tonic-gate range = 0; 1010*0Sstevel@tonic-gate 1011*0Sstevel@tonic-gate lastc = *pat->loc1; 1012*0Sstevel@tonic-gate } 1013*0Sstevel@tonic-gate if (range) CCL_SET(tab, pat->cmap['-']); 1014*0Sstevel@tonic-gate 1015*0Sstevel@tonic-gate if (pat->loc1 < pat->loc2) pat->loc1++; 1016*0Sstevel@tonic-gate else err("syntax error - missing ]"); 1017*0Sstevel@tonic-gate 1018*0Sstevel@tonic-gate if (comp) { 1019*0Sstevel@tonic-gate CCL_SET(tab, pat->cmap[NL]); 1020*0Sstevel@tonic-gate for (i = 0; i < CCL_SIZ; i++) tab[i] ^= 0xff; 1021*0Sstevel@tonic-gate } 1022*0Sstevel@tonic-gate for (i = 0; i < 256; i++) { 1023*0Sstevel@tonic-gate if (pat->cmap[i] != i) CCL_CLR(tab, i); 1024*0Sstevel@tonic-gate if (CCL_CHK(tab, i)) { 1025*0Sstevel@tonic-gate lastc = i; 1026*0Sstevel@tonic-gate count++; 1027*0Sstevel@tonic-gate } 1028*0Sstevel@tonic-gate } 1029*0Sstevel@tonic-gate if (count == 1) 1030*0Sstevel@tonic-gate *tab = (char)lastc; 1031*0Sstevel@tonic-gate return (count); 1032*0Sstevel@tonic-gate } 1033*0Sstevel@tonic-gate 1034*0Sstevel@tonic-gate /* 1035*0Sstevel@tonic-gate * egrep patterns: 1036*0Sstevel@tonic-gate * 1037*0Sstevel@tonic-gate * Alternation: d0: d1 { '|' d1 }* 1038*0Sstevel@tonic-gate * Concatenation: d1: d2 { d2 }* 1039*0Sstevel@tonic-gate * Repetition: d2: d3 { '*' | '?' | '+' } 1040*0Sstevel@tonic-gate * Literal: d3: lit | '.' | '[]' | '(' d0 ')' 1041*0Sstevel@tonic-gate */ 1042*0Sstevel@tonic-gate 1043*0Sstevel@tonic-gate static Expr * 1044*0Sstevel@tonic-gate d3(re_re *r, PATTERN *pat) 1045*0Sstevel@tonic-gate { 1046*0Sstevel@tonic-gate Expr *e; 1047*0Sstevel@tonic-gate uchar_t *tab; 1048*0Sstevel@tonic-gate int count; 1049*0Sstevel@tonic-gate 1050*0Sstevel@tonic-gate switch (toktype) { 1051*0Sstevel@tonic-gate case Backslash: 1052*0Sstevel@tonic-gate case Literal: 1053*0Sstevel@tonic-gate e = newexpr(Literal, toklit, (Expr *)NULL, (Expr *)NULL); 1054*0Sstevel@tonic-gate lex(r, pat); 1055*0Sstevel@tonic-gate break; 1056*0Sstevel@tonic-gate case Dot: 1057*0Sstevel@tonic-gate e = newexpr(Dot, '.', (Expr *)NULL, (Expr *)NULL); 1058*0Sstevel@tonic-gate lex(r, pat); 1059*0Sstevel@tonic-gate break; 1060*0Sstevel@tonic-gate case Charclass: 1061*0Sstevel@tonic-gate tab = egmalloc(CCL_SIZ * sizeof (uchar_t)); 1062*0Sstevel@tonic-gate count = ccl(pat, tab); 1063*0Sstevel@tonic-gate if (count == 1) { 1064*0Sstevel@tonic-gate toklit = *tab; 1065*0Sstevel@tonic-gate e = newexpr(Literal, toklit, (Expr *)NULL, 1066*0Sstevel@tonic-gate (Expr *)NULL); 1067*0Sstevel@tonic-gate } else { 1068*0Sstevel@tonic-gate e = newexpr(Charclass, '[', (Expr *)NULL, (Expr *)NULL); 1069*0Sstevel@tonic-gate e->l = (Expr *)count; /* number of chars */ 1070*0Sstevel@tonic-gate e->r = (Expr *)tab; /* bitmap of chars */ 1071*0Sstevel@tonic-gate } 1072*0Sstevel@tonic-gate lex(r, pat); 1073*0Sstevel@tonic-gate break; 1074*0Sstevel@tonic-gate case Lpar: 1075*0Sstevel@tonic-gate lex(r, pat); 1076*0Sstevel@tonic-gate count = ++parno; 1077*0Sstevel@tonic-gate e = d0(r, pat); 1078*0Sstevel@tonic-gate if (toktype == Rpar) 1079*0Sstevel@tonic-gate lex(r, pat); 1080*0Sstevel@tonic-gate else 1081*0Sstevel@tonic-gate err("syntax error - missing )"); 1082*0Sstevel@tonic-gate return (e); 1083*0Sstevel@tonic-gate default: 1084*0Sstevel@tonic-gate err("syntax error"); 1085*0Sstevel@tonic-gate e = NULL; 1086*0Sstevel@tonic-gate } 1087*0Sstevel@tonic-gate return (e); 1088*0Sstevel@tonic-gate } 1089*0Sstevel@tonic-gate 1090*0Sstevel@tonic-gate static Expr * 1091*0Sstevel@tonic-gate d2(re_re *r, PATTERN *pat) 1092*0Sstevel@tonic-gate { 1093*0Sstevel@tonic-gate Expr *e; 1094*0Sstevel@tonic-gate Exprtype t; 1095*0Sstevel@tonic-gate 1096*0Sstevel@tonic-gate e = d3(r, pat); 1097*0Sstevel@tonic-gate while ((toktype == Star) || (toktype == Plus) || (toktype == Quest)) { 1098*0Sstevel@tonic-gate t = toktype; 1099*0Sstevel@tonic-gate lex(r, pat); 1100*0Sstevel@tonic-gate e = newexpr(t, 0, e, (Expr *)NULL); 1101*0Sstevel@tonic-gate } 1102*0Sstevel@tonic-gate return (e); 1103*0Sstevel@tonic-gate } 1104*0Sstevel@tonic-gate 1105*0Sstevel@tonic-gate static Expr * 1106*0Sstevel@tonic-gate d1(re_re *r, PATTERN *pat) 1107*0Sstevel@tonic-gate { 1108*0Sstevel@tonic-gate Expr *e, *f; 1109*0Sstevel@tonic-gate 1110*0Sstevel@tonic-gate e = d2(r, pat); 1111*0Sstevel@tonic-gate while ((toktype == Literal) || (toktype == Dot) || (toktype == Lpar) || 1112*0Sstevel@tonic-gate (toktype == Backslash) || (toktype == Charclass)) { 1113*0Sstevel@tonic-gate f = d2(r, pat); 1114*0Sstevel@tonic-gate e = newexpr(Cat, 0, e, f); 1115*0Sstevel@tonic-gate } 1116*0Sstevel@tonic-gate return (e); 1117*0Sstevel@tonic-gate } 1118*0Sstevel@tonic-gate 1119*0Sstevel@tonic-gate static Expr * 1120*0Sstevel@tonic-gate d0(re_re *r, PATTERN *pat) 1121*0Sstevel@tonic-gate { 1122*0Sstevel@tonic-gate Expr *e, *f; 1123*0Sstevel@tonic-gate 1124*0Sstevel@tonic-gate e = d1(r, pat); 1125*0Sstevel@tonic-gate while (toktype == Alternate) { 1126*0Sstevel@tonic-gate lex(r, pat); 1127*0Sstevel@tonic-gate if (toktype == EOP) 1128*0Sstevel@tonic-gate continue; 1129*0Sstevel@tonic-gate f = d1(r, pat); 1130*0Sstevel@tonic-gate e = newexpr(Alternate, 0, e, f); 1131*0Sstevel@tonic-gate } 1132*0Sstevel@tonic-gate return (e); 1133*0Sstevel@tonic-gate } 1134*0Sstevel@tonic-gate 1135*0Sstevel@tonic-gate static Expr * 1136*0Sstevel@tonic-gate eall(re_re *r, PATTERN *pat) 1137*0Sstevel@tonic-gate { 1138*0Sstevel@tonic-gate Expr *e; 1139*0Sstevel@tonic-gate 1140*0Sstevel@tonic-gate while (toktype == Alternate) /* bogus but user-friendly */ 1141*0Sstevel@tonic-gate lex(r, pat); 1142*0Sstevel@tonic-gate e = d0(r, pat); 1143*0Sstevel@tonic-gate while (toktype == Alternate) /* bogus but user-friendly */ 1144*0Sstevel@tonic-gate lex(r, pat); 1145*0Sstevel@tonic-gate if (toktype != EOP) 1146*0Sstevel@tonic-gate err("syntax error"); 1147*0Sstevel@tonic-gate return (e); 1148*0Sstevel@tonic-gate } 1149*0Sstevel@tonic-gate 1150*0Sstevel@tonic-gate static void 1151*0Sstevel@tonic-gate err(char *s) 1152*0Sstevel@tonic-gate { 1153*0Sstevel@tonic-gate message = s; 1154*0Sstevel@tonic-gate longjmp(env, 1); 1155*0Sstevel@tonic-gate } 1156*0Sstevel@tonic-gate 1157*0Sstevel@tonic-gate static int 1158*0Sstevel@tonic-gate re_lit(PATTERN *pat, uchar_t **b, uchar_t **e) 1159*0Sstevel@tonic-gate { 1160*0Sstevel@tonic-gate bestlen = 0; 1161*0Sstevel@tonic-gate pat->fullmatch = YES; 1162*0Sstevel@tonic-gate START 1163*0Sstevel@tonic-gate traverse(pat, pat->re_ptr->root->l); 1164*0Sstevel@tonic-gate FINISH 1165*0Sstevel@tonic-gate if (bestlen < 2) 1166*0Sstevel@tonic-gate return (0); 1167*0Sstevel@tonic-gate *b = egmalloc(bestlen * sizeof (uchar_t)); 1168*0Sstevel@tonic-gate (void) memmove(*b, best, bestlen); 1169*0Sstevel@tonic-gate *e = *b + bestlen - 1; 1170*0Sstevel@tonic-gate return (bestlen - 1); 1171*0Sstevel@tonic-gate } 1172*0Sstevel@tonic-gate 1173*0Sstevel@tonic-gate static void 1174*0Sstevel@tonic-gate traverse(PATTERN *pat, Expr *e) 1175*0Sstevel@tonic-gate { 1176*0Sstevel@tonic-gate switch (e->type) { 1177*0Sstevel@tonic-gate case Literal: 1178*0Sstevel@tonic-gate ADDL(e->lit) 1179*0Sstevel@tonic-gate break; 1180*0Sstevel@tonic-gate case Cat: 1181*0Sstevel@tonic-gate traverse(pat, e->l); 1182*0Sstevel@tonic-gate traverse(pat, e->r); 1183*0Sstevel@tonic-gate break; 1184*0Sstevel@tonic-gate case Plus: 1185*0Sstevel@tonic-gate traverse(pat, e->l); 1186*0Sstevel@tonic-gate FINISH /* can't go on past a + */ 1187*0Sstevel@tonic-gate pat->fullmatch = NO; 1188*0Sstevel@tonic-gate START /* but we can start with one! */ 1189*0Sstevel@tonic-gate traverse(pat, e->l); 1190*0Sstevel@tonic-gate break; 1191*0Sstevel@tonic-gate default: 1192*0Sstevel@tonic-gate FINISH 1193*0Sstevel@tonic-gate pat->fullmatch = NO; 1194*0Sstevel@tonic-gate START 1195*0Sstevel@tonic-gate break; 1196*0Sstevel@tonic-gate } 1197*0Sstevel@tonic-gate } 1198*0Sstevel@tonic-gate 1199*0Sstevel@tonic-gate static re_bm * 1200*0Sstevel@tonic-gate re_bmcomp(uchar_t *pb, uchar_t *pe, uchar_t *cmap) 1201*0Sstevel@tonic-gate { 1202*0Sstevel@tonic-gate int j; 1203*0Sstevel@tonic-gate int delta[256]; 1204*0Sstevel@tonic-gate re_bm *b; 1205*0Sstevel@tonic-gate 1206*0Sstevel@tonic-gate b = (re_bm *)egmalloc(sizeof (*b)); 1207*0Sstevel@tonic-gate 1208*0Sstevel@tonic-gate b->patlen = pe - pb; 1209*0Sstevel@tonic-gate b->cmap = cmap; 1210*0Sstevel@tonic-gate b->bmpat = pb; 1211*0Sstevel@tonic-gate 1212*0Sstevel@tonic-gate delta_2(b); 1213*0Sstevel@tonic-gate 1214*0Sstevel@tonic-gate for (j = 0; j < 256; j++) 1215*0Sstevel@tonic-gate delta[j] = b->patlen; 1216*0Sstevel@tonic-gate 1217*0Sstevel@tonic-gate for (pe--; pb < pe; pb++) 1218*0Sstevel@tonic-gate delta[b->cmap[*pb]] = pe - pb; 1219*0Sstevel@tonic-gate 1220*0Sstevel@tonic-gate delta[b->cmap[*pb]] = LARGE; 1221*0Sstevel@tonic-gate 1222*0Sstevel@tonic-gate for (j = 0; j < 256; j++) 1223*0Sstevel@tonic-gate b->delta0[j] = delta[b->cmap[j]]; 1224*0Sstevel@tonic-gate return (b); 1225*0Sstevel@tonic-gate } 1226*0Sstevel@tonic-gate 1227*0Sstevel@tonic-gate static void 1228*0Sstevel@tonic-gate delta_2(re_bm *b) 1229*0Sstevel@tonic-gate { 1230*0Sstevel@tonic-gate int m = b->patlen; 1231*0Sstevel@tonic-gate int i, k, j; 1232*0Sstevel@tonic-gate 1233*0Sstevel@tonic-gate b->delta2 = (int *)egmalloc(m * sizeof (int)); 1234*0Sstevel@tonic-gate 1235*0Sstevel@tonic-gate for (j = 0; j < m; j++) { 1236*0Sstevel@tonic-gate k = 1; 1237*0Sstevel@tonic-gate again: 1238*0Sstevel@tonic-gate while (k <= j && b->bmpat[j-k] == b->bmpat[j]) k++; 1239*0Sstevel@tonic-gate 1240*0Sstevel@tonic-gate for (i = j + 1; i < m; i++) { 1241*0Sstevel@tonic-gate if (k <= i && b->bmpat[i-k] != b->bmpat[i]) { 1242*0Sstevel@tonic-gate k++; 1243*0Sstevel@tonic-gate goto again; 1244*0Sstevel@tonic-gate } 1245*0Sstevel@tonic-gate } 1246*0Sstevel@tonic-gate b->delta2[j] = k + m - j - 1; 1247*0Sstevel@tonic-gate } 1248*0Sstevel@tonic-gate } 1249*0Sstevel@tonic-gate 1250*0Sstevel@tonic-gate static BOOL 1251*0Sstevel@tonic-gate re_bmexec(PATTERN *pat, uchar_t *s, uchar_t *e, uchar_t **mb, uchar_t **me) 1252*0Sstevel@tonic-gate { 1253*0Sstevel@tonic-gate re_bm *b = pat->bm_ptr; 1254*0Sstevel@tonic-gate uchar_t *sp; 1255*0Sstevel@tonic-gate int k; 1256*0Sstevel@tonic-gate 1257*0Sstevel@tonic-gate s += b->patlen - 1; 1258*0Sstevel@tonic-gate while ((unsigned long)s < (unsigned long)e) { 1259*0Sstevel@tonic-gate while ((unsigned long)(s += b->delta0[*s]) < (unsigned long)e) 1260*0Sstevel@tonic-gate ; 1261*0Sstevel@tonic-gate if ((unsigned long)s < (unsigned long)(e + b->patlen)) 1262*0Sstevel@tonic-gate return (NO); /* no match */ 1263*0Sstevel@tonic-gate s -= LARGE; 1264*0Sstevel@tonic-gate for (k = b->patlen-2, sp = s-1; k >= 0; k--) { 1265*0Sstevel@tonic-gate if (b->cmap[*sp--] != b->bmpat[k]) break; 1266*0Sstevel@tonic-gate } 1267*0Sstevel@tonic-gate if (k < 0) { 1268*0Sstevel@tonic-gate *mb = ++sp; 1269*0Sstevel@tonic-gate *me = s+1; 1270*0Sstevel@tonic-gate if (grepmatch(pat, mb, me)) 1271*0Sstevel@tonic-gate return (YES); 1272*0Sstevel@tonic-gate s = *mb; 1273*0Sstevel@tonic-gate } else if (k < 0) { 1274*0Sstevel@tonic-gate s++; 1275*0Sstevel@tonic-gate } else { 1276*0Sstevel@tonic-gate int j; 1277*0Sstevel@tonic-gate j = b->delta2[k]; 1278*0Sstevel@tonic-gate k = b->delta0[*++sp]; 1279*0Sstevel@tonic-gate if ((j > k) || (k == (int)LARGE)) 1280*0Sstevel@tonic-gate k = j; 1281*0Sstevel@tonic-gate s = sp + k; 1282*0Sstevel@tonic-gate } 1283*0Sstevel@tonic-gate } 1284*0Sstevel@tonic-gate return (NO); 1285*0Sstevel@tonic-gate } 1286*0Sstevel@tonic-gate 1287*0Sstevel@tonic-gate static re_cw * 1288*0Sstevel@tonic-gate re_recw(re_re *r, uchar_t *map) 1289*0Sstevel@tonic-gate { 1290*0Sstevel@tonic-gate Expr *e, *root = r->root; 1291*0Sstevel@tonic-gate re_cw *pat; 1292*0Sstevel@tonic-gate uchar_t *buf; 1293*0Sstevel@tonic-gate 1294*0Sstevel@tonic-gate if (root->type != EOP) 1295*0Sstevel@tonic-gate return (NULL); 1296*0Sstevel@tonic-gate e = root->l; 1297*0Sstevel@tonic-gate pat = re_cwinit(map); 1298*0Sstevel@tonic-gate buf = (uchar_t *)egmalloc(20000 * sizeof (uchar_t)); 1299*0Sstevel@tonic-gate if (!altlist(e, buf, pat)) { 1300*0Sstevel@tonic-gate return (NULL); 1301*0Sstevel@tonic-gate } 1302*0Sstevel@tonic-gate re_cwcomp(pat); 1303*0Sstevel@tonic-gate return (pat); 1304*0Sstevel@tonic-gate } 1305*0Sstevel@tonic-gate 1306*0Sstevel@tonic-gate static BOOL 1307*0Sstevel@tonic-gate altlist(Expr *e, uchar_t *buf, re_cw *pat) 1308*0Sstevel@tonic-gate { 1309*0Sstevel@tonic-gate if (e->type == Alternate) 1310*0Sstevel@tonic-gate return ((BOOL)(altlist(e->l, buf, pat) && 1311*0Sstevel@tonic-gate altlist(e->r, buf, pat))); 1312*0Sstevel@tonic-gate return (word(e, buf, pat)); 1313*0Sstevel@tonic-gate } 1314*0Sstevel@tonic-gate 1315*0Sstevel@tonic-gate static BOOL 1316*0Sstevel@tonic-gate word(Expr *e, uchar_t *buf, re_cw *pat) 1317*0Sstevel@tonic-gate { 1318*0Sstevel@tonic-gate static uchar_t *p; 1319*0Sstevel@tonic-gate 1320*0Sstevel@tonic-gate if (buf) p = buf; 1321*0Sstevel@tonic-gate 1322*0Sstevel@tonic-gate if (e->type == Cat) { 1323*0Sstevel@tonic-gate if (!word(e->l, (uchar_t *)NULL, pat)) 1324*0Sstevel@tonic-gate return (NO); 1325*0Sstevel@tonic-gate if (!word(e->r, (uchar_t *)NULL, pat)) 1326*0Sstevel@tonic-gate return (NO); 1327*0Sstevel@tonic-gate } else if (e->type == Literal) 1328*0Sstevel@tonic-gate *p++ = e->lit; 1329*0Sstevel@tonic-gate else 1330*0Sstevel@tonic-gate return (NO); 1331*0Sstevel@tonic-gate 1332*0Sstevel@tonic-gate if (buf) 1333*0Sstevel@tonic-gate re_cwadd(pat, buf, p); 1334*0Sstevel@tonic-gate return (YES); 1335*0Sstevel@tonic-gate } 1336*0Sstevel@tonic-gate 1337*0Sstevel@tonic-gate static re_cw * 1338*0Sstevel@tonic-gate re_cwinit(uchar_t *cmap) 1339*0Sstevel@tonic-gate { 1340*0Sstevel@tonic-gate re_cw *c; 1341*0Sstevel@tonic-gate 1342*0Sstevel@tonic-gate froot = NULL; 1343*0Sstevel@tonic-gate next_node = NULL; 1344*0Sstevel@tonic-gate next_link = NULL; 1345*0Sstevel@tonic-gate c = (re_cw *)egmalloc(sizeof (*c)); 1346*0Sstevel@tonic-gate c->nodeid = 0; 1347*0Sstevel@tonic-gate c->maxdepth = 0; 1348*0Sstevel@tonic-gate c->mindepth = 10000; 1349*0Sstevel@tonic-gate c->root = newnode(c, 0); 1350*0Sstevel@tonic-gate c->cmap = cmap; 1351*0Sstevel@tonic-gate return (c); 1352*0Sstevel@tonic-gate } 1353*0Sstevel@tonic-gate 1354*0Sstevel@tonic-gate static void 1355*0Sstevel@tonic-gate re_cwadd(re_cw *c, uchar_t *s, uchar_t *e) 1356*0Sstevel@tonic-gate { 1357*0Sstevel@tonic-gate Node *p, *state; 1358*0Sstevel@tonic-gate Link *l; 1359*0Sstevel@tonic-gate int depth; 1360*0Sstevel@tonic-gate 1361*0Sstevel@tonic-gate state = c->root; 1362*0Sstevel@tonic-gate while (s <= --e) { 1363*0Sstevel@tonic-gate for (l = state->alts; l; l = l->next) 1364*0Sstevel@tonic-gate if (l->lit == *e) 1365*0Sstevel@tonic-gate break; 1366*0Sstevel@tonic-gate if (l == NULL) 1367*0Sstevel@tonic-gate break; 1368*0Sstevel@tonic-gate else 1369*0Sstevel@tonic-gate state = l->node; 1370*0Sstevel@tonic-gate } 1371*0Sstevel@tonic-gate if (s <= e) { 1372*0Sstevel@tonic-gate depth = state->d+1; 1373*0Sstevel@tonic-gate l = newlink(*e--, p = newnode(c, depth++)); 1374*0Sstevel@tonic-gate l->next = state->alts; 1375*0Sstevel@tonic-gate state->alts = l; 1376*0Sstevel@tonic-gate state = p; 1377*0Sstevel@tonic-gate while (s <= e) { 1378*0Sstevel@tonic-gate state->alts = newlink(*e--, p = newnode(c, depth++)); 1379*0Sstevel@tonic-gate state = p; 1380*0Sstevel@tonic-gate } 1381*0Sstevel@tonic-gate if (c->mindepth >= depth) c->mindepth = depth-1; 1382*0Sstevel@tonic-gate } 1383*0Sstevel@tonic-gate state->out = 1; 1384*0Sstevel@tonic-gate } 1385*0Sstevel@tonic-gate 1386*0Sstevel@tonic-gate #ifdef DEBUG 1387*0Sstevel@tonic-gate static 1388*0Sstevel@tonic-gate pr(Node *n) 1389*0Sstevel@tonic-gate { 1390*0Sstevel@tonic-gate Link *l; 1391*0Sstevel@tonic-gate 1392*0Sstevel@tonic-gate printf("%d[%d,%d]: ", n->id, n->shift1, n->shift2); 1393*0Sstevel@tonic-gate for (l = n->alts; l; l = l->next) { 1394*0Sstevel@tonic-gate printf("edge from \"%d\" to \"%d\" label {\"%c\"};", 1395*0Sstevel@tonic-gate n->id, l->node->id, l->lit); 1396*0Sstevel@tonic-gate if (l->node->out) { 1397*0Sstevel@tonic-gate printf(" draw \"%d\" as Doublecircle;", l->node->id); 1398*0Sstevel@tonic-gate } 1399*0Sstevel@tonic-gate if (l->node->fail) { 1400*0Sstevel@tonic-gate printf(" edge from \"%d\" to \"%d\" dashed;", 1401*0Sstevel@tonic-gate l->node->id, l->node->fail->id); 1402*0Sstevel@tonic-gate } 1403*0Sstevel@tonic-gate printf("\n"); 1404*0Sstevel@tonic-gate pr(l->node); 1405*0Sstevel@tonic-gate } 1406*0Sstevel@tonic-gate } 1407*0Sstevel@tonic-gate #endif 1408*0Sstevel@tonic-gate 1409*0Sstevel@tonic-gate static void 1410*0Sstevel@tonic-gate fail(Node *root) 1411*0Sstevel@tonic-gate { 1412*0Sstevel@tonic-gate Link *qhead = NULL, *qtail = NULL; 1413*0Sstevel@tonic-gate Link *l, *ll; 1414*0Sstevel@tonic-gate Link *t; 1415*0Sstevel@tonic-gate Node *state, *r, *s; 1416*0Sstevel@tonic-gate int a; 1417*0Sstevel@tonic-gate 1418*0Sstevel@tonic-gate for (l = root->alts; l; l = l->next) { 1419*0Sstevel@tonic-gate ADD(l->node); 1420*0Sstevel@tonic-gate l->node->fail = root; 1421*0Sstevel@tonic-gate } 1422*0Sstevel@tonic-gate while (qhead) { 1423*0Sstevel@tonic-gate r = qhead->node; 1424*0Sstevel@tonic-gate DEL(); 1425*0Sstevel@tonic-gate for (l = r->alts; l; l = l->next) { 1426*0Sstevel@tonic-gate s = l->node; 1427*0Sstevel@tonic-gate a = l->lit; 1428*0Sstevel@tonic-gate ADD(s); 1429*0Sstevel@tonic-gate state = r->fail; 1430*0Sstevel@tonic-gate while (state) { 1431*0Sstevel@tonic-gate for (ll = state->alts; ll; ll = ll->next) 1432*0Sstevel@tonic-gate if (ll->lit == a) 1433*0Sstevel@tonic-gate break; 1434*0Sstevel@tonic-gate if (ll || (state == root)) { 1435*0Sstevel@tonic-gate if (ll) 1436*0Sstevel@tonic-gate state = ll->node; 1437*0Sstevel@tonic-gate /* 1438*0Sstevel@tonic-gate * do it here as only other exit is 1439*0Sstevel@tonic-gate * state 0 1440*0Sstevel@tonic-gate */ 1441*0Sstevel@tonic-gate if (state->out) { 1442*0Sstevel@tonic-gate s->out = 1; 1443*0Sstevel@tonic-gate } 1444*0Sstevel@tonic-gate break; 1445*0Sstevel@tonic-gate } else 1446*0Sstevel@tonic-gate state = state->fail; 1447*0Sstevel@tonic-gate } 1448*0Sstevel@tonic-gate s->fail = state; 1449*0Sstevel@tonic-gate } 1450*0Sstevel@tonic-gate } 1451*0Sstevel@tonic-gate zeroroot(root, root); 1452*0Sstevel@tonic-gate } 1453*0Sstevel@tonic-gate 1454*0Sstevel@tonic-gate static void 1455*0Sstevel@tonic-gate zeroroot(Node *root, Node *n) 1456*0Sstevel@tonic-gate { 1457*0Sstevel@tonic-gate Link *l; 1458*0Sstevel@tonic-gate 1459*0Sstevel@tonic-gate if (n->fail == root) 1460*0Sstevel@tonic-gate n->fail = NULL; 1461*0Sstevel@tonic-gate for (l = n->alts; l; l = l->next) 1462*0Sstevel@tonic-gate zeroroot(root, l->node); 1463*0Sstevel@tonic-gate } 1464*0Sstevel@tonic-gate 1465*0Sstevel@tonic-gate static void 1466*0Sstevel@tonic-gate shift(re_cw *c) 1467*0Sstevel@tonic-gate { 1468*0Sstevel@tonic-gate Link *qhead = NULL, *qtail = NULL; 1469*0Sstevel@tonic-gate Link *l; 1470*0Sstevel@tonic-gate Link *t; 1471*0Sstevel@tonic-gate Node *state, *r, *s; 1472*0Sstevel@tonic-gate int k; 1473*0Sstevel@tonic-gate 1474*0Sstevel@tonic-gate for (k = 0; k < 256; k++) 1475*0Sstevel@tonic-gate c->step[k] = c->mindepth+1; 1476*0Sstevel@tonic-gate c->root->shift1 = 1; 1477*0Sstevel@tonic-gate c->root->shift2 = c->mindepth; 1478*0Sstevel@tonic-gate for (l = c->root->alts; l; l = l->next) { 1479*0Sstevel@tonic-gate l->node->shift2 = c->root->shift2; 1480*0Sstevel@tonic-gate ADD(l->node); 1481*0Sstevel@tonic-gate l->node->fail = NULL; 1482*0Sstevel@tonic-gate } 1483*0Sstevel@tonic-gate while (qhead) { 1484*0Sstevel@tonic-gate r = qhead->node; 1485*0Sstevel@tonic-gate DEL(); 1486*0Sstevel@tonic-gate r->shift1 = c->mindepth; 1487*0Sstevel@tonic-gate r->shift2 = c->mindepth; 1488*0Sstevel@tonic-gate if ((state = r->fail) != NULL) { 1489*0Sstevel@tonic-gate do { 1490*0Sstevel@tonic-gate k = r->d - state->d; 1491*0Sstevel@tonic-gate if (k < state->shift1) { 1492*0Sstevel@tonic-gate state->shift1 = k; 1493*0Sstevel@tonic-gate } 1494*0Sstevel@tonic-gate if (r->out && (k < state->shift2)) { 1495*0Sstevel@tonic-gate state->shift2 = k; 1496*0Sstevel@tonic-gate } 1497*0Sstevel@tonic-gate } while ((state = state->fail) != NULL); 1498*0Sstevel@tonic-gate } 1499*0Sstevel@tonic-gate for (l = r->alts; l; l = l->next) { 1500*0Sstevel@tonic-gate s = l->node; 1501*0Sstevel@tonic-gate ADD(s); 1502*0Sstevel@tonic-gate } 1503*0Sstevel@tonic-gate } 1504*0Sstevel@tonic-gate shiftprop(c, c->root); 1505*0Sstevel@tonic-gate shifttab(c->root); 1506*0Sstevel@tonic-gate c->step[0] = 1; 1507*0Sstevel@tonic-gate } 1508*0Sstevel@tonic-gate 1509*0Sstevel@tonic-gate static void 1510*0Sstevel@tonic-gate shifttab(Node *n) 1511*0Sstevel@tonic-gate { 1512*0Sstevel@tonic-gate Link *l; 1513*0Sstevel@tonic-gate Node **nn; 1514*0Sstevel@tonic-gate 1515*0Sstevel@tonic-gate n->tab = nn = (Node **)egmalloc(256 * sizeof (Node *)); 1516*0Sstevel@tonic-gate (void) memset((char *)n->tab, 0, 256 * sizeof (Node *)); 1517*0Sstevel@tonic-gate for (l = n->alts; l; l = l->next) 1518*0Sstevel@tonic-gate nn[l->lit] = l->node; 1519*0Sstevel@tonic-gate } 1520*0Sstevel@tonic-gate 1521*0Sstevel@tonic-gate static void 1522*0Sstevel@tonic-gate shiftprop(re_cw *c, Node *n) 1523*0Sstevel@tonic-gate { 1524*0Sstevel@tonic-gate Link *l; 1525*0Sstevel@tonic-gate Node *nn; 1526*0Sstevel@tonic-gate 1527*0Sstevel@tonic-gate for (l = n->alts; l; l = l->next) { 1528*0Sstevel@tonic-gate if (c->step[l->lit] > l->node->d) 1529*0Sstevel@tonic-gate c->step[l->lit] = l->node->d; 1530*0Sstevel@tonic-gate nn = l->node; 1531*0Sstevel@tonic-gate if (n->shift2 < nn->shift2) 1532*0Sstevel@tonic-gate nn->shift2 = n->shift2; 1533*0Sstevel@tonic-gate shiftprop(c, nn); 1534*0Sstevel@tonic-gate } 1535*0Sstevel@tonic-gate } 1536*0Sstevel@tonic-gate 1537*0Sstevel@tonic-gate static void 1538*0Sstevel@tonic-gate re_cwcomp(re_cw *c) 1539*0Sstevel@tonic-gate { 1540*0Sstevel@tonic-gate fail(c->root); 1541*0Sstevel@tonic-gate shift(c); 1542*0Sstevel@tonic-gate } 1543*0Sstevel@tonic-gate 1544*0Sstevel@tonic-gate static BOOL 1545*0Sstevel@tonic-gate re_cwexec(PATTERN *pat, uchar_t *rs, uchar_t *re, uchar_t **mb, uchar_t **me) 1546*0Sstevel@tonic-gate { 1547*0Sstevel@tonic-gate Node *state; 1548*0Sstevel@tonic-gate Link *l; 1549*0Sstevel@tonic-gate uchar_t *sp; 1550*0Sstevel@tonic-gate uchar_t *s; 1551*0Sstevel@tonic-gate uchar_t *e; 1552*0Sstevel@tonic-gate Node *ostate; 1553*0Sstevel@tonic-gate int k; 1554*0Sstevel@tonic-gate re_cw *c = pat->cw_ptr; 1555*0Sstevel@tonic-gate uchar_t fake[1]; 1556*0Sstevel@tonic-gate uchar_t mappedsp; 1557*0Sstevel@tonic-gate 1558*0Sstevel@tonic-gate fake[0] = 0; 1559*0Sstevel@tonic-gate state = c->root; 1560*0Sstevel@tonic-gate 1561*0Sstevel@tonic-gate s = rs+c->mindepth-1; 1562*0Sstevel@tonic-gate e = re; 1563*0Sstevel@tonic-gate while (s < e) { 1564*0Sstevel@tonic-gate /* scan */ 1565*0Sstevel@tonic-gate for (sp = s; (ostate = state) != NULL; ) { 1566*0Sstevel@tonic-gate mappedsp = c->cmap[*sp]; 1567*0Sstevel@tonic-gate if (state->tab) { 1568*0Sstevel@tonic-gate if ((state = state->tab[mappedsp]) == NULL) 1569*0Sstevel@tonic-gate goto nomatch; 1570*0Sstevel@tonic-gate } else { 1571*0Sstevel@tonic-gate for (l = state->alts; ; l = l->next) { 1572*0Sstevel@tonic-gate if (l == NULL) 1573*0Sstevel@tonic-gate goto nomatch; 1574*0Sstevel@tonic-gate if (l->lit == mappedsp) { 1575*0Sstevel@tonic-gate state = l->node; 1576*0Sstevel@tonic-gate break; 1577*0Sstevel@tonic-gate } 1578*0Sstevel@tonic-gate } 1579*0Sstevel@tonic-gate } 1580*0Sstevel@tonic-gate if (state->out) { 1581*0Sstevel@tonic-gate *mb = sp; 1582*0Sstevel@tonic-gate *me = s+1; 1583*0Sstevel@tonic-gate if (fixloc(mb, me)) 1584*0Sstevel@tonic-gate return (YES); 1585*0Sstevel@tonic-gate } 1586*0Sstevel@tonic-gate if (--sp < rs) { 1587*0Sstevel@tonic-gate sp = fake; 1588*0Sstevel@tonic-gate break; 1589*0Sstevel@tonic-gate } 1590*0Sstevel@tonic-gate } 1591*0Sstevel@tonic-gate nomatch: 1592*0Sstevel@tonic-gate k = c->step[c->cmap[*sp]] - ostate->d - 1; 1593*0Sstevel@tonic-gate if (k < ostate->shift1) 1594*0Sstevel@tonic-gate k = ostate->shift1; 1595*0Sstevel@tonic-gate if (k > ostate->shift2) 1596*0Sstevel@tonic-gate k = ostate->shift2; 1597*0Sstevel@tonic-gate s += k; 1598*0Sstevel@tonic-gate state = c->root; 1599*0Sstevel@tonic-gate } 1600*0Sstevel@tonic-gate return (NO); 1601*0Sstevel@tonic-gate } 1602*0Sstevel@tonic-gate 1603*0Sstevel@tonic-gate static Node * 1604*0Sstevel@tonic-gate newnode(re_cw *c, int d) 1605*0Sstevel@tonic-gate { 1606*0Sstevel@tonic-gate static Node *lim = NULL; 1607*0Sstevel@tonic-gate static int incr = 256; 1608*0Sstevel@tonic-gate 1609*0Sstevel@tonic-gate if (!next_node) lim = NULL; 1610*0Sstevel@tonic-gate if (next_node == lim) { 1611*0Sstevel@tonic-gate next_node = (Node *)egmalloc(incr * sizeof (Node)); 1612*0Sstevel@tonic-gate lim = next_node + incr; 1613*0Sstevel@tonic-gate } 1614*0Sstevel@tonic-gate next_node->d = d; 1615*0Sstevel@tonic-gate if (d > c->maxdepth) c->maxdepth = d; 1616*0Sstevel@tonic-gate next_node->id = c->nodeid++; 1617*0Sstevel@tonic-gate next_node->alts = NULL; 1618*0Sstevel@tonic-gate next_node->tab = NULL; 1619*0Sstevel@tonic-gate next_node->out = 0; 1620*0Sstevel@tonic-gate return (next_node++); 1621*0Sstevel@tonic-gate } 1622*0Sstevel@tonic-gate 1623*0Sstevel@tonic-gate static Link * 1624*0Sstevel@tonic-gate newlink(uchar_t lit, Node *n) 1625*0Sstevel@tonic-gate { 1626*0Sstevel@tonic-gate static Link *lim = NULL; 1627*0Sstevel@tonic-gate static int incr = 256; 1628*0Sstevel@tonic-gate 1629*0Sstevel@tonic-gate if (!next_link) lim = NULL; 1630*0Sstevel@tonic-gate if (next_link == lim) { 1631*0Sstevel@tonic-gate next_link = (Link *)egmalloc(incr * sizeof (Link)); 1632*0Sstevel@tonic-gate lim = next_link + incr; 1633*0Sstevel@tonic-gate } 1634*0Sstevel@tonic-gate next_link->lit = lit; 1635*0Sstevel@tonic-gate next_link->node = n; 1636*0Sstevel@tonic-gate next_link->next = NULL; 1637*0Sstevel@tonic-gate return (next_link++); 1638*0Sstevel@tonic-gate } 1639*0Sstevel@tonic-gate 1640*0Sstevel@tonic-gate int 1641*0Sstevel@tonic-gate egrep(char *f, FILE *o, char *fo) 1642*0Sstevel@tonic-gate { 1643*0Sstevel@tonic-gate uchar_t buff[MAXBUFSIZE + ESIZE]; 1644*0Sstevel@tonic-gate 1645*0Sstevel@tonic-gate buffer = buff; 1646*0Sstevel@tonic-gate *buffer++ = NL; /* New line precedes buffer to prevent runover */ 1647*0Sstevel@tonic-gate file = f; 1648*0Sstevel@tonic-gate output = o; 1649*0Sstevel@tonic-gate format = fo; 1650*0Sstevel@tonic-gate return (execute()); 1651*0Sstevel@tonic-gate } 1652*0Sstevel@tonic-gate 1653*0Sstevel@tonic-gate static int 1654*0Sstevel@tonic-gate execute(void) 1655*0Sstevel@tonic-gate { 1656*0Sstevel@tonic-gate LINE current; 1657*0Sstevel@tonic-gate BOOL matched; 1658*0Sstevel@tonic-gate BOOL all_searched; /* file being matched until end */ 1659*0Sstevel@tonic-gate 1660*0Sstevel@tonic-gate if ((file_desc = open(file, O_RDONLY)) < 0) { 1661*0Sstevel@tonic-gate return (-1); 1662*0Sstevel@tonic-gate } 1663*0Sstevel@tonic-gate init_file(¤t); 1664*0Sstevel@tonic-gate /* while there is more get more text from the data stream */ 1665*0Sstevel@tonic-gate for (;;) { 1666*0Sstevel@tonic-gate all_searched = NO; 1667*0Sstevel@tonic-gate 1668*0Sstevel@tonic-gate /* 1669*0Sstevel@tonic-gate * Find next new-line in buffer. 1670*0Sstevel@tonic-gate * Begin after previous new line character 1671*0Sstevel@tonic-gate */ 1672*0Sstevel@tonic-gate 1673*0Sstevel@tonic-gate current.prntbuf = current.newline + 1; 1674*0Sstevel@tonic-gate current.ln++; /* increment line number */ 1675*0Sstevel@tonic-gate 1676*0Sstevel@tonic-gate if (current.prntbuf < bufend) { 1677*0Sstevel@tonic-gate /* There is more text in buffer */ 1678*0Sstevel@tonic-gate 1679*0Sstevel@tonic-gate /* 1680*0Sstevel@tonic-gate * Take our next 1681*0Sstevel@tonic-gate * "line" as the entire remaining buffer. 1682*0Sstevel@tonic-gate * However, if there is more of the file yet 1683*0Sstevel@tonic-gate * to be read in, exclude any incomplete 1684*0Sstevel@tonic-gate * line at end. 1685*0Sstevel@tonic-gate */ 1686*0Sstevel@tonic-gate if (file_stat == NO_MORE) { 1687*0Sstevel@tonic-gate all_searched = YES; 1688*0Sstevel@tonic-gate current.newline = bufend - 1; 1689*0Sstevel@tonic-gate if (*current.newline != NL) { 1690*0Sstevel@tonic-gate current.newline = bufend; 1691*0Sstevel@tonic-gate } 1692*0Sstevel@tonic-gate } else { 1693*0Sstevel@tonic-gate /* 1694*0Sstevel@tonic-gate * Find end of the last 1695*0Sstevel@tonic-gate * complete line in the buffer. 1696*0Sstevel@tonic-gate */ 1697*0Sstevel@tonic-gate current.newline = bufend; 1698*0Sstevel@tonic-gate while (*--current.newline != NL) { 1699*0Sstevel@tonic-gate } 1700*0Sstevel@tonic-gate if (current.newline < current.prntbuf) { 1701*0Sstevel@tonic-gate /* end not found */ 1702*0Sstevel@tonic-gate current.newline = bufend; 1703*0Sstevel@tonic-gate } 1704*0Sstevel@tonic-gate } 1705*0Sstevel@tonic-gate } else { 1706*0Sstevel@tonic-gate /* There is no more text in the buffer. */ 1707*0Sstevel@tonic-gate current.newline = bufend; 1708*0Sstevel@tonic-gate } 1709*0Sstevel@tonic-gate if (current.newline >= bufend) { 1710*0Sstevel@tonic-gate /* 1711*0Sstevel@tonic-gate * There is no more text in the buffer, 1712*0Sstevel@tonic-gate * or no new line was found. 1713*0Sstevel@tonic-gate */ 1714*0Sstevel@tonic-gate switch (file_stat) { 1715*0Sstevel@tonic-gate case MORE: /* file partly unread */ 1716*0Sstevel@tonic-gate case BEGIN: 1717*0Sstevel@tonic-gate fgetfile(¤t); 1718*0Sstevel@tonic-gate 1719*0Sstevel@tonic-gate current.ln--; 1720*0Sstevel@tonic-gate continue; /* with while loop */ 1721*0Sstevel@tonic-gate case NO_MORE: 1722*0Sstevel@tonic-gate break; 1723*0Sstevel@tonic-gate } 1724*0Sstevel@tonic-gate /* Nothing more to read in for this file. */ 1725*0Sstevel@tonic-gate if (current.newline <= current.prntbuf) { 1726*0Sstevel@tonic-gate /* Nothing in the buffer, either */ 1727*0Sstevel@tonic-gate /* We are done with the file. */ 1728*0Sstevel@tonic-gate current.ln--; 1729*0Sstevel@tonic-gate break; /* out of while loop */ 1730*0Sstevel@tonic-gate } 1731*0Sstevel@tonic-gate /* There is no NL at the end of the file */ 1732*0Sstevel@tonic-gate } 1733*0Sstevel@tonic-gate 1734*0Sstevel@tonic-gate matched = pattern_match(&match_pattern, ¤t); 1735*0Sstevel@tonic-gate if (matched) { 1736*0Sstevel@tonic-gate int nc; 1737*0Sstevel@tonic-gate 1738*0Sstevel@tonic-gate get_ncount(¤t, match_pattern.loc1); 1739*0Sstevel@tonic-gate get_line(¤t, match_pattern.loc2); 1740*0Sstevel@tonic-gate 1741*0Sstevel@tonic-gate nc = current.newline + 1 - current.prntbuf; 1742*0Sstevel@tonic-gate (void) fprintf(output, format, file, current.ln); 1743*0Sstevel@tonic-gate (void) fwrite((char *)current.prntbuf, 1, nc, output); 1744*0Sstevel@tonic-gate } else { 1745*0Sstevel@tonic-gate if (all_searched) 1746*0Sstevel@tonic-gate break; /* out of while loop */ 1747*0Sstevel@tonic-gate 1748*0Sstevel@tonic-gate get_ncount(¤t, current.newline + 1); 1749*0Sstevel@tonic-gate } 1750*0Sstevel@tonic-gate } 1751*0Sstevel@tonic-gate 1752*0Sstevel@tonic-gate (void) close(file_desc); 1753*0Sstevel@tonic-gate return (0); 1754*0Sstevel@tonic-gate } 1755*0Sstevel@tonic-gate 1756*0Sstevel@tonic-gate static void 1757*0Sstevel@tonic-gate init_file(LINE *cur_ptr) 1758*0Sstevel@tonic-gate { 1759*0Sstevel@tonic-gate file_stat = BEGIN; 1760*0Sstevel@tonic-gate cur_ptr->ln = 0; 1761*0Sstevel@tonic-gate bufend = buffer; 1762*0Sstevel@tonic-gate cur_ptr->newline = buffer - 1; 1763*0Sstevel@tonic-gate } 1764*0Sstevel@tonic-gate 1765*0Sstevel@tonic-gate static BOOL 1766*0Sstevel@tonic-gate pattern_match(PATTERN *pat, LINE *lptr) 1767*0Sstevel@tonic-gate { 1768*0Sstevel@tonic-gate if ((*pat->procfn)(pat, lptr->prntbuf - 1, lptr->newline + 1, 1769*0Sstevel@tonic-gate &pat->loc1, &pat->loc2)) { 1770*0Sstevel@tonic-gate return (YES); 1771*0Sstevel@tonic-gate } else { 1772*0Sstevel@tonic-gate pat->loc1 = lptr->prntbuf; 1773*0Sstevel@tonic-gate pat->loc2 = lptr->newline - 1; 1774*0Sstevel@tonic-gate return (NO); 1775*0Sstevel@tonic-gate } 1776*0Sstevel@tonic-gate } /* end of function pattern_match() */ 1777*0Sstevel@tonic-gate 1778*0Sstevel@tonic-gate static void 1779*0Sstevel@tonic-gate fgetfile(LINE *cur_ptr) 1780*0Sstevel@tonic-gate { 1781*0Sstevel@tonic-gate /* 1782*0Sstevel@tonic-gate * This function reads as much of the current file into the buffer 1783*0Sstevel@tonic-gate * as will fit. 1784*0Sstevel@tonic-gate */ 1785*0Sstevel@tonic-gate int bytes; /* bytes read in current buffer */ 1786*0Sstevel@tonic-gate int bufsize = MAXBUFSIZE; /* free space in data buffer */ 1787*0Sstevel@tonic-gate int save_current; 1788*0Sstevel@tonic-gate uchar_t *begin = cur_ptr->prntbuf; 1789*0Sstevel@tonic-gate 1790*0Sstevel@tonic-gate /* 1791*0Sstevel@tonic-gate * Bytes of current incomplete line, if any, save_current in buffer. 1792*0Sstevel@tonic-gate * These must be saved. 1793*0Sstevel@tonic-gate */ 1794*0Sstevel@tonic-gate save_current = (int)(bufend - begin); 1795*0Sstevel@tonic-gate 1796*0Sstevel@tonic-gate if (file_stat == MORE) { 1797*0Sstevel@tonic-gate /* 1798*0Sstevel@tonic-gate * A portion of the file fills the buffer. We must clear 1799*0Sstevel@tonic-gate * out the dead wood to make room for more of the file. 1800*0Sstevel@tonic-gate */ 1801*0Sstevel@tonic-gate 1802*0Sstevel@tonic-gate int k = 0; 1803*0Sstevel@tonic-gate 1804*0Sstevel@tonic-gate k = begin - buffer; 1805*0Sstevel@tonic-gate if (!k) { 1806*0Sstevel@tonic-gate /* 1807*0Sstevel@tonic-gate * We have one humungous current line, 1808*0Sstevel@tonic-gate * which fills the whole buffer. 1809*0Sstevel@tonic-gate * Toss it. 1810*0Sstevel@tonic-gate */ 1811*0Sstevel@tonic-gate begin = bufend; 1812*0Sstevel@tonic-gate k = begin - buffer; 1813*0Sstevel@tonic-gate save_current = 0; 1814*0Sstevel@tonic-gate } 1815*0Sstevel@tonic-gate 1816*0Sstevel@tonic-gate begin = buffer; 1817*0Sstevel@tonic-gate bufend = begin + save_current; 1818*0Sstevel@tonic-gate 1819*0Sstevel@tonic-gate bufsize = MAXBUFSIZE - save_current; 1820*0Sstevel@tonic-gate 1821*0Sstevel@tonic-gate if (save_current > 0) { 1822*0Sstevel@tonic-gate /* 1823*0Sstevel@tonic-gate * Must save portion of current line. 1824*0Sstevel@tonic-gate * Copy to beginning of buffer. 1825*0Sstevel@tonic-gate */ 1826*0Sstevel@tonic-gate (void) memmove(buffer, buffer + k, save_current); 1827*0Sstevel@tonic-gate } 1828*0Sstevel@tonic-gate } 1829*0Sstevel@tonic-gate 1830*0Sstevel@tonic-gate /* Now read in the file. */ 1831*0Sstevel@tonic-gate 1832*0Sstevel@tonic-gate do { 1833*0Sstevel@tonic-gate bytes = read(file_desc, (char *)bufend, (unsigned int)bufsize); 1834*0Sstevel@tonic-gate if (bytes < 0) { 1835*0Sstevel@tonic-gate /* can't read any more of file */ 1836*0Sstevel@tonic-gate bytes = 0; 1837*0Sstevel@tonic-gate } 1838*0Sstevel@tonic-gate bufend += bytes; 1839*0Sstevel@tonic-gate bufsize -= bytes; 1840*0Sstevel@tonic-gate } while (bytes > 0 && bufsize > 0); 1841*0Sstevel@tonic-gate 1842*0Sstevel@tonic-gate 1843*0Sstevel@tonic-gate if (begin >= bufend) { 1844*0Sstevel@tonic-gate /* No new lines or incomplete line in buffer */ 1845*0Sstevel@tonic-gate file_stat = NO_MORE; 1846*0Sstevel@tonic-gate } else if (bufsize) { 1847*0Sstevel@tonic-gate /* Still space in the buffer, so we have read entire file */ 1848*0Sstevel@tonic-gate file_stat = NO_MORE; 1849*0Sstevel@tonic-gate } else { 1850*0Sstevel@tonic-gate /* We filled entire buffer, so there may be more yet to read */ 1851*0Sstevel@tonic-gate file_stat = MORE; 1852*0Sstevel@tonic-gate } 1853*0Sstevel@tonic-gate /* Note: bufend is 1 past last good char */ 1854*0Sstevel@tonic-gate *bufend = NL; /* Sentinel new-line character */ 1855*0Sstevel@tonic-gate /* Set newline to character preceding the current line */ 1856*0Sstevel@tonic-gate cur_ptr->newline = begin - 1; 1857*0Sstevel@tonic-gate } 1858*0Sstevel@tonic-gate 1859*0Sstevel@tonic-gate static void 1860*0Sstevel@tonic-gate get_line(LINE *cur_ptr, uchar_t *s) 1861*0Sstevel@tonic-gate { 1862*0Sstevel@tonic-gate while (*s++ != NL) { 1863*0Sstevel@tonic-gate } 1864*0Sstevel@tonic-gate cur_ptr->newline = --s; 1865*0Sstevel@tonic-gate cur_ptr->ln++; 1866*0Sstevel@tonic-gate } 1867*0Sstevel@tonic-gate 1868*0Sstevel@tonic-gate static void 1869*0Sstevel@tonic-gate get_ncount(LINE *cur_ptr, uchar_t *s) 1870*0Sstevel@tonic-gate { 1871*0Sstevel@tonic-gate uchar_t *p = cur_ptr->prntbuf; 1872*0Sstevel@tonic-gate 1873*0Sstevel@tonic-gate while (*--s != NL) { 1874*0Sstevel@tonic-gate } 1875*0Sstevel@tonic-gate cur_ptr->newline = s++; 1876*0Sstevel@tonic-gate while ((s > p) && 1877*0Sstevel@tonic-gate (p = (uchar_t *)memchr((char *)p, NL, s - p)) != NULL) { 1878*0Sstevel@tonic-gate cur_ptr->ln++; 1879*0Sstevel@tonic-gate ++p; 1880*0Sstevel@tonic-gate } 1881*0Sstevel@tonic-gate cur_ptr->ln--; 1882*0Sstevel@tonic-gate cur_ptr->prntbuf = s; 1883*0Sstevel@tonic-gate } 1884