user/mawk/re_cmpl.c

   1
   2 /********************************************
   3 re_cmpl.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: re_cmpl.c,v $
  14  * Revision 1.6  1994/12/13  00:14:58  mike
  15  * \\ -> \ on second replacement scan
  16  *
  17  * Revision 1.5  1994/10/08  19:15:51  mike
  18  * remove SM_DOS
  19  *
  20  * Revision 1.4  1993/07/21  01:17:53  mike
  21  * handle "&" as replacement correctly
  22  *
  23  * Revision 1.3  1993/07/17  13:23:10  mike
  24  * indent and general code cleanup
  25  *
  26  * Revision 1.2  1993/07/15  23:38:23  mike
  27  * SIZE_T and indent
  28  *
  29  * Revision 1.1.1.1  1993/07/03  18:58:19  mike
  30  * move source to cvs
  31  *
  32  * Revision 5.2  1993/01/01  21:30:48  mike
  33  * split new_STRING() into new_STRING and new_STRING0
  34  *
  35  * Revision 5.1  1991/12/05  07:56:25  brennan
  36  * 1.1 pre-release
  37  *
  38 */
  39
  40
  41 /*  re_cmpl.c  */
  42
  43 #include "mawk.h"
  44 #include "memory.h"
  45 #include "scan.h"
  46 #include "regexp.h"
  47 #include "repl.h"
  48
  49
  50 static CELL *PROTO(REPL_compile, (STRING *)) ;
  51
  52 typedef struct re_node
  53 {
  54    STRING *sval ;
  55    PTR re ;
  56    struct re_node *link ;
  57 } RE_NODE ;
  58
  59 /* a list of compiled regular expressions */
  60 static RE_NODE *re_list ;
  61
  62 static char efmt[] = "regular expression compile failed (%s)\n%s" ;
  63
  64 /* compile a STRING to a regular expression machine.
  65    Search a list of pre-compiled strings first
  66 */
  67 PTR
  68 re_compile(sval)
  69    STRING *sval ;
  70 {
  71    register RE_NODE *p ;
  72    RE_NODE *q ;
  73    char *s ;
  74
  75    /* search list */
  76    s = sval->str ;
  77    p = re_list ;
  78    q = (RE_NODE *) 0 ;
  79    while (p)
  80    {
  81       if (strcmp(s, p->sval->str) == 0) /* found */
  82       {
  83          if (!q)                /* already at front */
  84             goto _return ;
  85          else  /* delete from list for move to front */
  86          {
  87             q->link = p->link ; goto found ;
  88          }
  89
  90       }
  91       else
  92       {
  93          q = p ; p = p->link ;
  94       }
  95    }
  96
  97    /* not found */
  98    p = ZMALLOC(RE_NODE) ;
  99    p->sval = sval ;
 100
 101    sval->ref_cnt++ ;
 102    if (!(p->re = REcompile(s)))
 103    {
 104       if (mawk_state == EXECUTION)
 105          rt_error(efmt, REerrlist[REerrno], s) ;
 106       else  /* compiling */
 107       {
 108          compile_error(efmt, REerrlist[REerrno], s) ;
 109          return (PTR) 0 ;
 110       }
 111    }
 112
 113
 114 found :
 115 /* insert p at the front of the list */
 116    p->link = re_list ; re_list = p ;
 117
 118 _return :
 119
 120 #ifdef  DEBUG
 121    if (dump_RE)  REmprint(p->re, stderr) ;
 122 #endif
 123    return p->re ;
 124 }
 125
 126
 127
 128 /* this is only used by da() */
 129
 130
 131 char *
 132 re_uncompile(m)
 133    PTR m ;
 134 {
 135    register RE_NODE *p ;
 136
 137    for (p = re_list; p; p = p->link)
 138       if (p->re == m)  return p->sval->str ;
 139 #ifdef  DEBUG
 140    bozo("non compiled machine") ;
 141 #endif
 142 }
 143
 144
 145
 146 /*=================================================*/
 147 /*  replacement  operations   */
 148
 149 /* create a replacement CELL from a STRING *  */
 150
 151 static CELL *
 152 REPL_compile(sval)
 153    STRING *sval ;
 154 {
 155    int i = 0 ;
 156    register char *p = sval->str ;
 157    register char *q ;
 158    char *xbuff ;
 159    CELL *cp ;
 160
 161    q = xbuff = (char *) zmalloc(sval->len + 1) ;
 162
 163    while (1)
 164    {
 165       switch (*p)
 166       {
 167          case 0:
 168             *q = 0 ;
 169             goto done ;
 170
 171          case '\\':
 172             if (p[1] == '&'|| p[1] == '\\')
 173             {
 174                *q++ = p[1] ;
 175                p += 2 ;
 176                continue ;
 177             }
 178             else  break ;
 179
 180          case '&':
 181             /* if empty we don't need to make a node */
 182             if (q != xbuff)
 183             {
 184                *q = 0 ;
 185                split_buff[i++] = new_STRING(xbuff) ;
 186             }
 187             /* and a null node for the '&'  */
 188             split_buff[i++] = (STRING *) 0 ;
 189             /*  reset  */
 190             p++ ;  q = xbuff ;
 191             continue ;
 192
 193          default:
 194             break ;
 195       }
 196
 197       *q++ = *p++ ;
 198    }
 199
 200 done :
 201    /* if we have one empty string it will get made now */
 202    if (q > xbuff || i == 0)  split_buff[i++] = new_STRING(xbuff) ;
 203
 204    /* This will never happen */
 205    if (i > MAX_SPLIT)  overflow("replacement pieces", MAX_SPLIT) ;
 206
 207    cp = ZMALLOC(CELL) ;
 208    if (i == 1 && split_buff[0])
 209    {
 210       cp->type = C_REPL ;
 211       cp->ptr = (PTR) split_buff[0] ;
 212    }
 213    else
 214    {
 215       STRING **sp = (STRING **)
 216       (cp->ptr = zmalloc(sizeof(STRING *) * i)) ;
 217       int j = 0 ;
 218
 219       while (j < i)  *sp++ = split_buff[j++] ;
 220
 221       cp->type = C_REPLV ;
 222       cp->vcnt = i ;
 223    }
 224    zfree(xbuff, sval->len + 1) ;
 225    return cp ;
 226 }
 227
 228 /* free memory used by a replacement CELL  */
 229
 230 void
 231 repl_destroy(cp)
 232    register CELL *cp ;
 233 {
 234    register STRING **p ;
 235    unsigned cnt ;
 236
 237    if (cp->type == C_REPL)  free_STRING(string(cp)) ;
 238    else  /* an C_REPLV        */
 239    {
 240       p = (STRING **) cp->ptr ;
 241       for (cnt = cp->vcnt; cnt; cnt--)
 242       {
 243          if (*p)  free_STRING(*p) ;
 244          p++ ;
 245       }
 246       zfree(cp->ptr, cp->vcnt * sizeof(STRING *)) ;
 247    }
 248 }
 249
 250 /* copy a C_REPLV cell to another CELL */
 251
 252 CELL *
 253 replv_cpy(target, source)
 254    CELL *target, *source ;
 255 {
 256    STRING **t, **s ;
 257    unsigned cnt ;
 258
 259    target->type = C_REPLV ;
 260    cnt = target->vcnt = source->vcnt ;
 261    target->ptr = (PTR) zmalloc(cnt * sizeof(STRING *)) ;
 262
 263    t = (STRING **) target->ptr ;
 264    s = (STRING **) source->ptr ;
 265    while (cnt)
 266    {
 267       cnt-- ;
 268       if ( *s ) (*s)->ref_cnt++ ;
 269       *t++ = *s++ ;
 270    }
 271    return target ;
 272 }
 273
 274
 275 /* here's our old friend linked linear list with move to the front
 276    for compilation of replacement CELLs  */
 277
 278 typedef struct repl_node
 279 {
 280    struct repl_node *link ;
 281    STRING *sval ;                /* the input */
 282    CELL *cp ;                    /* the output */
 283 } REPL_NODE ;
 284
 285 static REPL_NODE *repl_list ;
 286
 287 /* search the list (with move to the front) for a compiled
 288    separator.
 289    return a ptr to a CELL (C_REPL or C_REPLV)
 290 */
 291
 292 CELL *
 293 repl_compile(sval)
 294    STRING *sval ;
 295 {
 296    register REPL_NODE *p ;
 297    REPL_NODE *q ;
 298    char *s ;
 299
 300    /* search the list */
 301    s = sval->str ;
 302    p = repl_list ;
 303    q = (REPL_NODE *) 0 ;
 304    while (p)
 305    {
 306       if (strcmp(s, p->sval->str) == 0) /* found */
 307       {
 308          if (!q)                /* already at front */
 309             return p->cp ;
 310          else  /* delete from list for move to front */
 311          {
 312             q->link = p->link ;
 313             goto found ;
 314          }
 315
 316       }
 317       else
 318       {
 319          q = p ; p = p->link ;
 320       }
 321    }
 322
 323    /* not found */
 324    p = ZMALLOC(REPL_NODE) ;
 325    p->sval = sval ;
 326    sval->ref_cnt++ ;
 327    p->cp = REPL_compile(sval) ;
 328
 329 found :
 330 /* insert p at the front of the list */
 331    p->link = repl_list ; repl_list = p ;
 332    return p->cp ;
 333 }
 334
 335 /* return the string for a CELL or type REPL or REPLV,
 336    this is only used by da()  */
 337
 338
 339 char *
 340 repl_uncompile(cp)
 341    CELL *cp ;
 342 {
 343    register REPL_NODE *p = repl_list ;
 344
 345    if (cp->type == C_REPL)
 346    {
 347       while (p)
 348       {
 349          if (p->cp->type == C_REPL && p->cp->ptr == cp->ptr)
 350             return p->sval->str ;
 351          else  p = p->link ;
 352       }
 353    }
 354    else
 355    {
 356       while (p)
 357       {
 358          if (p->cp->type == C_REPLV &&
 359              memcmp(cp->ptr, p->cp->ptr, cp->vcnt * sizeof(STRING *))
 360              == 0)
 361             return p->sval->str ;
 362          else  p = p->link ;
 363       }
 364    }
 365
 366 #if  DEBUG
 367    bozo("unable to uncompile an repl") ;
 368 #endif
 369 }
 370
 371 /*
 372   convert a C_REPLV to  C_REPL
 373      replacing the &s with sval
 374 */
 375
 376 CELL *
 377 replv_to_repl(cp, sval)
 378 CELL *cp ; STRING *sval ;
 379 {
 380    register STRING **p ;
 381    STRING **sblock = (STRING **) cp->ptr ;
 382    unsigned cnt, vcnt = cp->vcnt ;
 383    unsigned len ;
 384    char *target ;
 385
 386 #ifdef  DEBUG
 387    if (cp->type != C_REPLV)  bozo("not replv") ;
 388 #endif
 389
 390    p = sblock ; cnt = vcnt ; len = 0 ;
 391    while (cnt--)
 392    {
 393       if (*p)  len += (*p++)->len ;
 394       else
 395       {
 396          *p++ = sval ;
 397          sval->ref_cnt++ ;
 398          len += sval->len ;
 399       }
 400    }
 401    cp->type = C_REPL ;
 402    cp->ptr = (PTR) new_STRING0(len) ;
 403
 404    p = sblock ; cnt = vcnt ; target = string(cp)->str ;
 405    while (cnt--)
 406    {
 407       memcpy(target, (*p)->str, (*p)->len) ;
 408       target += (*p)->len ;
 409       free_STRING(*p) ;
 410       p++ ;
 411    }
 412
 413    zfree(sblock, vcnt * sizeof(STRING *)) ;
 414    return cp ;
 415 }