Sync with various changes from 3.0 branch. Add two new files for config stuff.
[privoxy.git] / pcrs.c
1 const char pcrs_rcs[] = "$Id: pcrs.c,v 1.18 2002/03/08 14:17:14 oes Exp $";
2
3 /*********************************************************************
4  *
5  * File        :  $Source: /cvsroot/ijbswa/current/pcrs.c,v $
6  *
7  * Purpose     :  pcrs is a supplement to the pcre library by Philip Hazel
8  *                <ph10@cam.ac.uk> and adds Perl-style substitution. That
9  *                is, it mimics Perl's 's' operator. See pcrs(3) for details.
10  *
11  *
12  * Copyright   :  Written and Copyright (C) 2000, 2001 by Andreas S. Oesterhelt
13  *                <andreas@oesterhelt.org>
14  *
15  *                This program is free software; you can redistribute it 
16  *                and/or modify it under the terms of the GNU Lesser
17  *                General Public License (LGPL), version 2.1, which  should
18  *                be included in this distribution (see LICENSE.txt), with
19  *                the exception that the permission to replace that license
20  *                with the GNU General Public License (GPL) given in section
21  *                3 is restricted to version 2 of the GPL.
22  *
23  *                This program is distributed in the hope that it will
24  *                be useful, but WITHOUT ANY WARRANTY; without even the
25  *                implied warranty of MERCHANTABILITY or FITNESS FOR A
26  *                PARTICULAR PURPOSE.  See the license for more details.
27  *
28  *                The GNU Lesser General Public License should be included
29  *                with this file.  If not, you can view it at
30  *                http://www.gnu.org/licenses/lgpl.html
31  *                or write to the Free Software Foundation, Inc., 59
32  *                Temple Place - Suite 330, Boston, MA  02111-1307, USA.
33  *
34  * Revisions   :
35  *    $Log: pcrs.c,v $
36  *    Revision 1.18  2002/03/08 14:17:14  oes
37  *    Fixing -Wconversion warnings
38  *
39  *    Revision 1.17  2002/03/08 13:45:48  oes
40  *    Hiding internal functions
41  *
42  *    Revision 1.16  2001/11/30 21:32:14  jongfoster
43  *    Fixing signed/unsigned comparison (Andreas please check this!)
44  *    One tab->space
45  *
46  *    Revision 1.15  2001/09/20 16:11:06  steudten
47  *
48  *    Add casting for some string functions.
49  *
50  *    Revision 1.14  2001/09/09 21:41:57  oes
51  *    Fixing yet another silly bug
52  *
53  *    Revision 1.13  2001/09/06 14:05:59  oes
54  *    Fixed silly bug
55  *
56  *    Revision 1.12  2001/08/18 11:35:00  oes
57  *    - Introduced pcrs_strerror()
58  *    - made some NULL arguments non-fatal
59  *    - added support for \n \r \e \b \t \f \a \0 in substitute
60  *    - made quoting adhere to standard rules
61  *    - added warning for bad backrefs
62  *    - added pcrs_execute_list()
63  *    - fixed comments
64  *    - bugfix & cosmetics
65  *
66  *    Revision 1.11  2001/08/15 15:32:03  oes
67  *     - Added support for Perl's special variables $+, $' and $`
68  *     - Improved the substitute parser
69  *     - Replaced the hard limit for the maximum number of matches
70  *       by dynamic reallocation
71  *
72  *    Revision 1.10  2001/08/05 13:13:11  jongfoster
73  *    Making parameters "const" where possible.
74  *
75  *    Revision 1.9  2001/07/18 17:27:00  oes
76  *    Changed interface; Cosmetics
77  *
78  *    Revision 1.8  2001/06/29 21:45:41  oes
79  *    Indentation, CRLF->LF, Tab-> Space
80  *
81  *    Revision 1.7  2001/06/29 13:33:04  oes
82  *    - Cleaned up, renamed and reordered functions,
83  *      improved comments
84  *    - Removed my_strsep
85  *    - Replaced globalflag with a general flags int
86  *      that holds PCRS_GLOBAL, PCRS_SUCCESS, and PCRS_TRIVIAL
87  *    - Introduced trivial option that will prevent pcrs
88  *      from honouring backreferences in the substitute,
89  *      which is useful for large substitutes that are
90  *      red in from somewhere and saves the pain of escaping
91  *      the backrefs
92  *    - Introduced convenience function pcrs_free_joblist()
93  *    - Split pcrs_make_job() into pcrs_compile(), which still
94  *      takes a complete s/// comand as argument and parses it,
95  *      and a new function pcrs_make_job, which takes the
96  *      three separate components. This should make for a
97  *      much friendlier frontend.
98  *    - Removed create_pcrs_job() which was useless
99  *    - Fixed a bug in pcrs_execute
100  *    - Success flag is now handled by pcrs instead of user
101  *
102  *    Revision 1.6  2001/06/03 19:12:45  oes
103  *    added FIXME
104  *
105  *    Revision 1.5  2001/05/29 09:50:24  jongfoster
106  *    (Fixed one int -> size_t)
107  *
108  *    Revision 1.4  2001/05/25 14:12:40  oes
109  *    Fixed bug: Empty substitutes now detected
110  *
111  *    Revision 1.3  2001/05/25 11:03:55  oes
112  *    Added sanity check for NULL jobs to pcrs_exec_substitution
113  *
114  *    Revision 1.2  2001/05/22 18:46:04  oes
115  *
116  *      Added support for PCRE_UNGREEDY behaviour to pcrs,
117  *      which is selected by the (nonstandard and therefore
118  *      capital) letter 'U' in the option string.
119  *      It causes the quantifiers to be ungreedy by default.
120  *      Appending a ? turns back to greedy (!).
121  *
122  *    Revision 1.1.1.1  2001/05/15 13:59:02  oes
123  *    Initial import of version 2.9.3 source tree
124  *
125  *
126  *********************************************************************/
127 \f
128
129 #include <pcre.h>
130 #include <string.h>
131 #include <ctype.h>
132
133 #include "pcrs.h"
134
135 const char pcrs_h_rcs[] = PCRS_H_VERSION;
136
137 /*
138  * Internal prototypes
139  */
140
141 static int              pcrs_parse_perl_options(const char *optstring, int *flags);
142 static pcrs_substitute *pcrs_compile_replacement(const char *replacement, int trivialflag,
143                         int capturecount, int *errptr);
144
145 /*********************************************************************
146  *
147  * Function    :  pcrs_strerror
148  *
149  * Description :  Return a string describing a given error code.
150  *             
151  * Parameters  :
152  *          1  :  error = the error code
153  *
154  * Returns     :  char * to the descriptive string
155  *
156  *********************************************************************/
157 const char *pcrs_strerror(const int error)
158 {
159    if (error < 0)
160    {
161       switch (error)
162       {
163          /* Passed-through PCRE error: */
164          case PCRE_ERROR_NOMEMORY:     return "(pcre:) No memory";
165
166          /* Shouldn't happen unless PCRE or PCRS bug, or user messed with compiled job: */
167          case PCRE_ERROR_NULL:         return "(pcre:) NULL code or subject or ovector";
168          case PCRE_ERROR_BADOPTION:    return "(pcre:) Unrecognized option bit";
169          case PCRE_ERROR_BADMAGIC:     return "(pcre:) Bad magic number in code";
170          case PCRE_ERROR_UNKNOWN_NODE: return "(pcre:) Bad node in pattern";
171
172          /* Can't happen / not passed: */
173          case PCRE_ERROR_NOSUBSTRING:  return "(pcre:) Fire in power supply"; 
174          case PCRE_ERROR_NOMATCH:      return "(pcre:) Water in power supply";
175
176          /* PCRS errors: */
177          case PCRS_ERR_NOMEM:          return "(pcrs:) No memory";
178          case PCRS_ERR_CMDSYNTAX:      return "(pcrs:) Syntax error while parsing command";
179          case PCRS_ERR_STUDY:          return "(pcrs:) PCRE error while studying the pattern";
180          case PCRS_ERR_BADJOB:         return "(pcrs:) Bad job - NULL job, pattern or substitute";
181          case PCRS_WARN_BADREF:        return "(pcrs:) Backreference out of range";
182
183          /* What's that? */
184          default:  return "Unknown error";
185       }
186    }
187    /* error >= 0: No error */
188    return "(pcrs:) Everything's just fine. Thanks for asking.";
189
190 }
191
192
193 /*********************************************************************
194  *
195  * Function    :  pcrs_parse_perl_options
196  *
197  * Description :  This function parses a string containing the options to
198  *                Perl's s/// operator. It returns an integer that is the
199  *                pcre equivalent of the symbolic optstring.
200  *                Since pcre doesn't know about Perl's 'g' (global) or pcrs',
201  *                'T' (trivial) options but pcrs needs them, the corresponding
202  *                flags are set if 'g'or 'T' is encountered.
203  *                Note: The 'T' and 'U' options do not conform to Perl.
204  *             
205  * Parameters  :
206  *          1  :  optstring = string with options in perl syntax
207  *          2  :  flags = see description
208  *
209  * Returns     :  option integer suitable for pcre 
210  *
211  *********************************************************************/
212 static int pcrs_parse_perl_options(const char *optstring, int *flags)
213 {
214    size_t i;
215    int rc = 0;
216    *flags = 0;
217
218    if (NULL == optstring) return 0;
219
220    for (i = 0; i < strlen(optstring); i++)
221    {
222       switch(optstring[i])
223       {
224          case 'e': break; /* ToDo ;-) */
225          case 'g': *flags |= PCRS_GLOBAL; break;
226          case 'i': rc |= PCRE_CASELESS; break;
227          case 'm': rc |= PCRE_MULTILINE; break;
228          case 'o': break;
229          case 's': rc |= PCRE_DOTALL; break;
230          case 'x': rc |= PCRE_EXTENDED; break;
231          case 'U': rc |= PCRE_UNGREEDY; break;
232          case 'T': *flags |= PCRS_TRIVIAL; break;
233          default: break;
234       }
235    }
236    return rc;
237
238 }
239
240
241 /*********************************************************************
242  *
243  * Function    :  pcrs_compile_replacement
244  *
245  * Description :  This function takes a Perl-style replacement (2nd argument
246  *                to the s/// operator and returns a compiled pcrs_substitute,
247  *                or NULL if memory allocation for the substitute structure
248  *                fails.
249  *
250  * Parameters  :
251  *          1  :  replacement = replacement part of s/// operator
252  *                              in perl syntax
253  *          2  :  trivialflag = Flag that causes backreferences to be
254  *                              ignored.
255  *          3  :  capturecount = Number of capturing subpatterns in
256  *                               the pattern. Needed for $+ handling.
257  *          4  :  errptr = pointer to an integer in which error
258  *                         conditions can be returned.
259  *
260  * Returns     :  pcrs_substitute data structure, or NULL if an
261  *                error is encountered. In that case, *errptr has
262  *                the reason.
263  *
264  *********************************************************************/
265 static pcrs_substitute *pcrs_compile_replacement(const char *replacement, int trivialflag, int capturecount, int *errptr)
266 {
267    int i, k, l, quoted;
268    size_t length;
269    char *text;
270    pcrs_substitute *r;
271
272    i = k = l = quoted = 0;
273
274    /*
275     * Sanity check
276     */
277    if (NULL == replacement)
278    {
279       replacement = "";
280    }
281
282    /*
283     * Get memory or fail
284     */
285    if (NULL == (r = (pcrs_substitute *)malloc(sizeof(pcrs_substitute))))
286    {
287       *errptr = PCRS_ERR_NOMEM;
288       return NULL;
289    }
290    memset(r, '\0', sizeof(pcrs_substitute));
291
292    length = strlen(replacement);
293
294    if (NULL == (text = (char *)malloc(length + 1)))
295    {
296       free(r);
297       *errptr = PCRS_ERR_NOMEM;
298       return NULL;
299    }
300    memset(text, '\0', length + 1);
301    
302
303    /*
304     * In trivial mode, just copy the substitute text
305     */
306    if (trivialflag)
307    {
308       text = strncpy(text, replacement, length + 1);
309       k = length;
310    }
311
312    /*
313     * Else, parse, cut out and record all backreferences
314     */
315    else
316    {
317       while (i < (int)length)
318       {
319          /* Quoting */
320          if (replacement[i] == '\\')
321          {
322             if (quoted)
323             {
324                text[k++] = replacement[i++];
325                quoted = 0;
326             }
327             else
328             {
329                if (replacement[i+1] && strchr("tnrfae0", replacement[i+1]))
330                {
331                   switch (replacement[++i])
332                   {
333                   case 't':
334                      text[k++] = '\t';
335                      break;
336                   case 'n':
337                      text[k++] = '\n';
338                      break;
339                   case 'r':
340                      text[k++] = '\r';
341                      break;
342                   case 'f':
343                      text[k++] = '\f';
344                      break;
345                   case 'a':
346                      text[k++] = 7;
347                      break;
348                   case 'e':
349                      text[k++] = 27;
350                      break;
351                   case '0':
352                      text[k++] = '\0';
353                      break;
354                   }
355                   i++;
356                }
357                else
358                {
359                   quoted = 1;
360                   i++;
361                }
362             }
363             continue;
364          }
365
366          /* Backreferences */
367          if (replacement[i] == '$' && !quoted && i < (int)(length - 1))
368          {
369             char *symbol, symbols[] = "'`+&";
370             r->block_length[l] = k - r->block_offset[l];
371
372             /* Numerical backreferences */
373             if (isdigit((int)replacement[i + 1]))
374             {
375                while (i < (int)length && isdigit((int)replacement[++i]))
376                {
377                   r->backref[l] = r->backref[l] * 10 + replacement[i] - 48;
378                }
379                if (r->backref[l] > capturecount)
380                {
381                   *errptr = PCRS_WARN_BADREF;
382                }
383             }
384
385             /* Symbolic backreferences: */
386             else if (NULL != (symbol = strchr(symbols, replacement[i + 1])))
387             {
388                
389                if (symbol - symbols == 2) /* $+ */
390                {
391                   r->backref[l] = capturecount;
392                }
393                else if (symbol - symbols == 3) /* $& */
394                {
395                   r->backref[l] = 0;
396                }
397                else /* $' or $` */
398                {
399                   r->backref[l] = PCRS_MAX_SUBMATCHES + 1 - (symbol - symbols);
400                }
401                i += 2;
402             }
403
404             /* Invalid backref -> plain '$' */
405             else
406             {
407                goto plainchar;
408             }
409
410             /* Valid and in range? -> record */
411             if (r->backref[l] < PCRS_MAX_SUBMATCHES + 2)
412             {
413                r->backref_count[r->backref[l]] += 1;
414                r->block_offset[++l] = k;
415             }
416             else
417             {
418                *errptr = PCRS_WARN_BADREF;
419             }   
420             continue;
421          }
422          
423 plainchar:
424          /* Plain chars are copied */
425          text[k++] = replacement[i++];
426          quoted = 0;
427       }
428    } /* -END- if (!trivialflag) */
429
430    /*
431     * Finish & return
432     */
433    r->text = text;
434    r->backrefs = l;
435    r->block_length[l] = k - r->block_offset[l];
436
437    return r;
438
439 }
440
441
442 /*********************************************************************
443  *
444  * Function    :  pcrs_free_job
445  *
446  * Description :  Frees the memory used by a pcrs_job struct and its
447  *                dependant structures.
448  *
449  * Parameters  :
450  *          1  :  job = pointer to the pcrs_job structure to be freed
451  *
452  * Returns     :  a pointer to the next job, if there was any, or
453  *                NULL otherwise. 
454  *
455  *********************************************************************/
456 pcrs_job *pcrs_free_job(pcrs_job *job)
457 {
458    pcrs_job *next;
459
460    if (job == NULL)
461    {
462       return NULL;
463    }
464    else
465    {
466       next = job->next;
467       if (job->pattern != NULL) free(job->pattern);
468       if (job->hints != NULL) free(job->hints);
469       if (job->substitute != NULL)
470       {
471          if (job->substitute->text != NULL) free(job->substitute->text);
472          free(job->substitute);
473       }
474       free(job);
475    }
476    return next;
477
478 }
479
480
481 /*********************************************************************
482  *
483  * Function    :  pcrs_free_joblist
484  *
485  * Description :  Iterates through a chained list of pcrs_job's and
486  *                frees them using pcrs_free_job.
487  *
488  * Parameters  :
489  *          1  :  joblist = pointer to the first pcrs_job structure to
490  *                be freed
491  *
492  * Returns     :  N/A
493  *
494  *********************************************************************/
495 void pcrs_free_joblist(pcrs_job *joblist)
496 {
497    while ( NULL != (joblist = pcrs_free_job(joblist)) ) {};
498
499    return;
500
501 }
502
503
504 /*********************************************************************
505  *
506  * Function    :  pcrs_compile_command
507  *
508  * Description :  Parses a string with a Perl-style s/// command, 
509  *                calls pcrs_compile, and returns a corresponding
510  *                pcrs_job, or NULL if parsing or compiling the job
511  *                fails.
512  *
513  * Parameters  :
514  *          1  :  command = string with perl-style s/// command
515  *          2  :  errptr = pointer to an integer in which error
516  *                         conditions can be returned.
517  *
518  * Returns     :  a corresponding pcrs_job data structure, or NULL
519  *                if an error was encountered. In that case, *errptr
520  *                has the reason.
521  *
522  *********************************************************************/
523 pcrs_job *pcrs_compile_command(const char *command, int *errptr)
524 {
525    int i, k, l, quoted = FALSE;
526    size_t limit;
527    char delimiter;
528    char *tokens[4];   
529    pcrs_job *newjob;
530    
531    i = k = l = 0;
532    
533    /*
534     * Tokenize the perl command
535     */
536    limit = strlen(command);
537    if (limit < 4)
538    {
539       *errptr = PCRS_ERR_CMDSYNTAX;
540       return NULL;
541    }
542    else
543    {
544       delimiter = command[1];
545    }
546
547    tokens[l] = (char *) malloc(limit + 1);
548
549    for (i = 0; i <= (int)limit; i++)
550    {
551       
552       if (command[i] == delimiter && !quoted)
553       {
554          if (l == 3)
555          {
556             l = -1;
557             break;
558          }
559          tokens[0][k++] = '\0';
560          tokens[++l] = tokens[0] + k;
561          continue;
562       }
563       
564       else if (command[i] == '\\' && !quoted)
565       {
566          quoted = TRUE;
567          if (command[i+1] == delimiter) continue;
568       }
569       else
570       {
571          quoted = FALSE;
572       }
573       tokens[0][k++] = command[i];
574    }
575
576    /*
577     * Syntax error ?
578     */
579    if (l != 3)
580    {
581       *errptr = PCRS_ERR_CMDSYNTAX;
582       free(tokens[0]);
583       return NULL;
584    }
585    
586    newjob = pcrs_compile(tokens[1], tokens[2], tokens[3], errptr);
587    free(tokens[0]);
588    return newjob;
589    
590 }
591
592
593 /*********************************************************************
594  *
595  * Function    :  pcrs_compile
596  *
597  * Description :  Takes the three arguments to a perl s/// command
598  *                and compiles a pcrs_job structure from them.
599  *
600  * Parameters  :
601  *          1  :  pattern = string with perl-style pattern
602  *          2  :  substitute = string with perl-style substitute
603  *          3  :  options = string with perl-style options
604  *          4  :  errptr = pointer to an integer in which error
605  *                         conditions can be returned.
606  *
607  * Returns     :  a corresponding pcrs_job data structure, or NULL
608  *                if an error was encountered. In that case, *errptr
609  *                has the reason.
610  *
611  *********************************************************************/
612 pcrs_job *pcrs_compile(const char *pattern, const char *substitute, const char *options, int *errptr)
613 {
614    pcrs_job *newjob;
615    int flags;
616    int capturecount;
617    const char *error;
618
619    *errptr = 0;
620
621    /* 
622     * Handle NULL arguments
623     */
624    if (pattern == NULL) pattern = "";
625    if (substitute == NULL) substitute = "";
626
627
628    /* 
629     * Get and init memory
630     */
631    if (NULL == (newjob = (pcrs_job *)malloc(sizeof(pcrs_job))))
632    {
633       *errptr = PCRS_ERR_NOMEM;
634       return NULL;
635    }
636    memset(newjob, '\0', sizeof(pcrs_job));
637
638
639    /*
640     * Evaluate the options
641     */
642    newjob->options = pcrs_parse_perl_options(options, &flags);
643    newjob->flags = flags;
644
645
646    /*
647     * Compile the pattern
648     */
649    newjob->pattern = pcre_compile(pattern, newjob->options, &error, errptr, NULL);
650    if (newjob->pattern == NULL)
651    {
652       pcrs_free_job(newjob);
653       return NULL;
654    }
655
656
657    /*
658     * Generate hints. This has little overhead, since the
659     * hints will be NULL for a boring pattern anyway.
660     */
661    newjob->hints = pcre_study(newjob->pattern, 0, &error);
662    if (error != NULL)
663    {
664       *errptr = PCRS_ERR_STUDY;
665       pcrs_free_job(newjob);
666       return NULL;
667    }
668  
669
670    /* 
671     * Determine the number of capturing subpatterns. 
672     * This is needed for handling $+ in the substitute.
673     */
674    if (0 > (*errptr = pcre_fullinfo(newjob->pattern, newjob->hints, PCRE_INFO_CAPTURECOUNT, &capturecount)))
675    {
676       pcrs_free_job(newjob);
677       return NULL;
678    }
679  
680
681    /*
682     * Compile the substitute
683     */
684    if (NULL == (newjob->substitute = pcrs_compile_replacement(substitute, newjob->flags & PCRS_TRIVIAL, capturecount, errptr)))
685    {
686       pcrs_free_job(newjob);
687       return NULL;
688    }
689  
690    return newjob;
691
692 }
693
694
695 /*********************************************************************
696  *
697  * Function    :  pcrs_execute_list
698  *
699  * Description :  This is a multiple job wrapper for pcrs_execute().
700  *                Apply the regular substitutions defined by the jobs in
701  *                the joblist to the subject.
702  *                The subject itself is left untouched, memory for the result
703  *                is malloc()ed and it is the caller's responsibility to free
704  *                the result when it's no longer needed.
705  *
706  * Parameters  :
707  *          1  :  joblist = the chained list of pcrs_jobs to be executed
708  *          2  :  subject = the subject string
709  *          3  :  subject_length = the subject's length 
710  *                INCLUDING the terminating zero, if string!
711  *          4  :  result = char** for returning  the result 
712  *          5  :  result_length = size_t* for returning the result's length
713  *
714  * Returns     :  On success, the number of substitutions that were made.
715  *                 May be > 1 if job->flags contained PCRS_GLOBAL
716  *                On failiure, the (negative) pcre error code describing the
717  *                 failiure, which may be translated to text using pcrs_strerror().
718  *
719  *********************************************************************/
720 int pcrs_execute_list(pcrs_job *joblist, char *subject, size_t subject_length, char **result, size_t *result_length)
721 {
722    pcrs_job *job;
723    char *old, *new;
724    int hits, total_hits;
725  
726    old = subject;
727    *result_length = subject_length;
728    hits = total_hits = 0;
729
730    for (job = joblist; job != NULL; job = job->next)
731    {
732       hits = pcrs_execute(job, old, *result_length, &new, result_length);
733
734       if (old != subject) free(old);
735
736       if (hits < 0)
737       {
738          return(hits);
739       }
740       else
741       {
742          total_hits += hits;
743          old = new;
744       }
745    }
746
747    *result = new;
748    return(total_hits);
749
750 }
751
752
753 /*********************************************************************
754  *
755  * Function    :  pcrs_execute
756  *
757  * Description :  Apply the regular substitution defined by the job to the
758  *                subject.
759  *                The subject itself is left untouched, memory for the result
760  *                is malloc()ed and it is the caller's responsibility to free
761  *                the result when it's no longer needed.
762  *
763  * Parameters  :
764  *          1  :  job = the pcrs_job to be executed
765  *          2  :  subject = the subject (== original) string
766  *          3  :  subject_length = the subject's length 
767  *                INCLUDING the terminating zero, if string!
768  *          4  :  result = char** for returning  the result 
769  *          5  :  result_length = size_t* for returning the result's length
770  *
771  * Returns     :  On success, the number of substitutions that were made.
772  *                 May be > 1 if job->flags contained PCRS_GLOBAL
773  *                On failiure, the (negative) pcre error code describing the
774  *                 failiure, which may be translated to text using pcrs_strerror().
775  *
776  *********************************************************************/
777 int pcrs_execute(pcrs_job *job, char *subject, size_t subject_length, char **result, size_t *result_length)
778 {
779    int offsets[3 * PCRS_MAX_SUBMATCHES],
780        offset,
781        i, k,
782        matches_found,
783        submatches,
784        max_matches = PCRS_MAX_MATCH_INIT;
785    size_t newsize;
786    pcrs_match *matches, *dummy;
787    char *result_offset;
788
789    offset = i = k = 0;
790
791    /* 
792     * Sanity check & memory allocation
793     */
794    if (job == NULL || job->pattern == NULL || job->substitute == NULL)
795    {
796       *result = NULL;
797       return(PCRS_ERR_BADJOB);
798    }
799
800    if (NULL == (matches = (pcrs_match *)malloc(max_matches * sizeof(pcrs_match))))
801    {
802       *result = NULL;
803       return(PCRS_ERR_NOMEM);
804    }
805    memset(matches, '\0', max_matches * sizeof(pcrs_match));
806
807
808    /*
809     * Find the pattern and calculate the space
810     * requirements for the result
811     */
812    newsize = subject_length;
813
814    while ((submatches = pcre_exec(job->pattern, job->hints, subject, (int)subject_length, offset, 0, offsets, 3 * PCRS_MAX_SUBMATCHES)) > 0)
815    {
816       job->flags |= PCRS_SUCCESS;
817       matches[i].submatches = submatches;
818
819       for (k = 0; k < submatches; k++)
820       {
821          matches[i].submatch_offset[k] = offsets[2 * k];
822
823          /* Note: Non-found optional submatches have length -1-(-1)==0 */
824          matches[i].submatch_length[k] = offsets[2 * k + 1] - offsets[2 * k]; 
825
826          /* reserve mem for each submatch as often as it is ref'd */
827          newsize += matches[i].submatch_length[k] * job->substitute->backref_count[k]; 
828       }
829       /* plus replacement text size minus match text size */
830       newsize += strlen(job->substitute->text) - matches[i].submatch_length[0]; 
831
832       /* chunk before match */
833       matches[i].submatch_offset[PCRS_MAX_SUBMATCHES] = 0;
834       matches[i].submatch_length[PCRS_MAX_SUBMATCHES] = offsets[0];
835       newsize += offsets[0] * job->substitute->backref_count[PCRS_MAX_SUBMATCHES];
836
837       /* chunk after match */
838       matches[i].submatch_offset[PCRS_MAX_SUBMATCHES + 1] = offsets[1];
839       matches[i].submatch_length[PCRS_MAX_SUBMATCHES + 1] = subject_length - offsets[1] - 1;
840       newsize += (subject_length - offsets[1]) * job->substitute->backref_count[PCRS_MAX_SUBMATCHES + 1];
841
842       /* Storage for matches exhausted? -> Extend! */
843       if (++i >= max_matches)
844       {
845          max_matches = (int)(max_matches * PCRS_MAX_MATCH_GROW);
846          if (NULL == (dummy = (pcrs_match *)realloc(matches, max_matches * sizeof(pcrs_match))))
847          {
848             free(matches);
849             *result = NULL;
850             return(PCRS_ERR_NOMEM);
851          }
852          matches = dummy;
853       }
854
855       /* Non-global search or limit reached? */
856       if (!(job->flags & PCRS_GLOBAL)) break;
857
858       /* Don't loop on empty matches */
859       if (offsets[1] == offset)
860          if ((size_t)offset < subject_length)
861             offset++;
862          else
863             break;
864       /* Go find the next one */
865       else
866          offset = offsets[1];
867    }
868    /* Pass pcre error through if (bad) failiure */
869    if (submatches < PCRE_ERROR_NOMATCH)
870    {
871       free(matches);
872       return submatches;   
873    }
874    matches_found = i;
875
876
877    /* 
878     * Get memory for the result
879     */
880    if ((*result = (char *)malloc(newsize)) == NULL)   /* must be free()d by caller */
881    {
882       free(matches);
883       return PCRS_ERR_NOMEM;
884    }
885
886
887    /* 
888     * Replace
889     */
890    offset = 0;
891    result_offset = *result;
892
893    for (i = 0; i < matches_found; i++)
894    {
895       /* copy the chunk preceding the match */
896       memcpy(result_offset, subject + offset, (size_t)matches[i].submatch_offset[0] - offset); 
897       result_offset += matches[i].submatch_offset[0] - offset;
898
899       /* For every segment of the substitute.. */
900       for (k = 0; k <= job->substitute->backrefs; k++)
901       {
902          /* ...copy its text.. */
903          memcpy(result_offset, job->substitute->text + job->substitute->block_offset[k], job->substitute->block_length[k]);
904          result_offset += job->substitute->block_length[k];
905
906          /* ..plus, if it's not the last chunk, i.e.: There *is* a backref.. */
907          if (k != job->substitute->backrefs
908              /* ..in legal range.. */
909              && job->substitute->backref[k] < PCRS_MAX_SUBMATCHES + 2
910              /* ..and referencing a nonempty match.. */
911              && matches[i].submatch_length[job->substitute->backref[k]] > 0)
912          {
913             /* ..copy the submatch that is ref'd. */
914             memcpy(
915                result_offset,
916                subject + matches[i].submatch_offset[job->substitute->backref[k]],
917                matches[i].submatch_length[job->substitute->backref[k]]
918             );
919             result_offset += matches[i].submatch_length[job->substitute->backref[k]];
920          }
921       }
922       offset =  matches[i].submatch_offset[0] + matches[i].submatch_length[0];
923    }
924
925    /* Copy the rest. */
926    memcpy(result_offset, subject + offset, subject_length - offset);
927
928    *result_length = newsize;
929    free(matches);
930    return matches_found;
931
932 }
933
934
935 /*
936   Local Variables:
937   tab-width: 3
938   end:
939 */