pcrs.c

   1 const char pcrs_rcs[] = "$Id: pcrs.c,v 1.9 2001/07/18 17:27:00 oes Exp $";
   2
   3 /*********************************************************************
   4  *
   5  * File        :  $Source: /cvsroot/ijbswa/current/pcrs.c,v $
   6  *
   7  * Purpose     :  pcrs is a supplement to the brilliant pcre library by Philip
   8  *                Hazel (ph10@cam.ac.uk) and adds Perl-style substitution. That
   9  *                is, it mimics Perl's 's' operator.
  10  *
  11  *                Currently, there's no documentation besides comments and the
  12  *                source itself ;-)
  13  *
  14  *                Note: In addition to perl's options, 'U' for ungreedy and 'T'
  15  *                for trivial (i.e.: ignore backrefs in the substitute) are
  16  *                supported.
  17  *
  18  * Copyright   :  Written and Copyright (C) 2000, 2001 by Andreas S. Oesterhelt
  19  *                <andreas@oesterhelt.org>
  20  *
  21  *                This program is free software; you can redistribute it
  22  *                and/or modify it under the terms of the GNU General
  23  *                Public License as published by the Free Software
  24  *                Foundation; either version 2 of the License, or (at
  25  *                your option) any later version.
  26  *
  27  *                This program is distributed in the hope that it will
  28  *                be useful, but WITHOUT ANY WARRANTY; without even the
  29  *                implied warranty of MERCHANTABILITY or FITNESS FOR A
  30  *                PARTICULAR PURPOSE.  See the GNU General Public
  31  *                License for more details.
  32  *
  33  *                The GNU General Public License should be included with
  34  *                this file.  If not, you can view it at
  35  *                http://www.gnu.org/copyleft/gpl.html
  36  *                or write to the Free Software Foundation, Inc., 59
  37  *                Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  38  *
  39  * Revisions   :
  40  *    $Log: pcrs.c,v $
  41  *    Revision 1.9  2001/07/18 17:27:00  oes
  42  *    Changed interface; Cosmetics
  43  *
  44  *    Revision 1.8  2001/06/29 21:45:41  oes
  45  *    Indentation, CRLF->LF, Tab-> Space
  46  *
  47  *    Revision 1.7  2001/06/29 13:33:04  oes
  48  *    - Cleaned up, renamed and reordered functions,
  49  *      improved comments
  50  *    - Removed my_strsep
  51  *    - Replaced globalflag with a general flags int
  52  *      that holds PCRS_GLOBAL, PCRS_SUCCESS, and PCRS_TRIVIAL
  53  *    - Introduced trivial option that will prevent pcrs
  54  *      from honouring backreferences in the substitute,
  55  *      which is useful for large substitutes that are
  56  *      red in from somewhere and saves the pain of escaping
  57  *      the backrefs
  58  *    - Introduced convenience function pcrs_free_joblist()
  59  *    - Split pcrs_make_job() into pcrs_compile(), which still
  60  *      takes a complete s/// comand as argument and parses it,
  61  *      and a new function pcrs_make_job, which takes the
  62  *      three separate components. This should make for a
  63  *      much friendlier frontend.
  64  *    - Removed create_pcrs_job() which was useless
  65  *    - Fixed a bug in pcrs_execute
  66  *    - Success flag is now handled by pcrs instead of user
  67  *    - Removed logentry from cancelled commit
  68  *
  69  *    Revision 1.6  2001/06/03 19:12:45  oes
  70  *    added FIXME
  71  *
  72  *    Revision 1.5  2001/05/29 09:50:24  jongfoster
  73  *    Unified blocklist/imagelist/permissionslist.
  74  *    File format is still under discussion, but the internal changes
  75  *    are (mostly) done.
  76  *
  77  *    Also modified interceptor behaviour:
  78  *    - We now intercept all URLs beginning with one of the following
  79  *      prefixes (and *only* these prefixes):
  80  *        * http://i.j.b/
  81  *        * http://ijbswa.sf.net/config/
  82  *        * http://ijbswa.sourceforge.net/config/
  83  *    - New interceptors "home page" - go to http://i.j.b/ to see it.
  84  *    - Internal changes so that intercepted and fast redirect pages
  85  *      are not replaced with an image.
  86  *    - Interceptors now have the option to send a binary page direct
  87  *      to the client. (i.e. ijb-send-banner uses this)
  88  *    - Implemented show-url-info interceptor.  (Which is why I needed
  89  *      the above interceptors changes - a typical URL is
  90  *      "http://i.j.b/show-url-info?url=www.somesite.com/banner.gif".
  91  *      The previous mechanism would not have intercepted that, and
  92  *      if it had been intercepted then it then it would have replaced
  93  *      it with an image.)
  94  *
  95  *    Revision 1.4  2001/05/25 14:12:40  oes
  96  *    Fixed bug: Empty substitutes now detected
  97  *
  98  *    Revision 1.3  2001/05/25 11:03:55  oes
  99  *    Added sanity check for NULL jobs to pcrs_exec_substitution
 100  *
 101  *    Revision 1.2  2001/05/22 18:46:04  oes
 102  *
 103  *    - Enabled filtering banners by size rather than URL
 104  *      by adding patterns that replace all standard banner
 105  *      sizes with the "Junkbuster" gif to the re_filterfile
 106  *
 107  *    - Enabled filtering WebBugs by providing a pattern
 108  *      which kills all 1x1 images
 109  *
 110  *    - Added support for PCRE_UNGREEDY behaviour to pcrs,
 111  *      which is selected by the (nonstandard and therefore
 112  *      capital) letter 'U' in the option string.
 113  *      It causes the quantifiers to be ungreedy by default.
 114  *      Appending a ? turns back to greedy (!).
 115  *
 116  *    - Added a new interceptor ijb-send-banner, which
 117  *      sends back the "Junkbuster" gif. Without imagelist or
 118  *      MSIE detection support, or if tinygif = 1, or the
 119  *      URL isn't recognized as an imageurl, a lame HTML
 120  *      explanation is sent instead.
 121  *
 122  *    - Added new feature, which permits blocking remote
 123  *      script redirects and firing back a local redirect
 124  *      to the browser.
 125  *      The feature is conditionally compiled, i.e. it
 126  *      can be disabled with --disable-fast-redirects,
 127  *      plus it must be activated by a "fast-redirects"
 128  *      line in the config file, has its own log level
 129  *      and of course wants to be displayed by show-proxy-args
 130  *      Note: Boy, all the #ifdefs in 1001 locations and
 131  *      all the fumbling with configure.in and acconfig.h
 132  *      were *way* more work than the feature itself :-(
 133  *
 134  *    - Because a generic redirect template was needed for
 135  *      this, tinygif = 3 now uses the same.
 136  *
 137  *    - Moved GIFs, and other static HTTP response templates
 138  *      to project.h
 139  *
 140  *    - Some minor fixes
 141  *
 142  *    - Removed some >400 CRs again (Jon, you really worked
 143  *      a lot! ;-)
 144  *
 145  *    Revision 1.1.1.1  2001/05/15 13:59:02  oes
 146  *    Initial import of version 2.9.3 source tree
 147  *
 148  *
 149  *********************************************************************/
 150 \f
 151
 152 #include <pcre.h>
 153 #include <string.h>
 154 #include "pcrs.h"
 155 const char pcrs_h_rcs[] = PCRS_H_VERSION;
 156
 157
 158 /*********************************************************************
 159  *
 160  * Function    :  pcrs_compile_perl_options
 161  *
 162  * Description :  This function parses a string containing the options to
 163  *                Perl's s/// operator. It returns an integer that is the
 164  *                pcre equivalent of the symbolic optstring.
 165  *                Since pcre doesn't know about Perl's 'g' (global) or pcrs',
 166  *                'T' (trivial) options but pcrs needs them, the corresponding
 167  *                flags are set if 'g'or 'T' is encountered.
 168  *                Note: The 'T' and 'U' options do not conform to Perl.
 169  *
 170  * Parameters  :
 171  *          1  :  optstring = string with options in perl syntax
 172  *          2  :  flags = see description
 173  *
 174  * Returns     :  option integer suitable for pcre
 175  *
 176  *********************************************************************/
 177 int pcrs_compile_perl_options(const char *optstring, int *flags)
 178 {
 179    size_t i;
 180    int rc = 0;
 181    *flags = 0;
 182    for (i=0; i < strlen(optstring); i++)
 183    {
 184       switch(optstring[i])
 185       {
 186          case 'e': break;
 187          case 'g': *flags |= PCRS_GLOBAL; break;
 188          case 'i': rc |= PCRE_CASELESS; break;
 189          case 'm': rc |= PCRE_MULTILINE; break;
 190          case 'o': break;
 191          case 's': rc |= PCRE_DOTALL; break;
 192          case 'x': rc |= PCRE_EXTENDED; break;
 193          case 'U': rc |= PCRE_UNGREEDY; break;
 194            case 'T': *flags |= PCRS_TRIVIAL; break;
 195          default:  break;
 196       }
 197    }
 198    return rc;
 199
 200 }
 201
 202
 203 /*********************************************************************
 204  *
 205  * Function    :  pcrs_compile_replacement
 206  *
 207  * Description :  This function takes a Perl-style replacement (2nd argument
 208  *                to the s/// operator and returns a compiled pcrs_substitute,
 209  *                or NULL if memory allocation for the substitute structure
 210  *                fails.
 211  *
 212  * Parameters  :
 213  *          1  :  replacement = replacement part of s/// operator
 214  *                              in perl syntax
 215  *          2  :  errptr = pointer to an integer in which error
 216  *                         conditions can be returned.
 217  *
 218  * Returns     :  pcrs_substitute data structure, or NULL if an
 219  *                error is encountered. In that case, *errptr has
 220  *                the reason.
 221  *
 222  *********************************************************************/
 223 pcrs_substitute *pcrs_compile_replacement(const char *replacement, int trivialflag, int *errptr)
 224 {
 225    int length, i, k = 0, l = 0, quoted = 0, idx;
 226    char *text, *num_ptr, *numbers = "0123456789";
 227    pcrs_substitute *r;
 228
 229    r = (pcrs_substitute *)malloc(sizeof(pcrs_substitute));
 230    if (r == NULL) return NULL;
 231    memset(r, '\0', sizeof(pcrs_substitute));
 232
 233    text = strdup(replacement);      /* must be free()d by caller */
 234    if (text  == NULL)
 235    {
 236       *errptr = PCRS_ERR_NOMEM;
 237       free(r);
 238       return NULL;
 239    }
 240
 241    length = strlen(replacement);
 242
 243    if (trivialflag)
 244    {
 245        k = length;
 246    }
 247    else
 248    {
 249       for (i=0; i < length; i++)
 250       {
 251          /* Backslash treatment */
 252          if (replacement[i] == '\\')
 253          {
 254             if (quoted)
 255             {
 256                text[k++] = replacement[i];
 257                quoted = 0;
 258             }
 259             else
 260             {
 261                quoted = 1;
 262             }
 263             continue;
 264          }
 265
 266          /* Dollar treatment */
 267          if (replacement[i] == '$' && !quoted && i < length - 1)
 268          {
 269             if (strchr("0123456789&", replacement[i + 1]) == NULL)
 270             {
 271                text[k++] = replacement[i];
 272             }
 273             else
 274             {
 275                r->block_length[l] = k - r->block_offset[l];
 276                r->backref[l] = 0;
 277                if (replacement[i + 1] != '&')
 278                {
 279                   while ((num_ptr = strchr(numbers, replacement[++i])) != NULL && i < length)
 280                   {
 281                      idx = num_ptr - numbers;
 282                      r->backref[l] = r->backref[l] * 10 + idx;
 283                   }
 284                   i--;
 285                }
 286                else
 287                   i++;
 288                if (r->backref[l] < PCRS_MAX_SUBMATCHES)
 289                   r->backref_count[r->backref[l]] += 1;
 290                l++;
 291                r->block_offset[l] = k;
 292             }
 293             continue;
 294          }
 295
 296          /* Plain char treatment */
 297          text[k++] = replacement[i];
 298          quoted = 0;
 299       }
 300    } /* -END- if (!trivialflag) */
 301
 302    text[k] = '\0';
 303    r->text = text;
 304    r->backrefs = l;
 305    r->block_length[l] = k - r->block_offset[l];
 306    return r;
 307
 308 }
 309
 310
 311 /*********************************************************************
 312  *
 313  * Function    :  pcrs_free_job
 314  *
 315  * Description :  Frees the memory used by a pcrs_job struct and its
 316  *                dependant structures. Returns a pointer to the next
 317  *                job, if there was any, or NULL otherwise.
 318  *
 319  * Parameters  :
 320  *          1  :  job = pointer to the pcrs_job structure to be freed
 321  *
 322  * Returns     :  a pointer to the next job, if there was any, or
 323  *                NULL otherwise.
 324  *
 325  *********************************************************************/
 326 pcrs_job *pcrs_free_job(pcrs_job *job)
 327 {
 328    pcrs_job *next;
 329
 330    if (job == NULL)
 331    {
 332       return NULL;
 333    }
 334    else
 335    {
 336       next = job->next;
 337       if (job->pattern != NULL) free(job->pattern);
 338       if (job->hints != NULL) free(job->hints);
 339       if (job->substitute != NULL)
 340       {
 341          if (job->substitute->text != NULL) free(job->substitute->text);
 342          free(job->substitute);
 343       }
 344       free(job);
 345    }
 346    return next;
 347
 348 }
 349
 350 /*********************************************************************
 351  *
 352  * Function    :  pcrs_free_joblist
 353  *
 354  * Description :  Iterates through a chained list of pcrs_job's and
 355  *                frees them using pcrs_free_job.
 356  *
 357  * Parameters  :
 358  *          1  :  joblist = pointer to the first pcrs_job structure to
 359  *                be freed
 360  *
 361  * Returns     :  N/A
 362  *
 363  *********************************************************************/
 364 void pcrs_free_joblist(pcrs_job *joblist)
 365 {
 366    while ( NULL != (joblist = pcrs_free_job(joblist)) ) {};
 367
 368    return;
 369
 370 }
 371
 372
 373 /*********************************************************************
 374  *
 375  * Function    :  pcrs_compile_command
 376  *
 377  * Description :  Parses a string with a Perl-style s/// command,
 378  *                calls pcrs_compile, and returns a corresponding
 379  *                pcrs_job, or NULL if parsing or compiling the job
 380  *                fails.
 381  *
 382  * Parameters  :
 383  *          1  :  command = string with perl-style s/// command
 384  *          2  :  errptr = pointer to an integer in which error
 385  *                         conditions can be returned.
 386  *
 387  * Returns     :  a corresponding pcrs_job data structure, or NULL
 388  *                if an error was encountered. In that case, *errptr
 389  *                has the reason.
 390  *
 391  *********************************************************************/
 392 pcrs_job *pcrs_compile_command(const char *command, int *errptr)
 393 {
 394    int i, k, l, limit, quoted = FALSE;
 395    char delimiter;
 396    char *tokens[4];
 397    pcrs_job *newjob;
 398
 399    i = k = l = 0;
 400
 401    /*
 402     * Tokenize the perl command
 403     */
 404    limit = strlen(command);
 405    if (limit < 4)
 406    {
 407       *errptr = PCRS_ERR_CMDSYNTAX;
 408       return NULL;
 409    }
 410    else
 411    {
 412      delimiter = command[1];
 413    }
 414
 415    tokens[l] = (char *) malloc(limit + 1);
 416
 417    for (i=0; i <= limit; i++)
 418    {
 419
 420       if (command[i] == delimiter && !quoted)
 421       {
 422            if (l == 3)
 423                 {
 424                    l = -1;
 425             break;
 426          }
 427           tokens[0][k++] = '\0';
 428          tokens[++l] = tokens[0] + k;
 429          continue;
 430       }
 431
 432       else if (command[i] == '\\' && !quoted && i+1 < limit && command[i+1] == delimiter)
 433       {
 434          quoted = TRUE;
 435          continue;
 436       }
 437       tokens[0][k++] = command[i];
 438       quoted = FALSE;
 439    }
 440
 441
 442    /*
 443     * Syntax error ?
 444     */
 445    if (l != 3)
 446    {
 447       *errptr = PCRS_ERR_CMDSYNTAX;
 448       free(tokens[0]);
 449       return NULL;
 450    }
 451
 452    newjob = pcrs_compile(tokens[1], tokens[2], tokens[3], errptr);
 453    free(tokens[0]);
 454    return newjob;
 455
 456 }
 457
 458
 459 /*********************************************************************
 460  *
 461  * Function    :  pcrs_compile
 462  *
 463  * Description :  Takes the three arguments to a perl s/// command
 464  *                and compiles a pcrs_job structure from them.
 465  *
 466  * Parameters  :
 467  *          1  :  pattern = string with perl-style pattern
 468  *          2  :  substitute = string with perl-style substitute
 469  *          3  :  options = string with perl-style options
 470  *          4  :  errptr = pointer to an integer in which error
 471  *                         conditions can be returned.
 472  *
 473  * Returns     :  a corresponding pcrs_job data structure, or NULL
 474  *                if an error was encountered. In that case, *errptr
 475  *                has the reason.
 476  *
 477  *********************************************************************/
 478 pcrs_job *pcrs_compile(const char *pattern, const char *substitute, const char *options, int *errptr)
 479 {
 480    pcrs_job *newjob;
 481    int flags;
 482    const char *error;
 483
 484
 485    /*
 486     * Handle NULL arguments
 487     */
 488    if (pattern == NULL) pattern = "";
 489    if (substitute == NULL) substitute = "";
 490    if (options == NULL) options = "";
 491
 492
 493    /*
 494     * Get and init memory
 495     */
 496    if (NULL == (newjob = (pcrs_job *)malloc(sizeof(pcrs_job))))
 497    {
 498       *errptr = PCRS_ERR_NOMEM;
 499       return NULL;
 500    }
 501    memset(newjob, '\0', sizeof(pcrs_job));
 502
 503
 504    /*
 505     * Evaluate the options
 506     */
 507    newjob->options = pcrs_compile_perl_options(options, &flags);
 508    newjob->flags = flags;
 509
 510
 511    /*
 512     * Compile the pattern
 513     */
 514    newjob->pattern = pcre_compile(pattern, newjob->options, &error, errptr, NULL);
 515    if (newjob->pattern == NULL)
 516    {
 517       pcrs_free_job(newjob);
 518       return NULL;
 519    }
 520
 521
 522    /*
 523     * Generate hints. This has little overhead, since the
 524     * hints will be NULL for a boring pattern anyway.
 525     */
 526    newjob->hints = pcre_study(newjob->pattern, 0, &error);
 527    if (error != NULL)
 528    {
 529       *errptr = PCRS_ERR_STUDY;
 530       pcrs_free_job(newjob);
 531       return NULL;
 532    }
 533
 534
 535    /*
 536     * Compile the substitute
 537     */
 538    if (NULL == (newjob->substitute = pcrs_compile_replacement(substitute, newjob->flags & PCRS_TRIVIAL, errptr)))
 539    {
 540       pcrs_free_job(newjob);
 541       return NULL;
 542    }
 543
 544    return newjob;
 545
 546 }
 547
 548
 549 /*********************************************************************
 550  *
 551  * Function    :  pcrs_execute
 552  *
 553  * Description :  Modify the subject by executing the regular substitution
 554  *                defined by the job. Since the result may be longer than
 555  *                the subject, its space requirements are precalculated in
 556  *                the matching phase and new memory is allocated accordingly.
 557  *                It is the caller's responsibility to free the result when
 558  *                it's no longer needed.
 559  *
 560  * Parameters  :
 561  *          1  :  job = the pcrs_job to be executed
 562  *          2  :  subject = the subject (== original) string
 563  *          3  :  subject_length = the subject's length
 564  *                INCLUDING the terminating zero, if string!
 565  *          4  :  result = char** for returning  the result
 566  *          5  :  result_length = int* for returning the result's length
 567  *
 568  * Returns     :  the number of substitutions that were made. May be > 1
 569  *                if job->flags contained PCRS_GLOBAL
 570  *
 571  *********************************************************************/
 572 int pcrs_execute(pcrs_job *job, char *subject, int subject_length, char **result, int *result_length)
 573 {
 574    int offsets[3 * PCRS_MAX_SUBMATCHES],
 575        offset, i, k,
 576        matches_found,
 577        newsize,
 578        submatches;
 579    pcrs_match matches[PCRS_MAX_MATCHES];
 580    char *result_offset;
 581
 582    offset = i = k = 0;
 583
 584    /*
 585     * Sanity check
 586     */
 587    if (job == NULL || job->pattern == NULL || job->substitute == NULL)
 588    {
 589       *result = NULL;
 590       return(PCRS_ERR_BADJOB);
 591    }
 592
 593
 594    /*
 595     * Find the pattern and calculate the space
 596     * requirements for the result (newsize)
 597     */
 598    newsize=subject_length;
 599
 600    while ((submatches = pcre_exec(job->pattern, job->hints, subject, subject_length, offset, 0, offsets, 3 * PCRS_MAX_SUBMATCHES)) > 0)
 601    {
 602       job->flags |= PCRS_SUCCESS;
 603       matches[i].submatches = submatches;
 604       for (k=0; k < submatches; k++)
 605       {
 606          matches[i].submatch_offset[k] = offsets[2 * k];
 607
 608          /* Note: Non-found optional submatches have length -1-(-1)==0 */
 609          matches[i].submatch_length[k] = offsets[2 * k + 1] - offsets[2 * k];
 610
 611          /* reserve mem for each submatch as often as it is ref'd */
 612          newsize += matches[i].submatch_length[k] * job->substitute->backref_count[k];
 613       }
 614       /* plus replacement text size minus match text size */
 615       newsize += strlen(job->substitute->text) - matches[i].submatch_length[0];
 616
 617       /* Non-global search or limit reached? */
 618       if (++i >= PCRS_MAX_MATCHES || !(job->flags & PCRS_GLOBAL) ) break;
 619
 620       /* Don't loop on empty matches */
 621       if (offsets[1] == offset)
 622          if (offset < subject_length)
 623             offset++;
 624          else
 625             break;
 626       /* Go find the next one */
 627       else
 628          offset = offsets[1];
 629    }
 630    /* Pass pcre error through if failiure */
 631    if (submatches < -1) return submatches;
 632    matches_found = i;
 633
 634
 635    /*
 636     * Get memory for the result
 637     */
 638    if ((*result = (char *)malloc(newsize)) == NULL)   /* must be free()d by caller */
 639    {
 640       return PCRS_ERR_NOMEM;
 641    }
 642
 643
 644    /*
 645     * Replace
 646     */
 647    offset = 0;
 648    result_offset = *result;
 649
 650    for (i=0; i < matches_found; i++)
 651    {
 652       /* copy the chunk preceding the match */
 653       memcpy(result_offset, subject + offset, matches[i].submatch_offset[0] - offset);
 654       result_offset += matches[i].submatch_offset[0] - offset;
 655
 656       /* For every segment of the substitute.. */
 657       for (k=0; k <= job->substitute->backrefs; k++)
 658       {
 659          /* ...copy its text.. */
 660          memcpy(result_offset, job->substitute->text + job->substitute->block_offset[k], job->substitute->block_length[k]);
 661          result_offset += job->substitute->block_length[k];
 662
 663          /* ..plus, if it's not the last chunk, i.e.: There *is* a backref.. */
 664          if (k != job->substitute->backrefs
 665              /* ..in legal range.. */
 666              && job->substitute->backref[k] <= PCRS_MAX_SUBMATCHES
 667              /* ..and referencing a nonempty match.. */
 668              && matches[i].submatch_length[job->substitute->backref[k]] > 0)
 669          {
 670             /* ..copy the submatch that is ref'd. */
 671             memcpy(
 672                result_offset,
 673                subject + matches[i].submatch_offset[job->substitute->backref[k]],
 674                matches[i].submatch_length[job->substitute->backref[k]]
 675             );
 676             result_offset += matches[i].submatch_length[job->substitute->backref[k]];
 677          }
 678       }
 679       offset =  matches[i].submatch_offset[0] + matches[i].submatch_length[0];
 680    }
 681
 682    /* Copy the rest. */
 683    memcpy(result_offset, subject + offset, subject_length - offset);
 684
 685    *result_length = newsize;
 686    return matches_found;
 687
 688 }
 689
 690
 691 /*
 692   Local Variables:
 693   tab-width: 3
 694   end:
 695 */