usr/src/cmd/egrep/egrep.y

   1 %{
   2 /*
   3  * CDDL HEADER START
   4  *
   5  * The contents of this file are subject to the terms of the
   6  * Common Development and Distribution License, Version 1.0 only
   7  * (the "License").  You may not use this file except in compliance
   8  * with the License.
   9  *
  10  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  11  * or http://www.opensolaris.org/os/licensing.
  12  * See the License for the specific language governing permissions
  13  * and limitations under the License.
  14  *
  15  * When distributing Covered Code, include this CDDL HEADER in each
  16  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  17  * If applicable, add the following below this CDDL HEADER, with the
  18  * fields enclosed by brackets "[]" replaced with your own identifying
  19  * information: Portions Copyright [yyyy] [name of copyright owner]
  20  *
  21  * CDDL HEADER END
  22  */
  23 %}
  24 /*
  25  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
  26  * Use is subject to license terms.
  27  */
  28
  29 /*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
  30 /*        All Rights Reserved   */
  31
  32 /*      Copyright (c) 1987, 1988 Microsoft Corporation  */
  33 /*        All Rights Reserved   */
  34
  35 /*
  36  * Copyright 2013 Damian Bogel. All rights reserved.
  37  */
  38
  39 /*
  40  * egrep -- print lines containing (or not containing) a regular expression
  41  *
  42  *      status returns:
  43  *              0 - ok, and some matches
  44  *              1 - ok, but no matches
  45  *              2 - some error; matches irrelevant
  46  */
  47 %token CHAR MCHAR DOT MDOT CCL NCCL MCCL NMCCL OR CAT STAR PLUS QUEST
  48 %left OR
  49 %left CHAR MCHAR DOT CCL NCCL MCCL NMCCL '('
  50 %left CAT
  51 %left STAR PLUS QUEST
  52
  53 %{
  54 #include <stdio.h>
  55 #include <ctype.h>
  56 #include <memory.h>
  57 #include <wchar.h>
  58 #include <wctype.h>
  59 #include <widec.h>
  60 #include <stdlib.h>
  61 #include <limits.h>
  62 #include <locale.h>
  63
  64 #define STDIN_FILENAME gettext("(standard input)")
  65
  66 #define BLKSIZE 512     /* size of reported disk blocks */
  67 #define EBUFSIZ 8192
  68 #define MAXLIN 350
  69 #define NCHARS 256
  70 #define MAXPOS 4000
  71 #define NSTATES 64
  72 #define FINAL -1
  73 #define RIGHT '\n'      /* serves as record separator and as $ */
  74 #define LEFT '\n'       /* beginning of line */
  75 int gotofn[NSTATES][NCHARS];
  76 int state[NSTATES];
  77 int out[NSTATES];
  78 int line  = 1;
  79 int *name;
  80 int *left;
  81 int *right;
  82 int *parent;
  83 int *foll;
  84 int *positions;
  85 char *chars;
  86 wchar_t *lower;
  87 wchar_t *upper;
  88 int maxlin, maxclin, maxwclin, maxpos;
  89 int nxtpos = 0;
  90 int inxtpos;
  91 int nxtchar = 0;
  92 int *tmpstat;
  93 int *initstat;
  94 int istat;
  95 int nstate = 1;
  96 int xstate;
  97 int count;
  98 int icount;
  99 char *input;
 100
 101
 102 wchar_t lyylval;
 103 wchar_t nextch();
 104 wchar_t maxmin();
 105 int compare();
 106 void overflo();
 107
 108 char reinit = 0;
 109
 110 long long lnum;
 111 int     bflag;
 112 int     cflag;
 113 int     eflag;
 114 int     fflag;
 115 int     Hflag;
 116 int     hflag;
 117 int     iflag;
 118 int     lflag;
 119 int     nflag;
 120 int     qflag;
 121 int     vflag;
 122 int     nfile;
 123 long long blkno;
 124 long long tln;
 125 int     nsucc;
 126 int     badbotch;
 127 extern  char *optarg;
 128 extern  int optind;
 129
 130 int     f;
 131 FILE    *expfile;
 132 %}
 133
 134 %%
 135 s:      t
 136                 {
 137                   unary(FINAL, $1);
 138                   line--;
 139                 }
 140         ;
 141 t:      b r
 142                 { $$ = node(CAT, $1, $2); }
 143         | OR b r OR
 144                 { $$ = node(CAT, $2, $3); }
 145         | OR b r
 146                 { $$ = node(CAT, $2, $3); }
 147         | b r OR
 148                 { $$ = node(CAT, $1, $2); }
 149         ;
 150 b:
 151                 { /* if(multibyte)
 152                         $$ = mdotenter();
 153                   else */
 154                         $$ = enter(DOT);
 155                   $$ = unary(STAR, $$);
 156                 }
 157         ;
 158 r:      CHAR
 159                 { $$ = iflag && isalpha($1) ?
 160                 node(OR, enter(tolower($1)), enter(toupper($1))) : enter($1); }
 161         | MCHAR
 162                 { $$ = (iflag && iswalpha(lyylval)) ?
 163                 node(OR, mchar(towlower(lyylval)), mchar(towupper(lyylval))) :
 164                 mchar(lyylval); }
 165         | DOT
 166                 { if(multibyte)
 167                         $$ = mdotenter();
 168                   else
 169                         $$ = enter(DOT);
 170                 }
 171         | CCL
 172                 { $$ = cclenter(CCL); }
 173         | NCCL
 174                 { $$ = cclenter(NCCL); }
 175         | MCCL
 176                 { $$ = ccl(CCL); }
 177         | NMCCL
 178                 { $$ = ccl(NCCL); }
 179         ;
 180
 181 r:      r OR r
 182                 { $$ = node(OR, $1, $3); }
 183         | r r %prec CAT
 184                 { $$ = node(CAT, $1, $2); }
 185         | r STAR
 186                 { $$ = unary(STAR, $1); }
 187         | r PLUS
 188                 { $$ = unary(PLUS, $1); }
 189         | r QUEST
 190                 { $$ = unary(QUEST, $1); }
 191         | '(' r ')'
 192                 { $$ = $2; }
 193         | error
 194         ;
 195
 196 %%
 197 void    add(int *, int);
 198 void    clearg(void);
 199 void    execute(char *);
 200 void    follow(int);
 201 int     mgetc(void);
 202 void    synerror(void);
 203
 204
 205 void
 206 yyerror(char *s)
 207 {
 208         fprintf(stderr, "egrep: %s\n", s);
 209         exit(2);
 210 }
 211
 212 int
 213 yylex(void)
 214 {
 215         extern int yylval;
 216         int cclcnt, x, ccount, oldccount;
 217         wchar_t c, lc;
 218
 219         c = nextch();
 220         switch(c) {
 221                 case '^':
 222                         yylval = LEFT;
 223                         return(CHAR);
 224                 case '$':
 225                         c = RIGHT;
 226                         goto defchar;
 227                 case '|': return (OR);
 228                 case '*': return (STAR);
 229                 case '+': return (PLUS);
 230                 case '?': return (QUEST);
 231                 case '(': return (c);
 232                 case ')': return (c);
 233                 case '.': return(DOT);
 234                 case '\0': return (0);
 235                 case RIGHT: return (OR);
 236                 case '[':
 237                         x = (multibyte ? MCCL : CCL);
 238                         cclcnt = 0;
 239                         count = nxtchar++;
 240                         if ((c = nextch()) == '^') {
 241                                 x = (multibyte ? NMCCL : NCCL);
 242                                 c = nextch();
 243                         }
 244                         lc = 0;
 245                         do {
 246                                 if (iflag && iswalpha(c))
 247                                         c = towlower(c);
 248                                 if (c == '\0') synerror();
 249                                 if (c == '-' && cclcnt > 0 && lc != 0) {
 250                                         if ((c = nextch()) != 0) {
 251                                                 if(c == ']') {
 252                                                         chars[nxtchar++] = '-';
 253                                                         cclcnt++;
 254                                                         break;
 255                                                 }
 256                                                 if (iflag && iswalpha(c))
 257                                                         c = towlower(c);
 258                                                 if (!multibyte ||
 259                                                 (c & WCHAR_CSMASK) == (lc & WCHAR_CSMASK) &&
 260                                                 lc < c &&
 261                                                 !iswcntrl(c) && !iswcntrl(lc)) {
 262                                                         if (nxtchar >= maxclin)
 263                                                                 if (allocchars() == 0)
 264                                                                         overflo();
 265                                                         chars[nxtchar++] = '-';
 266                                                         cclcnt++;
 267                                                 }
 268                                         }
 269                                 }
 270                                 ccount = oldccount = nxtchar;
 271                                 if(ccount + MB_LEN_MAX >= maxclin)
 272                                         if(allocchars() == 0)
 273                                                 overflo();
 274                                 ccount += wctomb(&chars[ccount], c);
 275                                 cclcnt += ccount - oldccount;
 276                                 nxtchar += ccount - oldccount;
 277                                 lc = c;
 278                         } while ((c = nextch()) != ']');
 279                         chars[count] = cclcnt;
 280                         return(x);
 281
 282                 case '\\':
 283                         if ((c = nextch()) == '\0') synerror();
 284                 defchar:
 285                 default:
 286                         if (c <= 0177) {
 287                                 yylval = c;
 288                                 return (CHAR);
 289                         } else {
 290                                 lyylval = c;
 291                                 return (MCHAR);
 292                         }
 293         }
 294 }
 295
 296 wchar_t
 297 nextch(void)
 298 {
 299         wchar_t lc;
 300         char multic[MB_LEN_MAX];
 301         int length, d;
 302         if (fflag) {
 303                 if ((length = _mbftowc(multic, &lc, mgetc, &d)) < 0)
 304                         synerror();
 305                 if(length == 0)
 306                         lc = '\0';
 307         }
 308         else  {
 309                 if((length = mbtowc(&lc, input, MB_LEN_MAX)) == -1)
 310                         synerror();
 311                 if(length == 0)
 312                         return(0);
 313                 input += length;
 314         }
 315         return(lc);
 316 }
 317
 318 int
 319 mgetc(void)
 320 {
 321         return(getc(expfile));
 322 }
 323
 324 void
 325 synerror(void)
 326 {
 327         fprintf(stderr, gettext("egrep: syntax error\n"));
 328         exit(2);
 329 }
 330
 331 int
 332 enter(int x)
 333 {
 334         if(line >= maxlin)
 335                 if(alloctree() == 0)
 336                         overflo();
 337         name[line] = x;
 338         left[line] = 0;
 339         right[line] = 0;
 340         return(line++);
 341 }
 342
 343 int
 344 cclenter(int x)
 345 {
 346         int linno;
 347         linno = enter(x);
 348         right[linno] = count;
 349         return (linno);
 350 }
 351
 352 int
 353 node(int x, int l, int r)
 354 {
 355         if(line >= maxlin)
 356                 if(alloctree() == 0)
 357                         overflo();
 358         name[line] = x;
 359         left[line] = l;
 360         right[line] = r;
 361         parent[l] = line;
 362         parent[r] = line;
 363         return(line++);
 364 }
 365
 366 int
 367 unary(int x, int d)
 368 {
 369         if(line >= maxlin)
 370                 if(alloctree() == 0)
 371                         overflo();
 372         name[line] = x;
 373         left[line] = d;
 374         right[line] = 0;
 375         parent[d] = line;
 376         return(line++);
 377 }
 378
 379 int
 380 allocchars(void)
 381 {
 382         maxclin += MAXLIN;
 383         if((chars = realloc(chars, maxclin)) == (char *)0)
 384                 return 0;
 385         return 1;
 386 }
 387
 388 int
 389 alloctree(void)
 390 {
 391         maxlin += MAXLIN;
 392         if((name = (int *)realloc(name, maxlin*sizeof(int))) == (int *)0)
 393                 return 0;
 394         if((left = (int *)realloc(left, maxlin*sizeof(int))) == (int *)0)
 395                 return 0;
 396         if((right = (int *)realloc(right, maxlin*sizeof(int))) == (int *)0)
 397                 return 0;
 398         if((parent = (int *)realloc(parent, maxlin*sizeof(int))) == (int *)0)
 399                 return 0;
 400         if((foll = (int *)realloc(foll, maxlin*sizeof(int))) == (int *)0)
 401                 return 0;
 402         if((tmpstat = (int *)realloc(tmpstat, maxlin*sizeof(int))) == (int *)0)
 403                 return 0;
 404         if((initstat = (int *)realloc(initstat, maxlin*sizeof(int))) == (int *)0)
 405                 return 0;
 406         return 1;
 407 }
 408
 409 void
 410 overflo(void)
 411 {
 412         fprintf(stderr, gettext("egrep: regular expression too long\n"));
 413         exit(2);
 414 }
 415
 416 void
 417 cfoll(int v)
 418 {
 419         int i;
 420         if (left[v] == 0) {
 421                 count = 0;
 422                 for (i=1; i<=line; i++) tmpstat[i] = 0;
 423                 follow(v);
 424                 add(foll, v);
 425         }
 426         else if (right[v] == 0) cfoll(left[v]);
 427         else {
 428                 cfoll(left[v]);
 429                 cfoll(right[v]);
 430         }
 431 }
 432
 433 void
 434 cgotofn(void)
 435 {
 436         int i;
 437         count = 0;
 438         inxtpos = nxtpos;
 439         for (i=3; i<=line; i++) tmpstat[i] = 0;
 440         if (cstate(line-1)==0) {
 441                 tmpstat[line] = 1;
 442                 count++;
 443                 out[1] = 1;
 444         }
 445         for (i=3; i<=line; i++) initstat[i] = tmpstat[i];
 446         count--;                /*leave out position 1 */
 447         icount = count;
 448         tmpstat[1] = 0;
 449         add(state, 1);
 450         istat = nxtst(1, LEFT);
 451 }
 452
 453 int
 454 nxtst(int s, int c)
 455 {
 456         int i, num, k;
 457         int pos, curpos, number, newpos;
 458         num = positions[state[s]];
 459         count = icount;
 460         for (i=3; i<=line; i++) tmpstat[i] = initstat[i];
 461         pos = state[s] + 1;
 462         for (i=0; i<num; i++) {
 463                 curpos = positions[pos];
 464                 k = name[curpos];
 465                 if (k >= 0)
 466                         if (
 467                                 (k == c)
 468                                 || (k == DOT && dot(c))
 469                                 || (k == MDOT && mdot(c))
 470                                 || (k == CCL && dot(c) && member(c, right[curpos], 1))
 471                                 || (k == NCCL && dot(c) && member(c, right[curpos], 0))
 472                                 || (k == MCCL && mdot(c) && member(c, right[curpos], 1))
 473                         ) {
 474                                 number = positions[foll[curpos]];
 475                                 newpos = foll[curpos] + 1;
 476                                 for (k=0; k<number; k++) {
 477                                         if (tmpstat[positions[newpos]] != 1) {
 478                                                 tmpstat[positions[newpos]] = 1;
 479                                                 count++;
 480                                         }
 481                                         newpos++;
 482                                 }
 483                         }
 484                 pos++;
 485         }
 486         if (notin(nstate)) {
 487                 if (++nstate >= NSTATES) {
 488                         for (i=1; i<NSTATES; i++)
 489                                 out[i] = 0;
 490                         for (i=1; i<NSTATES; i++)
 491                                 for (k=0; k<NCHARS; k++)
 492                                         gotofn[i][k] = 0;
 493                         nstate = 1;
 494                         nxtpos = inxtpos;
 495                         reinit = 1;
 496                         add(state, nstate);
 497                         if (tmpstat[line] == 1) out[nstate] = 1;
 498                         return nstate;
 499                 }
 500                 add(state, nstate);
 501                 if (tmpstat[line] == 1) out[nstate] = 1;
 502                 gotofn[s][c] = nstate;
 503                 return nstate;
 504         }
 505         else {
 506                 gotofn[s][c] = xstate;
 507                 return xstate;
 508         }
 509 }
 510
 511
 512 int
 513 cstate(int v)
 514 {
 515         int b;
 516         if (left[v] == 0) {
 517                 if (tmpstat[v] != 1) {
 518                         tmpstat[v] = 1;
 519                         count++;
 520                 }
 521                 return(1);
 522         }
 523         else if (right[v] == 0) {
 524                 if (cstate(left[v]) == 0) return (0);
 525                 else if (name[v] == PLUS) return (1);
 526                 else return (0);
 527         }
 528         else if (name[v] == CAT) {
 529                 if (cstate(left[v]) == 0 && cstate(right[v]) == 0) return (0);
 530                 else return (1);
 531         }
 532         else { /* name[v] == OR */
 533                 b = cstate(right[v]);
 534                 if (cstate(left[v]) == 0 || b == 0) return (0);
 535                 else return (1);
 536         }
 537 }
 538
 539
 540 int
 541 dot(int c)
 542 {
 543         if(multibyte && c >= 0200 && (!iscntrl(c) || c == SS2 && eucw2 || c == SS3 && eucw3))
 544                 return(0);
 545         if(c == RIGHT || c == LEFT)
 546                 return(0);
 547         return(1);
 548 }
 549
 550 int
 551 mdot(int c)
 552 {
 553         if(c >= 0200 && !iscntrl(c))
 554                 return(1);
 555         return(0);
 556 }
 557
 558 int
 559 member(int symb, int set, int torf)
 560 {
 561         int i, num, pos, c, lc;
 562         if(symb == RIGHT || symb == LEFT)
 563                 return(0);
 564         num = chars[set];
 565         pos = set + 1;
 566         lc = 0;
 567         if(iflag)
 568                 symb = tolower(symb);
 569         for (i=0; i<num; i++) {
 570                 c = (unsigned char)chars[pos++];
 571                 if(c == '-' && lc != 0 && ++i < num) {
 572                         c = (unsigned char)chars[pos++];
 573                         if(lc <= symb && symb <= c)
 574                                 return(torf);
 575                 }
 576                 if (symb == c)
 577                         return (torf);
 578                 lc = c;
 579         }
 580         return(!torf);
 581 }
 582
 583 int
 584 notin(int n)
 585 {
 586         int i, j, pos;
 587         for (i=1; i<=n; i++) {
 588                 if (positions[state[i]] == count) {
 589                         pos = state[i] + 1;
 590                         for (j=0; j < count; j++)
 591                                 if (tmpstat[positions[pos++]] != 1) goto nxt;
 592                         xstate = i;
 593                         return (0);
 594                 }
 595                 nxt: ;
 596         }
 597         return (1);
 598 }
 599
 600 void
 601 add(int *array, int n)
 602 {
 603         int i;
 604         if (nxtpos + count >= maxpos) {
 605                 maxpos += MAXPOS + count;
 606                 if((positions = (int *)realloc(positions, maxpos *sizeof(int))) == (int *)0)
 607                         overflo();
 608         }
 609         array[n] = nxtpos;
 610         positions[nxtpos++] = count;
 611         for (i=3; i <= line; i++) {
 612                 if (tmpstat[i] == 1) {
 613                         positions[nxtpos++] = i;
 614                 }
 615         }
 616 }
 617
 618 void
 619 follow(int v)
 620 {
 621         int p;
 622         if (v == line) return;
 623         p = parent[v];
 624         switch(name[p]) {
 625                 case STAR:
 626                 case PLUS:      cstate(v);
 627                                 follow(p);
 628                                 return;
 629
 630                 case OR:
 631                 case QUEST:     follow(p);
 632                                 return;
 633
 634                 case CAT:       if (v == left[p]) {
 635                                         if (cstate(right[p]) == 0) {
 636                                                 follow(p);
 637                                                 return;
 638                                         }
 639                                 }
 640                                 else follow(p);
 641                                 return;
 642                 case FINAL:     if (tmpstat[line] != 1) {
 643                                         tmpstat[line] = 1;
 644                                         count++;
 645                                 }
 646                                 return;
 647         }
 648 }
 649
 650 #define USAGE "[ -bchHilnsqv ] [ -e exp ] [ -f file ] [ strings ] [ file ] ..."
 651
 652 int
 653 main(int argc, char **argv)
 654 {
 655         char c;
 656         char nl = '\n';
 657         int errflag = 0;
 658
 659         (void)setlocale(LC_ALL, "");
 660
 661 #if !defined(TEXT_DOMAIN)               /* Should be defined by cc -D */
 662         #define TEXT_DOMAIN "SYS_TEST"  /* Use this only if it weren't. */
 663 #endif
 664         (void) textdomain(TEXT_DOMAIN);
 665
 666         while((c = getopt(argc, argv, "ybcie:f:Hhlnvsq")) != -1)
 667                 switch(c) {
 668
 669                 case 'b':
 670                         bflag++;
 671                         continue;
 672
 673                 case 'c':
 674                         cflag++;
 675                         continue;
 676
 677                 case 'e':
 678                         eflag++;
 679                         input = optarg;
 680                         continue;
 681
 682                 case 'f':
 683                         fflag++;
 684                         expfile = fopen(optarg, "r");
 685                         if(expfile == NULL) {
 686                                 fprintf(stderr,
 687                                   gettext("egrep: can't open %s\n"), optarg);
 688                                 exit(2);
 689                         }
 690                         continue;
 691
 692                 case 'H':
 693                         if (!lflag) /* H is excluded by l as in GNU grep */
 694                                 Hflag++;
 695                         hflag = 0; /* H excludes h */
 696                         continue;
 697
 698                 case 'h':
 699                         hflag++;
 700                         Hflag = 0; /* h excludes H */
 701                         continue;
 702
 703                 case 'y':
 704                 case 'i':
 705                         iflag++;
 706                         continue;
 707
 708                 case 'l':
 709                         lflag++;
 710                         Hflag = 0; /* l excludes H */
 711                         continue;
 712
 713                 case 'n':
 714                         nflag++;
 715                         continue;
 716
 717                 case 'q':
 718                 case 's': /* Solaris: legacy option */
 719                         qflag++;
 720                         continue;
 721
 722                 case 'v':
 723                         vflag++;
 724                         continue;
 725
 726                 case '?':
 727                         errflag++;
 728                 }
 729         if (errflag || ((argc <= 0) && !fflag && !eflag)) {
 730                 fprintf(stderr, gettext("usage: egrep %s\n"), gettext(USAGE));
 731                 exit(2);
 732         }
 733         if(!eflag && !fflag) {
 734                 input = argv[optind];
 735                 optind++;
 736         }
 737
 738         argc -= optind;
 739         argv = &argv[optind];
 740
 741         /* allocate initial space for arrays */
 742         if((name = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
 743                 overflo();
 744         if((left = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
 745                 overflo();
 746         if((right = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
 747                 overflo();
 748         if((parent = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
 749                 overflo();
 750         if((foll = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
 751                 overflo();
 752         if((tmpstat = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
 753                 overflo();
 754         if((initstat = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
 755                 overflo();
 756         if((chars = (char *)malloc(MAXLIN)) == (char *)0)
 757                 overflo();
 758         if((lower = (wchar_t *)malloc(MAXLIN*sizeof(wchar_t))) == (wchar_t *)0)
 759                 overflo();
 760         if((upper = (wchar_t *)malloc(MAXLIN*sizeof(wchar_t))) == (wchar_t *)0)
 761                 overflo();
 762         if((positions = (int *)malloc(MAXPOS*sizeof(int))) == (int *)0)
 763                 overflo();
 764         maxlin = MAXLIN;
 765         maxclin = MAXLIN;
 766         maxwclin = MAXLIN;
 767         maxpos = MAXPOS;
 768
 769         yyparse();
 770
 771         cfoll(line-1);
 772         cgotofn();
 773         nfile = argc;
 774         if (argc<=0) {
 775                 execute(0);
 776         }
 777         else while (--argc >= 0) {
 778                 if (reinit == 1) clearg();
 779                 execute(*argv++);
 780         }
 781         return (badbotch ? 2 : nsucc==0);
 782 }
 783
 784 void
 785 execute(char *file)
 786 {
 787         char *p;
 788         int cstat;
 789         wchar_t c;
 790         int t;
 791         long count;
 792         long count1, count2;
 793         long nchars;
 794         int succ;
 795         char *ptr, *ptrend, *lastptr;
 796         char *buf;
 797         long lBufSiz;
 798         FILE *f;
 799         int nlflag;
 800
 801         lBufSiz = EBUFSIZ;
 802         if ((buf = malloc (lBufSiz + EBUFSIZ)) == NULL) {
 803                 exit (2); /* out of memory - BAIL */
 804         }
 805
 806         if (file) {
 807                 if ((f = fopen(file, "r")) == NULL) {
 808                         fprintf(stderr,
 809                                 gettext("egrep: can't open %s\n"), file);
 810                         badbotch=1;
 811                         return;
 812                 }
 813         } else {
 814                 f = stdin;
 815                 file = STDIN_FILENAME;
 816         }
 817         lnum = 1;
 818         tln = 0;
 819         if((count = read(fileno(f), buf, EBUFSIZ)) <= 0) {
 820                 fclose(f);
 821
 822                 if (cflag && !qflag) {
 823                         if (Hflag || (nfile > 1 && !hflag))
 824                                 fprintf(stdout, "%s:", file);
 825                         fprintf(stdout, "%lld\n", tln);
 826                 }
 827                 return;
 828         }
 829
 830         blkno = count;
 831         ptr = buf;
 832         for(;;) {
 833                 if((ptrend = memchr(ptr, '\n', buf + count - ptr)) == NULL) {
 834                         /*
 835                                 move the unused partial record to the head of the buffer
 836                         */
 837                         if (ptr > buf) {
 838                                 count = buf + count - ptr;
 839                                 memmove (buf, ptr, count);
 840                                 ptr = buf;
 841                         }
 842
 843                         /*
 844                                 Get a bigger buffer if this one is full
 845                         */
 846                         if(count > lBufSiz) {
 847                                 /*
 848                                         expand the buffer
 849                                 */
 850                                 lBufSiz += EBUFSIZ;
 851                                 if ((buf = realloc (buf, lBufSiz + EBUFSIZ)) == NULL) {
 852                                         exit (2); /* out of memory - BAIL */
 853                                 }
 854
 855                                 ptr = buf;
 856                         }
 857
 858                         p = buf + count;
 859                         if((count1 = read(fileno(f), p, EBUFSIZ)) > 0) {
 860                                 count += count1;
 861                                 blkno += count1;
 862                                 continue;
 863                         }
 864                         ptrend = ptr + count;
 865                         nlflag = 0;
 866                 } else
 867                         nlflag = 1;
 868                 *ptrend = '\n';
 869                 p = ptr;
 870                 lastptr = ptr;
 871                 cstat = istat;
 872                 succ = 0;
 873                 for(;;) {
 874                         if(out[cstat]) {
 875                                 if(multibyte && p > ptr) {
 876                                         wchar_t wchar;
 877                                         int length;
 878                                         char *endptr = p;
 879                                         p = lastptr;
 880                                         while(p < endptr) {
 881                                                 length = mbtowc(&wchar, p, MB_LEN_MAX);
 882                                                 if(length <= 1)
 883                                                         p++;
 884                                                 else
 885                                                         p += length;
 886                                         }
 887                                         if(p == endptr) {
 888                                                 succ = !vflag;
 889                                                 break;
 890                                         }
 891                                         cstat = 1;
 892                                         length = mbtowc(&wchar, lastptr, MB_LEN_MAX);
 893                                         if(length <= 1)
 894                                                 lastptr++;
 895                                         else
 896                                                 lastptr += length;
 897                                         p = lastptr;
 898                                         continue;
 899                                 }
 900                                 succ = !vflag;
 901                                 break;
 902                         }
 903                         c = (unsigned char)*p++;
 904                         if ((t = gotofn[cstat][c]) == 0)
 905                                 cstat = nxtst(cstat, c);
 906                         else
 907                                 cstat = t;
 908                         if(c == RIGHT) {
 909                                 if(out[cstat]) {
 910                                         succ = !vflag;
 911                                         break;
 912                                 }
 913                                 succ = vflag;
 914                                 break;
 915                         }
 916                 }
 917                 if (succ) {
 918                         nsucc = 1;
 919                         if (lflag || qflag) {
 920                                 if (!qflag)
 921                                         (void) printf("%s\n", file);
 922                                 fclose(f);
 923                                 return;
 924                         }
 925                         if (cflag) {
 926                                 tln++;
 927                         } else {
 928                                 if (Hflag || (nfile > 1 && !hflag))
 929                                         printf("%s:", file);
 930                                 if (bflag) {
 931                                         nchars = blkno - (buf + count - ptrend) - 2;
 932                                         if(nlflag)
 933                                                 nchars++;
 934                                         printf("%lld:", nchars/BLKSIZE);
 935                                 }
 936                                 if (nflag)
 937                                         printf("%lld:", lnum);
 938                                 if(nlflag)
 939                                         nchars = ptrend - ptr + 1;
 940                                 else
 941                                         nchars = ptrend - ptr;
 942                                 fwrite(ptr, (size_t)1, (size_t)nchars, stdout);
 943                         }
 944                 }
 945                 if(!nlflag)
 946                         break;
 947                 ptr = ptrend + 1;
 948                 if(ptr >= buf + count) {
 949                         ptr = buf;
 950                         if((count = read(fileno(f), buf, EBUFSIZ)) <= 0)
 951                                 break;
 952                         blkno += count;
 953                 }
 954                 lnum++;
 955                 if (reinit == 1)
 956                         clearg();
 957         }
 958         fclose(f);
 959         if (cflag && !qflag) {
 960                 if (Hflag || (nfile > 1 && !hflag))
 961                         printf("%s:", file);
 962                 printf("%lld\n", tln);
 963         }
 964 }
 965
 966 void
 967 clearg(void)
 968 {
 969         int i, k;
 970         for (i=1; i<=nstate; i++)
 971                 out[i] = 0;
 972         for (i=1; i<=nstate; i++)
 973                 for (k=0; k<NCHARS; k++)
 974                         gotofn[i][k] = 0;
 975         nstate = 1;
 976         nxtpos = inxtpos;
 977         reinit = 0;
 978         count = 0;
 979         for (i=3; i<=line; i++) tmpstat[i] = 0;
 980         if (cstate(line-1)==0) {
 981                 tmpstat[line] = 1;
 982                 count++;
 983                 out[1] = 1;
 984         }
 985         for (i=3; i<=line; i++) initstat[i] = tmpstat[i];
 986         count--;                /*leave out position 1 */
 987         icount = count;
 988         tmpstat[1] = 0;
 989         add(state, 1);
 990         istat = nxtst(1, LEFT);
 991 }
 992
 993 int
 994 mdotenter(void)
 995 {
 996         int i, x1, x2;
 997         x1 = enter(DOT);
 998         x2 = enter(MDOT);
 999         for(i = 1; i < (int) eucw1; i++)
1000                 x2 = node(CAT, x2, enter(MDOT));
1001         x1 = node(OR, x1, x2);
1002         if(eucw2) {
1003                 x2 = enter('\216');
1004                 for(i = 1; i <= (int) eucw2; i++)
1005                         x2 = node(CAT, x2, enter(MDOT));
1006                 x1 = node(OR, x1, x2);
1007         }
1008         if(eucw3) {
1009                 x2 = enter('\217');
1010                 for(i = 1; i <= (int) eucw3; i++)
1011                         x2 = node(CAT, x2, enter(MDOT));
1012                 x1 = node(OR, x1, x2);
1013         }
1014         return(x1);
1015 }
1016
1017 int
1018 mchar(wchar_t c)
1019 {
1020         char multichar[MB_LEN_MAX+1];
1021         char *p;
1022         int x1, lc, length;
1023
1024         length = wctomb(multichar, c);
1025         p = multichar;
1026         *(p + length) = '\0';
1027         x1 = enter((unsigned char)*p++);
1028         while(lc = (unsigned char)*p++)
1029                 x1 = node(CAT, x1, enter(lc));
1030         return(x1);
1031 }
1032
1033 int
1034 ccl(int type)
1035 {
1036         wchar_t c, lc;
1037         char multic1[MB_LEN_MAX];
1038         char multic2[MB_LEN_MAX];
1039         int x1, x2, length, current, last, cclcnt;
1040         x2 = 0;
1041         current = 0;
1042         last = genrange(type);
1043         nxtchar = count + 1;
1044         cclcnt = 0;
1045         /* create usual character class for single byte characters */
1046         while(current <= last && (isascii(c = lower[current]) || c <= 0377 && iscntrl(c))) {
1047                 cclcnt++;
1048                 chars[nxtchar++] = c;
1049                 if(lower[current] != upper[current]) {
1050                         chars[nxtchar++] = '-';
1051                         chars[nxtchar++] = upper[current];
1052                         cclcnt += 2;
1053                 }
1054                 current++;
1055         }
1056
1057         if(cclcnt)
1058                 chars[count] = cclcnt;
1059         else
1060                 nxtchar = count;
1061         if(current > 0)
1062                 /* single byte part of character class */
1063                 x2 = cclenter(type);
1064         else if(type == NCCL)
1065                 /* all single byte characters match */
1066                 x2 = enter(DOT);
1067         while(current <= last) {
1068                 if(upper[current] == lower[current])
1069                         x1 = mchar(lower[current]);
1070                 else {
1071                         length = wctomb(multic1, lower[current]);
1072                         wctomb(multic2, upper[current]);
1073                         x1 = range((unsigned char *)multic1,
1074                             (unsigned char *)multic2, length);
1075                 }
1076                 if(x2)
1077                         x2 = node(OR, x2, x1);
1078                 else
1079                         x2 = x1;
1080                 current++;
1081         }
1082         return x2;
1083 }
1084
1085 int
1086 range(unsigned char *p1, unsigned char *p2, int length)
1087 {
1088         char multic[MB_LEN_MAX+1];
1089         char *p;
1090         int i, x1, x2;
1091         if(length == 1)
1092                 return(classenter(*p1, *p2));
1093         if(p1[0] == p2[0])
1094                 return(node(CAT, enter(p1[0]), range(p1+1, p2+1, length - 1)));
1095         p = multic;
1096         for(i = 1; i < length; i++)
1097                 *p++ = 0377;
1098         x1 = node(CAT, enter(p1[0]),
1099             range(p1+1, (unsigned char *)multic, length - 1));
1100         if((unsigned char)(p1[0] + 1) < p2[0]) {
1101                 x2 = classenter(p1[0] + 1, p2[0] - 1);
1102                 for(i = 1; i < length; i++)
1103                         x2 = node(CAT, x2, enter(MDOT));
1104                 x1 = node(OR, x1, x2);
1105         }
1106         p = multic;
1107         for(i = 1; i < length; i++)
1108                 *p++ = 0200;
1109         x2 = node(CAT, enter(p2[0]),
1110             range((unsigned char *)multic, p2+1, length - 1));
1111         return node(OR, x1, x2);
1112 }
1113
1114 int
1115 classenter(int x1, int x2)
1116 {
1117         static int max, min;
1118         if(!max) {
1119                 int i;
1120                 for(i = 0200; i <= 0377; i++)
1121                         if(!iscntrl(i))
1122                                 break;
1123                 min = i;
1124                 for(i = 0377; i >= 0200; i--)
1125                         if(!iscntrl(i))
1126                                 break;
1127                 max = i;
1128         }
1129         if(x1 <= min && x2 >= max)
1130                 return enter(MDOT);
1131         if(nxtchar + 4 >= maxclin)
1132                 if(allocchars() == 0)
1133                         overflo();
1134         count = nxtchar++;
1135         chars[nxtchar++] = x1;
1136         chars[nxtchar++] = '-';
1137         chars[nxtchar++] = x2;
1138         chars[count] = 3;
1139         return cclenter(MCCL);
1140 }
1141
1142 int
1143 genrange(int type)
1144 {
1145         char *p, *endp;
1146         int current, nel, i, last, length;
1147         wchar_t c, lc;
1148
1149         current = 0;
1150         p = &chars[count+1];
1151         endp = &chars[count+1] + chars[count];
1152         lc = 0;
1153
1154         /* convert character class into union of ranges */
1155         while(p < endp) {
1156                 length = mbtowc(&c, p, MB_LEN_MAX);
1157                 p += length;
1158                 if(c == '-' && lc != 0) {
1159                         length = mbtowc(&c, p, MB_LEN_MAX);
1160                         upper[current-1] = c;
1161                         p += length;
1162                 } else {
1163                         lower[current] = c;
1164                         upper[current++] = c;
1165                 }
1166                 lc = c;
1167         }
1168         nel = current;
1169         /* sort lower and upper bounds of ranges */
1170         qsort((char *)lower, nel, sizeof(wchar_t), compare);
1171         qsort((char *)upper, nel, sizeof(wchar_t), compare);
1172         last = current - 1;
1173         current = 0;
1174         /* combine overlapping or adjacent ranges */
1175         for(i = 0; i < last; i++)
1176                 if(upper[i] >= lower[i+1] - 1)
1177                         upper[current] = upper[i+1];
1178                 else {
1179                         lower[++current] = lower[i+1];
1180                         upper[current] = upper[i+1];
1181                 }
1182         if(type == NCCL) {
1183                 /* find complement of character class */
1184                 int j, next;
1185                 i = 0;
1186                 while(i <= current && isascii(c=lower[i]) || c <= 0377 && iscntrl(c))
1187                         i++;
1188                 if(i > current) {
1189                         /* match all multibyte characters */
1190                         if(eucw2) {
1191                                 lower[i] = maxmin(WCHAR_CS2, 0);
1192                                 upper[i++] = maxmin(WCHAR_CS2, 1);
1193                         }
1194                         if(eucw3) {
1195                                 lower[i] = maxmin(WCHAR_CS3, 0);
1196                                 upper[i++] = maxmin(WCHAR_CS3, 1);
1197                         }
1198                         lower[i] = maxmin(WCHAR_CS1, 0);
1199                         upper[i++] = maxmin(WCHAR_CS1, 1);
1200                         return i - 1;
1201                 }
1202                 next = current + 1;
1203                 if(next + current + 2 >= maxwclin) {
1204                         maxwclin += MAXLIN + next + current + 2;
1205                         if((lower = (wchar_t *)realloc(lower, maxwclin *sizeof(wchar_t))) == (wchar_t *)0 ||
1206                            (upper = (wchar_t *)realloc(upper, maxwclin * sizeof(wchar_t))) == (wchar_t *)0)
1207                                 overflo();
1208                 }
1209                 if(eucw2 && lower[i] > maxmin(WCHAR_CS2, 0)) {
1210                         lower[next] = maxmin(WCHAR_CS2, 0);
1211                         if((lower[i] & WCHAR_CSMASK) != WCHAR_CS2) {
1212                                 upper[next++] = maxmin(WCHAR_CS2, 1);
1213                                 if((lower[i] & WCHAR_CSMASK) == WCHAR_CS1 && eucw3) {
1214                                         lower[next] = maxmin(WCHAR_CS3, 0);
1215                                         upper[next++] = maxmin(WCHAR_CS3, 1);
1216                                 }
1217                                 if(lower[i] > maxmin(lower[i] & WCHAR_CSMASK, 0)) {
1218                                         lower[next] = maxmin(lower[i] & WCHAR_CSMASK, 0);
1219                                         upper[next++] = lower[i] - 1;
1220                                 }
1221                         } else
1222                                 upper[next++] = lower[i] - 1;
1223                 } else if(lower[i] > maxmin(lower[i] & WCHAR_CSMASK, 0)) {
1224                         lower[next] = maxmin(lower[i] & WCHAR_CSMASK, 0);
1225                         upper[next++] = lower[i] - 1;
1226                 }
1227                 for(j = i; j < current; j++) {
1228                         if(upper[j] < maxmin(upper[j] & WCHAR_CSMASK, 1)) {
1229                                 lower[next] = upper[j] + 1;
1230                                 if((upper[j] & WCHAR_CSMASK) != (lower[j+1] & WCHAR_CSMASK)) {
1231                                         upper[next++] = maxmin(upper[j] & WCHAR_CSMASK, 1);
1232                                         if(eucw3 && (upper[j] & WCHAR_CSMASK) == WCHAR_CS2 && (lower[j+1] & WCHAR_CSMASK) == WCHAR_CS1) {
1233                                                 lower[next] = maxmin(WCHAR_CS3, 0);
1234                                                 upper[next++] = maxmin(WCHAR_CS3, 1);
1235                                         }
1236                                         if(lower[j+1] > maxmin(lower[j+1] & WCHAR_CSMASK, 0)) {
1237                                                 lower[next] = maxmin(lower[j+1] & WCHAR_CSMASK, 0);
1238                                                 upper[next++] = lower[j+1] - 1;
1239                                         }
1240                                 } else
1241                                         upper[next++] = lower[j+1] - 1;
1242                         } else if(lower[j+1] > maxmin(lower[j+1], 0)) {
1243                                 lower[next] = maxmin(lower[j+1], 0);
1244                                 upper[next++] = lower[j+1] - 1;
1245                         }
1246                 }
1247                 if(upper[current] < maxmin(upper[current] & WCHAR_CSMASK, 1)) {
1248                         lower[next] = upper[current] + 1;
1249                         upper[next++] = maxmin(upper[current] & WCHAR_CSMASK, 1);
1250                 }
1251                 if((upper[current] & WCHAR_CSMASK) != WCHAR_CS1) {
1252                         if((upper[current] & WCHAR_CSMASK) == WCHAR_CS2 && eucw3) {
1253                                 lower[next] = maxmin(WCHAR_CS3, 0);
1254                                 upper[next++] = maxmin(WCHAR_CS3, 1);
1255                         }
1256                         lower[next] = maxmin(WCHAR_CS1, 0);
1257                         upper[next++] = maxmin(WCHAR_CS1, 1);
1258                 }
1259                 for(j = current + 1; j < next; j++) {
1260                         lower[i] = lower[j];
1261                         upper[i++] = upper[j];
1262                 }
1263                 current = i - 1;
1264         }
1265         return(current);
1266 }
1267
1268 int
1269 compare(wchar_t *c, wchar_t *d)
1270 {
1271         if(*c < *d)
1272                 return -1;
1273         if(*c == *d)
1274                 return 0;
1275         return 1;
1276 }
1277
1278 wchar_t
1279 maxmin(wchar_t c, int flag)
1280 {
1281         static wchar_t minmax1[2], minmax2[2], minmax3[2];
1282
1283         if(!minmax1[0]) {
1284                 /* compute min and max process codes for all code sets */
1285                 int length, i;
1286                 char multic[MB_LEN_MAX], minmax[2];
1287                 for(i = 0377; i >= 0200; i--)
1288                         if(!iscntrl(i))
1289                                 break;
1290                 minmax[1] = i;
1291                 for(i = 0240; i <= 0377; i++)
1292                         if(!iscntrl(i))
1293                                 break;
1294                 minmax[0] = i;
1295                 for(i = 0; i <= 1; i++) {
1296                         length = MB_LEN_MAX;
1297                         while(length--)
1298                                 multic[length] = minmax[i];
1299                         mbtowc(&minmax1[i], multic, MB_LEN_MAX);
1300                         if(eucw2) {
1301                                 multic[0] = SS2;
1302                                 mbtowc(&minmax2[i], multic, MB_LEN_MAX);
1303                         }
1304                         if(eucw3) {
1305                                 multic[0] = SS3;
1306                                 mbtowc(&minmax3[i], multic, MB_LEN_MAX);
1307                         }
1308                 }
1309         }
1310         switch(c) {
1311                 case WCHAR_CS1: return minmax1[flag];
1312                 case WCHAR_CS2: return minmax2[flag];
1313                 case WCHAR_CS3: return minmax3[flag];
1314         }
1315
1316         /* NOTREACHED */
1317         return (0);
1318 }