rexp/rexp3.c

   1
   2 /********************************************
   3 rexp3.c
   4 copyright 1991, Michael D. Brennan
   5
   6 This is a source file for mawk, an implementation of
   7 the AWK programming language.
   8
   9 Mawk is distributed without warranty under the terms of
  10 the GNU General Public License, version 2, 1991.
  11 ********************************************/
  12
  13 /*$Log: rexp3.c,v $
  14  * Revision 1.3  1993/07/24  17:55:15  mike
  15  * more cleanup
  16  *
  17  * Revision 1.2  1993/07/23  13:21:48  mike
  18  * cleanup rexp code
  19  *
  20  * Revision 1.1.1.1  1993/07/03  18:58:28  mike
  21  * move source to cvs
  22  *
  23  * Revision 3.6  1992/12/24  00:44:53  mike
  24  * fixed potential LMDOS bozo with M_STR+U_ON+END_ON
  25  * fixed minor bug in M_CLASS+U_ON+END_ON
  26  *
  27  * Revision 3.5  1992/01/21  17:33:20  brennan
  28  * added some casts so that character classes work with signed chars
  29  *
  30  * Revision 3.4  91/10/29  10:54:09  brennan
  31  * SIZE_T
  32  *
  33  * Revision 3.3  91/08/13  09:10:18  brennan
  34  * VERSION .9994
  35  *
  36  * Revision 3.2  91/06/10  16:18:17  brennan
  37  * changes for V7
  38  *
  39  * Revision 3.1  91/06/07  10:33:28  brennan
  40  * VERSION 0.995
  41  *
  42  * Revision 1.4  91/05/31  10:56:32  brennan
  43  * stack_empty hack for DOS large model
  44  *
  45 */
  46
  47 /*  match a string against a machine   */
  48
  49 #include "rexp.h"
  50
  51
  52
  53 extern RT_STATE *RE_run_stack_base ;
  54 extern RT_STATE *RE_run_stack_limit ;
  55 extern RT_STATE *RE_run_stack_empty ;
  56
  57 RT_STATE *RE_new_run_stack() ;
  58
  59
  60 #define  push(mx,sx,ssx,ux)   if (++stackp == RE_run_stack_limit)\
  61                                 stackp = RE_new_run_stack() ;\
  62 stackp->m=(mx);stackp->s=(sx);stackp->ss=(ssx);\
  63 stackp->u = (ux)
  64
  65
  66 #define   CASE_UANY(x)  case  x + U_OFF :  case  x + U_ON
  67
  68 /* returns start of first longest match and the length by
  69    reference.  If no match returns NULL and length zero */
  70
  71    char *REmatch(str, machine, lenp)
  72    char *str ;
  73    PTR machine ;
  74    unsigned *lenp ;
  75 {
  76    register STATE *m = (STATE *) machine ;
  77    register char *s = str ;
  78    char *ss ;
  79    register RT_STATE *stackp ;
  80    int u_flag, t ;
  81    char *str_end, *ts ;
  82
  83    /* state of current best match stored here */
  84    char *cb_ss ;                 /* the start */
  85    char *cb_e ;                  /* the end , pts at first char not matched */
  86
  87    *lenp = 0 ;
  88
  89    /* check for the easy case */
  90    if ((m + 1)->type == M_ACCEPT && m->type == M_STR)
  91    {
  92       if ((ts = str_str(s, m->data.str, m->len)))        *lenp = m->len ;
  93       return ts ;
  94    }
  95
  96    u_flag = U_ON ; cb_ss = ss = str_end = (char *) 0 ;
  97    stackp = RE_run_stack_empty ;
  98    goto reswitch ;
  99
 100 refill :
 101    if (stackp == RE_run_stack_empty)
 102    {
 103       if (cb_ss)  *lenp = cb_e - cb_ss ;
 104       return cb_ss ;
 105    }
 106    ss = stackp->ss ;
 107    s = stackp--->s ;
 108    if (cb_ss)                   /* does new state start too late ? */
 109    {
 110       if (ss)
 111       {
 112          if (cb_ss < ss)  goto refill ;
 113       }
 114       else if (cb_ss < s)  goto refill ;
 115    }
 116
 117    m = (stackp + 1)->m ;
 118    u_flag = (stackp + 1)->u ;
 119
 120
 121 reswitch  :
 122
 123    switch (m->type + u_flag)
 124    {
 125       case M_STR + U_OFF + END_OFF:
 126          if (strncmp(s, m->data.str, m->len))  goto refill ;
 127          if (!ss)
 128          {
 129             if (cb_ss && s > cb_ss)  goto refill ;
 130             else  ss = s ;
 131          }
 132          s += m->len ;  m++ ;
 133          goto reswitch ;
 134
 135       case M_STR + U_OFF + END_ON:
 136          if (strcmp(s, m->data.str))  goto refill ;
 137          if (!ss)
 138          {
 139             if (cb_ss && s > cb_ss)  goto refill ;
 140             else  ss = s ;
 141          }
 142          s += m->len ;  m++ ;
 143          goto reswitch ;
 144
 145       case M_STR + U_ON + END_OFF:
 146          if (!(s = str_str(s, m->data.str, m->len)))  goto refill ;
 147          push(m, s + 1, ss, U_ON) ;
 148          if (!ss)
 149          {
 150             if (cb_ss && s > cb_ss)  goto refill ;
 151             else  ss = s ;
 152          }
 153          s += m->len ; m++ ; u_flag = U_OFF ;
 154          goto reswitch ;
 155
 156       case M_STR + U_ON + END_ON:
 157          if (!str_end)  str_end = s + strlen(s) ;
 158          t = (str_end - s) - m->len ;
 159          if (t < 0 || memcmp(ts = s + t, m->data.str, m->len))
 160             goto refill ;
 161          if (!ss)
 162          {
 163             if (cb_ss && ts > cb_ss)  goto refill ;
 164             else  ss = ts ;
 165          }
 166          s = str_end ; m++ ; u_flag = U_OFF ;
 167          goto reswitch ;
 168
 169       case M_CLASS + U_OFF + END_OFF:
 170          if (!ison(*m->data.bvp, s[0]))  goto refill ;
 171          if (!ss)
 172          {
 173             if (cb_ss && s > cb_ss)  goto refill ;
 174             else  ss = s ;
 175          }
 176          s++ ; m++ ;
 177          goto reswitch ;
 178
 179       case M_CLASS + U_OFF + END_ON:
 180          if (s[1] || !ison(*m->data.bvp, s[0]))  goto refill ;
 181          if (!ss)
 182          {
 183             if (cb_ss && s > cb_ss)  goto refill ;
 184             else  ss = s ;
 185          }
 186          s++ ; m++ ;
 187          goto reswitch ;
 188
 189       case M_CLASS + U_ON + END_OFF:
 190          while (!ison(*m->data.bvp, s[0]))
 191          {
 192             if (s[0] == 0)  goto refill ;
 193             else  s++ ;
 194          }
 195          s++ ;
 196          push(m, s, ss, U_ON) ;
 197          if (!ss)
 198          {
 199             if (cb_ss && s - 1 > cb_ss)  goto refill ;
 200             else  ss = s - 1 ;
 201          }
 202          m++ ; u_flag = U_OFF ;
 203          goto reswitch ;
 204
 205       case M_CLASS + U_ON + END_ON:
 206          if (!str_end)  str_end = s + strlen(s) ;
 207          if (s[0] == 0 || !ison(*m->data.bvp, str_end[-1]))
 208             goto refill ;
 209          if (!ss)
 210          {
 211             if (cb_ss && str_end - 1 > cb_ss)  goto refill ;
 212             else  ss = str_end - 1 ;
 213          }
 214          s = str_end ; m++ ; u_flag = U_OFF ;
 215          goto reswitch ;
 216
 217       case M_ANY + U_OFF + END_OFF:
 218          if (s[0] == 0)  goto refill ;
 219          if (!ss)
 220          {
 221             if (cb_ss && s > cb_ss)  goto refill ;
 222             else  ss = s ;
 223          }
 224          s++ ; m++ ;
 225          goto reswitch ;
 226
 227       case M_ANY + U_OFF + END_ON:
 228          if (s[0] == 0 || s[1] != 0)  goto refill ;
 229          if (!ss)
 230          {
 231             if (cb_ss && s > cb_ss)  goto refill ;
 232             else  ss = s ;
 233          }
 234          s++ ; m++ ;
 235          goto reswitch ;
 236
 237       case M_ANY + U_ON + END_OFF:
 238          if (s[0] == 0)  goto refill ;
 239          s++ ;
 240          push(m, s, ss, U_ON) ;
 241          if (!ss)
 242          {
 243             if (cb_ss && s - 1 > cb_ss)  goto refill ;
 244             else  ss = s - 1 ;
 245          }
 246          m++ ; u_flag = U_OFF ;
 247          goto reswitch ;
 248
 249       case M_ANY + U_ON + END_ON:
 250          if (s[0] == 0)  goto refill ;
 251          if (!str_end)  str_end = s + strlen(s) ;
 252          if (!ss)
 253          {
 254             if (cb_ss && str_end - 1 > cb_ss)  goto refill ;
 255             else  ss = str_end - 1 ;
 256          }
 257          s = str_end ; m++ ; u_flag = U_OFF ;
 258          goto reswitch ;
 259
 260       case M_START + U_OFF + END_OFF:
 261       case M_START + U_ON + END_OFF:
 262          if (s != str)  goto refill ;
 263          ss = s ;
 264          m++ ;  u_flag = U_OFF ;
 265          goto reswitch ;
 266
 267       case M_START + U_OFF + END_ON:
 268       case M_START + U_ON + END_ON:
 269          if (s != str || s[0] != 0)  goto refill ;
 270          ss = s ;
 271          m++ ; u_flag = U_OFF ;
 272          goto reswitch ;
 273
 274       case M_END + U_OFF:
 275          if (s[0] != 0)  goto refill ;
 276          if (!ss)
 277          {
 278             if (cb_ss && s > cb_ss)  goto refill ;
 279             else  ss = s ;
 280          }
 281          m++ ; goto reswitch ;
 282
 283       case M_END + U_ON:
 284          s = str_end ? str_end : (str_end = s + strlen(s)) ;
 285          if (!ss)
 286          {
 287             if (cb_ss && s > cb_ss)  goto refill ;
 288             else  ss = s ;
 289          }
 290          m++ ; u_flag = U_OFF ;
 291          goto reswitch ;
 292
 293        CASE_UANY(M_U):
 294          if (!ss)
 295          {
 296             if (cb_ss && s > cb_ss)  goto refill ;
 297             else  ss = s ;
 298          }
 299          u_flag = U_ON ; m++ ;
 300          goto reswitch ;
 301
 302        CASE_UANY(M_1J):
 303          m += m->data.jump ;
 304          goto reswitch ;
 305
 306        CASE_UANY(M_2JA):        /* take the non jump branch */
 307          push(m + m->data.jump, s, ss, u_flag) ;
 308          m++ ;
 309          goto reswitch ;
 310
 311        CASE_UANY(M_2JB):        /* take the jump branch */
 312          push(m + 1, s, ss, u_flag) ;
 313          m += m->data.jump ;
 314          goto reswitch ;
 315
 316       case M_ACCEPT + U_OFF:
 317          if (!ss)  ss = s ;
 318          if (!cb_ss || ss < cb_ss || (ss == cb_ss && s > cb_e))
 319          {
 320             /* we have a new current best */
 321             cb_ss = ss ; cb_e = s ;
 322          }
 323          goto refill ;
 324
 325       case M_ACCEPT + U_ON:
 326          if (!ss)  ss = s ;
 327          else  s = str_end ? str_end : (str_end = s + strlen(s)) ;
 328
 329          if (!cb_ss || ss < cb_ss || (ss == cb_ss && s > cb_e))
 330          {
 331             /* we have a new current best */
 332             cb_ss = ss ; cb_e = s ;
 333          }
 334          goto refill ;
 335
 336       default:
 337          RE_panic("unexpected case in REmatch") ;
 338    }
 339 }