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