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