- Enabled filtering banners by size rather than URL
[privoxy.git] / pcrs.c
1 const char pcrs_rcs[] = "$Id: pcrs.c,v 1.1.1.1 2001/05/15 13:59:02 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.1.1.1  2001/05/15 13:59:02  oes
47  *    Initial import of version 2.9.3 source tree
48  *
49  *
50  *********************************************************************/
51 \f
52
53 #include <pcre.h>
54 #include <string.h>
55 #include "pcrs.h"
56 const char pcrs_h_rcs[] = PCRS_H_VERSION;
57
58
59 /*********************************************************************
60  *
61  * Function    :  my_strsep
62  *
63  * Description :  Convenience function. It acts like strsep, except that
64  *                it respects quoting of the delimiter character with the
65  *                quote character. (And, of course, quoting the quote char
66  *                with itself.)  Called from `pcrs_make_job'.
67  *
68  * Parameters  :
69  *          1  :  token = current token
70  *          2  :  text = string to tokenize
71  *          3  :  delimiter = single character deliminter
72  *          4  :  quote_char = character to cause quoting
73  *
74  * Returns     :  -1 => failure, else the length of the token found.
75  *                In the latter case, *text is the token's start.
76  *
77  *********************************************************************/
78 int my_strsep(char *token, char **text, char delimiter, char quote_char)
79 {
80    int i, k=0, limit, quoted = FALSE;
81
82    limit = strlen(*text);
83    if ( 0 == limit )
84    {
85       return -1;
86    }
87
88    token[0] = '\0';
89
90    for (i=0; i < limit; i++)
91    {
92       if (text[0][i] == delimiter && !quoted)
93       {
94          *text += 1;
95          break;
96       }
97       else if (text[0][i] == quote_char && !quoted && i+1 < limit && text[0][i+1] == delimiter)
98       {
99          quoted = TRUE;
100          continue;
101       }
102       token[k++] = text[0][i];
103       quoted = FALSE;
104    }
105    token[k] = '\0';
106    *text += i;
107    return k;
108
109 }
110
111
112 /*********************************************************************
113  *
114  * Function    :  pcrs_compile_perl_options
115  *
116  * Description :  This function parses a string containing the options to
117  *                Perl's s/// operator. It returns an integer that is the
118  *                pcre equivalent of the symbolic optstring.
119  *                Since pcre doesn't know about Perl's 'g' (global) option,
120  *                but pcrs needs it, the globalflag integer is set if 'g'
121  *                is encountered.
122  *
123  * Parameters  :
124  *          1  :  optstring = string with options in perl syntax
125  *          2  :  globalflag = see description
126  *
127  * Returns     :  option integer suitable for pcre 
128  *
129  *********************************************************************/
130 int pcrs_compile_perl_options(char *optstring, int *globalflag)
131 {
132    int i, rc = 0;
133    *globalflag = 0;
134    for (i=0; i < strlen(optstring); i++)
135    {
136       switch(optstring[i])
137       {
138          case 'e': break;
139          case 'g': *globalflag = 1; break;
140          case 'i': rc |= PCRE_CASELESS; break;
141          case 'm': rc |= PCRE_MULTILINE; break;
142          case 'o': break;
143          case 's': rc |= PCRE_DOTALL; break;
144          case 'x': rc |= PCRE_EXTENDED; break;
145          case 'U': rc |= PCRE_UNGREEDY; break;
146          default:  break;
147       }
148    }
149    return rc;
150
151 }
152
153
154 /*********************************************************************
155  *
156  * Function    :  pcrs_compile_replacement
157  *
158  * Description :  This function takes a Perl-style replacement (2nd argument
159  *                to the s/// operator and returns a compiled pcrs_substitute,
160  *                or NULL if memory allocation for the substitute structure
161  *                fails.
162  *
163  * Parameters  :
164  *          1  :  replacement = replacement part of s/// operator
165  *                              in perl syntax
166  *          2  :  errptr = pointer to an integer in which error
167  *                         conditions can be returned.
168  *
169  * Returns     :  pcrs_substitute data structure, or NULL if an
170  *                error is encountered. In that case, *errptr has
171  *                the reason.
172  *
173  *********************************************************************/
174 pcrs_substitute *pcrs_compile_replacement(char *replacement, int *errptr)
175 {
176    int length, i, k = 0, l = 0, quoted = 0, idx;
177    char *text, *num_ptr, *numbers = "0123456789";
178    pcrs_substitute *r;
179
180    r = (pcrs_substitute *)malloc(sizeof(pcrs_substitute));
181    if (r == NULL) return NULL;
182    memset(r, '\0', sizeof(pcrs_substitute));
183
184    text = strdup(replacement);      /* must be free()d by caller */
185    if (text  == NULL)
186    {
187       *errptr = PCRS_ERR_NOMEM;
188       free(r);
189       return NULL;
190    }
191
192    length = strlen(replacement);
193
194    for (i=0; i < length; i++)
195    {
196       /* Backslash treatment */
197       if (replacement[i] == '\\')
198       {
199          if (quoted)
200          {
201             text[k++] = replacement[i];
202             quoted = 0;
203          }
204          else
205          {
206             quoted = 1;
207          }
208          continue;
209       }
210
211       /* Dollar treatment */
212       if (replacement[i] == '$' && !quoted && i < length - 1)
213       {
214          if (strchr("0123456789&", replacement[i + 1]) == NULL)
215          {
216             text[k++] = replacement[i];
217          }
218          else
219          {
220             r->block_length[l] = k - r->block_offset[l];
221             r->backref[l] = 0;
222             if (replacement[i + 1] != '&')
223             {
224                while ((num_ptr = strchr(numbers, replacement[++i])) != NULL && i < length)
225                {
226                   idx = num_ptr - numbers;
227                   r->backref[l] = r->backref[l] * 10 + idx;
228                }
229                i--;
230             }
231             else
232                i++;
233             if (r->backref[l] < PCRS_MAX_SUBMATCHES)
234                r->backref_count[r->backref[l]] += 1;
235             l++;
236             r->block_offset[l] = k;
237          }
238          continue;
239       }
240
241       /* Plain char treatment */
242       text[k++] = replacement[i];
243       quoted = 0;
244    }
245
246    text[k] = '\0';
247    r->text = text;
248    r->backrefs = l;
249    r->block_length[l] = k - r->block_offset[l];
250    return r;
251
252 }
253
254
255 /*********************************************************************
256  *
257  * Function    :  pcrs_free_job
258  *
259  * Description :  Frees the memory used by a pcrs_job struct and its
260  *                dependant structures. Returns a pointer to the next
261  *                job, if there was any, or NULL otherwise.
262  *
263  * Parameters  :
264  *          1  :  job = pointer to the pcrs_job structure to be freed
265  *
266  * Returns     : a pointer to the next job, if there was any, or
267  *               NULL otherwise. 
268  *
269  *********************************************************************/
270 pcrs_job *pcrs_free_job(pcrs_job *job)
271 {
272    pcrs_job *next;
273
274    if (job == NULL)
275    {
276       return NULL;
277    }
278    else
279    {
280       next = job->next;
281       if (job->pattern != NULL) free(job->pattern);
282       if (job->hints != NULL) free(job->hints);
283       if (job->substitute != NULL)
284       {
285          if (job->substitute->text != NULL) free(job->substitute->text);
286          free(job->substitute);
287       }
288       free(job);
289    }
290    return next;
291
292 }
293
294
295 /*********************************************************************
296  *
297  * Function    :  pcrs_make_job
298  *
299  * Description :  Main entry point. Takes a string with a Perl-style
300  *                s/// command and returns a corresponding pcrs_job,
301  *                or NULL if compiling the job fails at any stage.
302  *                Diagnostics could obviously be improved.
303  *
304  * Parameters  :
305  *          1  :  command = string with perl-style s/// command
306  *          2  :  errptr = pointer to an integer in which error
307  *                         conditions can be returned.
308  *
309  * Returns     :  a corresponding pcrs_job data structure, or NULL
310  *                if an error was encountered. In that case, *errptr
311  *                has the reason.
312  *
313  *********************************************************************/
314 pcrs_job *pcrs_make_job(char *command, int *errptr)
315 {
316    char *dummy, *token, delimiter;
317    const char *error;
318    int i = 0, globalflag;
319    pcrs_job *newjob;
320
321    /* Get and init memory */
322    if ((newjob = (pcrs_job *)malloc(sizeof(pcrs_job))) == NULL)
323    {
324       *errptr = PCRS_ERR_NOMEM;
325       return NULL;
326    }
327    memset(newjob, '\0', sizeof(pcrs_job));
328
329    /* Command too short? */
330    if (strlen(command) < 4)
331    {
332       *errptr = PCRS_ERR_CMDSYNTAX;
333       pcrs_free_job(newjob);
334       return NULL;
335    }
336
337    /* Split command into tokens and handle them */
338    delimiter = command[1];
339    token = (char *)malloc(strlen(command)); /* current token */
340    dummy = (char *)malloc(strlen(command)); /* must store pattern, since we can't */
341                                             /* use it until the options are known */
342    while (my_strsep(token, &command, delimiter, '\\') >= 0)
343    {
344       switch (i)
345       {
346   /* We don't care about the command and assume 's' */
347          case 0:
348             break;
349
350          /* The pattern */
351          case 1:
352             strcpy(dummy, token);
353             break;
354
355          /* The substitute */
356          case 2:
357             newjob->substitute = pcrs_compile_replacement(token, errptr);
358             if (newjob->substitute == NULL)
359             {
360                pcrs_free_job(newjob);
361                return NULL;
362             }
363             break;
364
365          /* The options */
366          case 3:
367             newjob->options = pcrs_compile_perl_options(token, &globalflag);
368             newjob->globalflag = globalflag;
369             break;
370
371          /* There shouldn't be anything else! */
372          default:
373             *errptr = PCRS_ERR_CMDSYNTAX;
374             pcrs_free_job(newjob);
375             return NULL;
376       }
377       i++;
378    }
379    free(token);
380
381    /* Compile the pattern */
382    newjob->pattern = pcre_compile(dummy, newjob->options, &error, errptr, NULL);
383    if (newjob->pattern == NULL)
384    {
385       pcrs_free_job(newjob);
386       return NULL;
387    }
388    free(dummy);
389
390    /*
391     * Generate hints. This has little overhead, since the
392     * hints will be NULL for a boring pattern anyway.
393     */
394    newjob->hints = pcre_study(newjob->pattern, 0, &error);
395    if (error != NULL)
396    {
397       *errptr = PCRS_ERR_STUDY;
398       pcrs_free_job(newjob);
399       return NULL;
400    }
401
402    return newjob;
403
404 }
405
406
407 /*********************************************************************
408  *
409  * Function    :  create_pcrs_job
410  *
411  * Description :  Create a job from all its components, if you don't
412  *                have a Perl command to start from. Rather boring.
413  *
414  * Parameters  :
415  *          1  :  pattern = pointer to pcre pattern
416  *          2  :  hints = pointer to pcre hints
417  *          3  :  options = options in pcre format
418  *          4  :  globalflag = flag that indicates if global matching is desired
419  *          5  :  substitute = pointer to pcrs_substitute data structure
420  *          2  :  errptr = pointer to an integer in which error
421  *                         conditions can be returned.
422  *
423  * Returns     :  pcrs_job structure, or NULL if an error was encountered.
424  *                In that case, *errptr has the reason why.
425  *
426  *********************************************************************/
427 pcrs_job *create_pcrs_job(pcre *pattern, pcre_extra *hints, int options, int globalflag, pcrs_substitute *substitute, int *errptr)
428 {
429    pcrs_job *newjob;
430
431    if ((newjob = (pcrs_job *)malloc(sizeof(pcrs_job))) == NULL)
432    {
433       *errptr = PCRS_ERR_NOMEM;
434       return NULL;
435    }
436    memset(newjob, '\0', sizeof(pcrs_job));
437
438    newjob->pattern = pattern;
439    newjob->hints = hints;
440    newjob->options = options;
441    newjob->globalflag = globalflag;
442    newjob->substitute = substitute;
443
444    return(newjob);
445
446 }
447
448
449 /*********************************************************************
450  *
451  * Function    :  pcrs_exec_substitution
452  *
453  * Description :  Modify the subject by executing the regular substitution
454  *                defined by the job. Since the result may be longer than
455  *                the subject, its space requirements are precalculated in
456  *                the matching phase and new memory is allocated accordingly.
457  *                It is the caller's responsibility to free the result when
458  *                it's no longer needed.
459  *
460  * Parameters  :
461  *          1  :  job = the pcrs_job to be executed
462  *          2  :  subject = the subject (== original) string
463  *          3  :  subject_length = the subject's length
464  *          4  :  result = char** for returning  the result 
465  *          5  :  result_length = int* for returning the result's length
466  *
467  * Returns     :  the number of substitutions that were made. May be > 1
468  *                if job->globalflag was set
469  *
470  *********************************************************************/
471 int pcrs_exec_substitution(pcrs_job *job, char *subject, int subject_length, char **result, int *result_length)
472 {
473    int offsets[3 * PCRS_MAX_SUBMATCHES],
474       offset = 0, i=0, k, matches_found, newsize, submatches;
475    pcrs_match matches[PCRS_MAX_MATCHES];
476    char *result_offset;
477
478    newsize=subject_length;
479
480    /* Find.. */
481    while ((submatches = pcre_exec(job->pattern, job->hints, subject, subject_length, offset, 0, offsets, 99)) > 0)
482    {
483       matches[i].submatches = submatches;
484       for (k=0; k < submatches; k++)
485       {
486          matches[i].submatch_offset[k] = offsets[2 * k];
487          matches[i].submatch_length[k] = offsets[2 * k + 1] - offsets[2 * k]; /* Non-found optional submatches have length -1-(-1)==0 */
488          newsize += matches[i].submatch_length[k] * job->substitute->backref_count[k]; /* reserve mem for each submatch as often as it is ref'd */
489       }
490       newsize += strlen(job->substitute->text) - matches[i].submatch_length[0]; /* plus replacement text size minus match text size */
491
492       /* Non-global search or limit reached? */
493       if (++i >= PCRS_MAX_MATCHES || !job->globalflag ) break;
494
495       /* Don't loop on empty matches */
496       if (offsets[1] == offset)
497          if (offset < subject_length)
498             offset++;
499          else
500             break;
501       /* Go find the next one */
502       else
503          offset = offsets[1];
504    }
505    if (submatches < -1) return submatches;   /* Pass pcre error through */
506    matches_found = i;
507
508    /* ..get memory ..*/
509    if ((*result = (char *)malloc(newsize)) == NULL)   /* must be free()d by caller */
510    {
511       return PCRS_ERR_NOMEM;
512    }
513
514    /* ..and replace */
515    offset = 0;
516    result_offset = *result;
517
518    for (i=0; i < matches_found; i++)
519    {
520       memcpy(result_offset, subject + offset, matches[i].submatch_offset[0] - offset); /* copy the chunk preceding the match */
521       result_offset += matches[i].submatch_offset[0] - offset;
522
523       /* For every segment of the substitute.. */
524       for (k=0; k <= job->substitute->backrefs; k++)
525       {
526          /* ...copy its text.. */
527          memcpy(result_offset, job->substitute->text + job->substitute->block_offset[k], job->substitute->block_length[k]);
528          result_offset += job->substitute->block_length[k];
529
530          /* ..plus, if it's not the last chunk (i.e.: There IS a backref).. */
531          if (k != job->substitute->backrefs
532              /* ..and a nonempty match.. */
533              && matches[i].submatch_length[job->substitute->backref[k]] > 0
534              /* ..and in legal range, ... */
535              && job->substitute->backref[k] <= PCRS_MAX_SUBMATCHES)
536          {
537             /* copy the submatch that is ref'd. */
538             memcpy(
539                result_offset,
540                subject + matches[i].submatch_offset[job->substitute->backref[k]],
541                matches[i].submatch_length[job->substitute->backref[k]]
542             );
543             result_offset += matches[i].submatch_length[job->substitute->backref[k]];
544          }
545       }
546       offset =  matches[i].submatch_offset[0] + matches[i].submatch_length[0];
547    }
548
549    /* Copy the rest. */
550    memcpy(result_offset, subject + offset, subject_length - offset);
551
552    *result_length = newsize;
553    return matches_found;
554
555 }
556
557
558 /*
559   Local Variables:
560   tab-width: 3
561   end:
562 */