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