lib/contrib/regexpr.c

   1 /*
   2
   3 regexpr.c
   4
   5 Author: Tatu Ylonen <ylo@ngs.fi>
   6
   7 Copyright (c) 1991 Tatu Ylonen, Espoo, Finland
   8
   9 Permission to use, copy, modify, distribute, and sell this software
  10 and its documentation is hereby granted without fee, provided that the
  11 above copyright notice appears in all source code copies, the name of
  12 Tatu Ylonen is not used to advertise products containing this software
  13 or a derivation thereof, and all modified versions are clearly marked
  14 as such.
  15
  16 This software is provided "as is" without express or implied warranty.
  17
  18 Created: Thu Sep 26 17:14:05 1991 ylo
  19 Last modified: Sun Mar 29 16:47:31 1992 ylo
  20
  21 This code draws many ideas from the regular expression packages by
  22 Henry Spencer of the University of Toronto and Richard Stallman of the
  23 Free Software Foundation.
  24
  25 Emacs-specific code and syntax table code is almost directly borrowed
  26 from GNU regexp.
  27
  28 $Id$
  29
  30 */
  31
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35 #include <stdarg.h>
  36 #include <ctype.h>
  37 #include <sys/types.h>
  38 #include <sys/stat.h>
  39 #include <time.h>
  40
  41 #include <stdio.h>
  42 #include <assert.h>
  43 //#include "silc.h"
  44 #include "regexpr.h"
  45
  46 #define MACRO_BEGIN do {
  47 #define MACRO_END } while (0)
  48
  49 enum regexp_compiled_ops /* opcodes for compiled regexp */
  50 {
  51   Cend,                 /* end of pattern reached */
  52   Cbol,                 /* beginning of line */
  53   Ceol,                 /* end of line */
  54   Cset,                 /* character set.  Followed by 32 bytes of set. */
  55   Cexact,               /* followed by a byte to match */
  56   Canychar,             /* matches any character except newline */
  57   Cstart_memory,        /* set register start addr (followed by reg number) */
  58   Cend_memory,          /* set register end addr (followed by reg number) */
  59   Cmatch_memory,        /* match a duplicate of reg contents (regnum follows)*/
  60   Cjump,                /* followed by two bytes (lsb,msb) of displacement. */
  61   Cstar_jump,           /* will change to jump/update_failure_jump at runtime */
  62   Cfailure_jump,        /* jump to addr on failure */
  63   Cupdate_failure_jump, /* update topmost failure point and jump */
  64   Cdummy_failure_jump,  /* push a dummy failure point and jump */
  65   Cbegbuf,              /* match at beginning of buffer */
  66   Cendbuf,              /* match at end of buffer */
  67   Cwordbeg,             /* match at beginning of word */
  68   Cwordend,             /* match at end of word */
  69   Cwordbound,           /* match if at word boundary */
  70   Cnotwordbound,        /* match if not at word boundary */
  71 #ifdef emacs
  72   Cemacs_at_dot,        /* emacs only: matches at dot */
  73 #endif /* emacs */
  74   Csyntaxspec,          /* matches syntax code (1 byte follows) */
  75   Cnotsyntaxspec        /* matches if syntax code does not match (1 byte foll)*/
  76 };
  77
  78 enum regexp_syntax_op   /* syntax codes for plain and quoted characters */
  79 {
  80   Rend,                 /* special code for end of regexp */
  81   Rnormal,              /* normal character */
  82   Ranychar,             /* any character except newline */
  83   Rquote,               /* the quote character */
  84   Rbol,                 /* match beginning of line */
  85   Reol,                 /* match end of line */
  86   Roptional,            /* match preceding expression optionally */
  87   Rstar,                /* match preceding expr zero or more times */
  88   Rplus,                /* match preceding expr one or more times */
  89   Ror,                  /* match either of alternatives */
  90   Ropenpar,             /* opening parenthesis */
  91   Rclosepar,            /* closing parenthesis */
  92   Rmemory,              /* match memory register */
  93   Rextended_memory,     /* \vnn to match registers 10-99 */
  94   Ropenset,             /* open set.  Internal syntax hard-coded below. */
  95   /* the following are gnu extensions to "normal" regexp syntax */
  96   Rbegbuf,              /* beginning of buffer */
  97   Rendbuf,              /* end of buffer */
  98   Rwordchar,            /* word character */
  99   Rnotwordchar,         /* not word character */
 100   Rwordbeg,             /* beginning of word */
 101   Rwordend,             /* end of word */
 102   Rwordbound,           /* word bound */
 103   Rnotwordbound,        /* not word bound */
 104 #ifdef emacs
 105   Remacs_at_dot,        /* emacs: at dot */
 106   Remacs_syntaxspec,    /* syntaxspec */
 107   Remacs_notsyntaxspec, /* notsyntaxspec */
 108 #endif /* emacs */
 109   Rnum_ops
 110 };
 111
 112 static int re_compile_initialized = 0;
 113 static int regexp_syntax = 0;
 114 static unsigned char regexp_plain_ops[256];
 115 static unsigned char regexp_quoted_ops[256];
 116 static unsigned char regexp_precedences[Rnum_ops];
 117 static int regexp_context_indep_ops;
 118 static int regexp_ansi_sequences;
 119
 120 #define NUM_LEVELS  5    /* number of precedence levels in use */
 121 #define MAX_NESTING 100  /* max nesting level of operators */
 122
 123 #ifdef emacs
 124
 125 /* This code is for emacs compatibility only. */
 126
 127 #include "config.h"
 128 #include "lisp.h"
 129 #include "buffer.h"
 130 #include "syntax.h"
 131
 132 /* emacs defines NULL in some strange way? */
 133 #undef NULL
 134 #define NULL 0
 135
 136 #else /* emacs */
 137
 138 #define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)]
 139 #define Sword 1
 140
 141 #ifdef SYNTAX_TABLE
 142 char *re_syntax_table;
 143 #else
 144 static char re_syntax_table[256];
 145 #endif /* SYNTAX_TABLE */
 146
 147 #endif /* emacs */
 148
 149 static void re_compile_initialize()
 150 {
 151   int a;
 152
 153 #if !defined(emacs) && !defined(SYNTAX_TABLE)
 154   static int syntax_table_inited = 0;
 155
 156   if (!syntax_table_inited)
 157     {
 158       syntax_table_inited = 1;
 159       memset(re_syntax_table, 0, 256);
 160       for (a = 'a'; a <= 'z'; a++)
 161         re_syntax_table[a] = Sword;
 162       for (a = 'A'; a <= 'Z'; a++)
 163         re_syntax_table[a] = Sword;
 164       for (a = '0'; a <= '9'; a++)
 165         re_syntax_table[a] = Sword;
 166     }
 167 #endif /* !emacs && !SYNTAX_TABLE */
 168   re_compile_initialized = 1;
 169   for (a = 0; a < 256; a++)
 170     {
 171       regexp_plain_ops[a] = Rnormal;
 172       regexp_quoted_ops[a] = Rnormal;
 173     }
 174   for (a = '0'; a <= '9'; a++)
 175     regexp_quoted_ops[a] = Rmemory;
 176   regexp_plain_ops['\134'] = Rquote;
 177   if (regexp_syntax & RE_NO_BK_PARENS)
 178     {
 179       regexp_plain_ops['('] = Ropenpar;
 180       regexp_plain_ops[')'] = Rclosepar;
 181     }
 182   else
 183     {
 184       regexp_quoted_ops['('] = Ropenpar;
 185       regexp_quoted_ops[')'] = Rclosepar;
 186     }
 187   if (regexp_syntax & RE_NO_BK_VBAR)
 188     regexp_plain_ops['\174'] = Ror;
 189   else
 190     regexp_quoted_ops['\174'] = Ror;
 191   regexp_plain_ops['*'] = Rstar;
 192   if (regexp_syntax & RE_BK_PLUS_QM)
 193     {
 194       regexp_quoted_ops['+'] = Rplus;
 195       regexp_quoted_ops['?'] = Roptional;
 196     }
 197   else
 198     {
 199       regexp_plain_ops['+'] = Rplus;
 200       regexp_plain_ops['?'] = Roptional;
 201     }
 202   if (regexp_syntax & RE_NEWLINE_OR)
 203     regexp_plain_ops['\n'] = Ror;
 204   regexp_plain_ops['\133'] = Ropenset;
 205   regexp_plain_ops['\136'] = Rbol;
 206   regexp_plain_ops['$'] = Reol;
 207   regexp_plain_ops['.'] = Ranychar;
 208   if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS))
 209     {
 210 #ifdef emacs
 211       regexp_quoted_ops['='] = Remacs_at_dot;
 212       regexp_quoted_ops['s'] = Remacs_syntaxspec;
 213       regexp_quoted_ops['S'] = Remacs_notsyntaxspec;
 214 #endif /* emacs */
 215       regexp_quoted_ops['w'] = Rwordchar;
 216       regexp_quoted_ops['W'] = Rnotwordchar;
 217       regexp_quoted_ops['<'] = Rwordbeg;
 218       regexp_quoted_ops['>'] = Rwordend;
 219       regexp_quoted_ops['b'] = Rwordbound;
 220       regexp_quoted_ops['B'] = Rnotwordbound;
 221       regexp_quoted_ops['`'] = Rbegbuf;
 222       regexp_quoted_ops['\''] = Rendbuf;
 223     }
 224   if (regexp_syntax & RE_ANSI_HEX)
 225     regexp_quoted_ops['v'] = Rextended_memory;
 226   for (a = 0; a < Rnum_ops; a++)
 227     regexp_precedences[a] = 4;
 228   if (regexp_syntax & RE_TIGHT_VBAR)
 229     {
 230       regexp_precedences[Ror] = 3;
 231       regexp_precedences[Rbol] = 2;
 232       regexp_precedences[Reol] = 2;
 233     }
 234   else
 235     {
 236       regexp_precedences[Ror] = 2;
 237       regexp_precedences[Rbol] = 3;
 238       regexp_precedences[Reol] = 3;
 239     }
 240   regexp_precedences[Rclosepar] = 1;
 241   regexp_precedences[Rend] = 0;
 242   regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0;
 243   regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0;
 244 }
 245
 246 int re_set_syntax(syntax)
 247 int syntax;
 248 {
 249   int ret;
 250
 251   ret = regexp_syntax;
 252   regexp_syntax = syntax;
 253   re_compile_initialize();
 254   return ret;
 255 }
 256
 257 static int hex_char_to_decimal(ch)
 258 int ch;
 259 {
 260   if (ch >= '0' && ch <= '9')
 261     return ch - '0';
 262   if (ch >= 'a' && ch <= 'f')
 263     return ch - 'a' + 10;
 264   if (ch >= 'A' && ch <= 'F')
 265     return ch - 'A' + 10;
 266   return 16;
 267 }
 268
 269 char *re_compile_pattern(regex, size, bufp)
 270 char *regex;
 271 int size;
 272 regexp_t bufp;
 273 {
 274   int a, pos, op, current_level, level, opcode;
 275   int pattern_offset = 0, alloc;
 276   int starts[NUM_LEVELS * MAX_NESTING], starts_base;
 277   int future_jumps[MAX_NESTING], num_jumps;
 278   unsigned char ch = 0;
 279   char *pattern, *translate;
 280   int next_register, paren_depth, num_open_registers, open_registers[RE_NREGS];
 281   int beginning_context;
 282
 283 #define NEXTCHAR(var)                   \
 284   MACRO_BEGIN                           \
 285     if (pos >= size)                    \
 286       goto ends_prematurely;            \
 287     (var) = regex[pos];                 \
 288     pos++;                              \
 289   MACRO_END
 290
 291 #define ALLOC(amount)                           \
 292   MACRO_BEGIN                                   \
 293     if (pattern_offset+(amount) > alloc)        \
 294       {                                         \
 295         alloc += 256 + (amount);                \
 296         pattern = realloc(pattern, alloc);      \
 297         if (!pattern)                           \
 298           goto out_of_memory;                   \
 299       }                                         \
 300   MACRO_END
 301
 302 #define STORE(ch) pattern[pattern_offset++] = (ch)
 303
 304 #define CURRENT_LEVEL_START (starts[starts_base + current_level])
 305
 306 #define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset
 307
 308 #define PUSH_LEVEL_STARTS if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
 309                             starts_base += NUM_LEVELS;                  \
 310                           else                                          \
 311                             goto too_complex
 312
 313 #define POP_LEVEL_STARTS starts_base -= NUM_LEVELS
 314
 315 #define PUT_ADDR(offset,addr)                           \
 316   MACRO_BEGIN                                           \
 317     int disp = (addr) - (offset) - 2;                   \
 318     pattern[(offset)] = disp & 0xff;                    \
 319     pattern[(offset)+1] = (disp>>8) & 0xff;             \
 320   MACRO_END
 321
 322 #define INSERT_JUMP(pos,type,addr)                      \
 323   MACRO_BEGIN                                           \
 324     int a, p = (pos), t = (type), ad = (addr);          \
 325     for (a = pattern_offset - 1; a >= p; a--)           \
 326       pattern[a + 3] = pattern[a];                      \
 327     pattern[p] = t;                                     \
 328     PUT_ADDR(p+1,ad);                                   \
 329     pattern_offset += 3;                                \
 330   MACRO_END
 331
 332 #define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))
 333
 334 #define SET_FIELDS                              \
 335   MACRO_BEGIN                                   \
 336     bufp->allocated = alloc;                    \
 337     bufp->buffer = pattern;                     \
 338     bufp->used = pattern_offset;                \
 339   MACRO_END
 340
 341 #define GETHEX(var)                                             \
 342   MACRO_BEGIN                                                   \
 343     char gethex_ch, gethex_value;                               \
 344     NEXTCHAR(gethex_ch);                                        \
 345     gethex_value = hex_char_to_decimal(gethex_ch);              \
 346     if (gethex_value == 16)                                     \
 347       goto hex_error;                                           \
 348     NEXTCHAR(gethex_ch);                                        \
 349     gethex_ch = hex_char_to_decimal(gethex_ch);                 \
 350     if (gethex_ch == 16)                                        \
 351       goto hex_error;                                           \
 352     (var) = gethex_value * 16 + gethex_ch;                      \
 353   MACRO_END
 354
 355 #define ANSI_TRANSLATE(ch)                              \
 356   MACRO_BEGIN                                           \
 357     switch (ch)                                         \
 358       {                                                 \
 359       case 'a':                                         \
 360       case 'A':                                         \
 361         ch = 7; /* audible bell */                      \
 362         break;                                          \
 363       case 'b':                                         \
 364       case 'B':                                         \
 365         ch = 8; /* backspace */                         \
 366         break;                                          \
 367       case 'f':                                         \
 368       case 'F':                                         \
 369         ch = 12; /* form feed */                        \
 370         break;                                          \
 371       case 'n':                                         \
 372       case 'N':                                         \
 373         ch = 10; /* line feed */                        \
 374         break;                                          \
 375       case 'r':                                         \
 376       case 'R':                                         \
 377         ch = 13; /* carriage return */                  \
 378         break;                                          \
 379       case 't':                                         \
 380       case 'T':                                         \
 381         ch = 9; /* tab */                               \
 382         break;                                          \
 383       case 'v':                                         \
 384       case 'V':                                         \
 385         ch = 11; /* vertical tab */                     \
 386         break;                                          \
 387       case 'x': /* hex code */                          \
 388       case 'X':                                         \
 389         GETHEX(ch);                                     \
 390         break;                                          \
 391       default:                                          \
 392         /* other characters passed through */           \
 393         if (translate)                                  \
 394           ch = translate[(unsigned char)ch];            \
 395         break;                                          \
 396       }                                                 \
 397   MACRO_END
 398
 399   if (!re_compile_initialized)
 400     re_compile_initialize();
 401   bufp->used = 0;
 402   bufp->fastmap_accurate = 0;
 403   bufp->uses_registers = 0;
 404   translate = bufp->translate;
 405   pattern = bufp->buffer;
 406   alloc = bufp->allocated;
 407   if (alloc == 0 || pattern == NULL)
 408     {
 409       alloc = 256;
 410       pattern = malloc(alloc);
 411       if (!pattern)
 412         goto out_of_memory;
 413     }
 414   pattern_offset = 0;
 415   starts_base = 0;
 416   num_jumps = 0;
 417   current_level = 0;
 418   SET_LEVEL_START;
 419   num_open_registers = 0;
 420   next_register = 1;
 421   paren_depth = 0;
 422   beginning_context = 1;
 423   op = -1;
 424   /* we use Rend dummy to ensure that pending jumps are updated (due to
 425      low priority of Rend) before exiting the loop. */
 426   pos = 0;
 427   while (op != Rend)
 428     {
 429       if (pos >= size)
 430         op = Rend;
 431       else
 432         {
 433           NEXTCHAR(ch);
 434           if (translate)
 435             ch = translate[(unsigned char)ch];
 436           op = regexp_plain_ops[(unsigned char)ch];
 437           if (op == Rquote)
 438             {
 439               NEXTCHAR(ch);
 440               op = regexp_quoted_ops[(unsigned char)ch];
 441               if (op == Rnormal && regexp_ansi_sequences)
 442                 ANSI_TRANSLATE(ch);
 443             }
 444         }
 445       level = regexp_precedences[op];
 446       /* printf("ch='%c' op=%d level=%d current_level=%d curlevstart=%d\n",
 447              ch, op, level, current_level, CURRENT_LEVEL_START); */
 448       if (level > current_level)
 449         {
 450           for (current_level++; current_level < level; current_level++)
 451             SET_LEVEL_START;
 452           SET_LEVEL_START;
 453         }
 454       else
 455         if (level < current_level)
 456           {
 457             current_level = level;
 458             for (;num_jumps > 0 &&
 459                  future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
 460                  num_jumps--)
 461               PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
 462           }
 463       switch (op)
 464         {
 465         case Rend:
 466           break;
 467         case Rnormal:
 468         normal_char:
 469           opcode = Cexact;
 470         store_opcode_and_arg: /* opcode & ch must be set */
 471           SET_LEVEL_START;
 472           ALLOC(2);
 473           STORE(opcode);
 474           STORE(ch);
 475           break;
 476         case Ranychar:
 477           opcode = Canychar;
 478         store_opcode:
 479           SET_LEVEL_START;
 480           ALLOC(1);
 481           STORE(opcode);
 482           break;
 483         case Rquote:
 484           abort();
 485           /*NOTREACHED*/
 486         case Rbol:
 487           if (!beginning_context) {
 488             if (regexp_context_indep_ops)
 489               goto op_error;
 490             else
 491               goto normal_char;
 492           }
 493           opcode = Cbol;
 494           goto store_opcode;
 495         case Reol:
 496           if (!((pos >= size) ||
 497                 ((regexp_syntax & RE_NO_BK_VBAR) ?
 498                  (regex[pos] == '\174') :
 499                  (pos+1 < size && regex[pos] == '\134' &&
 500                   regex[pos+1] == '\174')) ||
 501                 ((regexp_syntax & RE_NO_BK_PARENS)?
 502                  (regex[pos] == ')'):
 503                  (pos+1 < size && regex[pos] == '\134' &&
 504                   regex[pos+1] == ')')))) {
 505             if (regexp_context_indep_ops)
 506               goto op_error;
 507             else
 508               goto normal_char;
 509           }
 510           opcode = Ceol;
 511           goto store_opcode;
 512           break;
 513         case Roptional:
 514           if (beginning_context) {
 515             if (regexp_context_indep_ops)
 516               goto op_error;
 517             else
 518               goto normal_char;
 519           }
 520           if (CURRENT_LEVEL_START == pattern_offset)
 521             break; /* ignore empty patterns for ? */
 522           ALLOC(3);
 523           INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
 524                       pattern_offset + 3);
 525           break;
 526         case Rstar:
 527         case Rplus:
 528           if (beginning_context) {
 529             if (regexp_context_indep_ops)
 530               goto op_error;
 531             else
 532               goto normal_char;
 533           }
 534           if (CURRENT_LEVEL_START == pattern_offset)
 535             break; /* ignore empty patterns for + and * */
 536           ALLOC(9);
 537           INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
 538                       pattern_offset + 6);
 539           INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
 540           if (op == Rplus)  /* jump over initial failure_jump */
 541             INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
 542                         CURRENT_LEVEL_START + 6);
 543           break;
 544         case Ror:
 545           ALLOC(6);
 546           INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
 547                       pattern_offset + 6);
 548           if (num_jumps >= MAX_NESTING)
 549             goto too_complex;
 550           STORE(Cjump);
 551           future_jumps[num_jumps++] = pattern_offset;
 552           STORE(0);
 553           STORE(0);
 554           SET_LEVEL_START;
 555           break;
 556         case Ropenpar:
 557           SET_LEVEL_START;
 558           if (next_register < RE_NREGS)
 559             {
 560               bufp->uses_registers = 1;
 561               ALLOC(2);
 562               STORE(Cstart_memory);
 563               STORE(next_register);
 564               open_registers[num_open_registers++] = next_register;
 565               next_register++;
 566             }
 567           paren_depth++;
 568           PUSH_LEVEL_STARTS;
 569           current_level = 0;
 570           SET_LEVEL_START;
 571           break;
 572         case Rclosepar:
 573           if (paren_depth <= 0)
 574             goto parenthesis_error;
 575           POP_LEVEL_STARTS;
 576           current_level = regexp_precedences[Ropenpar];
 577           paren_depth--;
 578           if (paren_depth < num_open_registers)
 579             {
 580               bufp->uses_registers = 1;
 581               ALLOC(2);
 582               STORE(Cend_memory);
 583               num_open_registers--;
 584               STORE(open_registers[num_open_registers]);
 585             }
 586           break;
 587         case Rmemory:
 588           if (ch == '0')
 589             goto bad_match_register;
 590           assert(ch >= '0' && ch <= '9');
 591           bufp->uses_registers = 1;
 592           opcode = Cmatch_memory;
 593           ch -= '0';
 594           goto store_opcode_and_arg;
 595         case Rextended_memory:
 596           NEXTCHAR(ch);
 597           if (ch < '0' || ch > '9')
 598             goto bad_match_register;
 599           NEXTCHAR(a);
 600           if (a < '0' || a > '9')
 601             goto bad_match_register;
 602           ch = 10 * (a - '0') + ch - '0';
 603           if (ch <= 0 || ch >= RE_NREGS)
 604             goto bad_match_register;
 605           bufp->uses_registers = 1;
 606           opcode = Cmatch_memory;
 607           goto store_opcode_and_arg;
 608         case Ropenset:
 609           {
 610             int complement,prev,offset,range,firstchar;
 611
 612             SET_LEVEL_START;
 613             ALLOC(1+256/8);
 614             STORE(Cset);
 615             offset = pattern_offset;
 616             for (a = 0; a < 256/8; a++)
 617               STORE(0);
 618             NEXTCHAR(ch);
 619             if (translate)
 620               ch = translate[(unsigned char)ch];
 621             if (ch == '\136')
 622               {
 623                 complement = 1;
 624                 NEXTCHAR(ch);
 625                 if (translate)
 626                   ch = translate[(unsigned char)ch];
 627               }
 628             else
 629               complement = 0;
 630             prev = -1;
 631             range = 0;
 632             firstchar = 1;
 633             while (ch != '\135' || firstchar)
 634               {
 635                 firstchar = 0;
 636                 if (regexp_ansi_sequences && ch == '\134')
 637                   {
 638                     NEXTCHAR(ch);
 639                     ANSI_TRANSLATE(ch);
 640                   }
 641                 if (range)
 642                   {
 643                     for (a = prev; a <= ch; a++)
 644                       SETBIT(pattern, offset, a);
 645                     prev = -1;
 646                     range = 0;
 647                   }
 648                 else
 649                   if (prev != -1 && ch == '-')
 650                     range = 1;
 651                   else
 652                     {
 653                       SETBIT(pattern, offset, ch);
 654                       prev = ch;
 655                     }
 656                 NEXTCHAR(ch);
 657                 if (translate)
 658                   ch = translate[(unsigned char)ch];
 659               }
 660             if (range)
 661               SETBIT(pattern, offset, '-');
 662             if (complement)
 663               {
 664                 for (a = 0; a < 256/8; a++)
 665                   pattern[offset+a] ^= 0xff;
 666               }
 667             break;
 668           }
 669         case Rbegbuf:
 670           opcode = Cbegbuf;
 671           goto store_opcode;
 672         case Rendbuf:
 673           opcode = Cendbuf;
 674           goto store_opcode;
 675         case Rwordchar:
 676           opcode = Csyntaxspec;
 677           ch = Sword;
 678           goto store_opcode_and_arg;
 679         case Rnotwordchar:
 680           opcode = Cnotsyntaxspec;
 681           ch = Sword;
 682           goto store_opcode_and_arg;
 683         case Rwordbeg:
 684           opcode = Cwordbeg;
 685           goto store_opcode;
 686         case Rwordend:
 687           opcode = Cwordend;
 688           goto store_opcode;
 689         case Rwordbound:
 690           opcode = Cwordbound;
 691           goto store_opcode;
 692         case Rnotwordbound:
 693           opcode = Cnotwordbound;
 694           goto store_opcode;
 695 #ifdef emacs
 696         case Remacs_at_dot:
 697           opcode = Cemacs_at_dot;
 698           goto store_opcode;
 699         case Remacs_syntaxspec:
 700           NEXTCHAR(ch);
 701           if (translate)
 702             ch = translate[(unsigned char)ch];
 703           opcode = Csyntaxspec;
 704           ch = syntax_spec_code[(unsigned char)ch];
 705           goto store_opcode_and_arg;
 706         case Remacs_notsyntaxspec:
 707           NEXTCHAR(ch);
 708           if (translate)
 709             ch = translate[(unsigned char)ch];
 710           opcode = Cnotsyntaxspec;
 711           ch = syntax_spec_code[(unsigned char)ch];
 712           goto store_opcode_and_arg;
 713 #endif /* emacs */
 714         default:
 715           abort();
 716         }
 717       beginning_context = (op == Ropenpar || op == Ror);
 718     }
 719   if (starts_base != 0)
 720     goto parenthesis_error;
 721   assert(num_jumps == 0);
 722   ALLOC(1);
 723   STORE(Cend);
 724   SET_FIELDS;
 725   return NULL;
 726
 727  op_error:
 728   SET_FIELDS;
 729   return "Badly placed special character";
 730
 731  bad_match_register:
 732   SET_FIELDS;
 733   return "Bad match register number";
 734
 735  hex_error:
 736   SET_FIELDS;
 737   return "Bad hexadecimal number";
 738
 739  parenthesis_error:
 740   SET_FIELDS;
 741   return "Badly placed parenthesis";
 742
 743  out_of_memory:
 744   SET_FIELDS;
 745   return "Out of memory";
 746
 747  ends_prematurely:
 748   SET_FIELDS;
 749   return "Regular expression ends prematurely";
 750
 751  too_complex:
 752   SET_FIELDS;
 753   return "Regular expression too complex";
 754 }
 755 #undef CHARAT
 756 #undef NEXTCHAR
 757 #undef GETHEX
 758 #undef ALLOC
 759 #undef STORE
 760 #undef CURRENT_LEVEL_START
 761 #undef SET_LEVEL_START
 762 #undef PUSH_LEVEL_STARTS
 763 #undef POP_LEVEL_STARTS
 764 #undef PUT_ADDR
 765 #undef INSERT_JUMP
 766 #undef SETBIT
 767 #undef SET_FIELDS
 768
 769 static void re_compile_fastmap_aux(code, pos, visited, can_be_null, fastmap)
 770 char *code, *visited, *can_be_null, *fastmap;
 771 int pos;
 772 {
 773   int a, b, syntaxcode;
 774
 775   if (visited[pos])
 776     return;  /* we have already been here */
 777   visited[pos] = 1;
 778   for (;;)
 779     switch (code[pos++])
 780       {
 781       case Cend:
 782         *can_be_null = 1;
 783         return;
 784       case Cbol:
 785       case Cbegbuf:
 786       case Cendbuf:
 787       case Cwordbeg:
 788       case Cwordend:
 789       case Cwordbound:
 790       case Cnotwordbound:
 791 #ifdef emacs
 792       case Cemacs_at_dot:
 793 #endif /* emacs */
 794         break;
 795       case Csyntaxspec:
 796         syntaxcode = code[pos++];
 797         for (a = 0; a < 256; a++)
 798           if (SYNTAX(a) == syntaxcode)
 799             fastmap[a] = 1;
 800         return;
 801       case Cnotsyntaxspec:
 802         syntaxcode = code[pos++];
 803         for (a = 0; a < 256; a++)
 804           if (SYNTAX(a) != syntaxcode)
 805             fastmap[a] = 1;
 806         return;
 807       case Ceol:
 808         fastmap['\n'] = 1;
 809         if (*can_be_null == 0)
 810           *can_be_null = 2;  /* can match null, but only at end of buffer*/
 811         return;
 812       case Cset:
 813         for (a = 0; a < 256/8; a++)
 814           if (code[pos + a] != 0)
 815             for (b = 0; b < 8; b++)
 816               if (code[pos + a] & (1 << b))
 817                 fastmap[(a << 3) + b] = 1;
 818         pos += 256/8;
 819         return;
 820       case Cexact:
 821         fastmap[(unsigned char)code[pos]] = 1;
 822         return;
 823       case Canychar:
 824         for (a = 0; a < 256; a++)
 825           if (a != '\n')
 826             fastmap[a] = 1;
 827         return;
 828       case Cstart_memory:
 829       case Cend_memory:
 830         pos++;
 831         break;
 832       case Cmatch_memory:
 833         for (a = 0; a < 256; a++)
 834           fastmap[a] = 1;
 835         *can_be_null = 1;
 836         return;
 837       case Cjump:
 838       case Cdummy_failure_jump:
 839       case Cupdate_failure_jump:
 840       case Cstar_jump:
 841         a = (unsigned char)code[pos++];
 842         a |= (unsigned char)code[pos++] << 8;
 843         pos += (int)(short)a;
 844         if (visited[pos])
 845           {
 846             /* argh... the regexp contains empty loops.  This is not
 847                good, as this may cause a failure stack overflow when
 848                matching.  Oh well. */
 849             /* this path leads nowhere; pursue other paths. */
 850             return;
 851           }
 852         visited[pos] = 1;
 853         break;
 854       case Cfailure_jump:
 855         a = (unsigned char)code[pos++];
 856         a |= (unsigned char)code[pos++] << 8;
 857         a = pos + (int)(short)a;
 858         re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap);
 859         break;
 860       default:
 861         abort();  /* probably some opcode is missing from this switch */
 862         /*NOTREACHED*/
 863       }
 864 }
 865
 866 static int re_do_compile_fastmap(buffer, used, pos, can_be_null, fastmap)
 867 char *buffer, *fastmap, *can_be_null;
 868 int used, pos;
 869 {
 870   char small_visited[512], *visited;
 871
 872   if (used <= sizeof(small_visited))
 873     visited = small_visited;
 874   else
 875     {
 876       visited = malloc(used);
 877       if (!visited)
 878         return 0;
 879     }
 880   *can_be_null = 0;
 881   memset(fastmap, 0, 256);
 882   memset(visited, 0, used);
 883   re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap);
 884   if (visited != small_visited)
 885     free(visited);
 886   return 1;
 887 }
 888
 889 void re_compile_fastmap(bufp)
 890 regexp_t bufp;
 891 {
 892   if (!bufp->fastmap || bufp->fastmap_accurate)
 893     return;
 894   assert(bufp->used > 0);
 895   if (!re_do_compile_fastmap(bufp->buffer, bufp->used, 0, &bufp->can_be_null,
 896                              bufp->fastmap))
 897     return;
 898   if (bufp->buffer[0] == Cbol)
 899     bufp->anchor = 1;   /* begline */
 900   else
 901     if (bufp->buffer[0] == Cbegbuf)
 902       bufp->anchor = 2; /* begbuf */
 903     else
 904       bufp->anchor = 0; /* none */
 905   bufp->fastmap_accurate = 1;
 906 }
 907
 908 #define INITIAL_FAILURES  128  /* initial # failure points to allocate */
 909 #define MAX_FAILURES     4100  /* max # of failure points before failing */
 910
 911 int re_match_2(bufp, string1, size1, string2, size2, pos, regs, mstop)
 912 regexp_t bufp;
 913 char *string1, *string2;
 914 int size1, size2, pos, mstop;
 915 regexp_registers_t regs;
 916 {
 917   struct failure_point { char *text, *partend, *code; }
 918     *failure_stack_start, *failure_sp, *failure_stack_end,
 919     initial_failure_stack[INITIAL_FAILURES];
 920   char *code, *translate, *text, *textend, *partend, *part_2_end;
 921   char *regstart_text[RE_NREGS], *regstart_partend[RE_NREGS];
 922   char *regend_text[RE_NREGS], *regend_partend[RE_NREGS];
 923   int a, b, ch, reg, regch, match_end;
 924   char *regtext, *regpartend, *regtextend;
 925
 926 #define PREFETCH                                        \
 927   MACRO_BEGIN                                           \
 928     if (text == partend)                                \
 929       {                                                 \
 930         if (text == textend)                            \
 931           goto fail;                                    \
 932         text = string2;                                 \
 933         partend = part_2_end;                           \
 934       }                                                 \
 935   MACRO_END
 936
 937 #define NEXTCHAR(var)                           \
 938   MACRO_BEGIN                                   \
 939     PREFETCH;                                   \
 940     (var) = (unsigned char)*text++;             \
 941     if (translate)                              \
 942       (var) = (unsigned char)translate[(var)];  \
 943   MACRO_END
 944
 945   assert(pos >= 0 && size1 >= 0 && size2 >= 0 && mstop >= 0);
 946   assert(mstop <= size1 + size2);
 947   assert(pos <= mstop);
 948
 949   if (pos <= size1)
 950     {
 951       text = string1 + pos;
 952       if (mstop <= size1)
 953         {
 954           partend = string1 + mstop;
 955           textend = partend;
 956         }
 957       else
 958         {
 959           partend = string1 + size1;
 960           textend = string2 + mstop - size1;
 961         }
 962       part_2_end = string2 + mstop - size1;
 963     }
 964   else
 965     {
 966       text = string2 + pos - size1;
 967       partend = string2 + mstop - size1;
 968       textend = partend;
 969       part_2_end = partend;
 970     }
 971
 972   if (bufp->uses_registers && regs != NULL)
 973     for (a = 0; a < RE_NREGS; a++)
 974       regend_text[a] = NULL;
 975
 976   code = bufp->buffer;
 977   translate = bufp->translate;
 978   failure_stack_start = failure_sp = initial_failure_stack;
 979   failure_stack_end = initial_failure_stack + INITIAL_FAILURES;
 980
 981 #if 0
 982   /* re_search_2 has already done this, and otherwise we get little benefit
 983      from this.  So I'll leave this out. */
 984   if (bufp->fastmap_accurate && !bufp->can_be_null &&
 985       text != textend &&
 986       !bufp->fastmap[translate ?
 987                      (unsigned char)translate[(unsigned char)*text] :
 988                      (unsigned char)*text])
 989     return -1;  /* it can't possibly match */
 990 #endif
 991
 992  continue_matching:
 993   for (;;)
 994     {
 995       switch (*code++)
 996         {
 997         case Cend:
 998           if (partend != part_2_end)
 999             match_end = text - string1;
1000           else
1001             match_end = text - string2 + size1;
1002           if (regs)
1003             {
1004               regs->start[0] = pos;
1005               regs->end[0] = match_end;
1006               if (!bufp->uses_registers)
1007                 {
1008                   for (a = 1; a < RE_NREGS; a++)
1009                     {
1010                       regs->start[a] = -1;
1011                       regs->end[a] = -1;
1012                     }
1013                 }
1014               else
1015                 {
1016                   for (a = 1; a < RE_NREGS; a++)
1017                     {
1018                       if (regend_text[a] == NULL)
1019                         {
1020                           regs->start[a] = -1;
1021                           regs->end[a] = -1;
1022                           continue;
1023                         }
1024                       if (regstart_partend[a] != part_2_end)
1025                         regs->start[a] = regstart_text[a] - string1;
1026                       else
1027                         regs->start[a] = regstart_text[a] - string2 + size1;
1028                       if (regend_partend[a] != part_2_end)
1029                         regs->end[a] = regend_text[a] - string1;
1030                       else
1031                         regs->end[a] = regend_text[a] - string2 + size1;
1032                     }
1033                 }
1034             }
1035           if (failure_stack_start != initial_failure_stack)
1036             free((char *)failure_stack_start);
1037           return match_end - pos;
1038         case Cbol:
1039           if (text == string1 || text[-1] == '\n') /* text[-1] always valid */
1040             break;
1041           goto fail;
1042         case Ceol:
1043           if (text == string2 + size2 ||
1044               (text == string1 + size1 ?
1045                (size2 == 0 || *string2 == '\n') :
1046                *text == '\n'))
1047             break;
1048           goto fail;
1049         case Cset:
1050           NEXTCHAR(ch);
1051           if (code[ch/8] & (1<<(ch & 7)))
1052             {
1053               code += 256/8;
1054               break;
1055             }
1056           goto fail;
1057         case Cexact:
1058           NEXTCHAR(ch);
1059           if (ch != (unsigned char)*code++)
1060             goto fail;
1061           break;
1062         case Canychar:
1063           NEXTCHAR(ch);
1064           if (ch == '\n')
1065             goto fail;
1066           break;
1067         case Cstart_memory:
1068           reg = *code++;
1069           regstart_text[reg] = text;
1070           regstart_partend[reg] = partend;
1071           break;
1072         case Cend_memory:
1073           reg = *code++;
1074           regend_text[reg] = text;
1075           regend_partend[reg] = partend;
1076           break;
1077         case Cmatch_memory:
1078           reg = *code++;
1079           if (regend_text[reg] == NULL)
1080             goto fail;  /* or should we just match nothing? */
1081           regtext = regstart_text[reg];
1082           regtextend = regend_text[reg];
1083           if (regstart_partend[reg] == regend_partend[reg])
1084             regpartend = regtextend;
1085           else
1086             regpartend = string1 + size1;
1087
1088           for (;regtext != regtextend;)
1089             {
1090               NEXTCHAR(ch);
1091               if (regtext == regpartend)
1092                 regtext = string2;
1093               regch = (unsigned char)*regtext++;
1094               if (translate)
1095                 regch = (unsigned char)translate[regch];
1096               if (regch != ch)
1097                 goto fail;
1098             }
1099           break;
1100         case Cstar_jump:
1101           /* star is coded as:
1102                1: failure_jump 2
1103                   ... code for operand of star
1104                   star_jump 1
1105                2: ... code after star
1106              We change the star_jump to update_failure_jump if we can determine
1107              that it is safe to do so; otherwise we change it to an ordinary
1108              jump.
1109              plus is coded as
1110                   jump 2
1111                1: failure_jump 3
1112                2: ... code for operand of plus
1113                   star_jump 1
1114                3: ... code after plus
1115              For star_jump considerations this is processed identically
1116              to star. */
1117           a = (unsigned char)*code++;
1118           a |= (unsigned char)*code++ << 8;
1119           a = (int)(short)a;
1120           {
1121             char map[256], can_be_null;
1122             char *p1, *p2;
1123
1124             p1 = code + a + 3; /* skip the failure_jump */
1125             assert(p1[-3] == Cfailure_jump);
1126             p2 = code;
1127             /* p1 points inside loop, p2 points to after loop */
1128             if (!re_do_compile_fastmap(bufp->buffer, bufp->used,
1129                                        p2 - bufp->buffer, &can_be_null, map))
1130               goto make_normal_jump;
1131             /* If we might introduce a new update point inside the loop,
1132                we can't optimize because then update_jump would update a
1133                wrong failure point.  Thus we have to be quite careful here. */
1134           loop_p1:
1135             /* loop until we find something that consumes a character */
1136             switch (*p1++)
1137               {
1138               case Cbol:
1139               case Ceol:
1140               case Cbegbuf:
1141               case Cendbuf:
1142               case Cwordbeg:
1143               case Cwordend:
1144               case Cwordbound:
1145               case Cnotwordbound:
1146 #ifdef emacs
1147               case Cemacs_at_dot:
1148 #endif /* emacs */
1149                 goto loop_p1;
1150               case Cstart_memory:
1151               case Cend_memory:
1152                 p1++;
1153                 goto loop_p1;
1154               case Cexact:
1155                 ch = (unsigned char)*p1++;
1156                 if (map[ch])
1157                   goto make_normal_jump;
1158                 break;
1159               case Canychar:
1160                 for (b = 0; b < 256; b++)
1161                   if (b != '\n' && map[b])
1162                     goto make_normal_jump;
1163                 break;
1164               case Cset:
1165                 for (b = 0; b < 256; b++)
1166                   if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
1167                     goto make_normal_jump;
1168                 p1 += 256/8;
1169                 break;
1170               default:
1171                 goto make_normal_jump;
1172               }
1173             /* now we know that we can't backtrack. */
1174             while (p1 != p2 - 3)
1175               {
1176                 switch (*p1++)
1177                   {
1178                   case Cend:
1179                     abort();  /* we certainly shouldn't get this inside loop */
1180                     /*NOTREACHED*/
1181                   case Cbol:
1182                   case Ceol:
1183                   case Canychar:
1184                   case Cbegbuf:
1185                   case Cendbuf:
1186                   case Cwordbeg:
1187                   case Cwordend:
1188                   case Cwordbound:
1189                   case Cnotwordbound:
1190 #ifdef emacs
1191                   case Cemacs_at_dot:
1192 #endif /* emacs */
1193                     break;
1194                   case Cset:
1195                     p1 += 256/8;
1196                     break;
1197                   case Cexact:
1198                   case Cstart_memory:
1199                   case Cend_memory:
1200                   case Cmatch_memory:
1201                   case Csyntaxspec:
1202                   case Cnotsyntaxspec:
1203                     p1++;
1204                     break;
1205                   case Cjump:
1206                   case Cstar_jump:
1207                   case Cfailure_jump:
1208                   case Cupdate_failure_jump:
1209                   case Cdummy_failure_jump:
1210                     goto make_normal_jump;
1211                   default:
1212                     printf("regexpr.c: processing star_jump: unknown op %d\n", p1[-1]);
1213                     break;
1214                   }
1215               }
1216             goto make_update_jump;
1217           }
1218         make_normal_jump:
1219           /* printf("changing to normal jump\n"); */
1220           code -= 3;
1221           *code = Cjump;
1222           break;
1223         make_update_jump:
1224           /* printf("changing to update jump\n"); */
1225           code -= 2;
1226           a += 3;  /* jump to after the Cfailure_jump */
1227           code[-1] = Cupdate_failure_jump;
1228           code[0] = a & 0xff;
1229           code[1] = a >> 8;
1230           /* fall to next case */
1231         case Cupdate_failure_jump:
1232           failure_sp[-1].text = text;
1233           failure_sp[-1].partend = partend;
1234           /* fall to next case */
1235         case Cjump:
1236           a = (unsigned char)*code++;
1237           a |= (unsigned char)*code++ << 8;
1238           code += (int)(short)a;
1239           break;
1240         case Cdummy_failure_jump:
1241         case Cfailure_jump:
1242           if (failure_sp == failure_stack_end)
1243             {
1244               if (failure_stack_start != initial_failure_stack)
1245                 goto error;
1246               failure_stack_start = (struct failure_point *)
1247                 malloc(MAX_FAILURES * sizeof(*failure_stack_start));
1248               failure_stack_end = failure_stack_start + MAX_FAILURES;
1249               memcpy((char *)failure_stack_start, (char *)initial_failure_stack,
1250                      INITIAL_FAILURES * sizeof(*failure_stack_start));
1251               failure_sp = failure_stack_start + INITIAL_FAILURES;
1252             }
1253           a = (unsigned char)*code++;
1254           a |= (unsigned char)*code++ << 8;
1255           a = (int)(short)a;
1256           if (code[-3] == Cdummy_failure_jump)
1257             { /* this is only used in plus */
1258               assert(*code == Cfailure_jump);
1259               b = (unsigned char)code[1];
1260               b |= (unsigned char)code[2] << 8;
1261               failure_sp->code = code + (int)(short)b + 3;
1262               failure_sp->text = NULL;
1263               code += a;
1264             }
1265           else
1266             {
1267               failure_sp->code = code + a;
1268               failure_sp->text = text;
1269               failure_sp->partend = partend;
1270             }
1271           failure_sp++;
1272           break;
1273         case Cbegbuf:
1274           if (text == string1)
1275             break;
1276           goto fail;
1277         case Cendbuf:
1278           if (size2 == 0 ? text == string1 + size1 : text == string2 + size2)
1279             break;
1280           goto fail;
1281         case Cwordbeg:
1282           if (text == string2 + size2)
1283             goto fail;
1284           if (size2 == 0 && text == string1 + size1)
1285             goto fail;
1286           if (SYNTAX(text == string1 + size1 ? *string1 : *text) != Sword)
1287             goto fail;
1288           if (text == string1)
1289             break;
1290           if (SYNTAX(text[-1]) != Sword)
1291             break;
1292           goto fail;
1293         case Cwordend:
1294           if (text == string1)
1295             goto fail;
1296           if (SYNTAX(text[-1]) != Sword)
1297             goto fail;
1298           if (text == string2 + size2)
1299             break;
1300           if (size2 == 0 && text == string1 + size1)
1301             break;
1302           if (SYNTAX(*text) == Sword)
1303             goto fail;
1304           break;
1305         case Cwordbound:
1306           /* Note: as in gnu regexp, this also matches at the beginning
1307              and end of buffer. */
1308           if (text == string1 || text == string2 + size2 ||
1309               (size2 == 0 && text == string1 + size1))
1310             break;
1311           if ((SYNTAX(text[-1]) == Sword) ^
1312               (SYNTAX(text == string1 + size1 ? *string2 : *text) == Sword))
1313             break;
1314           goto fail;
1315         case Cnotwordbound:
1316           /* Note: as in gnu regexp, this never matches at the beginning
1317              and end of buffer. */
1318           if (text == string1 || text == string2 + size2 ||
1319               (size2 == 0 && text == string1 + size1))
1320             goto fail;
1321           if (!((SYNTAX(text[-1]) == Sword) ^
1322                 (SYNTAX(text == string1 + size1 ? *string2 : *text) == Sword)))
1323             goto fail;
1324           break;
1325         case Csyntaxspec:
1326           NEXTCHAR(ch);
1327           if (SYNTAX(ch) != (unsigned char)*code++)
1328             goto fail;
1329           break;
1330         case Cnotsyntaxspec:
1331           NEXTCHAR(ch);
1332           if (SYNTAX(ch) != (unsigned char)*code++)
1333             break;
1334           goto fail;
1335 #ifdef emacs
1336         case Cemacs_at_dot:
1337           if (PTR_CHAR_POS((unsigned char *)text) + 1 != point)
1338             goto fail;
1339           break;
1340 #endif /* emacs */
1341         default:
1342           abort();
1343           /*NOTREACHED*/
1344         }
1345     }
1346   abort();
1347   /*NOTREACHED*/
1348
1349  fail:
1350   if (failure_sp != failure_stack_start)
1351     {
1352       failure_sp--;
1353       text = failure_sp->text;
1354       if (text == NULL)
1355         goto fail;
1356       partend = failure_sp->partend;
1357       code = failure_sp->code;
1358       goto continue_matching;
1359     }
1360   if (failure_stack_start != initial_failure_stack)
1361     free((char *)failure_stack_start);
1362   return -1;
1363
1364  error:
1365   if (failure_stack_start != initial_failure_stack)
1366     free((char *)failure_stack_start);
1367   return -2;
1368 }
1369
1370 #undef PREFETCH
1371 #undef NEXTCHAR
1372 #undef PUSH_FAILURE
1373
1374 int re_match(bufp, string, size, pos, regs)
1375 regexp_t bufp;
1376 char *string;
1377 int size, pos;
1378 regexp_registers_t regs;
1379 {
1380   return re_match_2(bufp, string, size, (char *)NULL, 0, pos, regs, size);
1381 }
1382
1383 int re_search_2(bufp, string1, size1, string2, size2, pos, range, regs,
1384                 mstop)
1385 regexp_t bufp;
1386 char *string1, *string2;
1387 int size1, size2, pos, range, mstop;
1388 regexp_registers_t regs;
1389 {
1390   char *fastmap, *translate, *text, *partstart, *partend;
1391   int dir, ret;
1392   char anchor;
1393
1394   assert(size1 >= 0 && size2 >= 0 && pos >= 0 && mstop >= 0);
1395   assert(pos + range >= 0 && pos + range <= size1 + size2);
1396   assert(pos <= mstop);
1397
1398   fastmap = bufp->fastmap;
1399   translate = bufp->translate;
1400   if (fastmap && !bufp->fastmap_accurate)
1401     re_compile_fastmap(bufp);
1402   anchor = bufp->anchor;
1403   if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
1404     fastmap = NULL;
1405   if (range < 0)
1406     {
1407       dir = -1;
1408       range = -range;
1409     }
1410   else
1411     dir = 1;
1412   if (anchor == 2) {
1413     if (pos != 0)
1414       return -1;
1415     else
1416       range = 0;
1417   }
1418   for (; range >= 0; range--, pos += dir)
1419     {
1420       if (fastmap)
1421         {
1422           if (dir == 1)
1423             { /* searching forwards */
1424               if (pos < size1)
1425                 {
1426                   text = string1 + pos;
1427                   if (pos + range > size1)
1428                     partend = string1 + size1;
1429                   else
1430                     partend = string1 + pos + range;
1431                 }
1432               else
1433                 {
1434                   text = string2 + pos - size1;
1435                   partend = string2 + pos + range - size1;
1436                 }
1437               partstart = text;
1438               if (translate)
1439                 while (text != partend &&
1440                        !fastmap[(unsigned char)
1441                                 translate[(unsigned char)*text]])
1442                   text++;
1443               else
1444                 while (text != partend && !fastmap[(unsigned char)*text])
1445                   text++;
1446               pos += text - partstart;
1447               range -= text - partstart;
1448               if (pos == size1 + size2 && bufp->can_be_null == 0)
1449                 return -1;
1450             }
1451           else
1452             { /* searching backwards */
1453               if (pos <= size1)
1454                 {
1455                   text = string1 + pos;
1456                   partstart = string1 + pos - range;
1457                 }
1458               else
1459                 {
1460                   text = string2 + pos - size1;
1461                   if (range < pos - size1)
1462                     partstart = string2 + pos - size1 - range;
1463                   else
1464                     partstart = string2;
1465                 }
1466               partend = text;
1467               if (translate)
1468                 while (text != partstart &&
1469                        !fastmap[(unsigned char)
1470                                 translate[(unsigned char)*text]])
1471                   text--;
1472               else
1473                 while (text != partstart &&
1474                        !fastmap[(unsigned char)*text])
1475                   text--;
1476               pos -= partend - text;
1477               range -= partend - text;
1478             }
1479         }
1480       if (anchor == 1)
1481         { /* anchored to begline */
1482           if (pos > 0 &&
1483               (pos <= size1 ? string1[pos - 1] :
1484                string2[pos - size1 - 1]) != '\n')
1485             continue;
1486         }
1487       assert(pos >= 0 && pos <= size1 + size2);
1488       ret = re_match_2(bufp, string1, size1, string2, size2, pos, regs, mstop);
1489       if (ret >= 0)
1490         return pos;
1491       if (ret == -2)
1492         return -2;
1493     }
1494   return -1;
1495 }
1496
1497 int re_search(bufp, string, size, startpos, range, regs)
1498 regexp_t bufp;
1499 char *string;
1500 int size, startpos, range;
1501 regexp_registers_t regs;
1502 {
1503   return re_search_2(bufp, string, size, (char *)NULL, 0,
1504                      startpos, range, regs, size);
1505 }
1506
1507 static struct re_pattern_buffer re_comp_buf;
1508
1509 char *re_comp(s)
1510 char *s;
1511 {
1512   if (s == NULL)
1513     {
1514       if (!re_comp_buf.buffer)
1515         return "Out of memory";
1516       return NULL;
1517     }
1518   if (!re_comp_buf.buffer)
1519     {
1520       /* the buffer will be allocated automatically */
1521       re_comp_buf.fastmap = malloc(256);
1522       re_comp_buf.translate = NULL;
1523     }
1524   return re_compile_pattern(s, strlen(s), &re_comp_buf);
1525 }
1526
1527 int re_exec(s)
1528 char *s;
1529 {
1530   int len = strlen(s);
1531
1532   return re_search(&re_comp_buf, s, len, 0, len, (regexp_registers_t)NULL) >= 0;
1533 }
1534
1535 /* POSIX Compatibility */
1536
1537 int regcomp(regex_t *preg, const char *regex, int cflags)
1538 {
1539   int syntax = 0;
1540   memset(preg, 0, sizeof(*preg));
1541   if (cflags & REG_EXTENDED)
1542     syntax |= (RE_CONTEXT_INDEP_OPS | RE_NO_BK_PARENS | RE_NO_BK_VBAR);
1543   re_set_syntax(syntax);
1544   if (re_compile_pattern((char *)regex, strlen(regex), preg) == NULL)
1545     return 0;
1546   return -1;
1547 }
1548
1549 int regexec(const regex_t *preg, const char *string, size_t nmatch,
1550             regmatch_t pmatch[], int eflags)
1551 {
1552   int len = strlen(string);
1553   int ret;
1554
1555   ret = re_search((regex_t *)preg, (char *)string, len, 0, len, (regexp_registers_t)NULL);
1556   if (ret >= 0)
1557     return 0;
1558
1559   return ret;
1560 }
1561
1562 size_t regerror(int errcode, const regex_t *preg, char *errbuf,
1563                 size_t errbuf_size)
1564 {
1565   return -1;
1566 }
1567
1568 void regfree(regex_t *preg)
1569 {
1570   free(preg->buffer);
1571 }
1572
1573 #ifdef TEST_REGEXP
1574
1575 int main()
1576 {
1577   char buf[500];
1578   char *cp;
1579   struct re_pattern_buffer exp;
1580   struct re_registers regs;
1581   int a,pos;
1582   char fastmap[256];
1583
1584   exp.allocated = 0;
1585   exp.buffer = 0;
1586   exp.translate = NULL;
1587   exp.fastmap = fastmap;
1588
1589   /* re_set_syntax(RE_NO_BK_PARENS|RE_NO_BK_VBAR|RE_ANSI_HEX); */
1590
1591   while (1)
1592     {
1593       printf("Enter regexp:\n");
1594       gets(buf);
1595       cp=re_compile_pattern(buf, strlen(buf), &exp);
1596       if (cp)
1597         {
1598           printf("Error: %s\n", cp);
1599           continue;
1600         }
1601       re_compile_fastmap(&exp);
1602       printf("dump:\n");
1603       for (pos = 0; pos < exp.used;)
1604         {
1605           printf("%d: ", pos);
1606           switch (exp.buffer[pos++])
1607             {
1608             case Cend:
1609               strcpy(buf, "end");
1610               break;
1611             case Cbol:
1612               strcpy(buf, "bol");
1613               break;
1614             case Ceol:
1615               strcpy(buf, "eol");
1616               break;
1617             case Cset:
1618               strcpy(buf, "set ");
1619               for (a = 0; a < 256/8; a++)
1620                 sprintf(buf+strlen(buf)," %02x",
1621                         (unsigned char)exp.buffer[pos++]);
1622               break;
1623             case Cexact:
1624               sprintf(buf, "exact '%c' 0x%x", exp.buffer[pos],
1625                       (unsigned char)exp.buffer[pos]);
1626               pos++;
1627               break;
1628             case Canychar:
1629               strcpy(buf, "anychar");
1630               break;
1631             case Cstart_memory:
1632               sprintf(buf, "start_memory %d", exp.buffer[pos++]);
1633               break;
1634             case Cend_memory:
1635               sprintf(buf, "end_memory %d", exp.buffer[pos++]);
1636               break;
1637             case Cmatch_memory:
1638               sprintf(buf, "match_memory %d", exp.buffer[pos++]);
1639               break;
1640             case Cjump:
1641             case Cdummy_failure_jump:
1642             case Cstar_jump:
1643             case Cfailure_jump:
1644             case Cupdate_failure_jump:
1645               a = (unsigned char)exp.buffer[pos++];
1646               a += (unsigned char)exp.buffer[pos++] << 8;
1647               a = (int)(short)a;
1648               switch (exp.buffer[pos-3])
1649                 {
1650                 case Cjump:
1651                   cp = "jump";
1652                   break;
1653                 case Cstar_jump:
1654                   cp = "star_jump";
1655                   break;
1656                 case Cfailure_jump:
1657                   cp = "failure_jump";
1658                   break;
1659                 case Cupdate_failure_jump:
1660                   cp = "update_failure_jump";
1661                   break;
1662                 case Cdummy_failure_jump:
1663                   cp = "dummy_failure_jump";
1664                   break;
1665                 default:
1666                   cp = "unknown jump";
1667                   break;
1668                 }
1669               sprintf(buf, "%s %d", cp, a + pos);
1670               break;
1671             case Cbegbuf:
1672               strcpy(buf,"begbuf");
1673               break;
1674             case Cendbuf:
1675               strcpy(buf,"endbuf");
1676               break;
1677             case Cwordbeg:
1678               strcpy(buf,"wordbeg");
1679               break;
1680             case Cwordend:
1681               strcpy(buf,"wordend");
1682               break;
1683             case Cwordbound:
1684               strcpy(buf,"wordbound");
1685               break;
1686             case Cnotwordbound:
1687               strcpy(buf,"notwordbound");
1688               break;
1689             default:
1690               sprintf(buf, "unknown code %d",
1691                       (unsigned char)exp.buffer[pos - 1]);
1692               break;
1693             }
1694           printf("%s\n", buf);
1695         }
1696       printf("can_be_null = %d uses_registers = %d anchor = %d\n",
1697              exp.can_be_null, exp.uses_registers, exp.anchor);
1698
1699       printf("fastmap:");
1700       for (a = 0; a < 256; a++)
1701         if (exp.fastmap[a])
1702           printf(" %d", a);
1703       printf("\n");
1704       printf("Enter strings.  An empty line terminates.\n");
1705       while (fgets(buf, sizeof(buf), stdin))
1706         {
1707           if (buf[0] == '\n')
1708             break;
1709           a = re_search(&exp, buf, strlen(buf), 0, strlen(buf), &regs);
1710           printf("search returns %d\n", a);
1711           if (a != -1)
1712             {
1713               for (a = 0; a < RE_NREGS; a++)
1714                 {
1715                   printf("buf %d: %d to %d\n", a, regs.start[a], regs.end[a]);
1716                 }
1717             }
1718         }
1719     }
1720 }
1721
1722 #endif /* TEST_REGEXP */