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