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