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. 26 DEFINE_int32(regexp_stack_limit, 256<<10, "default PCRE stack limit (bytes)"); 27 DEFINE_int32(regexp_match_limit, 1000000, 28 "default PCRE match limit (function calls)"); 29 30 namespace re2 { 31 32 // Maximum number of args we can set 33 static const int kMaxArgs = 16; 34 static 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. 43 static const int kPCREFrameSize = 700; 44 45 // Special name for missing C++ arguments. 46 PCRE::Arg PCRE::no_more_args((void*)NULL); 47 48 const PCRE::PartialMatchFunctor PCRE::PartialMatch = { }; 49 const PCRE::FullMatchFunctor PCRE::FullMatch = { } ; 50 const PCRE::ConsumeFunctor PCRE::Consume = { }; 51 const PCRE::FindAndConsumeFunctor PCRE::FindAndConsume = { }; 52 53 // If a regular expression has no error, its error_ field points here 54 static const string empty_string; 55 56 void 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 80 PCRE::PCRE(const char* pattern) { 81 Init(pattern, None, 0, 0, true); 82 } 83 PCRE::PCRE(const char* pattern, Option option) { 84 Init(pattern, option, 0, 0, true); 85 } 86 PCRE::PCRE(const string& pattern) { 87 Init(pattern.c_str(), None, 0, 0, true); 88 } 89 PCRE::PCRE(const string& pattern, Option option) { 90 Init(pattern.c_str(), option, 0, 0, true); 91 } 92 PCRE::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 97 PCRE::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 102 PCRE::~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 108 pcre* 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 147 bool 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; 183 done: 184 185 int consumed; 186 int vec[kVecSize]; 187 return re.DoMatchImpl(text, ANCHOR_BOTH, &consumed, args, n, vec, kVecSize); 188 } 189 190 bool 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; 226 done: 227 228 int consumed; 229 int vec[kVecSize]; 230 return re.DoMatchImpl(text, UNANCHORED, &consumed, args, n, vec, kVecSize); 231 } 232 233 bool 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; 269 done: 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 282 bool 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; 318 done: 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 331 bool 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 349 int 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 405 bool 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 417 string 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 454 bool PCRE::HitLimit() { 455 return hit_limit_; 456 } 457 458 void PCRE::ClearHitLimit() { 459 hit_limit_ = 0; 460 } 461 462 int 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 558 bool 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 597 bool 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 611 bool 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 647 bool 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. 686 int 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 700 bool 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 705 bool 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 711 bool 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 717 bool 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 724 bool 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 732 static 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 741 static 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 763 bool 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 780 bool 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 803 bool 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 815 bool 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 827 bool 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 839 bool 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 851 bool 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 868 bool 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 890 bool 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 932 bool 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 955 DEFINE_INTEGER_PARSERS(short); 956 DEFINE_INTEGER_PARSERS(ushort); 957 DEFINE_INTEGER_PARSERS(int); 958 DEFINE_INTEGER_PARSERS(uint); 959 DEFINE_INTEGER_PARSERS(long); 960 DEFINE_INTEGER_PARSERS(ulong); 961 DEFINE_INTEGER_PARSERS(longlong); 962 DEFINE_INTEGER_PARSERS(ulonglong); 963 964 #undef DEFINE_INTEGER_PARSERS 965 966 } // namespace re2 967
