cpp/src/phonenumbers/phonenumbermatcher.cc

   1 // Copyright (C) 2011 The Libphonenumber Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 // http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14 //
  15 // Author: Lara Rennie
  16 // Author: Tao Huang
  17 //
  18 // Implementation of a stateful class that finds and extracts telephone numbers
  19 // from text.
  20
  21 #include "phonenumbers/phonenumbermatcher.h"
  22
  23 #ifndef USE_ICU_REGEXP
  24 #error phonenumbermatcher depends on ICU (i.e. USE_ICU_REGEXP must be set)
  25 #endif  // USE_ICU_REGEXP
  26
  27 #include <ctype.h>
  28 #include <limits>
  29 #include <stddef.h>
  30 #include <string>
  31 #include <vector>
  32
  33 #include <unicode/uchar.h>
  34
  35 #include "base/logging.h"
  36 #include "base/memory/scoped_ptr.h"
  37 #include "base/memory/singleton.h"
  38 #include "phonenumbers/default_logger.h"
  39 #include "phonenumbers/encoding_utils.h"
  40 #include "phonenumbers/normalize_utf8.h"
  41 #include "phonenumbers/phonemetadata.pb.h"
  42 #include "phonenumbers/phonenumber.pb.h"
  43 #include "phonenumbers/phonenumbermatch.h"
  44 #include "phonenumbers/phonenumberutil.h"
  45 #include "phonenumbers/regexp_adapter.h"
  46 #include "phonenumbers/regexp_adapter_icu.h"
  47 #include "phonenumbers/stringutil.h"
  48
  49 #ifdef USE_RE2
  50 #include "phonenumbers/regexp_adapter_re2.h"
  51 #endif  // USE_RE2_AND_ICU
  52
  53 using std::numeric_limits;
  54 using std::string;
  55 using std::vector;
  56
  57 namespace i18n {
  58 namespace phonenumbers {
  59
  60 namespace {
  61 // Returns a regular expression quantifier with an upper and lower limit.
  62 string Limit(int lower, int upper) {
  63   DCHECK_GE(lower, 0);
  64   DCHECK_GT(upper, 0);
  65   DCHECK_LT(lower, upper);
  66   return StrCat("{", lower, ",", upper, "}");
  67 }
  68
  69 bool IsInvalidPunctuationSymbol(char32 character) {
  70   return character == '%' || u_charType(character) == U_CURRENCY_SYMBOL;
  71 }
  72
  73 // Helper method to get the national-number part of a number, formatted without
  74 // any national prefix, and return it as a set of digit blocks that would be
  75 // formatted together.
  76 void GetNationalNumberGroups(const PhoneNumberUtil& util,
  77                              const PhoneNumber& number,
  78                              vector<string>* digit_blocks) {
  79   // This will be in the format +CC-DG;ext=EXT where DG represents groups of
  80   // digits.
  81   string rfc3966_format;
  82   util.Format(number, PhoneNumberUtil::RFC3966, &rfc3966_format);
  83   // We remove the extension part from the formatted string before splitting it
  84   // into different groups.
  85   size_t end_index = rfc3966_format.find(';');
  86   if (end_index == string::npos) {
  87     end_index = rfc3966_format.length();
  88   }
  89   // The country-code will have a '-' following it.
  90   size_t start_index = rfc3966_format.find('-') + 1;
  91   SplitStringUsing(rfc3966_format.substr(start_index, end_index - start_index),
  92                    "-", digit_blocks);
  93 }
  94
  95 bool ContainsOnlyValidXChars(const PhoneNumber& number, const string& candidate,
  96                              const PhoneNumberUtil& util) {
  97   // The characters 'x' and 'X' can be (1) a carrier code, in which case they
  98   // always precede the national significant number or (2) an extension sign,
  99   // in which case they always precede the extension number. We assume a
 100   // carrier code is more than 1 digit, so the first case has to have more than
 101   // 1 consecutive 'x' or 'X', whereas the second case can only have exactly 1
 102   // 'x' or 'X'.
 103   size_t found;
 104   found = candidate.find_first_of("xX");
 105   // We ignore the character if 'x' or 'X' appears as the last character of
 106   // the string.
 107   while (found != string::npos && found < candidate.length() - 1) {
 108     // We only look for 'x' or 'X' in ASCII form.
 109     char next_char = candidate[found + 1];
 110     if (next_char == 'x' || next_char == 'X') {
 111       // This is the carrier code case, in which the 'X's always precede the
 112       // national significant number.
 113       ++found;
 114       if (util.IsNumberMatchWithOneString(
 115               number, candidate.substr(found, candidate.length() - found))
 116           != PhoneNumberUtil::NSN_MATCH) {
 117         return false;
 118       }
 119     } else {
 120       string normalized_extension(candidate.substr(found,
 121                                                    candidate.length() - found));
 122       util.NormalizeDigitsOnly(&normalized_extension);
 123       if (normalized_extension != number.extension()) {
 124         return false;
 125       }
 126     }
 127     found = candidate.find_first_of("xX", found + 1);
 128   }
 129   return true;
 130 }
 131 }  // namespace
 132
 133 #ifdef USE_GOOGLE_BASE
 134 class PhoneNumberMatcherRegExps {
 135   friend struct DefaultSingletonTraits<PhoneNumberMatcherRegExps>;
 136 #else
 137 class PhoneNumberMatcherRegExps : public Singleton<PhoneNumberMatcherRegExps> {
 138   friend class Singleton<PhoneNumberMatcherRegExps>;
 139 #endif  // USE_GOOGLE_BASE
 140  private:
 141   string opening_parens_;
 142   string closing_parens_;
 143   string non_parens_;
 144   // Limit on the number of pairs of brackets in a phone number.
 145   string bracket_pair_limit_;
 146   // Helper strings for the matching_brackets_ pattern.
 147   // An opening bracket at the beginning may not be closed, but subsequent ones
 148   // should be. It's also possible that the leading bracket was dropped, so we
 149   // shouldn't be surprised if we see a closing bracket first.
 150   string leading_maybe_matched_bracket_;
 151   string bracket_pairs_;
 152   // Limit on the number of leading (plus) characters.
 153   string lead_limit_;
 154   // Limit on the number of consecutive punctuation characters.
 155   string punctuation_limit_;
 156   // The maximum number of digits allowed in a digit-separated block. As we
 157   // allow all digits in a single block, this should be set high enough to
 158   // accommodate the entire national number and the international country code.
 159   int digit_block_limit_;
 160   // Limit on the number of blocks separated by punctuation. Uses
 161   // kDigitBlockLimit since some formats use spaces to separate each digit.
 162   string block_limit_;
 163   // A punctuation sequence allowing white space.
 164   string punctuation_;
 165   // A digits block without punctuation.
 166   string digit_sequence_;
 167   // Punctuation that may be at the start of a phone number - brackets and plus
 168   // signs.
 169   string lead_class_chars_;
 170   // Same as lead_class_chars_, but enclosed as a character class.
 171   string lead_class_;
 172   // Extra helper strings that form part of pattern_. These are stored
 173   // separately since StrCat has a limit of 12 args.
 174   string opening_punctuation_;
 175   string optional_extn_pattern_;
 176
 177  public:
 178   // We use two different reg-ex factories here for performance reasons. RE2 is
 179   // much faster for smaller reg-ex patterns, but the main pattern cannot be
 180   // handled by RE2 in an efficient way.
 181   scoped_ptr<const AbstractRegExpFactory> regexp_factory_for_pattern_;
 182   scoped_ptr<const AbstractRegExpFactory> regexp_factory_;
 183
 184   // Matches strings that look like publication pages. Example:
 185   // Computing Complete Answers to Queries in the Presence of Limited Access
 186   // Patterns. Chen Li. VLDB J. 12(3): 211-227 (2003).
 187   //
 188   // The string "211-227 (2003)" is not a telephone number.
 189   scoped_ptr<const RegExp> pub_pages_;
 190   // Matches strings that look like dates using "/" as a separator. Examples:
 191   // 3/10/2011, 31/10/96 or 08/31/95.
 192   scoped_ptr<const RegExp> slash_separated_dates_;
 193   // Matches timestamps. Examples: "2012-01-02 08:00". Note that the reg-ex does
 194   // not include trailing ":\d\d" -- that is covered by time_stamps_suffix_.
 195   scoped_ptr<const RegExp> time_stamps_;
 196   scoped_ptr<const RegExp> time_stamps_suffix_;
 197   // Pattern to check that brackets match. Opening brackets should be closed
 198   // within a phone number. This also checks that there is something inside the
 199   // brackets. Having no brackets at all is also fine.
 200   scoped_ptr<const RegExp> matching_brackets_;
 201   // Matches white-space, which may indicate the end of a phone number and the
 202   // start of something else (such as a neighbouring zip-code). If white-space
 203   // is found, continues to match all characters that are not typically used to
 204   // start a phone number.
 205   scoped_ptr<const RegExp> group_separator_;
 206   scoped_ptr<const RegExp> capture_up_to_second_number_start_pattern_;
 207   scoped_ptr<const RegExp> capturing_ascii_digits_pattern_;
 208   // Compiled reg-ex representing lead_class_;
 209   scoped_ptr<const RegExp> lead_class_pattern_;
 210   // Phone number pattern allowing optional punctuation.
 211   scoped_ptr<const RegExp> pattern_;
 212
 213 #ifdef USE_GOOGLE_BASE
 214   static PhoneNumberMatcherRegExps* GetInstance() {
 215     return Singleton<PhoneNumberMatcherRegExps>::get();
 216   }
 217 #endif  // USE_GOOGLE_BASE
 218
 219   PhoneNumberMatcherRegExps()
 220       : opening_parens_("(\\[\xEF\xBC\x88\xEF\xBC\xBB" /* "(\\[（［" */),
 221         closing_parens_(")\\]\xEF\xBC\x89\xEF\xBC\xBD" /* ")\\]）］" */),
 222         non_parens_(StrCat("[^", opening_parens_, closing_parens_, "]")),
 223         bracket_pair_limit_(Limit(0, 3)),
 224         leading_maybe_matched_bracket_(StrCat(
 225             "(?:[", opening_parens_, "])?",
 226             "(?:", non_parens_, "+[", closing_parens_, "])?")),
 227         bracket_pairs_(StrCat(
 228             "(?:[", opening_parens_, "]", non_parens_, "+",
 229             "[", closing_parens_, "])", bracket_pair_limit_)),
 230         lead_limit_(Limit(0, 2)),
 231         punctuation_limit_(Limit(0, 4)),
 232         digit_block_limit_(PhoneNumberUtil::kMaxLengthForNsn +
 233                            PhoneNumberUtil::kMaxLengthCountryCode),
 234         block_limit_(Limit(0, digit_block_limit_)),
 235         punctuation_(StrCat("[", PhoneNumberUtil::kValidPunctuation, "]",
 236                             punctuation_limit_)),
 237         digit_sequence_(StrCat("\\p{Nd}", Limit(1, digit_block_limit_))),
 238         lead_class_chars_(StrCat(opening_parens_, PhoneNumberUtil::kPlusChars)),
 239         lead_class_(StrCat("[", lead_class_chars_, "]")),
 240         opening_punctuation_(StrCat("(?:", lead_class_, punctuation_, ")")),
 241         optional_extn_pattern_(StrCat(
 242             "(?i)(?:",
 243             PhoneNumberUtil::GetInstance()->GetExtnPatternsForMatching(),
 244             ")?")),
 245         regexp_factory_for_pattern_(new ICURegExpFactory()),
 246 #ifdef USE_RE2
 247         regexp_factory_(new RE2RegExpFactory()),
 248 #else
 249         regexp_factory_(new ICURegExpFactory()),
 250 #endif  // USE_RE2
 251         pub_pages_(regexp_factory_->CreateRegExp(
 252             "\\d{1,5}-+\\d{1,5}\\s{0,4}\\(\\d{1,4}")),
 253         slash_separated_dates_(regexp_factory_->CreateRegExp(
 254             "(?:(?:[0-3]?\\d/[01]?\\d)|"
 255             "(?:[01]?\\d/[0-3]?\\d))/(?:[12]\\d)?\\d{2}")),
 256         time_stamps_(regexp_factory_->CreateRegExp(
 257             "[12]\\d{3}[-/]?[01]\\d[-/]?[0-3]\\d [0-2]\\d$")),
 258         time_stamps_suffix_(regexp_factory_->CreateRegExp(":[0-5]\\d")),
 259         matching_brackets_(regexp_factory_->CreateRegExp(
 260             StrCat(leading_maybe_matched_bracket_, non_parens_, "+",
 261                    bracket_pairs_, non_parens_, "*"))),
 262         group_separator_(regexp_factory_->CreateRegExp(
 263             StrCat("\\p{Z}", "[^", lead_class_chars_, "\\p{Nd}]*"))),
 264         capture_up_to_second_number_start_pattern_(
 265             regexp_factory_->CreateRegExp(
 266                 PhoneNumberUtil::kCaptureUpToSecondNumberStart)),
 267         capturing_ascii_digits_pattern_(
 268             regexp_factory_->CreateRegExp("(\\d+)")),
 269         lead_class_pattern_(regexp_factory_->CreateRegExp(lead_class_)),
 270         pattern_(regexp_factory_for_pattern_->CreateRegExp(
 271             StrCat("(", opening_punctuation_, lead_limit_,
 272                    digit_sequence_, "(?:", punctuation_, digit_sequence_, ")",
 273                    block_limit_, optional_extn_pattern_, ")"))) {
 274   }
 275
 276  private:
 277   DISALLOW_COPY_AND_ASSIGN(PhoneNumberMatcherRegExps);
 278 };
 279
 280 PhoneNumberMatcher::PhoneNumberMatcher(const PhoneNumberUtil& util,
 281                                        const string& text,
 282                                        const string& region_code,
 283                                        PhoneNumberMatcher::Leniency leniency,
 284                                        int max_tries)
 285     : reg_exps_(PhoneNumberMatcherRegExps::GetInstance()),
 286       phone_util_(util),
 287       text_(text),
 288       preferred_region_(region_code),
 289       leniency_(leniency),
 290       max_tries_(max_tries),
 291       state_(NOT_READY),
 292       last_match_(NULL),
 293       search_index_(0) {
 294 }
 295
 296 PhoneNumberMatcher::PhoneNumberMatcher(const string& text,
 297                                        const string& region_code)
 298     : reg_exps_(PhoneNumberMatcherRegExps::GetInstance()),
 299       phone_util_(*PhoneNumberUtil::GetInstance()),
 300       text_(text),
 301       preferred_region_(region_code),
 302       leniency_(VALID),
 303       max_tries_(numeric_limits<int>::max()),
 304       state_(NOT_READY),
 305       last_match_(NULL),
 306       search_index_(0) {
 307 }
 308
 309 PhoneNumberMatcher::~PhoneNumberMatcher() {
 310 }
 311
 312 // static
 313 bool PhoneNumberMatcher::IsLatinLetter(char32 letter) {
 314   // Combining marks are a subset of non-spacing-mark.
 315   if (!u_isalpha(letter) && (u_charType(letter) != U_NON_SPACING_MARK)) {
 316     return false;
 317   }
 318   UBlockCode block = ublock_getCode(letter);
 319   return ((block == UBLOCK_BASIC_LATIN) ||
 320       (block == UBLOCK_LATIN_1_SUPPLEMENT) ||
 321       (block == UBLOCK_LATIN_EXTENDED_A) ||
 322       (block == UBLOCK_LATIN_EXTENDED_ADDITIONAL) ||
 323       (block == UBLOCK_LATIN_EXTENDED_B) ||
 324       (block == UBLOCK_COMBINING_DIACRITICAL_MARKS));
 325 }
 326
 327 bool PhoneNumberMatcher::ParseAndVerify(const string& candidate, int offset,
 328                                         PhoneNumberMatch* match) {
 329   DCHECK(match);
 330   // Check the candidate doesn't contain any formatting which would indicate
 331   // that it really isn't a phone number.
 332   if (!reg_exps_->matching_brackets_->FullMatch(candidate)) {
 333     return false;
 334   }
 335
 336   // If leniency is set to VALID or stricter, we also want to skip numbers that
 337   // are surrounded by Latin alphabetic characters, to skip cases like
 338   // abc8005001234 or 8005001234def.
 339   if (leniency_ >= VALID) {
 340     // If the candidate is not at the start of the text, and does not start with
 341     // phone-number punctuation, check the previous character.
 342     scoped_ptr<RegExpInput> candidate_input(
 343         reg_exps_->regexp_factory_->CreateInput(candidate));
 344     if (offset > 0 &&
 345         !reg_exps_->lead_class_pattern_->Consume(candidate_input.get())) {
 346       char32 previous_char;
 347       const char* previous_char_ptr =
 348           EncodingUtils::BackUpOneUTF8Character(text_.c_str(),
 349                                                 text_.c_str() + offset);
 350       EncodingUtils::DecodeUTF8Char(previous_char_ptr, &previous_char);
 351       // We return false if it is a latin letter or an invalid punctuation
 352       // symbol.
 353       if (IsInvalidPunctuationSymbol(previous_char) ||
 354           IsLatinLetter(previous_char)) {
 355         return false;
 356       }
 357     }
 358     size_t lastCharIndex = offset + candidate.length();
 359     if (lastCharIndex < text_.length()) {
 360       char32 next_char;
 361       const char* next_char_ptr =
 362           EncodingUtils::AdvanceOneUTF8Character(
 363               text_.c_str() + lastCharIndex - 1);
 364       EncodingUtils::DecodeUTF8Char(next_char_ptr, &next_char);
 365       if (IsInvalidPunctuationSymbol(next_char) || IsLatinLetter(next_char)) {
 366         return false;
 367       }
 368     }
 369   }
 370
 371   PhoneNumber number;
 372   if (phone_util_.ParseAndKeepRawInput(candidate, preferred_region_, &number) !=
 373       PhoneNumberUtil::NO_PARSING_ERROR) {
 374     return false;
 375   }
 376   if (VerifyAccordingToLeniency(leniency_, number, candidate)) {
 377     match->set_start(offset);
 378     match->set_raw_string(candidate);
 379     // We used ParseAndKeepRawInput to create this number, but for now we don't
 380     // return the extra values parsed. TODO: stop clearing all values here and
 381     // switch all users over to using raw_input() rather than the raw_string()
 382     // of PhoneNumberMatch.
 383     number.clear_country_code_source();
 384     number.clear_preferred_domestic_carrier_code();
 385     number.clear_raw_input();
 386     match->set_number(number);
 387     return true;
 388   }
 389   return false;
 390 }
 391
 392 // Helper method to replace the verification method for each enum in the Java
 393 // version.
 394 bool PhoneNumberMatcher::VerifyAccordingToLeniency(
 395     Leniency leniency, const PhoneNumber& number,
 396     const string& candidate) const {
 397   switch (leniency) {
 398     case PhoneNumberMatcher::POSSIBLE:
 399       return phone_util_.IsPossibleNumber(number);
 400     case PhoneNumberMatcher::VALID:
 401       if (!phone_util_.IsValidNumber(number) ||
 402           !ContainsOnlyValidXChars(number, candidate, phone_util_)) {
 403         return false;
 404       }
 405       return IsNationalPrefixPresentIfRequired(number);
 406     case PhoneNumberMatcher::STRICT_GROUPING: {
 407       if (!phone_util_.IsValidNumber(number) ||
 408           !ContainsOnlyValidXChars(number, candidate, phone_util_) ||
 409           // Two or more slashes were present.
 410           (FindNth(candidate, '/', 2) != string::npos) ||
 411           !IsNationalPrefixPresentIfRequired(number)) {
 412         return false;
 413       }
 414       // TODO(lararennie,shaopengjia): Evaluate how this works for other locales
 415       // (testing has been limited to NANPA regions) and optimise if necessary.
 416       string normalized_candidate =
 417           NormalizeUTF8::NormalizeDecimalDigits(candidate);
 418       vector<string> formatted_number_groups;
 419       GetNationalNumberGroups(phone_util_, number, &formatted_number_groups);
 420       size_t from_index = 0;
 421       // Check each group of consecutive digits are not broken into separate
 422       // groups in the normalized_candidate string.
 423       for (size_t i = 0; i < formatted_number_groups.size(); ++i) {
 424         // Fails if the substring of normalized_candidate starting from
 425         // from_index doesn't contain the consecutive digits in digit_group.
 426         from_index = normalized_candidate.find(formatted_number_groups.at(i),
 427                                                from_index);
 428         if (from_index == string::npos) {
 429           return false;
 430         }
 431         // Moves from_index forward.
 432         from_index += formatted_number_groups.at(i).length();
 433         if (i == 0 && from_index < normalized_candidate.length()) {
 434           // We are at the position right after the NDC. Note although
 435           // normalized_candidate might contain non-ASCII formatting characters,
 436           // they won't be treated as ASCII digits when converted to a char.
 437           if (isdigit(normalized_candidate.at(from_index))) {
 438             // This means there is no formatting symbol after the NDC. In this
 439             // case, we only accept the number if there is no formatting
 440             // symbol at all in the number, except for extensions.
 441             string national_significant_number;
 442             phone_util_.GetNationalSignificantNumber(
 443                 number, &national_significant_number);
 444             return HasPrefixString(
 445                 normalized_candidate.substr(
 446                     from_index - formatted_number_groups.at(i).length()),
 447                 national_significant_number);
 448           }
 449         }
 450       }
 451       // The check here makes sure that we haven't mistakenly already used the
 452       // extension to match the last group of the subscriber number. Note the
 453       // extension cannot have formatting in-between digits.
 454       return
 455           normalized_candidate.substr(from_index).find(number.extension()) !=
 456           string::npos;
 457     }
 458     case PhoneNumberMatcher::EXACT_GROUPING: {
 459       if (!phone_util_.IsValidNumber(number) ||
 460           !ContainsOnlyValidXChars(number, candidate, phone_util_) ||
 461           // Two or more slashes were present.
 462           (FindNth(candidate, '/', 2) != string::npos) ||
 463           !IsNationalPrefixPresentIfRequired(number)) {
 464         return false;
 465       }
 466       // TODO(lararennie,shaopengjia): Evaluate how this works for other locales
 467       // (testing has been limited to NANPA regions) and optimise if necessary.
 468       vector<string> candidate_groups;
 469       string normalized_candidate =
 470           NormalizeUTF8::NormalizeDecimalDigits(candidate);
 471       const scoped_ptr<RegExpInput> candidate_number(
 472           reg_exps_->regexp_factory_->CreateInput(normalized_candidate));
 473       string digit_block;
 474       while (reg_exps_->capturing_ascii_digits_pattern_->FindAndConsume(
 475                  candidate_number.get(),
 476                  &digit_block)) {
 477         candidate_groups.push_back(digit_block);
 478       }
 479
 480       // Set this to the last group, skipping it if the number has an extension.
 481       int candidate_number_group_index =
 482           number.has_extension() ? candidate_groups.size() - 2
 483                                  : candidate_groups.size() - 1;
 484       // First we check if the national significant number is formatted as a
 485       // block. We use contains and not equals, since the national significant
 486       // number may be present with a prefix such as a national number prefix,
 487       // or the country code itself.
 488       string national_significant_number;
 489       phone_util_.GetNationalSignificantNumber(number,
 490                                                &national_significant_number);
 491       if (candidate_groups.size() == 1 ||
 492           candidate_groups.at(candidate_number_group_index).find(
 493               national_significant_number) != string::npos) {
 494         return true;
 495       }
 496       vector<string> formatted_number_groups;
 497       GetNationalNumberGroups(phone_util_, number, &formatted_number_groups);
 498       // Starting from the end, go through in reverse, excluding the first
 499       // group, and check the candidate and number groups are the same.
 500       for (int formatted_number_group_index =
 501                (formatted_number_groups.size() - 1);
 502            formatted_number_group_index > 0 &&
 503            candidate_number_group_index >= 0;
 504            --formatted_number_group_index, --candidate_number_group_index) {
 505         if (candidate_groups.at(candidate_number_group_index) !=
 506             formatted_number_groups.at(formatted_number_group_index)) {
 507           return false;
 508         }
 509       }
 510       // Now check the first group. There may be a national prefix at the start,
 511       // so we only check that the candidate group ends with the formatted
 512       // number group.
 513       return (candidate_number_group_index >= 0 &&
 514               HasSuffixString(candidate_groups.at(candidate_number_group_index),
 515                               formatted_number_groups.at(0)));
 516     }
 517     default:
 518       LOG(ERROR) << "No implementation defined for verification for leniency "
 519                  << static_cast<int>(leniency);
 520       return false;
 521   }
 522 }
 523
 524 bool PhoneNumberMatcher::ExtractInnerMatch(const string& candidate, int offset,
 525                                            PhoneNumberMatch* match) {
 526   DCHECK(match);
 527   // Try removing either the first or last "group" in the number and see if this
 528   // gives a result. We consider white space to be a possible indication of
 529   // the start or end of the phone number.
 530   scoped_ptr<RegExpInput> candidate_input(
 531       reg_exps_->regexp_factory_->CreateInput(candidate));
 532   if (reg_exps_->group_separator_->FindAndConsume(candidate_input.get(),
 533                                                   NULL)) {
 534     // Try the first group by itself.
 535     int group_start_index =
 536         candidate.length() - candidate_input->ToString().length();
 537     string first_group_only = candidate.substr(0, group_start_index);
 538     phone_util_.TrimUnwantedEndChars(&first_group_only);
 539     bool success = ParseAndVerify(first_group_only, offset, match);
 540     if (success) {
 541       return true;
 542     }
 543     --max_tries_;
 544
 545     // Try the rest of the candidate without the first group.
 546     string without_first_group(candidate_input->ToString());
 547     phone_util_.TrimUnwantedEndChars(&without_first_group);
 548     success =
 549         ParseAndVerify(without_first_group, offset + group_start_index, match);
 550     if (success) {
 551       return true;
 552     }
 553     --max_tries_;
 554
 555     if (max_tries_ > 0) {
 556       while (reg_exps_->group_separator_->FindAndConsume(candidate_input.get(),
 557                                                          NULL)) {
 558         // Find the last group.
 559       }
 560       int last_group_start =
 561           candidate.length() - candidate_input->ToString().length();
 562       string without_last_group = candidate.substr(0, last_group_start);
 563       phone_util_.TrimUnwantedEndChars(&without_last_group);
 564       if (without_last_group == first_group_only) {
 565         // If there are only two groups, then the group "without the last group"
 566         // is the same as the first group. In these cases, we don't want to
 567         // re-check the number group, so we exit already.
 568         return false;
 569       }
 570       success = ParseAndVerify(without_last_group, offset, match);
 571       if (success) {
 572         return true;
 573       }
 574       --max_tries_;
 575     }
 576   }
 577   return false;
 578 }
 579
 580 bool PhoneNumberMatcher::ExtractMatch(const string& candidate, int offset,
 581                                       PhoneNumberMatch* match) {
 582   DCHECK(match);
 583   // Skip a match that is more likely a publication page reference or a date.
 584   if (reg_exps_->pub_pages_->PartialMatch(candidate) ||
 585       reg_exps_->slash_separated_dates_->PartialMatch(candidate)) {
 586     return false;
 587   }
 588   // Skip potential time-stamps.
 589   if (reg_exps_->time_stamps_->PartialMatch(candidate)) {
 590     scoped_ptr<RegExpInput> following_text(
 591         reg_exps_->regexp_factory_->CreateInput(
 592             text_.substr(offset + candidate.size())));
 593     if (reg_exps_->time_stamps_suffix_->Consume(following_text.get())) {
 594       return false;
 595     }
 596   }
 597
 598   // Try to come up with a valid match given the entire candidate.
 599   if (ParseAndVerify(candidate, offset, match)) {
 600     return true;
 601   }
 602
 603   // If that failed, try to find an "inner match" - there might be a phone
 604   // number within this candidate.
 605   return ExtractInnerMatch(candidate, offset, match);
 606 }
 607
 608 bool PhoneNumberMatcher::HasNext() {
 609   if (state_ == NOT_READY) {
 610     PhoneNumberMatch temp_match;
 611     if (!Find(search_index_, &temp_match)) {
 612       state_ = DONE;
 613     } else {
 614       last_match_.reset(new PhoneNumberMatch(temp_match.start(),
 615                                              temp_match.raw_string(),
 616                                              temp_match.number()));
 617       search_index_ = last_match_->end();
 618       state_ = READY;
 619     }
 620   }
 621   return state_ == READY;
 622 }
 623
 624 bool PhoneNumberMatcher::Next(PhoneNumberMatch* match) {
 625   DCHECK(match);
 626   // Check the state and find the next match as a side-effect if necessary.
 627   if (!HasNext()) {
 628     return false;
 629   }
 630   match->CopyFrom(*last_match_);
 631   state_ = NOT_READY;
 632   last_match_.reset(NULL);
 633   return true;
 634 }
 635
 636 bool PhoneNumberMatcher::Find(int index, PhoneNumberMatch* match) {
 637   DCHECK(match);
 638
 639   scoped_ptr<RegExpInput> text(
 640       reg_exps_->regexp_factory_for_pattern_->CreateInput(text_.substr(index)));
 641   string candidate;
 642   while ((max_tries_ > 0) &&
 643          reg_exps_->pattern_->FindAndConsume(text.get(), &candidate)) {
 644     int start = text_.length() - text->ToString().length() - candidate.length();
 645     // Check for extra numbers at the end.
 646     reg_exps_->capture_up_to_second_number_start_pattern_->
 647         PartialMatch(candidate, &candidate);
 648     if (ExtractMatch(candidate, start, match)) {
 649       return true;
 650     }
 651
 652     index = start + candidate.length();
 653     --max_tries_;
 654   }
 655   return false;
 656 }
 657
 658 bool PhoneNumberMatcher::IsNationalPrefixPresentIfRequired(
 659     const PhoneNumber& number) const {
 660   // First, check how we deduced the country code. If it was written in
 661   // international format, then the national prefix is not required.
 662   if (number.country_code_source() != PhoneNumber::FROM_DEFAULT_COUNTRY) {
 663     return true;
 664   }
 665   string phone_number_region;
 666   phone_util_.GetRegionCodeForCountryCode(
 667       number.country_code(), &phone_number_region);
 668   const PhoneMetadata* metadata =
 669       phone_util_.GetMetadataForRegion(phone_number_region);
 670   if (!metadata) {
 671     return true;
 672   }
 673   // Check if a national prefix should be present when formatting this number.
 674   string national_number;
 675   phone_util_.GetNationalSignificantNumber(number, &national_number);
 676   const NumberFormat* format_rule =
 677       phone_util_.ChooseFormattingPatternForNumber(metadata->number_format(),
 678                                                    national_number);
 679   // To do this, we check that a national prefix formatting rule was present and
 680   // that it wasn't just the first-group symbol ($1) with punctuation.
 681   if (format_rule && !format_rule->national_prefix_formatting_rule().empty()) {
 682     if (format_rule->national_prefix_optional_when_formatting()) {
 683       // The national-prefix is optional in these cases, so we don't need to
 684       // check if it was present.
 685       return true;
 686     }
 687     // Remove the first-group symbol.
 688     string candidate_national_prefix_rule(
 689         format_rule->national_prefix_formatting_rule());
 690     // We assume that the first-group symbol will never be _before_ the national
 691     // prefix.
 692     candidate_national_prefix_rule.erase(
 693         candidate_national_prefix_rule.find("$1"));
 694     phone_util_.NormalizeDigitsOnly(&candidate_national_prefix_rule);
 695     if (candidate_national_prefix_rule.empty()) {
 696       // National Prefix not needed for this number.
 697       return true;
 698     }
 699     // Normalize the remainder.
 700     string raw_input_copy(number.raw_input());
 701     // Check if we found a national prefix and/or carrier code at the start of
 702     // the raw input, and return the result.
 703     phone_util_.NormalizeDigitsOnly(&raw_input_copy);
 704     return phone_util_.MaybeStripNationalPrefixAndCarrierCode(
 705         *metadata,
 706         &raw_input_copy,
 707         NULL);  // Don't need to keep the stripped carrier code.
 708   }
 709   return true;
 710 }
 711
 712 }  // namespace phonenumbers
 713 }  // namespace i18n