Making parameters "const" where possible.
[privoxy.git] / 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 */