pcrs.c

   1 const char pcrs_rcs[] = "$Id: pcrs.c,v 1.28 2007/08/18 14:37:27 fabiankeil Exp $";
   2 /*********************************************************************
   3  *
   4  * File        :  $Source: /cvsroot/ijbswa/current/pcrs.c,v $
   5  *
   6  * Purpose     :  pcrs is a supplement to the pcre library by Philip Hazel
   7  *                <ph10@cam.ac.uk> and adds Perl-style substitution. That
   8  *                is, it mimics Perl's 's' operator. See pcrs(3) for details.
   9  *
  10  *                WARNING: This file contains additional functions and bug
  11  *                fixes that aren't part of the latest official pcrs package
  12  *                (which apparently is no longer maintained).
  13  *
  14  * Copyright   :  Written and Copyright (C) 2000, 2001 by Andreas S. Oesterhelt
  15  *                <andreas@oesterhelt.org>
  16  *
  17  *                Copyright (C) 2006, 2007 Fabian Keil <fk@fabiankeil.de>
  18  *
  19  *                This program is free software; you can redistribute it
  20  *                and/or modify it under the terms of the GNU Lesser
  21  *                General Public License (LGPL), version 2.1, which  should
  22  *                be included in this distribution (see LICENSE.txt), with
  23  *                the exception that the permission to replace that license
  24  *                with the GNU General Public License (GPL) given in section
  25  *                3 is restricted to version 2 of the GPL.
  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 license for more details.
  31  *
  32  *                The GNU Lesser General Public License should be included
  33  *                with this file.  If not, you can view it at
  34  *                http://www.gnu.org/licenses/lgpl.html
  35  *                or write to the Free Software Foundation, Inc., 59
  36  *                Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  37  *
  38  * Revisions   :
  39  *    $Log: pcrs.c,v $
  40  *    Revision 1.28  2007/08/18 14:37:27  fabiankeil
  41  *    Ditch hex_to_byte() in favour of xtoi().
  42  *
  43  *    Revision 1.27  2007/08/05 13:47:04  fabiankeil
  44  *    #1763173 from Stefan Huehner: s@const static@static const@.
  45  *
  46  *    Revision 1.26  2007/07/01 13:29:54  fabiankeil
  47  *    Add limited hex notation support for the PCRS
  48  *    substitution text ('\x7e' = '~'). Closes #1627140.
  49  *
  50  *    Revision 1.25  2007/04/30 15:02:18  fabiankeil
  51  *    Introduce dynamic pcrs jobs that can resolve variables.
  52  *
  53  *    Revision 1.24  2007/01/05 15:46:12  fabiankeil
  54  *    Don't use strlen() to calculate the length of
  55  *    the pcrs substitutes. They don't have to be valid C
  56  *    strings and getting their length wrong can result in
  57  *    user-controlled memory corruption.
  58  *
  59  *    Thanks to Felix Gröbert for reporting the problem
  60  *    and providing the fix [#1627140].
  61  *
  62  *    Revision 1.23  2006/12/29 17:53:05  fabiankeil
  63  *    Fixed gcc43 conversion warnings.
  64  *
  65  *    Revision 1.22  2006/12/24 17:34:20  fabiankeil
  66  *    Add pcrs_strerror() message for PCRE_ERROR_MATCHLIMIT
  67  *    and give a hint why an error code might be unknown.
  68  *
  69  *    Catch NULL subjects early in pcrs_execute().
  70  *
  71  *    Revision 1.21  2006/07/18 14:48:47  david__schmidt
  72  *    Reorganizing the repository: swapping out what was HEAD (the old 3.1 branch)
  73  *    with what was really the latest development (the v_3_0_branch branch)
  74  *
  75  *    Revision 1.19.2.4  2005/05/07 21:50:55  david__schmidt
  76  *    A few memory leaks plugged (mostly on error paths)
  77  *
  78  *    Revision 1.19.2.3  2003/12/04 12:32:45  oes
  79  *    Append a trailing nullbyte to result to facilitate string processing
  80  *
  81  *    Revision 1.19.2.2  2002/10/08 16:22:28  oes
  82  *    Bugfix: Need to check validity of backreferences explicitly,
  83  *    because when max_matches are reached and matches is expanded,
  84  *    realloc() does not zero the memory. Fixes Bug # 606227
  85  *
  86  *    Revision 1.19.2.1  2002/08/10 11:23:40  oes
  87  *    Include prce.h via project.h, where the appropriate
  88  *    source will have been selected
  89  *
  90  *    Revision 1.19  2002/03/08 14:47:48  oes
  91  *    Cosmetics
  92  *
  93  *    Revision 1.18  2002/03/08 14:17:14  oes
  94  *    Fixing -Wconversion warnings
  95  *
  96  *    Revision 1.17  2002/03/08 13:45:48  oes
  97  *    Hiding internal functions
  98  *
  99  *    Revision 1.16  2001/11/30 21:32:14  jongfoster
 100  *    Fixing signed/unsigned comparison (Andreas please check this!)
 101  *    One tab->space
 102  *
 103  *    Revision 1.15  2001/09/20 16:11:06  steudten
 104  *
 105  *    Add casting for some string functions.
 106  *
 107  *    Revision 1.14  2001/09/09 21:41:57  oes
 108  *    Fixing yet another silly bug
 109  *
 110  *    Revision 1.13  2001/09/06 14:05:59  oes
 111  *    Fixed silly bug
 112  *
 113  *    Revision 1.12  2001/08/18 11:35:00  oes
 114  *    - Introduced pcrs_strerror()
 115  *    - made some NULL arguments non-fatal
 116  *    - added support for \n \r \e \b \t \f \a \0 in substitute
 117  *    - made quoting adhere to standard rules
 118  *    - added warning for bad backrefs
 119  *    - added pcrs_execute_list()
 120  *    - fixed comments
 121  *    - bugfix & cosmetics
 122  *
 123  *    Revision 1.11  2001/08/15 15:32:03  oes
 124  *     - Added support for Perl's special variables $+, $' and $`
 125  *     - Improved the substitute parser
 126  *     - Replaced the hard limit for the maximum number of matches
 127  *       by dynamic reallocation
 128  *
 129  *    Revision 1.10  2001/08/05 13:13:11  jongfoster
 130  *    Making parameters "const" where possible.
 131  *
 132  *    Revision 1.9  2001/07/18 17:27:00  oes
 133  *    Changed interface; Cosmetics
 134  *
 135  *    Revision 1.8  2001/06/29 21:45:41  oes
 136  *    Indentation, CRLF->LF, Tab-> Space
 137  *
 138  *    Revision 1.7  2001/06/29 13:33:04  oes
 139  *    - Cleaned up, renamed and reordered functions,
 140  *      improved comments
 141  *    - Removed my_strsep
 142  *    - Replaced globalflag with a general flags int
 143  *      that holds PCRS_GLOBAL, PCRS_SUCCESS, and PCRS_TRIVIAL
 144  *    - Introduced trivial option that will prevent pcrs
 145  *      from honouring backreferences in the substitute,
 146  *      which is useful for large substitutes that are
 147  *      red in from somewhere and saves the pain of escaping
 148  *      the backrefs
 149  *    - Introduced convenience function pcrs_free_joblist()
 150  *    - Split pcrs_make_job() into pcrs_compile(), which still
 151  *      takes a complete s/// comand as argument and parses it,
 152  *      and a new function pcrs_make_job, which takes the
 153  *      three separate components. This should make for a
 154  *      much friendlier frontend.
 155  *    - Removed create_pcrs_job() which was useless
 156  *    - Fixed a bug in pcrs_execute
 157  *    - Success flag is now handled by pcrs instead of user
 158  *
 159  *    Revision 1.6  2001/06/03 19:12:45  oes
 160  *    added FIXME
 161  *
 162  *    Revision 1.5  2001/05/29 09:50:24  jongfoster
 163  *    (Fixed one int -> size_t)
 164  *
 165  *    Revision 1.4  2001/05/25 14:12:40  oes
 166  *    Fixed bug: Empty substitutes now detected
 167  *
 168  *    Revision 1.3  2001/05/25 11:03:55  oes
 169  *    Added sanity check for NULL jobs to pcrs_exec_substitution
 170  *
 171  *    Revision 1.2  2001/05/22 18:46:04  oes
 172  *
 173  *      Added support for PCRE_UNGREEDY behaviour to pcrs,
 174  *      which is selected by the (nonstandard and therefore
 175  *      capital) letter 'U' in the option string.
 176  *      It causes the quantifiers to be ungreedy by default.
 177  *      Appending a ? turns back to greedy (!).
 178  *
 179  *    Revision 1.1.1.1  2001/05/15 13:59:02  oes
 180  *    Initial import of version 2.9.3 source tree
 181  *
 182  *
 183  *********************************************************************/
 184 \f
 185
 186 #include <string.h>
 187 #include <ctype.h>
 188 #include <assert.h>
 189
 190 /*
 191  * Include project.h just so that the right pcre.h gets
 192  * included from there
 193  */
 194 #include "project.h"
 195
 196 /* For snprintf only */
 197 #include "miscutil.h"
 198 /* For xtoi */
 199 #include "encode.h"
 200
 201 #include "pcrs.h"
 202
 203 const char pcrs_h_rcs[] = PCRS_H_VERSION;
 204
 205 /*
 206  * Internal prototypes
 207  */
 208
 209 static int              pcrs_parse_perl_options(const char *optstring, int *flags);
 210 static pcrs_substitute *pcrs_compile_replacement(const char *replacement, int trivialflag,
 211                         int capturecount, int *errptr);
 212 static int              is_hex_sequence(const char *sequence);
 213
 214 /*********************************************************************
 215  *
 216  * Function    :  pcrs_strerror
 217  *
 218  * Description :  Return a string describing a given error code.
 219  *
 220  * Parameters  :
 221  *          1  :  error = the error code
 222  *
 223  * Returns     :  char * to the descriptive string
 224  *
 225  *********************************************************************/
 226 const char *pcrs_strerror(const int error)
 227 {
 228    if (error < 0)
 229    {
 230       switch (error)
 231       {
 232          /* Passed-through PCRE error: */
 233          case PCRE_ERROR_NOMEMORY:     return "(pcre:) No memory";
 234
 235          /* Shouldn't happen unless PCRE or PCRS bug, or user messed with compiled job: */
 236          case PCRE_ERROR_NULL:         return "(pcre:) NULL code or subject or ovector";
 237          case PCRE_ERROR_BADOPTION:    return "(pcre:) Unrecognized option bit";
 238          case PCRE_ERROR_BADMAGIC:     return "(pcre:) Bad magic number in code";
 239          case PCRE_ERROR_UNKNOWN_NODE: return "(pcre:) Bad node in pattern";
 240
 241          /* Can't happen / not passed: */
 242          case PCRE_ERROR_NOSUBSTRING:  return "(pcre:) Fire in power supply";
 243          case PCRE_ERROR_NOMATCH:      return "(pcre:) Water in power supply";
 244
 245 #ifdef PCRE_ERROR_MATCHLIMIT
 246          /*
 247           * Only reported by PCRE versions newer than our own.
 248           */
 249          case PCRE_ERROR_MATCHLIMIT:   return "(pcre:) Match limit reached";
 250 #endif /* def PCRE_ERROR_MATCHLIMIT */
 251
 252          /* PCRS errors: */
 253          case PCRS_ERR_NOMEM:          return "(pcrs:) No memory";
 254          case PCRS_ERR_CMDSYNTAX:      return "(pcrs:) Syntax error while parsing command";
 255          case PCRS_ERR_STUDY:          return "(pcrs:) PCRE error while studying the pattern";
 256          case PCRS_ERR_BADJOB:         return "(pcrs:) Bad job - NULL job, pattern or substitute";
 257          case PCRS_WARN_BADREF:        return "(pcrs:) Backreference out of range";
 258          case PCRS_WARN_TRUNCATION:
 259             return "(pcrs:) At least one variable was too big and has been truncated before compilation";
 260
 261          /*
 262           * XXX: With the exception of PCRE_ERROR_MATCHLIMIT we
 263           * only catch PCRE errors that can happen with our internal
 264           * version. If Privoxy is linked against a newer
 265           * PCRE version all bets are off ...
 266           */
 267          default:  return "Unknown error. Privoxy out of sync with PCRE?";
 268       }
 269    }
 270    /* error >= 0: No error */
 271    return "(pcrs:) Everything's just fine. Thanks for asking.";
 272
 273 }
 274
 275
 276 /*********************************************************************
 277  *
 278  * Function    :  pcrs_parse_perl_options
 279  *
 280  * Description :  This function parses a string containing the options to
 281  *                Perl's s/// operator. It returns an integer that is the
 282  *                pcre equivalent of the symbolic optstring.
 283  *                Since pcre doesn't know about Perl's 'g' (global) or pcrs',
 284  *                'T' (trivial) options but pcrs needs them, the corresponding
 285  *                flags are set if 'g'or 'T' is encountered.
 286  *                Note: The 'T' and 'U' options do not conform to Perl.
 287  *
 288  * Parameters  :
 289  *          1  :  optstring = string with options in perl syntax
 290  *          2  :  flags = see description
 291  *
 292  * Returns     :  option integer suitable for pcre
 293  *
 294  *********************************************************************/
 295 static int pcrs_parse_perl_options(const char *optstring, int *flags)
 296 {
 297    size_t i;
 298    int rc = 0;
 299    *flags = 0;
 300
 301    if (NULL == optstring) return 0;
 302
 303    for (i = 0; i < strlen(optstring); i++)
 304    {
 305       switch(optstring[i])
 306       {
 307          case 'e': break; /* ToDo ;-) */
 308          case 'g': *flags |= PCRS_GLOBAL; break;
 309          case 'i': rc |= PCRE_CASELESS; break;
 310          case 'm': rc |= PCRE_MULTILINE; break;
 311          case 'o': break;
 312          case 's': rc |= PCRE_DOTALL; break;
 313          case 'x': rc |= PCRE_EXTENDED; break;
 314          case 'U': rc |= PCRE_UNGREEDY; break;
 315          case 'T': *flags |= PCRS_TRIVIAL; break;
 316          default: break;
 317       }
 318    }
 319    return rc;
 320
 321 }
 322
 323
 324 /*********************************************************************
 325  *
 326  * Function    :  pcrs_compile_replacement
 327  *
 328  * Description :  This function takes a Perl-style replacement (2nd argument
 329  *                to the s/// operator and returns a compiled pcrs_substitute,
 330  *                or NULL if memory allocation for the substitute structure
 331  *                fails.
 332  *
 333  * Parameters  :
 334  *          1  :  replacement = replacement part of s/// operator
 335  *                              in perl syntax
 336  *          2  :  trivialflag = Flag that causes backreferences to be
 337  *                              ignored.
 338  *          3  :  capturecount = Number of capturing subpatterns in
 339  *                               the pattern. Needed for $+ handling.
 340  *          4  :  errptr = pointer to an integer in which error
 341  *                         conditions can be returned.
 342  *
 343  * Returns     :  pcrs_substitute data structure, or NULL if an
 344  *                error is encountered. In that case, *errptr has
 345  *                the reason.
 346  *
 347  *********************************************************************/
 348 static pcrs_substitute *pcrs_compile_replacement(const char *replacement, int trivialflag, int capturecount, int *errptr)
 349 {
 350    int i, k, l, quoted;
 351    size_t length;
 352    char *text;
 353    pcrs_substitute *r;
 354
 355    i = k = l = quoted = 0;
 356
 357    /*
 358     * Sanity check
 359     */
 360    if (NULL == replacement)
 361    {
 362       replacement = "";
 363    }
 364
 365    /*
 366     * Get memory or fail
 367     */
 368    if (NULL == (r = (pcrs_substitute *)malloc(sizeof(pcrs_substitute))))
 369    {
 370       *errptr = PCRS_ERR_NOMEM;
 371       return NULL;
 372    }
 373    memset(r, '\0', sizeof(pcrs_substitute));
 374
 375    length = strlen(replacement);
 376
 377    if (NULL == (text = (char *)malloc(length + 1)))
 378    {
 379       free(r);
 380       *errptr = PCRS_ERR_NOMEM;
 381       return NULL;
 382    }
 383    memset(text, '\0', length + 1);
 384
 385
 386    /*
 387     * In trivial mode, just copy the substitute text
 388     */
 389    if (trivialflag)
 390    {
 391       text = strncpy(text, replacement, length + 1);
 392       k = (int)length;
 393    }
 394
 395    /*
 396     * Else, parse, cut out and record all backreferences
 397     */
 398    else
 399    {
 400       while (i < (int)length)
 401       {
 402          /* Quoting */
 403          if (replacement[i] == '\\')
 404          {
 405             if (quoted)
 406             {
 407                text[k++] = replacement[i++];
 408                quoted = 0;
 409             }
 410             else
 411             {
 412                if (replacement[i+1] && strchr("tnrfae0", replacement[i+1]))
 413                {
 414                   switch (replacement[++i])
 415                   {
 416                   case 't':
 417                      text[k++] = '\t';
 418                      break;
 419                   case 'n':
 420                      text[k++] = '\n';
 421                      break;
 422                   case 'r':
 423                      text[k++] = '\r';
 424                      break;
 425                   case 'f':
 426                      text[k++] = '\f';
 427                      break;
 428                   case 'a':
 429                      text[k++] = 7;
 430                      break;
 431                   case 'e':
 432                      text[k++] = 27;
 433                      break;
 434                   case '0':
 435                      text[k++] = '\0';
 436                      break;
 437                   }
 438                   i++;
 439                }
 440                else if (is_hex_sequence(&replacement[i]))
 441                {
 442                   /*
 443                    * Replace a hex sequence with a single
 444                    * character with the sequence's ascii value.
 445                    * e.g.: '\x7e' => '~'
 446                    */
 447                   const int ascii_value = xtoi(&replacement[i+2]);
 448
 449                   assert(ascii_value > 0);
 450                   assert(ascii_value < 256);
 451                   text[k++] = (char)ascii_value;
 452                   i += 4;
 453                }
 454                else
 455                {
 456                   quoted = 1;
 457                   i++;
 458                }
 459             }
 460             continue;
 461          }
 462
 463          /* Backreferences */
 464          if (replacement[i] == '$' && !quoted && i < (int)(length - 1))
 465          {
 466             char *symbol, symbols[] = "'`+&";
 467             r->block_length[l] = (size_t)(k - r->block_offset[l]);
 468
 469             /* Numerical backreferences */
 470             if (isdigit((int)replacement[i + 1]))
 471             {
 472                while (i < (int)length && isdigit((int)replacement[++i]))
 473                {
 474                   r->backref[l] = r->backref[l] * 10 + replacement[i] - 48;
 475                }
 476                if (r->backref[l] > capturecount)
 477                {
 478                   *errptr = PCRS_WARN_BADREF;
 479                }
 480             }
 481
 482             /* Symbolic backreferences: */
 483             else if (NULL != (symbol = strchr(symbols, replacement[i + 1])))
 484             {
 485
 486                if (symbol - symbols == 2) /* $+ */
 487                {
 488                   r->backref[l] = capturecount;
 489                }
 490                else if (symbol - symbols == 3) /* $& */
 491                {
 492                   r->backref[l] = 0;
 493                }
 494                else /* $' or $` */
 495                {
 496                   r->backref[l] = PCRS_MAX_SUBMATCHES + 1 - (symbol - symbols);
 497                }
 498                i += 2;
 499             }
 500
 501             /* Invalid backref -> plain '$' */
 502             else
 503             {
 504                goto plainchar;
 505             }
 506
 507             /* Valid and in range? -> record */
 508             if (r->backref[l] < PCRS_MAX_SUBMATCHES + 2)
 509             {
 510                r->backref_count[r->backref[l]] += 1;
 511                r->block_offset[++l] = k;
 512             }
 513             else
 514             {
 515                *errptr = PCRS_WARN_BADREF;
 516             }
 517             continue;
 518          }
 519
 520 plainchar:
 521          /* Plain chars are copied */
 522          text[k++] = replacement[i++];
 523          quoted = 0;
 524       }
 525    } /* -END- if (!trivialflag) */
 526
 527    /*
 528     * Finish & return
 529     */
 530    r->text = text;
 531    r->backrefs = l;
 532    r->length = (size_t)k;
 533    r->block_length[l] = (size_t)(k - r->block_offset[l]);
 534
 535    return r;
 536
 537 }
 538
 539
 540 /*********************************************************************
 541  *
 542  * Function    :  pcrs_free_job
 543  *
 544  * Description :  Frees the memory used by a pcrs_job struct and its
 545  *                dependant structures.
 546  *
 547  * Parameters  :
 548  *          1  :  job = pointer to the pcrs_job structure to be freed
 549  *
 550  * Returns     :  a pointer to the next job, if there was any, or
 551  *                NULL otherwise.
 552  *
 553  *********************************************************************/
 554 pcrs_job *pcrs_free_job(pcrs_job *job)
 555 {
 556    pcrs_job *next;
 557
 558    if (job == NULL)
 559    {
 560       return NULL;
 561    }
 562    else
 563    {
 564       next = job->next;
 565       if (job->pattern != NULL) free(job->pattern);
 566       if (job->hints != NULL) free(job->hints);
 567       if (job->substitute != NULL)
 568       {
 569          if (job->substitute->text != NULL) free(job->substitute->text);
 570          free(job->substitute);
 571       }
 572       free(job);
 573    }
 574    return next;
 575
 576 }
 577
 578
 579 /*********************************************************************
 580  *
 581  * Function    :  pcrs_free_joblist
 582  *
 583  * Description :  Iterates through a chained list of pcrs_job's and
 584  *                frees them using pcrs_free_job.
 585  *
 586  * Parameters  :
 587  *          1  :  joblist = pointer to the first pcrs_job structure to
 588  *                be freed
 589  *
 590  * Returns     :  N/A
 591  *
 592  *********************************************************************/
 593 void pcrs_free_joblist(pcrs_job *joblist)
 594 {
 595    while ( NULL != (joblist = pcrs_free_job(joblist)) ) {};
 596
 597    return;
 598
 599 }
 600
 601
 602 /*********************************************************************
 603  *
 604  * Function    :  pcrs_compile_command
 605  *
 606  * Description :  Parses a string with a Perl-style s/// command,
 607  *                calls pcrs_compile, and returns a corresponding
 608  *                pcrs_job, or NULL if parsing or compiling the job
 609  *                fails.
 610  *
 611  * Parameters  :
 612  *          1  :  command = string with perl-style s/// command
 613  *          2  :  errptr = pointer to an integer in which error
 614  *                         conditions can be returned.
 615  *
 616  * Returns     :  a corresponding pcrs_job data structure, or NULL
 617  *                if an error was encountered. In that case, *errptr
 618  *                has the reason.
 619  *
 620  *********************************************************************/
 621 pcrs_job *pcrs_compile_command(const char *command, int *errptr)
 622 {
 623    int i, k, l, quoted = FALSE;
 624    size_t limit;
 625    char delimiter;
 626    char *tokens[4];
 627    pcrs_job *newjob;
 628
 629    i = k = l = 0;
 630
 631    /*
 632     * Tokenize the perl command
 633     */
 634    limit = strlen(command);
 635    if (limit < 4)
 636    {
 637       *errptr = PCRS_ERR_CMDSYNTAX;
 638       return NULL;
 639    }
 640    else
 641    {
 642       delimiter = command[1];
 643    }
 644
 645    tokens[l] = (char *) malloc(limit + 1);
 646
 647    for (i = 0; i <= (int)limit; i++)
 648    {
 649
 650       if (command[i] == delimiter && !quoted)
 651       {
 652          if (l == 3)
 653          {
 654             l = -1;
 655             break;
 656          }
 657          tokens[0][k++] = '\0';
 658          tokens[++l] = tokens[0] + k;
 659          continue;
 660       }
 661
 662       else if (command[i] == '\\' && !quoted)
 663       {
 664          quoted = TRUE;
 665          if (command[i+1] == delimiter) continue;
 666       }
 667       else
 668       {
 669          quoted = FALSE;
 670       }
 671       tokens[0][k++] = command[i];
 672    }
 673
 674    /*
 675     * Syntax error ?
 676     */
 677    if (l != 3)
 678    {
 679       *errptr = PCRS_ERR_CMDSYNTAX;
 680       free(tokens[0]);
 681       return NULL;
 682    }
 683
 684    newjob = pcrs_compile(tokens[1], tokens[2], tokens[3], errptr);
 685    free(tokens[0]);
 686    return newjob;
 687
 688 }
 689
 690
 691 /*********************************************************************
 692  *
 693  * Function    :  pcrs_compile
 694  *
 695  * Description :  Takes the three arguments to a perl s/// command
 696  *                and compiles a pcrs_job structure from them.
 697  *
 698  * Parameters  :
 699  *          1  :  pattern = string with perl-style pattern
 700  *          2  :  substitute = string with perl-style substitute
 701  *          3  :  options = string with perl-style options
 702  *          4  :  errptr = pointer to an integer in which error
 703  *                         conditions can be returned.
 704  *
 705  * Returns     :  a corresponding pcrs_job data structure, or NULL
 706  *                if an error was encountered. In that case, *errptr
 707  *                has the reason.
 708  *
 709  *********************************************************************/
 710 pcrs_job *pcrs_compile(const char *pattern, const char *substitute, const char *options, int *errptr)
 711 {
 712    pcrs_job *newjob;
 713    int flags;
 714    int capturecount;
 715    const char *error;
 716
 717    *errptr = 0;
 718
 719    /*
 720     * Handle NULL arguments
 721     */
 722    if (pattern == NULL) pattern = "";
 723    if (substitute == NULL) substitute = "";
 724
 725
 726    /*
 727     * Get and init memory
 728     */
 729    if (NULL == (newjob = (pcrs_job *)malloc(sizeof(pcrs_job))))
 730    {
 731       *errptr = PCRS_ERR_NOMEM;
 732       return NULL;
 733    }
 734    memset(newjob, '\0', sizeof(pcrs_job));
 735
 736
 737    /*
 738     * Evaluate the options
 739     */
 740    newjob->options = pcrs_parse_perl_options(options, &flags);
 741    newjob->flags = flags;
 742
 743
 744    /*
 745     * Compile the pattern
 746     */
 747    newjob->pattern = pcre_compile(pattern, newjob->options, &error, errptr, NULL);
 748    if (newjob->pattern == NULL)
 749    {
 750       pcrs_free_job(newjob);
 751       return NULL;
 752    }
 753
 754
 755    /*
 756     * Generate hints. This has little overhead, since the
 757     * hints will be NULL for a boring pattern anyway.
 758     */
 759    newjob->hints = pcre_study(newjob->pattern, 0, &error);
 760    if (error != NULL)
 761    {
 762       *errptr = PCRS_ERR_STUDY;
 763       pcrs_free_job(newjob);
 764       return NULL;
 765    }
 766
 767
 768    /*
 769     * Determine the number of capturing subpatterns.
 770     * This is needed for handling $+ in the substitute.
 771     */
 772    if (0 > (*errptr = pcre_fullinfo(newjob->pattern, newjob->hints, PCRE_INFO_CAPTURECOUNT, &capturecount)))
 773    {
 774       pcrs_free_job(newjob);
 775       return NULL;
 776    }
 777
 778
 779    /*
 780     * Compile the substitute
 781     */
 782    if (NULL == (newjob->substitute = pcrs_compile_replacement(substitute, newjob->flags & PCRS_TRIVIAL, capturecount, errptr)))
 783    {
 784       pcrs_free_job(newjob);
 785       return NULL;
 786    }
 787
 788    return newjob;
 789
 790 }
 791
 792
 793 /*********************************************************************
 794  *
 795  * Function    :  pcrs_execute_list
 796  *
 797  * Description :  This is a multiple job wrapper for pcrs_execute().
 798  *                Apply the regular substitutions defined by the jobs in
 799  *                the joblist to the subject.
 800  *                The subject itself is left untouched, memory for the result
 801  *                is malloc()ed and it is the caller's responsibility to free
 802  *                the result when it's no longer needed.
 803  *
 804  *                Note: For convenient string handling, a null byte is
 805  *                      appended to the result. It does not count towards the
 806  *                      result_length, though.
 807  *
 808  *
 809  * Parameters  :
 810  *          1  :  joblist = the chained list of pcrs_jobs to be executed
 811  *          2  :  subject = the subject string
 812  *          3  :  subject_length = the subject's length
 813  *          4  :  result = char** for returning  the result
 814  *          5  :  result_length = size_t* for returning the result's length
 815  *
 816  * Returns     :  On success, the number of substitutions that were made.
 817  *                 May be > 1 if job->flags contained PCRS_GLOBAL
 818  *                On failure, the (negative) pcre error code describing the
 819  *                 failure, which may be translated to text using pcrs_strerror().
 820  *
 821  *********************************************************************/
 822 int pcrs_execute_list(pcrs_job *joblist, char *subject, size_t subject_length, char **result, size_t *result_length)
 823 {
 824    pcrs_job *job;
 825    char *old, *new = NULL;
 826    int hits, total_hits;
 827
 828    old = subject;
 829    *result_length = subject_length;
 830    hits = total_hits = 0;
 831
 832    for (job = joblist; job != NULL; job = job->next)
 833    {
 834       hits = pcrs_execute(job, old, *result_length, &new, result_length);
 835
 836       if (old != subject) free(old);
 837
 838       if (hits < 0)
 839       {
 840          return(hits);
 841       }
 842       else
 843       {
 844          total_hits += hits;
 845          old = new;
 846       }
 847    }
 848
 849    *result = new;
 850    return(total_hits);
 851
 852 }
 853
 854
 855 /*********************************************************************
 856  *
 857  * Function    :  pcrs_execute
 858  *
 859  * Description :  Apply the regular substitution defined by the job to the
 860  *                subject.
 861  *                The subject itself is left untouched, memory for the result
 862  *                is malloc()ed and it is the caller's responsibility to free
 863  *                the result when it's no longer needed.
 864  *
 865  *                Note: For convenient string handling, a null byte is
 866  *                      appended to the result. It does not count towards the
 867  *                      result_length, though.
 868  *
 869  * Parameters  :
 870  *          1  :  job = the pcrs_job to be executed
 871  *          2  :  subject = the subject (== original) string
 872  *          3  :  subject_length = the subject's length
 873  *          4  :  result = char** for returning  the result
 874  *          5  :  result_length = size_t* for returning the result's length
 875  *
 876  * Returns     :  On success, the number of substitutions that were made.
 877  *                 May be > 1 if job->flags contained PCRS_GLOBAL
 878  *                On failure, the (negative) pcre error code describing the
 879  *                 failure, which may be translated to text using pcrs_strerror().
 880  *
 881  *********************************************************************/
 882 int pcrs_execute(pcrs_job *job, const char *subject, size_t subject_length, char **result, size_t *result_length)
 883 {
 884    int offsets[3 * PCRS_MAX_SUBMATCHES],
 885        offset,
 886        i, k,
 887        matches_found,
 888        submatches,
 889        max_matches = PCRS_MAX_MATCH_INIT;
 890    size_t newsize;
 891    pcrs_match *matches, *dummy;
 892    char *result_offset;
 893
 894    offset = i = k = 0;
 895
 896    /*
 897     * Sanity check & memory allocation
 898     */
 899    if (job == NULL || job->pattern == NULL || job->substitute == NULL || NULL == subject)
 900    {
 901       *result = NULL;
 902       return(PCRS_ERR_BADJOB);
 903    }
 904
 905    if (NULL == (matches = (pcrs_match *)malloc((size_t)max_matches * sizeof(pcrs_match))))
 906    {
 907       *result = NULL;
 908       return(PCRS_ERR_NOMEM);
 909    }
 910    memset(matches, '\0', (size_t)max_matches * sizeof(pcrs_match));
 911
 912
 913    /*
 914     * Find the pattern and calculate the space
 915     * requirements for the result
 916     */
 917    newsize = subject_length;
 918
 919    while ((submatches = pcre_exec(job->pattern, job->hints, subject, (int)subject_length, offset, 0, offsets, 3 * PCRS_MAX_SUBMATCHES)) > 0)
 920    {
 921       job->flags |= PCRS_SUCCESS;
 922       matches[i].submatches = submatches;
 923
 924       for (k = 0; k < submatches; k++)
 925       {
 926          matches[i].submatch_offset[k] = offsets[2 * k];
 927
 928          /* Note: Non-found optional submatches have length -1-(-1)==0 */
 929          matches[i].submatch_length[k] = (size_t)(offsets[2 * k + 1] - offsets[2 * k]);
 930
 931          /* reserve mem for each submatch as often as it is ref'd */
 932          newsize += matches[i].submatch_length[k] * (size_t)job->substitute->backref_count[k];
 933       }
 934       /* plus replacement text size minus match text size */
 935       newsize += job->substitute->length - matches[i].submatch_length[0];
 936
 937       /* chunk before match */
 938       matches[i].submatch_offset[PCRS_MAX_SUBMATCHES] = 0;
 939       matches[i].submatch_length[PCRS_MAX_SUBMATCHES] = (size_t)offsets[0];
 940       newsize += (size_t)offsets[0] * (size_t)job->substitute->backref_count[PCRS_MAX_SUBMATCHES];
 941
 942       /* chunk after match */
 943       matches[i].submatch_offset[PCRS_MAX_SUBMATCHES + 1] = offsets[1];
 944       matches[i].submatch_length[PCRS_MAX_SUBMATCHES + 1] = subject_length - (size_t)offsets[1] - 1;
 945       newsize += (subject_length - (size_t)offsets[1]) * (size_t)job->substitute->backref_count[PCRS_MAX_SUBMATCHES + 1];
 946
 947       /* Storage for matches exhausted? -> Extend! */
 948       if (++i >= max_matches)
 949       {
 950          max_matches = (int)(max_matches * PCRS_MAX_MATCH_GROW);
 951          if (NULL == (dummy = (pcrs_match *)realloc(matches, (size_t)max_matches * sizeof(pcrs_match))))
 952          {
 953             free(matches);
 954             *result = NULL;
 955             return(PCRS_ERR_NOMEM);
 956          }
 957          matches = dummy;
 958       }
 959
 960       /* Non-global search or limit reached? */
 961       if (!(job->flags & PCRS_GLOBAL)) break;
 962
 963       /* Don't loop on empty matches */
 964       if (offsets[1] == offset)
 965          if ((size_t)offset < subject_length)
 966             offset++;
 967          else
 968             break;
 969       /* Go find the next one */
 970       else
 971          offset = offsets[1];
 972    }
 973    /* Pass pcre error through if (bad) failiure */
 974    if (submatches < PCRE_ERROR_NOMATCH)
 975    {
 976       free(matches);
 977       return submatches;
 978    }
 979    matches_found = i;
 980
 981
 982    /*
 983     * Get memory for the result (must be freed by caller!)
 984     * and append terminating null byte.
 985     */
 986    if ((*result = (char *)malloc(newsize + 1)) == NULL)
 987    {
 988       free(matches);
 989       return PCRS_ERR_NOMEM;
 990    }
 991    else
 992    {
 993       (*result)[newsize] = '\0';
 994    }
 995
 996
 997    /*
 998     * Replace
 999     */
1000    offset = 0;
1001    result_offset = *result;
1002
1003    for (i = 0; i < matches_found; i++)
1004    {
1005       /* copy the chunk preceding the match */
1006       memcpy(result_offset, subject + offset, (size_t)(matches[i].submatch_offset[0] - offset));
1007       result_offset += matches[i].submatch_offset[0] - offset;
1008
1009       /* For every segment of the substitute.. */
1010       for (k = 0; k <= job->substitute->backrefs; k++)
1011       {
1012          /* ...copy its text.. */
1013          memcpy(result_offset, job->substitute->text + job->substitute->block_offset[k], job->substitute->block_length[k]);
1014          result_offset += job->substitute->block_length[k];
1015
1016          /* ..plus, if it's not the last chunk, i.e.: There *is* a backref.. */
1017          if (k != job->substitute->backrefs
1018              /* ..in legal range.. */
1019              && job->substitute->backref[k] < PCRS_MAX_SUBMATCHES + 2
1020              /* ..and referencing a real submatch.. */
1021              && job->substitute->backref[k] < matches[i].submatches
1022              /* ..that is nonempty.. */
1023              && matches[i].submatch_length[job->substitute->backref[k]] > 0)
1024          {
1025             /* ..copy the submatch that is ref'd. */
1026             memcpy(
1027                result_offset,
1028                subject + matches[i].submatch_offset[job->substitute->backref[k]],
1029                matches[i].submatch_length[job->substitute->backref[k]]
1030             );
1031             result_offset += matches[i].submatch_length[job->substitute->backref[k]];
1032          }
1033       }
1034       offset =  matches[i].submatch_offset[0] + (int)matches[i].submatch_length[0];
1035    }
1036
1037    /* Copy the rest. */
1038    memcpy(result_offset, subject + offset, subject_length - (size_t)offset);
1039
1040    *result_length = newsize;
1041    free(matches);
1042    return matches_found;
1043
1044 }
1045
1046
1047 #define is_hex_digit(x) ((x) && strchr("0123456789ABCDEF", toupper(x)))
1048
1049 /*********************************************************************
1050  *
1051  * Function    :  is_hex_sequence
1052  *
1053  * Description :  Checks the first four characters of a string
1054  *                and decides if they are a valid hex sequence
1055  *                (like '\x40').
1056  *
1057  * Parameters  :
1058  *          1  :  sequence = The string to check
1059  *
1060  * Returns     :  Non-zero if it's valid sequence, or
1061  *                Zero if it isn't.
1062  *
1063  *********************************************************************/
1064 static int is_hex_sequence(const char *sequence)
1065 {
1066    return (sequence[0] == '\\' &&
1067            sequence[1] == 'x'  &&
1068            is_hex_digit(sequence[2]) &&
1069            is_hex_digit(sequence[3]));
1070 }
1071
1072
1073 /*
1074  * Functions below this line are only part of the pcrs version
1075  * included in Privoxy. If you use any of them you should not
1076  * try to dynamically link against external pcrs versions.
1077  */
1078
1079 /*********************************************************************
1080  *
1081  * Function    :  pcrs_job_is_dynamic
1082  *
1083  * Description :  Checks if a job has the "D" (dynamic) option set.
1084  *
1085  * Parameters  :
1086  *          1  :  job = The job to check
1087  *
1088  * Returns     :  TRUE if the job is indeed dynamic, otherwise
1089  *                FALSE
1090  *
1091  *********************************************************************/
1092 int pcrs_job_is_dynamic (char *job)
1093 {
1094    const char delimiter = job[1];
1095    const size_t length = strlen(job);
1096    char *option;
1097
1098    if (length < 5)
1099    {
1100       /*
1101        * The shortest valid (but useless)
1102        * dynamic pattern is "s@@@D"
1103        */
1104       return FALSE;
1105    }
1106
1107    /*
1108     * Everything between the last character
1109     * and the last delimiter is an option ...
1110     */
1111    for (option = job + length; *option != delimiter; option--)
1112    {
1113       if (*option == 'D')
1114       {
1115          /*
1116           * ... and if said option is 'D' the job is dynamic.
1117           */
1118          return TRUE;
1119       }
1120    }
1121    return FALSE;
1122
1123 }
1124
1125
1126 /*********************************************************************
1127  *
1128  * Function    :  pcrs_get_delimiter
1129  *
1130  * Description :  Tries to find a character that is safe to
1131  *                be used as a pcrs delimiter for a certain string.
1132  *
1133  * Parameters  :
1134  *          1  :  string = The string to search in
1135  *
1136  * Returns     :  A safe delimiter if one was found, otherwise '\0'.
1137  *
1138  *********************************************************************/
1139 char pcrs_get_delimiter(const char *string)
1140 {
1141    /*
1142     * Some characters that are unlikely to
1143     * be part of pcrs replacement strings.
1144     */
1145    char delimiters[] = "><§#+*~%^°-:;µ!@";
1146    char *d = delimiters;
1147
1148    /* Take the first delimiter that isn't part of the string */
1149    while (*d && NULL != strchr(string, *d))
1150    {
1151       d++;
1152    }
1153    return *d;
1154
1155 }
1156
1157
1158 /*********************************************************************
1159  *
1160  * Function    :  pcrs_execute_single_command
1161  *
1162  * Description :  Apply single pcrs command to the subject.
1163  *                The subject itself is left untouched, memory for the result
1164  *                is malloc()ed and it is the caller's responsibility to free
1165  *                the result when it's no longer needed.
1166  *
1167  * Parameters  :
1168  *          1  :  subject = the subject (== original) string
1169  *          2  :  pcrs_command = the pcrs command as string (s@foo@bar@)
1170  *          3  :  hits = int* for returning  the number of modifications
1171  *
1172  * Returns     :  NULL in case of errors, otherwise the
1173  *                result of the pcrs command.
1174  *
1175  *********************************************************************/
1176 char *pcrs_execute_single_command(const char *subject, const char *pcrs_command, int *hits)
1177 {
1178    size_t size;
1179    char *result = NULL;
1180    pcrs_job *job;
1181
1182    assert(subject);
1183    assert(pcrs_command);
1184
1185    *hits = 0;
1186    size = strlen(subject);
1187
1188    job = pcrs_compile_command(pcrs_command, hits);
1189    if (NULL != job)
1190    {
1191       *hits = pcrs_execute(job, subject, size, &result, &size);
1192       if (*hits < 0)
1193       {
1194          freez(result);
1195       }
1196       pcrs_free_job(job);
1197    }
1198    return result;
1199
1200 }
1201
1202
1203 static const char warning[] = "... [too long, truncated]";
1204 /*********************************************************************
1205  *
1206  * Function    :  pcrs_compile_dynamic_command
1207  *
1208  * Description :  Takes a dynamic pcrs command, fills in the
1209  *                values of the variables and compiles it.
1210  *
1211  * Parameters  :
1212  *          1  :  csp = Current client state (buffers, headers, etc...)
1213  *          2  :  pcrs_command = The dynamic pcrs command to compile
1214  *          3  :  v = NULL terminated array of variables and their values.
1215  *          4  :  error = pcrs error code
1216  *
1217  * Returns     :  NULL in case of hard errors, otherwise the
1218  *                compiled pcrs job.
1219  *
1220  *********************************************************************/
1221 pcrs_job *pcrs_compile_dynamic_command(char *pcrs_command, const struct pcrs_variable v[], int *error)
1222 {
1223    char buf[PCRS_BUFFER_SIZE];
1224    const char *original_pcrs_command = pcrs_command;
1225    char *pcrs_command_tmp = NULL;
1226    pcrs_job *job = NULL;
1227    int truncation = 0;
1228    char d;
1229    int ret;
1230
1231    while ((NULL != v->name) && (NULL != pcrs_command))
1232    {
1233       assert(NULL != v->value);
1234
1235       if (NULL == strstr(pcrs_command, v->name))
1236       {
1237          /*
1238           * Skip the substitution if the variable
1239           * name isn't part of the pattern.
1240           */
1241          v++;
1242          continue;
1243       }
1244
1245       /* Use pcrs to replace the variable with its value. */
1246       d = pcrs_get_delimiter(v->value);
1247       if ('\0' == d)
1248       {
1249          /* No proper delimiter found */
1250          *error = PCRS_ERR_CMDSYNTAX;
1251          return NULL;
1252       }
1253
1254       /*
1255        * Variable names are supposed to contain alpha
1256        * numerical characters plus '_' only.
1257        */
1258       assert(NULL == strchr(v->name, d));
1259
1260       ret = snprintf(buf, sizeof(buf), "s%c\\$%s%c%s%cgT", d, v->name, d, v->value, d);
1261       assert(ret >= 0);
1262       if (ret >= sizeof(buf))
1263       {
1264          /*
1265           * Value didn't completely fit into buffer,
1266           * overwrite the end of the substitution text
1267           * with a truncation message and close the pattern
1268           * properly.
1269           */
1270          const size_t trailer_size = sizeof(warning) + 3; /* 3 for d + "gT" */
1271          char *trailer_start = buf + sizeof(buf) - trailer_size;
1272
1273          ret = snprintf(trailer_start, trailer_size, "%s%cgT", warning, d);
1274          assert(ret == trailer_size - 1);
1275          assert(sizeof(buf) == strlen(buf) + 1);
1276          truncation = 1;
1277       }
1278
1279       pcrs_command_tmp = pcrs_execute_single_command(pcrs_command, buf, error);
1280       if (NULL == pcrs_command_tmp)
1281       {
1282          return NULL;
1283       }
1284
1285       if (pcrs_command != original_pcrs_command)
1286       {
1287          freez(pcrs_command);
1288       }
1289       pcrs_command = pcrs_command_tmp;
1290
1291       v++;
1292    }
1293
1294    job = pcrs_compile_command(pcrs_command, error);
1295    if (pcrs_command != original_pcrs_command)
1296    {
1297       freez(pcrs_command);
1298    }
1299
1300    if (truncation)
1301    {
1302       *error = PCRS_WARN_TRUNCATION;
1303    }
1304
1305    return job;
1306
1307 }
1308
1309
1310 /*
1311   Local Variables:
1312   tab-width: 3
1313   end:
1314 */