1// Copyright 2003-2009 Google Inc.  All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// This is a variant of PCRE's pcrecpp.cc, originally written at Google.
6// The main changes are the addition of the HitLimit method and
7// compilation as PCRE in namespace re2.
8
9#include <errno.h>
10#include "util/util.h"
11#include "util/flags.h"
12#include "util/pcre.h"
13
14#ifdef WIN32
15#define strtoll _strtoi64
16#define strtoull _strtoui64
17#endif
18
19#define PCREPORT(level) LOG(level)
20
21// Default PCRE limits.
22// Defaults chosen to allow a plausible amount of CPU and
23// not exceed main thread stacks.  Note that other threads
24// often have smaller stacks, and therefore tightening
25// regexp_stack_limit may frequently be necessary.
26DEFINE_int32(regexp_stack_limit, 256<<10, "default PCRE stack limit (bytes)");
27DEFINE_int32(regexp_match_limit, 1000000,
28             "default PCRE match limit (function calls)");
29
30namespace re2 {
31
32// Maximum number of args we can set
33static const int kMaxArgs = 16;
34static const int kVecSize = (1 + kMaxArgs) * 3;  // results + PCRE workspace
35
36// Approximate size of a recursive invocation of PCRE's
37// internal "match()" frame.  This varies depending on the
38// compiler and architecture, of course, so the constant is
39// just a conservative estimate.  To find the exact number,
40// run regexp_unittest with --regexp_stack_limit=0 under
41// a debugger and look at the frames when it crashes.
42// The exact frame size was 656 in production on 2008/02/03.
43static const int kPCREFrameSize = 700;
44
45// Special name for missing C++ arguments.
46PCRE::Arg PCRE::no_more_args((void*)NULL);
47
48const PCRE::PartialMatchFunctor PCRE::PartialMatch = { };
49const PCRE::FullMatchFunctor PCRE::FullMatch = { } ;
50const PCRE::ConsumeFunctor PCRE::Consume = { };
51const PCRE::FindAndConsumeFunctor PCRE::FindAndConsume = { };
52
53// If a regular expression has no error, its error_ field points here
54static const string empty_string;
55
56void PCRE::Init(const char* pattern, Option options, int match_limit,
57              int stack_limit, bool report_errors) {
58  pattern_ = pattern;
59  options_ = options;
60  match_limit_ = match_limit;
61  stack_limit_ = stack_limit;
62  hit_limit_ = false;
63  error_ = &empty_string;
64  report_errors_ = report_errors;
65  re_full_ = NULL;
66  re_partial_ = NULL;
67
68  if (options & ~(EnabledCompileOptions | EnabledExecOptions)) {
69    error_ = new string("illegal regexp option");
70    PCREPORT(ERROR)
71        << "Error compiling '" << pattern << "': illegal regexp option";
72  } else {
73    re_partial_ = Compile(UNANCHORED);
74    if (re_partial_ != NULL) {
75      re_full_ = Compile(ANCHOR_BOTH);
76    }
77  }
78}
79
80PCRE::PCRE(const char* pattern) {
81  Init(pattern, None, 0, 0, true);
82}
83PCRE::PCRE(const char* pattern, Option option) {
84  Init(pattern, option, 0, 0, true);
85}
86PCRE::PCRE(const string& pattern) {
87  Init(pattern.c_str(), None, 0, 0, true);
88}
89PCRE::PCRE(const string& pattern, Option option) {
90  Init(pattern.c_str(), option, 0, 0, true);
91}
92PCRE::PCRE(const string& pattern, const PCRE_Options& re_option) {
93  Init(pattern.c_str(), re_option.option(), re_option.match_limit(),
94       re_option.stack_limit(), re_option.report_errors());
95}
96
97PCRE::PCRE(const char *pattern, const PCRE_Options& re_option) {
98  Init(pattern, re_option.option(), re_option.match_limit(),
99       re_option.stack_limit(), re_option.report_errors());
100}
101
102PCRE::~PCRE() {
103  if (re_full_ != NULL)         pcre_free(re_full_);
104  if (re_partial_ != NULL)      pcre_free(re_partial_);
105  if (error_ != &empty_string)  delete error_;
106}
107
108pcre* PCRE::Compile(Anchor anchor) {
109  // Special treatment for anchoring.  This is needed because at
110  // runtime pcre only provides an option for anchoring at the
111  // beginning of a string.
112  //
113  // There are three types of anchoring we want:
114  //    UNANCHORED      Compile the original pattern, and use
115  //                    a pcre unanchored match.
116  //    ANCHOR_START    Compile the original pattern, and use
117  //                    a pcre anchored match.
118  //    ANCHOR_BOTH     Tack a "\z" to the end of the original pattern
119  //                    and use a pcre anchored match.
120
121  const char* error;
122  int eoffset;
123  pcre* re;
124  if (anchor != ANCHOR_BOTH) {
125    re = pcre_compile(pattern_.c_str(),
126                      (options_ & EnabledCompileOptions),
127                      &error, &eoffset, NULL);
128  } else {
129    // Tack a '\z' at the end of PCRE.  Parenthesize it first so that
130    // the '\z' applies to all top-level alternatives in the regexp.
131    string wrapped = "(?:";  // A non-counting grouping operator
132    wrapped += pattern_;
133    wrapped += ")\\z";
134    re = pcre_compile(wrapped.c_str(),
135                      (options_ & EnabledCompileOptions),
136                      &error, &eoffset, NULL);
137  }
138  if (re == NULL) {
139    if (error_ == &empty_string) error_ = new string(error);
140    PCREPORT(ERROR) << "Error compiling '" << pattern_ << "': " << error;
141  }
142  return re;
143}
144
145/***** Convenience interfaces *****/
146
147bool PCRE::FullMatchFunctor::operator ()(const StringPiece& text,
148                                       const PCRE& re,
149                                       const Arg& a0,
150                                       const Arg& a1,
151                                       const Arg& a2,
152                                       const Arg& a3,
153                                       const Arg& a4,
154                                       const Arg& a5,
155                                       const Arg& a6,
156                                       const Arg& a7,
157                                       const Arg& a8,
158                                       const Arg& a9,
159                                       const Arg& a10,
160                                       const Arg& a11,
161                                       const Arg& a12,
162                                       const Arg& a13,
163                                       const Arg& a14,
164                                       const Arg& a15) const {
165  const Arg* args[kMaxArgs];
166  int n = 0;
167  if (&a0 == &no_more_args)  goto done; args[n++] = &a0;
168  if (&a1 == &no_more_args)  goto done; args[n++] = &a1;
169  if (&a2 == &no_more_args)  goto done; args[n++] = &a2;
170  if (&a3 == &no_more_args)  goto done; args[n++] = &a3;
171  if (&a4 == &no_more_args)  goto done; args[n++] = &a4;
172  if (&a5 == &no_more_args)  goto done; args[n++] = &a5;
173  if (&a6 == &no_more_args)  goto done; args[n++] = &a6;
174  if (&a7 == &no_more_args)  goto done; args[n++] = &a7;
175  if (&a8 == &no_more_args)  goto done; args[n++] = &a8;
176  if (&a9 == &no_more_args)  goto done; args[n++] = &a9;
177  if (&a10 == &no_more_args) goto done; args[n++] = &a10;
178  if (&a11 == &no_more_args) goto done; args[n++] = &a11;
179  if (&a12 == &no_more_args) goto done; args[n++] = &a12;
180  if (&a13 == &no_more_args) goto done; args[n++] = &a13;
181  if (&a14 == &no_more_args) goto done; args[n++] = &a14;
182  if (&a15 == &no_more_args) goto done; args[n++] = &a15;
183done:
184
185  int consumed;
186  int vec[kVecSize];
187  return re.DoMatchImpl(text, ANCHOR_BOTH, &consumed, args, n, vec, kVecSize);
188}
189
190bool PCRE::PartialMatchFunctor::operator ()(const StringPiece& text,
191                                          const PCRE& re,
192                                          const Arg& a0,
193                                          const Arg& a1,
194                                          const Arg& a2,
195                                          const Arg& a3,
196                                          const Arg& a4,
197                                          const Arg& a5,
198                                          const Arg& a6,
199                                          const Arg& a7,
200                                          const Arg& a8,
201                                          const Arg& a9,
202                                          const Arg& a10,
203                                          const Arg& a11,
204                                          const Arg& a12,
205                                          const Arg& a13,
206                                          const Arg& a14,
207                                          const Arg& a15) const {
208  const Arg* args[kMaxArgs];
209  int n = 0;
210  if (&a0 == &no_more_args)  goto done; args[n++] = &a0;
211  if (&a1 == &no_more_args)  goto done; args[n++] = &a1;
212  if (&a2 == &no_more_args)  goto done; args[n++] = &a2;
213  if (&a3 == &no_more_args)  goto done; args[n++] = &a3;
214  if (&a4 == &no_more_args)  goto done; args[n++] = &a4;
215  if (&a5 == &no_more_args)  goto done; args[n++] = &a5;
216  if (&a6 == &no_more_args)  goto done; args[n++] = &a6;
217  if (&a7 == &no_more_args)  goto done; args[n++] = &a7;
218  if (&a8 == &no_more_args)  goto done; args[n++] = &a8;
219  if (&a9 == &no_more_args)  goto done; args[n++] = &a9;
220  if (&a10 == &no_more_args) goto done; args[n++] = &a10;
221  if (&a11 == &no_more_args) goto done; args[n++] = &a11;
222  if (&a12 == &no_more_args) goto done; args[n++] = &a12;
223  if (&a13 == &no_more_args) goto done; args[n++] = &a13;
224  if (&a14 == &no_more_args) goto done; args[n++] = &a14;
225  if (&a15 == &no_more_args) goto done; args[n++] = &a15;
226done:
227
228  int consumed;
229  int vec[kVecSize];
230  return re.DoMatchImpl(text, UNANCHORED, &consumed, args, n, vec, kVecSize);
231}
232
233bool PCRE::ConsumeFunctor::operator ()(StringPiece* input,
234                                     const PCRE& pattern,
235                                     const Arg& a0,
236                                     const Arg& a1,
237                                     const Arg& a2,
238                                     const Arg& a3,
239                                     const Arg& a4,
240                                     const Arg& a5,
241                                     const Arg& a6,
242                                     const Arg& a7,
243                                     const Arg& a8,
244                                     const Arg& a9,
245                                     const Arg& a10,
246                                     const Arg& a11,
247                                     const Arg& a12,
248                                     const Arg& a13,
249                                     const Arg& a14,
250                                     const Arg& a15) const {
251  const Arg* args[kMaxArgs];
252  int n = 0;
253  if (&a0 == &no_more_args)  goto done; args[n++] = &a0;
254  if (&a1 == &no_more_args)  goto done; args[n++] = &a1;
255  if (&a2 == &no_more_args)  goto done; args[n++] = &a2;
256  if (&a3 == &no_more_args)  goto done; args[n++] = &a3;
257  if (&a4 == &no_more_args)  goto done; args[n++] = &a4;
258  if (&a5 == &no_more_args)  goto done; args[n++] = &a5;
259  if (&a6 == &no_more_args)  goto done; args[n++] = &a6;
260  if (&a7 == &no_more_args)  goto done; args[n++] = &a7;
261  if (&a8 == &no_more_args)  goto done; args[n++] = &a8;
262  if (&a9 == &no_more_args)  goto done; args[n++] = &a9;
263  if (&a10 == &no_more_args) goto done; args[n++] = &a10;
264  if (&a11 == &no_more_args) goto done; args[n++] = &a11;
265  if (&a12 == &no_more_args) goto done; args[n++] = &a12;
266  if (&a13 == &no_more_args) goto done; args[n++] = &a13;
267  if (&a14 == &no_more_args) goto done; args[n++] = &a14;
268  if (&a15 == &no_more_args) goto done; args[n++] = &a15;
269done:
270
271  int consumed;
272  int vec[kVecSize];
273  if (pattern.DoMatchImpl(*input, ANCHOR_START, &consumed,
274                          args, n, vec, kVecSize)) {
275    input->remove_prefix(consumed);
276    return true;
277  } else {
278    return false;
279  }
280}
281
282bool PCRE::FindAndConsumeFunctor::operator ()(StringPiece* input,
283                                            const PCRE& pattern,
284                                            const Arg& a0,
285                                            const Arg& a1,
286                                            const Arg& a2,
287                                            const Arg& a3,
288                                            const Arg& a4,
289                                            const Arg& a5,
290                                            const Arg& a6,
291                                            const Arg& a7,
292                                            const Arg& a8,
293                                            const Arg& a9,
294                                            const Arg& a10,
295                                            const Arg& a11,
296                                            const Arg& a12,
297                                            const Arg& a13,
298                                            const Arg& a14,
299                                            const Arg& a15) const {
300  const Arg* args[kMaxArgs];
301  int n = 0;
302  if (&a0 == &no_more_args)  goto done; args[n++] = &a0;
303  if (&a1 == &no_more_args)  goto done; args[n++] = &a1;
304  if (&a2 == &no_more_args)  goto done; args[n++] = &a2;
305  if (&a3 == &no_more_args)  goto done; args[n++] = &a3;
306  if (&a4 == &no_more_args)  goto done; args[n++] = &a4;
307  if (&a5 == &no_more_args)  goto done; args[n++] = &a5;
308  if (&a6 == &no_more_args)  goto done; args[n++] = &a6;
309  if (&a7 == &no_more_args)  goto done; args[n++] = &a7;
310  if (&a8 == &no_more_args)  goto done; args[n++] = &a8;
311  if (&a9 == &no_more_args)  goto done; args[n++] = &a9;
312  if (&a10 == &no_more_args) goto done; args[n++] = &a10;
313  if (&a11 == &no_more_args) goto done; args[n++] = &a11;
314  if (&a12 == &no_more_args) goto done; args[n++] = &a12;
315  if (&a13 == &no_more_args) goto done; args[n++] = &a13;
316  if (&a14 == &no_more_args) goto done; args[n++] = &a14;
317  if (&a15 == &no_more_args) goto done; args[n++] = &a15;
318done:
319
320  int consumed;
321  int vec[kVecSize];
322  if (pattern.DoMatchImpl(*input, UNANCHORED, &consumed,
323                          args, n, vec, kVecSize)) {
324    input->remove_prefix(consumed);
325    return true;
326  } else {
327    return false;
328  }
329}
330
331bool PCRE::Replace(string *str,
332                 const PCRE& pattern,
333                 const StringPiece& rewrite) {
334  int vec[kVecSize];
335  int matches = pattern.TryMatch(*str, 0, UNANCHORED, true, vec, kVecSize);
336  if (matches == 0)
337    return false;
338
339  string s;
340  if (!pattern.Rewrite(&s, rewrite, *str, vec, matches))
341    return false;
342
343  assert(vec[0] >= 0);
344  assert(vec[1] >= 0);
345  str->replace(vec[0], vec[1] - vec[0], s);
346  return true;
347}
348
349int PCRE::GlobalReplace(string *str,
350                      const PCRE& pattern,
351                      const StringPiece& rewrite) {
352  int count = 0;
353  int vec[kVecSize];
354  string out;
355  int start = 0;
356  bool last_match_was_empty_string = false;
357
358  for (; start <= str->length();) {
359    // If the previous match was for the empty string, we shouldn't
360    // just match again: we'll match in the same way and get an
361    // infinite loop.  Instead, we do the match in a special way:
362    // anchored -- to force another try at the same position --
363    // and with a flag saying that this time, ignore empty matches.
364    // If this special match returns, that means there's a non-empty
365    // match at this position as well, and we can continue.  If not,
366    // we do what perl does, and just advance by one.
367    // Notice that perl prints '@@@' for this;
368    //    perl -le '$_ = "aa"; s/b*|aa/@/g; print'
369    int matches;
370    if (last_match_was_empty_string) {
371      matches = pattern.TryMatch(*str, start, ANCHOR_START, false,
372                                 vec, kVecSize);
373      if (matches <= 0) {
374        if (start < str->length())
375          out.push_back((*str)[start]);
376        start++;
377        last_match_was_empty_string = false;
378        continue;
379      }
380    } else {
381      matches = pattern.TryMatch(*str, start, UNANCHORED, true, vec, kVecSize);
382      if (matches <= 0)
383        break;
384    }
385    int matchstart = vec[0], matchend = vec[1];
386    assert(matchstart >= start);
387    assert(matchend >= matchstart);
388
389    out.append(*str, start, matchstart - start);
390    pattern.Rewrite(&out, rewrite, *str, vec, matches);
391    start = matchend;
392    count++;
393    last_match_was_empty_string = (matchstart == matchend);
394  }
395
396  if (count == 0)
397    return 0;
398
399  if (start < str->length())
400    out.append(*str, start, str->length() - start);
401  swap(out, *str);
402  return count;
403}
404
405bool PCRE::Extract(const StringPiece &text,
406                 const PCRE& pattern,
407                 const StringPiece &rewrite,
408                 string *out) {
409  int vec[kVecSize];
410  int matches = pattern.TryMatch(text, 0, UNANCHORED, true, vec, kVecSize);
411  if (matches == 0)
412    return false;
413  out->clear();
414  return pattern.Rewrite(out, rewrite, text, vec, matches);
415}
416
417string PCRE::QuoteMeta(const StringPiece& unquoted) {
418  string result;
419  result.reserve(unquoted.size() << 1);
420
421  // Escape any ascii character not in [A-Za-z_0-9].
422  //
423  // Note that it's legal to escape a character even if it has no
424  // special meaning in a regular expression -- so this function does
425  // that.  (This also makes it identical to the perl function of the
426  // same name except for the null-character special case;
427  // see `perldoc -f quotemeta`.)
428  for (int ii = 0; ii < unquoted.length(); ++ii) {
429    // Note that using 'isalnum' here raises the benchmark time from
430    // 32ns to 58ns:
431    if ((unquoted[ii] < 'a' || unquoted[ii] > 'z') &&
432        (unquoted[ii] < 'A' || unquoted[ii] > 'Z') &&
433        (unquoted[ii] < '0' || unquoted[ii] > '9') &&
434        unquoted[ii] != '_' &&
435        // If this is the part of a UTF8 or Latin1 character, we need
436        // to copy this byte without escaping.  Experimentally this is
437        // what works correctly with the regexp library.
438        !(unquoted[ii] & 128)) {
439      if (unquoted[ii] == '\0') {  // Special handling for null chars.
440        // Can't use "\\0" since the next character might be a digit.
441        result += "\\x00";
442        continue;
443      }
444      result += '\\';
445    }
446    result += unquoted[ii];
447  }
448
449  return result;
450}
451
452/***** Actual matching and rewriting code *****/
453
454bool PCRE::HitLimit() {
455  return hit_limit_;
456}
457
458void PCRE::ClearHitLimit() {
459  hit_limit_ = 0;
460}
461
462int PCRE::TryMatch(const StringPiece& text,
463                 int startpos,
464                 Anchor anchor,
465                 bool empty_ok,
466                 int *vec,
467                 int vecsize) const {
468  pcre* re = (anchor == ANCHOR_BOTH) ? re_full_ : re_partial_;
469  if (re == NULL) {
470    PCREPORT(ERROR) << "Matching against invalid re: " << *error_;
471    return 0;
472  }
473
474  int match_limit = match_limit_;
475  if (match_limit <= 0) {
476    match_limit = FLAGS_regexp_match_limit;
477  }
478
479  int stack_limit = stack_limit_;
480  if (stack_limit <= 0) {
481    stack_limit = FLAGS_regexp_stack_limit;
482  }
483
484  pcre_extra extra = { 0 };
485  if (match_limit > 0) {
486    extra.flags |= PCRE_EXTRA_MATCH_LIMIT;
487    extra.match_limit = match_limit;
488  }
489  if (stack_limit > 0) {
490    extra.flags |= PCRE_EXTRA_MATCH_LIMIT_RECURSION;
491    extra.match_limit_recursion = stack_limit / kPCREFrameSize;
492  }
493
494  int options = 0;
495  if (anchor != UNANCHORED)
496    options |= PCRE_ANCHORED;
497  if (!empty_ok)
498    options |= PCRE_NOTEMPTY;
499
500  int rc = pcre_exec(re,              // The regular expression object
501                     &extra,
502                     (text.data() == NULL) ? "" : text.data(),
503                     text.size(),
504                     startpos,
505                     options,
506                     vec,
507                     vecsize);
508
509  // Handle errors
510  if (rc == 0) {
511    // pcre_exec() returns 0 as a special case when the number of
512    // capturing subpatterns exceeds the size of the vector.
513    // When this happens, there is a match and the output vector
514    // is filled, but we miss out on the positions of the extra subpatterns.
515    rc = vecsize / 2;
516  } else if (rc < 0) {
517    switch (rc) {
518      case PCRE_ERROR_NOMATCH:
519        return 0;
520      case PCRE_ERROR_MATCHLIMIT:
521        // Writing to hit_limit is not safe if multiple threads
522        // are using the PCRE, but the flag is only intended
523        // for use by unit tests anyway, so we let it go.
524        hit_limit_ = true;
525        PCREPORT(WARNING) << "Exceeded match limit of " << match_limit
526                        << " when matching '" << pattern_ << "'"
527                        << " against text that is " << text.size() << " bytes.";
528        return 0;
529      case PCRE_ERROR_RECURSIONLIMIT:
530        // See comment about hit_limit above.
531        hit_limit_ = true;
532        PCREPORT(WARNING) << "Exceeded stack limit of " << stack_limit
533                        << " when matching '" << pattern_ << "'"
534                        << " against text that is " << text.size() << " bytes.";
535        return 0;
536      default:
537        // There are other return codes from pcre.h :
538        // PCRE_ERROR_NULL           (-2)
539        // PCRE_ERROR_BADOPTION      (-3)
540        // PCRE_ERROR_BADMAGIC       (-4)
541        // PCRE_ERROR_UNKNOWN_NODE   (-5)
542        // PCRE_ERROR_NOMEMORY       (-6)
543        // PCRE_ERROR_NOSUBSTRING    (-7)
544        // ...
545        PCREPORT(ERROR) << "Unexpected return code: " << rc
546                      << " when matching '" << pattern_ << "'"
547                      << ", re=" << re
548                      << ", text=" << text
549                      << ", vec=" << vec
550                      << ", vecsize=" << vecsize;
551        return 0;
552    }
553  }
554
555  return rc;
556}
557
558bool PCRE::DoMatchImpl(const StringPiece& text,
559                     Anchor anchor,
560                     int* consumed,
561                     const Arg* const* args,
562                     int n,
563                     int* vec,
564                     int vecsize) const {
565  assert((1 + n) * 3 <= vecsize);  // results + PCRE workspace
566  int matches = TryMatch(text, 0, anchor, true, vec, vecsize);
567  assert(matches >= 0);  // TryMatch never returns negatives
568  if (matches == 0)
569    return false;
570
571  *consumed = vec[1];
572
573  if (n == 0 || args == NULL) {
574    // We are not interested in results
575    return true;
576  }
577  if (NumberOfCapturingGroups() < n) {
578    // PCRE has fewer capturing groups than number of arg pointers passed in
579    return false;
580  }
581
582  // If we got here, we must have matched the whole pattern.
583  // We do not need (can not do) any more checks on the value of 'matches' here
584  // -- see the comment for TryMatch.
585  for (int i = 0; i < n; i++) {
586    const int start = vec[2*(i+1)];
587    const int limit = vec[2*(i+1)+1];
588    if (!args[i]->Parse(text.data() + start, limit-start)) {
589      // TODO: Should we indicate what the error was?
590      return false;
591    }
592  }
593
594  return true;
595}
596
597bool PCRE::DoMatch(const StringPiece& text,
598                 Anchor anchor,
599                 int* consumed,
600                 const Arg* const args[],
601                 int n) const {
602  assert(n >= 0);
603  size_t const vecsize = (1 + n) * 3;  // results + PCRE workspace
604                                       // (as for kVecSize)
605  int *vec = new int[vecsize];
606  bool b = DoMatchImpl(text, anchor, consumed, args, n, vec, vecsize);
607  delete[] vec;
608  return b;
609}
610
611bool PCRE::Rewrite(string *out, const StringPiece &rewrite,
612                 const StringPiece &text, int *vec, int veclen) const {
613  int number_of_capturing_groups = NumberOfCapturingGroups();
614  for (const char *s = rewrite.data(), *end = s + rewrite.size();
615       s < end; s++) {
616    int c = *s;
617    if (c == '\\') {
618      c = *++s;
619      if (isdigit(c)) {
620        int n = (c - '0');
621        if (n >= veclen) {
622          if (n <= number_of_capturing_groups) {
623            // unmatched optional capturing group. treat
624            // its value as empty string; i.e., nothing to append.
625          } else {
626            PCREPORT(ERROR) << "requested group " << n
627                          << " in regexp " << rewrite.data();
628            return false;
629          }
630        }
631        int start = vec[2 * n];
632        if (start >= 0)
633          out->append(text.data() + start, vec[2 * n + 1] - start);
634      } else if (c == '\\') {
635        out->push_back('\\');
636      } else {
637        PCREPORT(ERROR) << "invalid rewrite pattern: " << rewrite.data();
638        return false;
639      }
640    } else {
641      out->push_back(c);
642    }
643  }
644  return true;
645}
646
647bool PCRE::CheckRewriteString(const StringPiece& rewrite, string* error) const {
648  int max_token = -1;
649  for (const char *s = rewrite.data(), *end = s + rewrite.size();
650       s < end; s++) {
651    int c = *s;
652    if (c != '\\') {
653      continue;
654    }
655    if (++s == end) {
656      *error = "Rewrite schema error: '\\' not allowed at end.";
657      return false;
658    }
659    c = *s;
660    if (c == '\\') {
661      continue;
662    }
663    if (!isdigit(c)) {
664      *error = "Rewrite schema error: "
665               "'\\' must be followed by a digit or '\\'.";
666      return false;
667    }
668    int n = (c - '0');
669    if (max_token < n) {
670      max_token = n;
671    }
672  }
673
674  if (max_token > NumberOfCapturingGroups()) {
675    SStringPrintf(error, "Rewrite schema requests %d matches, "
676                  "but the regexp only has %d parenthesized subexpressions.",
677                  max_token, NumberOfCapturingGroups());
678    return false;
679  }
680  return true;
681}
682
683
684// Return the number of capturing subpatterns, or -1 if the
685// regexp wasn't valid on construction.
686int PCRE::NumberOfCapturingGroups() const {
687  if (re_partial_ == NULL) return -1;
688
689  int result;
690  CHECK(pcre_fullinfo(re_partial_,       // The regular expression object
691                      NULL,              // We did not study the pattern
692                      PCRE_INFO_CAPTURECOUNT,
693                      &result) == 0);
694  return result;
695}
696
697
698/***** Parsers for various types *****/
699
700bool PCRE::Arg::parse_null(const char* str, int n, void* dest) {
701  // We fail if somebody asked us to store into a non-NULL void* pointer
702  return (dest == NULL);
703}
704
705bool PCRE::Arg::parse_string(const char* str, int n, void* dest) {
706  if (dest == NULL) return true;
707  reinterpret_cast<string*>(dest)->assign(str, n);
708  return true;
709}
710
711bool PCRE::Arg::parse_stringpiece(const char* str, int n, void* dest) {
712  if (dest == NULL) return true;
713  reinterpret_cast<StringPiece*>(dest)->set(str, n);
714  return true;
715}
716
717bool PCRE::Arg::parse_char(const char* str, int n, void* dest) {
718  if (n != 1) return false;
719  if (dest == NULL) return true;
720  *(reinterpret_cast<char*>(dest)) = str[0];
721  return true;
722}
723
724bool PCRE::Arg::parse_uchar(const char* str, int n, void* dest) {
725  if (n != 1) return false;
726  if (dest == NULL) return true;
727  *(reinterpret_cast<unsigned char*>(dest)) = str[0];
728  return true;
729}
730
731// Largest number spec that we are willing to parse
732static const int kMaxNumberLength = 32;
733
734// PCREQUIPCRES "buf" must have length at least kMaxNumberLength+1
735// PCREQUIPCRES "n > 0"
736// Copies "str" into "buf" and null-terminates if necessary.
737// Returns one of:
738//      a. "str" if no termination is needed
739//      b. "buf" if the string was copied and null-terminated
740//      c. "" if the input was invalid and has no hope of being parsed
741static const char* TerminateNumber(char* buf, const char* str, int n) {
742  if ((n > 0) && isspace(*str)) {
743    // We are less forgiving than the strtoxxx() routines and do not
744    // allow leading spaces.
745    return "";
746  }
747
748  // See if the character right after the input text may potentially
749  // look like a digit.
750  if (isdigit(str[n]) ||
751      ((str[n] >= 'a') && (str[n] <= 'f')) ||
752      ((str[n] >= 'A') && (str[n] <= 'F'))) {
753    if (n > kMaxNumberLength) return ""; // Input too big to be a valid number
754    memcpy(buf, str, n);
755    buf[n] = '\0';
756    return buf;
757  } else {
758    // We can parse right out of the supplied string, so return it.
759    return str;
760  }
761}
762
763bool PCRE::Arg::parse_long_radix(const char* str,
764                               int n,
765                               void* dest,
766                               int radix) {
767  if (n == 0) return false;
768  char buf[kMaxNumberLength+1];
769  str = TerminateNumber(buf, str, n);
770  char* end;
771  errno = 0;
772  long r = strtol(str, &end, radix);
773  if (end != str + n) return false;   // Leftover junk
774  if (errno) return false;
775  if (dest == NULL) return true;
776  *(reinterpret_cast<long*>(dest)) = r;
777  return true;
778}
779
780bool PCRE::Arg::parse_ulong_radix(const char* str,
781                                int n,
782                                void* dest,
783                                int radix) {
784  if (n == 0) return false;
785  char buf[kMaxNumberLength+1];
786  str = TerminateNumber(buf, str, n);
787  if (str[0] == '-') {
788   // strtoul() will silently accept negative numbers and parse
789   // them.  This module is more strict and treats them as errors.
790   return false;
791  }
792
793  char* end;
794  errno = 0;
795  unsigned long r = strtoul(str, &end, radix);
796  if (end != str + n) return false;   // Leftover junk
797  if (errno) return false;
798  if (dest == NULL) return true;
799  *(reinterpret_cast<unsigned long*>(dest)) = r;
800  return true;
801}
802
803bool PCRE::Arg::parse_short_radix(const char* str,
804                                int n,
805                                void* dest,
806                                int radix) {
807  long r;
808  if (!parse_long_radix(str, n, &r, radix)) return false; // Could not parse
809  if ((short)r != r) return false;       // Out of range
810  if (dest == NULL) return true;
811  *(reinterpret_cast<short*>(dest)) = r;
812  return true;
813}
814
815bool PCRE::Arg::parse_ushort_radix(const char* str,
816                                 int n,
817                                 void* dest,
818                                 int radix) {
819  unsigned long r;
820  if (!parse_ulong_radix(str, n, &r, radix)) return false; // Could not parse
821  if ((ushort)r != r) return false;                      // Out of range
822  if (dest == NULL) return true;
823  *(reinterpret_cast<unsigned short*>(dest)) = r;
824  return true;
825}
826
827bool PCRE::Arg::parse_int_radix(const char* str,
828                              int n,
829                              void* dest,
830                              int radix) {
831  long r;
832  if (!parse_long_radix(str, n, &r, radix)) return false; // Could not parse
833  if ((int)r != r) return false;         // Out of range
834  if (dest == NULL) return true;
835  *(reinterpret_cast<int*>(dest)) = r;
836  return true;
837}
838
839bool PCRE::Arg::parse_uint_radix(const char* str,
840                               int n,
841                               void* dest,
842                               int radix) {
843  unsigned long r;
844  if (!parse_ulong_radix(str, n, &r, radix)) return false; // Could not parse
845  if ((uint)r != r) return false;                       // Out of range
846  if (dest == NULL) return true;
847  *(reinterpret_cast<unsigned int*>(dest)) = r;
848  return true;
849}
850
851bool PCRE::Arg::parse_longlong_radix(const char* str,
852                                   int n,
853                                   void* dest,
854                                   int radix) {
855  if (n == 0) return false;
856  char buf[kMaxNumberLength+1];
857  str = TerminateNumber(buf, str, n);
858  char* end;
859  errno = 0;
860  int64 r = strtoll(str, &end, radix);
861  if (end != str + n) return false;   // Leftover junk
862  if (errno) return false;
863  if (dest == NULL) return true;
864  *(reinterpret_cast<int64*>(dest)) = r;
865  return true;
866}
867
868bool PCRE::Arg::parse_ulonglong_radix(const char* str,
869                                    int n,
870                                    void* dest,
871                                    int radix) {
872  if (n == 0) return false;
873  char buf[kMaxNumberLength+1];
874  str = TerminateNumber(buf, str, n);
875  if (str[0] == '-') {
876    // strtoull() will silently accept negative numbers and parse
877    // them.  This module is more strict and treats them as errors.
878    return false;
879  }
880  char* end;
881  errno = 0;
882  uint64 r = strtoull(str, &end, radix);
883  if (end != str + n) return false;   // Leftover junk
884  if (errno) return false;
885  if (dest == NULL) return true;
886  *(reinterpret_cast<uint64*>(dest)) = r;
887  return true;
888}
889
890bool PCRE::Arg::parse_double(const char* str, int n, void* dest) {
891  if (n == 0) return false;
892  static const int kMaxLength = 200;
893  char buf[kMaxLength];
894  if (n >= kMaxLength) return false;
895  memcpy(buf, str, n);
896  buf[n] = '\0';
897  errno = 0;
898  char* end;
899  double r = strtod(buf, &end);
900  if (end != buf + n) {
901#ifdef COMPILER_MSVC
902    // Microsoft's strtod() doesn't handle inf and nan, so we have to
903    // handle it explicitly.  Speed is not important here because this
904    // code is only called in unit tests.
905    bool pos = true;
906    const char* i = buf;
907    if ('-' == *i) {
908      pos = false;
909      ++i;
910    } else if ('+' == *i) {
911      ++i;
912    }
913    if (0 == stricmp(i, "inf") || 0 == stricmp(i, "infinity")) {
914      r = numeric_limits<double>::infinity();
915      if (!pos)
916        r = -r;
917    } else if (0 == stricmp(i, "nan")) {
918      r = numeric_limits<double>::quiet_NaN();
919    } else {
920      return false;
921    }
922#else
923    return false;   // Leftover junk
924#endif
925  }
926  if (errno) return false;
927  if (dest == NULL) return true;
928  *(reinterpret_cast<double*>(dest)) = r;
929  return true;
930}
931
932bool PCRE::Arg::parse_float(const char* str, int n, void* dest) {
933  double r;
934  if (!parse_double(str, n, &r)) return false;
935  if (dest == NULL) return true;
936  *(reinterpret_cast<float*>(dest)) = static_cast<float>(r);
937  return true;
938}
939
940
941#define DEFINE_INTEGER_PARSERS(name)                                        \
942  bool PCRE::Arg::parse_##name(const char* str, int n, void* dest) {          \
943    return parse_##name##_radix(str, n, dest, 10);                          \
944  }                                                                         \
945  bool PCRE::Arg::parse_##name##_hex(const char* str, int n, void* dest) {    \
946    return parse_##name##_radix(str, n, dest, 16);                          \
947  }                                                                         \
948  bool PCRE::Arg::parse_##name##_octal(const char* str, int n, void* dest) {  \
949    return parse_##name##_radix(str, n, dest, 8);                           \
950  }                                                                         \
951  bool PCRE::Arg::parse_##name##_cradix(const char* str, int n, void* dest) { \
952    return parse_##name##_radix(str, n, dest, 0);                           \
953  }
954
955DEFINE_INTEGER_PARSERS(short);
956DEFINE_INTEGER_PARSERS(ushort);
957DEFINE_INTEGER_PARSERS(int);
958DEFINE_INTEGER_PARSERS(uint);
959DEFINE_INTEGER_PARSERS(long);
960DEFINE_INTEGER_PARSERS(ulong);
961DEFINE_INTEGER_PARSERS(longlong);
962DEFINE_INTEGER_PARSERS(ulonglong);
963
964#undef DEFINE_INTEGER_PARSERS
965
966}  // namespace re2
967