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 I18N_PHONENUMBERS_USE_ICU_REGEXP
  24 #error phonenumbermatcher depends on ICU \
  25     (i.e. I18N_PHONENUMBERS_USE_ICU_REGEXP must be set)
  26 #endif  // I18N_PHONENUMBERS_USE_ICU_REGEXP
  27
  28 #include <ctype.h>
  29 #include <stddef.h>
  30 #include <limits>
  31 #include <map>
  32 #include <string>
  33 #include <utility>
  34 #include <vector>
  35
  36 #include <unicode/uchar.h>
  37
  38 #include "phonenumbers/alternate_format.h"
  39 #include "phonenumbers/base/logging.h"
  40 #include "phonenumbers/base/memory/scoped_ptr.h"
  41 #include "phonenumbers/base/memory/singleton.h"
  42 #include "phonenumbers/callback.h"
  43 #include "phonenumbers/default_logger.h"
  44 #include "phonenumbers/encoding_utils.h"
  45 #include "phonenumbers/normalize_utf8.h"
  46 #include "phonenumbers/phonemetadata.pb.h"
  47 #include "phonenumbers/phonenumber.pb.h"
  48 #include "phonenumbers/phonenumbermatch.h"
  49 #include "phonenumbers/phonenumberutil.h"
  50 #include "phonenumbers/regexp_adapter.h"
  51 #include "phonenumbers/regexp_adapter_icu.h"
  52 #include "phonenumbers/stringutil.h"
  53
  54 #ifdef I18N_PHONENUMBERS_USE_RE2
  55 #include "phonenumbers/regexp_adapter_re2.h"
  56 #endif  // I18N_PHONENUMBERS_USE_RE2_AND_ICU
  57
  58 using std::make_pair;
  59 using std::map;
  60 using std::numeric_limits;
  61 using std::string;
  62 using std::vector;
  63
  64 namespace i18n {
  65 namespace phonenumbers {
  66
  67 namespace {
  68 // Returns a regular expression quantifier with an upper and lower limit.
  69 string Limit(int lower, int upper) {
  70   DCHECK_GE(lower, 0);
  71   DCHECK_GT(upper, 0);
  72   DCHECK_LT(lower, upper);
  73   return StrCat("{", lower, ",", upper, "}");
  74 }
  75
  76 bool IsInvalidPunctuationSymbol(char32 character) {
  77   return character == '%' || u_charType(character) == U_CURRENCY_SYMBOL;
  78 }
  79
  80 bool ContainsOnlyValidXChars(const PhoneNumber& number, const string& candidate,
  81                              const PhoneNumberUtil& util) {
  82   // The characters 'x' and 'X' can be (1) a carrier code, in which case they
  83   // always precede the national significant number or (2) an extension sign,
  84   // in which case they always precede the extension number. We assume a
  85   // carrier code is more than 1 digit, so the first case has to have more than
  86   // 1 consecutive 'x' or 'X', whereas the second case can only have exactly 1
  87   // 'x' or 'X'.
  88   size_t found;
  89   found = candidate.find_first_of("xX");
  90   // We ignore the character if 'x' or 'X' appears as the last character of
  91   // the string.
  92   while (found != string::npos && found < candidate.length() - 1) {
  93     // We only look for 'x' or 'X' in ASCII form.
  94     char next_char = candidate[found + 1];
  95     if (next_char == 'x' || next_char == 'X') {
  96       // This is the carrier code case, in which the 'X's always precede the
  97       // national significant number.
  98       ++found;
  99       if (util.IsNumberMatchWithOneString(
 100               number, candidate.substr(found, candidate.length() - found))
 101           != PhoneNumberUtil::NSN_MATCH) {
 102         return false;
 103       }
 104     } else {
 105       string normalized_extension(candidate.substr(found,
 106                                                    candidate.length() - found));
 107       util.NormalizeDigitsOnly(&normalized_extension);
 108       if (normalized_extension != number.extension()) {
 109         return false;
 110       }
 111     }
 112     found = candidate.find_first_of("xX", found + 1);
 113   }
 114   return true;
 115 }
 116
 117 bool AllNumberGroupsRemainGrouped(
 118     const PhoneNumberUtil& util,
 119     const PhoneNumber& number,
 120     const string& normalized_candidate,
 121     const vector<string>& formatted_number_groups) {
 122   size_t from_index = 0;
 123   if (number.country_code_source() != PhoneNumber::FROM_DEFAULT_COUNTRY) {
 124     // First skip the country code if the normalized candidate contained it.
 125     string country_code = SimpleItoa(number.country_code());
 126     from_index = normalized_candidate.find(country_code) + country_code.size();
 127   }
 128   // Check each group of consecutive digits are not broken into separate
 129   // groupings in the normalized_candidate string.
 130   for (size_t i = 0; i < formatted_number_groups.size(); ++i) {
 131     // Fails if the substring of normalized_candidate starting from from_index
 132     // doesn't contain the consecutive digits in formatted_number_groups.at(i).
 133     from_index = normalized_candidate.find(formatted_number_groups.at(i),
 134                                            from_index);
 135     if (from_index == string::npos) {
 136       return false;
 137     }
 138     // Moves from_index forward.
 139     from_index += formatted_number_groups.at(i).length();
 140     if (i == 0 && from_index < normalized_candidate.length()) {
 141       // We are at the position right after the NDC. We get the region used for
 142       // formatting information based on the country code in the phone number,
 143       // rather than the number itself, as we do not need to distinguish between
 144       // different countries with the same country calling code and this is
 145       // faster.
 146       string region;
 147       util.GetRegionCodeForCountryCode(number.country_code(), &region);
 148       string ndd_prefix;
 149       util.GetNddPrefixForRegion(region, true, &ndd_prefix);
 150       // Note although normalized_candidate might contain non-ASCII formatting
 151       // characters, they won't be treated as ASCII digits when converted to a
 152       // char.
 153       if (!ndd_prefix.empty() && isdigit(normalized_candidate.at(from_index))) {
 154         // This means there is no formatting symbol after the NDC. In this case,
 155         // we only accept the number if there is no formatting symbol at all in
 156         // the number, except for extensions. This is only important for
 157         // countries with national prefixes.
 158         string national_significant_number;
 159         util.GetNationalSignificantNumber(number, &national_significant_number);
 160         return HasPrefixString(normalized_candidate.substr(
 161             from_index - formatted_number_groups.at(i).length()),
 162             national_significant_number);
 163         }
 164       }
 165     }
 166     // The check here makes sure that we haven't mistakenly already used the
 167     // extension to match the last group of the subscriber number. Note the
 168     // extension cannot have formatting in-between digits.
 169     return normalized_candidate.substr(from_index)
 170         .find(number.extension()) != string::npos;
 171 }
 172
 173 bool LoadAlternateFormats(PhoneMetadataCollection* alternate_formats) {
 174 #if defined(I18N_PHONENUMBERS_USE_ALTERNATE_FORMATS)
 175   if (!alternate_formats->ParseFromArray(alternate_format_get(),
 176                                          alternate_format_size())) {
 177     LOG(ERROR) << "Could not parse binary data.";
 178     return false;
 179   }
 180   return true;
 181 #else
 182   return false;
 183 #endif
 184 }
 185
 186 }  // namespace
 187
 188 class PhoneNumberMatcherRegExps : public Singleton<PhoneNumberMatcherRegExps> {
 189  private:
 190   friend class Singleton<PhoneNumberMatcherRegExps>;
 191
 192   string opening_parens_;
 193   string closing_parens_;
 194   string non_parens_;
 195   // Limit on the number of pairs of brackets in a phone number.
 196   string bracket_pair_limit_;
 197   // Helper strings for the matching_brackets_ pattern.
 198   // An opening bracket at the beginning may not be closed, but subsequent ones
 199   // should be. It's also possible that the leading bracket was dropped, so we
 200   // shouldn't be surprised if we see a closing bracket first.
 201   string leading_maybe_matched_bracket_;
 202   string bracket_pairs_;
 203   // Limit on the number of leading (plus) characters.
 204   string lead_limit_;
 205   // Limit on the number of consecutive punctuation characters.
 206   string punctuation_limit_;
 207   // The maximum number of digits allowed in a digit-separated block. As we
 208   // allow all digits in a single block, this should be set high enough to
 209   // accommodate the entire national number and the international country code.
 210   int digit_block_limit_;
 211   // Limit on the number of blocks separated by punctuation. Uses
 212   // kDigitBlockLimit since some formats use spaces to separate each digit.
 213   string block_limit_;
 214   // A punctuation sequence allowing white space.
 215   string punctuation_;
 216   // A digits block without punctuation.
 217   string digit_sequence_;
 218   // Punctuation that may be at the start of a phone number - brackets and plus
 219   // signs.
 220   string lead_class_chars_;
 221   // Same as lead_class_chars_, but enclosed as a character class.
 222   string lead_class_;
 223   // Extra helper strings that form part of pattern_. These are stored
 224   // separately since StrCat has a limit of 12 args.
 225   string opening_punctuation_;
 226   string optional_extn_pattern_;
 227
 228  public:
 229   // We use two different reg-ex factories here for performance reasons. RE2 is
 230   // much faster for smaller reg-ex patterns, but the main pattern cannot be
 231   // handled by RE2 in an efficient way.
 232   scoped_ptr<const AbstractRegExpFactory> regexp_factory_for_pattern_;
 233   scoped_ptr<const AbstractRegExpFactory> regexp_factory_;
 234
 235   // Matches strings that look like publication pages. Example:
 236   // Computing Complete Answers to Queries in the Presence of Limited Access
 237   // Patterns. Chen Li. VLDB J. 12(3): 211-227 (2003).
 238   //
 239   // The string "211-227 (2003)" is not a telephone number.
 240   scoped_ptr<const RegExp> pub_pages_;
 241   // Matches strings that look like dates using "/" as a separator. Examples:
 242   // 3/10/2011, 31/10/96 or 08/31/95.
 243   scoped_ptr<const RegExp> slash_separated_dates_;
 244   // Matches timestamps. Examples: "2012-01-02 08:00". Note that the reg-ex does
 245   // not include trailing ":\d\d" -- that is covered by time_stamps_suffix_.
 246   scoped_ptr<const RegExp> time_stamps_;
 247   scoped_ptr<const RegExp> time_stamps_suffix_;
 248   // Pattern to check that brackets match. Opening brackets should be closed
 249   // within a phone number. This also checks that there is something inside the
 250   // brackets. Having no brackets at all is also fine.
 251   scoped_ptr<const RegExp> matching_brackets_;
 252   // Patterns used to extract phone numbers from a larger phone-number-like
 253   // pattern. These are ordered according to specificity. For example,
 254   // white-space is last since that is frequently used in numbers, not just to
 255   // separate two numbers. We have separate patterns since we don't want to
 256   // break up the phone-number-like text on more than one different kind of
 257   // symbol at one time, although symbols of the same type (e.g. space) can be
 258   // safely grouped together.
 259   //
 260   // Note that if there is a match, we will always check any text found up to
 261   // the first match as well.
 262   scoped_ptr<vector<const RegExp*> > inner_matches_;
 263   scoped_ptr<const RegExp> capture_up_to_second_number_start_pattern_;
 264   scoped_ptr<const RegExp> capturing_ascii_digits_pattern_;
 265   // Compiled reg-ex representing lead_class_;
 266   scoped_ptr<const RegExp> lead_class_pattern_;
 267   // Phone number pattern allowing optional punctuation.
 268   scoped_ptr<const RegExp> pattern_;
 269
 270   PhoneNumberMatcherRegExps()
 271       : opening_parens_("(\\[\xEF\xBC\x88\xEF\xBC\xBB" /* "(\\[（［" */),
 272         closing_parens_(")\\]\xEF\xBC\x89\xEF\xBC\xBD" /* ")\\]）］" */),
 273         non_parens_(StrCat("[^", opening_parens_, closing_parens_, "]")),
 274         bracket_pair_limit_(Limit(0, 3)),
 275         leading_maybe_matched_bracket_(StrCat(
 276             "(?:[", opening_parens_, "])?",
 277             "(?:", non_parens_, "+[", closing_parens_, "])?")),
 278         bracket_pairs_(StrCat(
 279             "(?:[", opening_parens_, "]", non_parens_, "+",
 280             "[", closing_parens_, "])", bracket_pair_limit_)),
 281         lead_limit_(Limit(0, 2)),
 282         punctuation_limit_(Limit(0, 4)),
 283         digit_block_limit_(PhoneNumberUtil::kMaxLengthForNsn +
 284                            PhoneNumberUtil::kMaxLengthCountryCode),
 285         block_limit_(Limit(0, digit_block_limit_)),
 286         punctuation_(StrCat("[", PhoneNumberUtil::kValidPunctuation, "]",
 287                             punctuation_limit_)),
 288         digit_sequence_(StrCat("\\p{Nd}", Limit(1, digit_block_limit_))),
 289         lead_class_chars_(StrCat(opening_parens_, PhoneNumberUtil::kPlusChars)),
 290         lead_class_(StrCat("[", lead_class_chars_, "]")),
 291         opening_punctuation_(StrCat("(?:", lead_class_, punctuation_, ")")),
 292         optional_extn_pattern_(StrCat(
 293             "(?i)(?:",
 294             PhoneNumberUtil::GetInstance()->GetExtnPatternsForMatching(),
 295             ")?")),
 296         regexp_factory_for_pattern_(new ICURegExpFactory()),
 297 #ifdef I18N_PHONENUMBERS_USE_RE2
 298         regexp_factory_(new RE2RegExpFactory()),
 299 #else
 300         regexp_factory_(new ICURegExpFactory()),
 301 #endif  // I18N_PHONENUMBERS_USE_RE2
 302         pub_pages_(regexp_factory_->CreateRegExp(
 303             "\\d{1,5}-+\\d{1,5}\\s{0,4}\\(\\d{1,4}")),
 304         slash_separated_dates_(regexp_factory_->CreateRegExp(
 305             "(?:(?:[0-3]?\\d/[01]?\\d)|"
 306             "(?:[01]?\\d/[0-3]?\\d))/(?:[12]\\d)?\\d{2}")),
 307         time_stamps_(regexp_factory_->CreateRegExp(
 308             "[12]\\d{3}[-/]?[01]\\d[-/]?[0-3]\\d +[0-2]\\d$")),
 309         time_stamps_suffix_(regexp_factory_->CreateRegExp(":[0-5]\\d")),
 310         matching_brackets_(regexp_factory_->CreateRegExp(
 311             StrCat(leading_maybe_matched_bracket_, non_parens_, "+",
 312                    bracket_pairs_, non_parens_, "*"))),
 313         inner_matches_(new vector<const RegExp*>()),
 314         capture_up_to_second_number_start_pattern_(
 315             regexp_factory_->CreateRegExp(
 316                 PhoneNumberUtil::kCaptureUpToSecondNumberStart)),
 317         capturing_ascii_digits_pattern_(
 318             regexp_factory_->CreateRegExp("(\\d+)")),
 319         lead_class_pattern_(regexp_factory_->CreateRegExp(lead_class_)),
 320         pattern_(regexp_factory_for_pattern_->CreateRegExp(
 321             StrCat("(", opening_punctuation_, lead_limit_,
 322                    digit_sequence_, "(?:", punctuation_, digit_sequence_, ")",
 323                    block_limit_, optional_extn_pattern_, ")"))) {
 324     inner_matches_->push_back(
 325         // Breaks on the slash - e.g. "651-234-2345/332-445-1234"
 326         regexp_factory_->CreateRegExp("/+(.*)"));
 327     inner_matches_->push_back(
 328         // Note that the bracket here is inside the capturing group, since we
 329         // consider it part of the phone number. Will match a pattern like
 330         // "(650) 223 3345 (754) 223 3321".
 331         regexp_factory_->CreateRegExp("(\\([^(]*)"));
 332     inner_matches_->push_back(
 333         // Breaks on a hyphen - e.g. "12345 - 332-445-1234 is my number." We
 334         // require a space on either side of the hyphen for it to be considered
 335         // a separator.
 336         regexp_factory_->CreateRegExp("(?:\\p{Z}-|-\\p{Z})\\p{Z}*(.+)"));
 337     inner_matches_->push_back(
 338         // Various types of wide hyphens. Note we have decided not to enforce a
 339         // space here, since it's possible that it's supposed to be used to
 340         // break two numbers without spaces, and we haven't seen many instances
 341         // of it used within a number.
 342         regexp_factory_->CreateRegExp(
 343             "[\xE2\x80\x92-\x2D\xE2\x80\x95\xEF\xBC\x8D]" /* "‒-―－" */
 344             "\\p{Z}*(.+)"));
 345     inner_matches_->push_back(
 346         // Breaks on a full stop - e.g. "12345. 332-445-1234 is my number."
 347         regexp_factory_->CreateRegExp("\\.+\\p{Z}*([^.]+)"));
 348     inner_matches_->push_back(
 349         // Breaks on space - e.g. "3324451234 8002341234"
 350         regexp_factory_->CreateRegExp("\\p{Z}+(\\P{Z}+)"));
 351   }
 352
 353  private:
 354   DISALLOW_COPY_AND_ASSIGN(PhoneNumberMatcherRegExps);
 355 };
 356
 357 class AlternateFormats : public Singleton<AlternateFormats> {
 358  public:
 359   PhoneMetadataCollection format_data_;
 360
 361   map<int, const PhoneMetadata*> calling_code_to_alternate_formats_map_;
 362
 363   AlternateFormats()
 364       : format_data_(),
 365         calling_code_to_alternate_formats_map_() {
 366     if (!LoadAlternateFormats(&format_data_)) {
 367       LOG(DFATAL) << "Could not parse compiled-in metadata.";
 368       return;
 369     }
 370     for (RepeatedPtrField<PhoneMetadata>::const_iterator it =
 371              format_data_.metadata().begin();
 372          it != format_data_.metadata().end();
 373          ++it) {
 374       calling_code_to_alternate_formats_map_.insert(
 375           make_pair(it->country_code(), &*it));
 376     }
 377   }
 378
 379   const PhoneMetadata* GetAlternateFormatsForCountry(int country_calling_code)
 380       const {
 381     map<int, const PhoneMetadata*>::const_iterator it =
 382         calling_code_to_alternate_formats_map_.find(country_calling_code);
 383     if (it != calling_code_to_alternate_formats_map_.end()) {
 384       return it->second;
 385     }
 386     return NULL;
 387   }
 388
 389  private:
 390   DISALLOW_COPY_AND_ASSIGN(AlternateFormats);
 391 };
 392
 393 PhoneNumberMatcher::PhoneNumberMatcher(const PhoneNumberUtil& util,
 394                                        const string& text,
 395                                        const string& region_code,
 396                                        PhoneNumberMatcher::Leniency leniency,
 397                                        int max_tries)
 398     : reg_exps_(PhoneNumberMatcherRegExps::GetInstance()),
 399       alternate_formats_(AlternateFormats::GetInstance()),
 400       phone_util_(util),
 401       text_(text),
 402       preferred_region_(region_code),
 403       leniency_(leniency),
 404       max_tries_(max_tries),
 405       state_(NOT_READY),
 406       last_match_(NULL),
 407       search_index_(0) {
 408 }
 409
 410 PhoneNumberMatcher::PhoneNumberMatcher(const string& text,
 411                                        const string& region_code)
 412     : reg_exps_(PhoneNumberMatcherRegExps::GetInstance()),
 413       alternate_formats_(NULL),  // Not used.
 414       phone_util_(*PhoneNumberUtil::GetInstance()),
 415       text_(text),
 416       preferred_region_(region_code),
 417       leniency_(VALID),
 418       max_tries_(numeric_limits<int>::max()),
 419       state_(NOT_READY),
 420       last_match_(NULL),
 421       search_index_(0) {
 422 }
 423
 424 PhoneNumberMatcher::~PhoneNumberMatcher() {
 425 }
 426
 427 // static
 428 bool PhoneNumberMatcher::IsLatinLetter(char32 letter) {
 429   // Combining marks are a subset of non-spacing-mark.
 430   if (!u_isalpha(letter) && (u_charType(letter) != U_NON_SPACING_MARK)) {
 431     return false;
 432   }
 433   UBlockCode block = ublock_getCode(letter);
 434   return ((block == UBLOCK_BASIC_LATIN) ||
 435       (block == UBLOCK_LATIN_1_SUPPLEMENT) ||
 436       (block == UBLOCK_LATIN_EXTENDED_A) ||
 437       (block == UBLOCK_LATIN_EXTENDED_ADDITIONAL) ||
 438       (block == UBLOCK_LATIN_EXTENDED_B) ||
 439       (block == UBLOCK_COMBINING_DIACRITICAL_MARKS));
 440 }
 441
 442 bool PhoneNumberMatcher::ParseAndVerify(const string& candidate, int offset,
 443                                         PhoneNumberMatch* match) {
 444   DCHECK(match);
 445   // Check the candidate doesn't contain any formatting which would indicate
 446   // that it really isn't a phone number.
 447   if (!reg_exps_->matching_brackets_->FullMatch(candidate) ||
 448       reg_exps_->pub_pages_->PartialMatch(candidate)) {
 449     return false;
 450   }
 451
 452   // If leniency is set to VALID or stricter, we also want to skip numbers that
 453   // are surrounded by Latin alphabetic characters, to skip cases like
 454   // abc8005001234 or 8005001234def.
 455   if (leniency_ >= VALID) {
 456     // If the candidate is not at the start of the text, and does not start with
 457     // phone-number punctuation, check the previous character.
 458     scoped_ptr<RegExpInput> candidate_input(
 459         reg_exps_->regexp_factory_->CreateInput(candidate));
 460     if (offset > 0 &&
 461         !reg_exps_->lead_class_pattern_->Consume(candidate_input.get())) {
 462       char32 previous_char;
 463       const char* previous_char_ptr =
 464           EncodingUtils::BackUpOneUTF8Character(text_.c_str(),
 465                                                 text_.c_str() + offset);
 466       EncodingUtils::DecodeUTF8Char(previous_char_ptr, &previous_char);
 467       // We return false if it is a latin letter or an invalid punctuation
 468       // symbol.
 469       if (IsInvalidPunctuationSymbol(previous_char) ||
 470           IsLatinLetter(previous_char)) {
 471         return false;
 472       }
 473     }
 474     size_t lastCharIndex = offset + candidate.length();
 475     if (lastCharIndex < text_.length()) {
 476       char32 next_char;
 477       const char* next_char_ptr =
 478           EncodingUtils::AdvanceOneUTF8Character(
 479               text_.c_str() + lastCharIndex - 1);
 480       EncodingUtils::DecodeUTF8Char(next_char_ptr, &next_char);
 481       if (IsInvalidPunctuationSymbol(next_char) || IsLatinLetter(next_char)) {
 482         return false;
 483       }
 484     }
 485   }
 486
 487   PhoneNumber number;
 488   if (phone_util_.ParseAndKeepRawInput(candidate, preferred_region_, &number) !=
 489       PhoneNumberUtil::NO_PARSING_ERROR) {
 490     return false;
 491   }
 492
 493
 494   // Check Israel * numbers: these are a special case in that they are
 495   // four-digit numbers that our library supports, but they can only be dialled
 496   // with a leading *. Since we don't actually store or detect the * in our
 497   // phone number library, this means in practice we detect most four digit
 498   // numbers as being valid for Israel. We are considering moving these numbers
 499   // to ShortNumberInfo instead, in which case this problem would go away, but
 500   // in the meantime we want to restrict the false matches so we only allow
 501   // these numbers if they are preceded by a star. We enforce this for all
 502   // leniency levels even though these numbers are technically accepted by
 503   // isPossibleNumber and isValidNumber since we consider it to be a deficiency
 504   // in those methods that they accept these numbers without the *.
 505   // TODO: Remove this or make it significantly less hacky once
 506   // we've decided how to handle these short codes going forward in
 507   // ShortNumberInfo. We could use the formatting rules for instance, but that
 508   // would be slower.
 509   string region_code;
 510   phone_util_.GetRegionCodeForCountryCode(number.country_code(), &region_code);
 511   if (region_code == "IL") {
 512     string national_number;
 513     phone_util_.GetNationalSignificantNumber(number, &national_number);
 514     if (national_number.length() == 4 &&
 515         // Just check the previous char, since * is an ASCII character.
 516         (offset == 0 || (offset > 0 && text_[offset - 1] != '*'))) {
 517       // No match.
 518       return false;
 519     }
 520   }
 521
 522   if (VerifyAccordingToLeniency(leniency_, number, candidate)) {
 523     match->set_start(offset);
 524     match->set_raw_string(candidate);
 525     // We used ParseAndKeepRawInput to create this number, but for now we don't
 526     // return the extra values parsed. TODO: stop clearing all values here and
 527     // switch all users over to using raw_input() rather than the raw_string()
 528     // of PhoneNumberMatch.
 529     number.clear_country_code_source();
 530     number.clear_preferred_domestic_carrier_code();
 531     number.clear_raw_input();
 532     match->set_number(number);
 533     return true;
 534   }
 535   return false;
 536 }
 537
 538 // Helper method to replace the verification method for each enum in the Java
 539 // version.
 540 bool PhoneNumberMatcher::VerifyAccordingToLeniency(
 541     Leniency leniency, const PhoneNumber& number,
 542     const string& candidate) const {
 543   switch (leniency) {
 544     case PhoneNumberMatcher::POSSIBLE:
 545       return phone_util_.IsPossibleNumber(number);
 546     case PhoneNumberMatcher::VALID:
 547       if (!phone_util_.IsValidNumber(number) ||
 548           !ContainsOnlyValidXChars(number, candidate, phone_util_)) {
 549         return false;
 550       }
 551       return IsNationalPrefixPresentIfRequired(number);
 552     case PhoneNumberMatcher::STRICT_GROUPING: {
 553       if (!phone_util_.IsValidNumber(number) ||
 554           !ContainsOnlyValidXChars(number, candidate, phone_util_) ||
 555           ContainsMoreThanOneSlashInNationalNumber(
 556               number, candidate, phone_util_) ||
 557           !IsNationalPrefixPresentIfRequired(number)) {
 558         return false;
 559       }
 560       ResultCallback4<bool, const PhoneNumberUtil&, const PhoneNumber&,
 561                       const string&, const vector<string>&>* callback =
 562           NewPermanentCallback(&AllNumberGroupsRemainGrouped);
 563       bool is_valid = CheckNumberGroupingIsValid(number, candidate, callback);
 564       delete(callback);
 565       return is_valid;
 566     }
 567     case PhoneNumberMatcher::EXACT_GROUPING: {
 568       if (!phone_util_.IsValidNumber(number) ||
 569           !ContainsOnlyValidXChars(number, candidate, phone_util_) ||
 570           ContainsMoreThanOneSlashInNationalNumber(
 571               number, candidate, phone_util_) ||
 572           !IsNationalPrefixPresentIfRequired(number)) {
 573         return false;
 574       }
 575       ResultCallback4<bool, const PhoneNumberUtil&, const PhoneNumber&,
 576                       const string&, const vector<string>&>* callback =
 577           NewPermanentCallback(
 578               this, &PhoneNumberMatcher::AllNumberGroupsAreExactlyPresent);
 579       bool is_valid = CheckNumberGroupingIsValid(number, candidate, callback);
 580       delete(callback);
 581       return is_valid;
 582     }
 583     default:
 584       LOG(ERROR) << "No implementation defined for verification for leniency "
 585                  << static_cast<int>(leniency);
 586       return false;
 587   }
 588 }
 589
 590 bool PhoneNumberMatcher::ExtractInnerMatch(const string& candidate, int offset,
 591                                            PhoneNumberMatch* match) {
 592   DCHECK(match);
 593   for (vector<const RegExp*>::const_iterator regex =
 594            reg_exps_->inner_matches_->begin();
 595            regex != reg_exps_->inner_matches_->end(); regex++) {
 596     scoped_ptr<RegExpInput> candidate_input(
 597         reg_exps_->regexp_factory_->CreateInput(candidate));
 598     bool is_first_match = true;
 599     string group;
 600     while ((*regex)->FindAndConsume(candidate_input.get(), &group) &&
 601            max_tries_ > 0) {
 602       int group_start_index = candidate.length() -
 603           candidate_input->ToString().length() - group.length();
 604       if (is_first_match) {
 605         // We should handle any group before this one too.
 606         string first_group_only = candidate.substr(0, group_start_index);
 607         phone_util_.TrimUnwantedEndChars(&first_group_only);
 608         bool success = ParseAndVerify(first_group_only, offset, match);
 609         if (success) {
 610           return true;
 611         }
 612         --max_tries_;
 613         is_first_match = false;
 614       }
 615       phone_util_.TrimUnwantedEndChars(&group);
 616       bool success = ParseAndVerify(group, offset + group_start_index, match);
 617       if (success) {
 618         return true;
 619       }
 620       --max_tries_;
 621     }
 622   }
 623   return false;
 624 }
 625
 626 bool PhoneNumberMatcher::ExtractMatch(const string& candidate, int offset,
 627                                       PhoneNumberMatch* match) {
 628   DCHECK(match);
 629   // Skip a match that is more likely to be a date.
 630   if (reg_exps_->slash_separated_dates_->PartialMatch(candidate)) {
 631     return false;
 632   }
 633
 634   // Skip potential time-stamps.
 635   if (reg_exps_->time_stamps_->PartialMatch(candidate)) {
 636     scoped_ptr<RegExpInput> following_text(
 637         reg_exps_->regexp_factory_->CreateInput(
 638             text_.substr(offset + candidate.size())));
 639     if (reg_exps_->time_stamps_suffix_->Consume(following_text.get())) {
 640       return false;
 641     }
 642   }
 643
 644   // Try to come up with a valid match given the entire candidate.
 645   if (ParseAndVerify(candidate, offset, match)) {
 646     return true;
 647   }
 648
 649   // If that failed, try to find an "inner match" - there might be a phone
 650   // number within this candidate.
 651   return ExtractInnerMatch(candidate, offset, match);
 652 }
 653
 654 bool PhoneNumberMatcher::HasNext() {
 655   if (state_ == NOT_READY) {
 656     PhoneNumberMatch temp_match;
 657     if (!Find(search_index_, &temp_match)) {
 658       state_ = DONE;
 659     } else {
 660       last_match_.reset(new PhoneNumberMatch(temp_match.start(),
 661                                              temp_match.raw_string(),
 662                                              temp_match.number()));
 663       search_index_ = last_match_->end();
 664       state_ = READY;
 665     }
 666   }
 667   return state_ == READY;
 668 }
 669
 670 bool PhoneNumberMatcher::Next(PhoneNumberMatch* match) {
 671   DCHECK(match);
 672   // Check the state and find the next match as a side-effect if necessary.
 673   if (!HasNext()) {
 674     return false;
 675   }
 676   match->CopyFrom(*last_match_);
 677   state_ = NOT_READY;
 678   last_match_.reset(NULL);
 679   return true;
 680 }
 681
 682 bool PhoneNumberMatcher::Find(int index, PhoneNumberMatch* match) {
 683   DCHECK(match);
 684
 685   scoped_ptr<RegExpInput> text(
 686       reg_exps_->regexp_factory_for_pattern_->CreateInput(text_.substr(index)));
 687   string candidate;
 688   while ((max_tries_ > 0) &&
 689          reg_exps_->pattern_->FindAndConsume(text.get(), &candidate)) {
 690     int start = text_.length() - text->ToString().length() - candidate.length();
 691     // Check for extra numbers at the end.
 692     reg_exps_->capture_up_to_second_number_start_pattern_->
 693         PartialMatch(candidate, &candidate);
 694     if (ExtractMatch(candidate, start, match)) {
 695       return true;
 696     }
 697
 698     index = start + candidate.length();
 699     --max_tries_;
 700   }
 701   return false;
 702 }
 703
 704 bool PhoneNumberMatcher::CheckNumberGroupingIsValid(
 705     const PhoneNumber& phone_number,
 706     const string& candidate,
 707     ResultCallback4<bool, const PhoneNumberUtil&, const PhoneNumber&,
 708                     const string&, const vector<string>&>* checker) const {
 709   DCHECK(checker);
 710   // TODO: Evaluate how this works for other locales (testing has been limited
 711   // to NANPA regions) and optimise if necessary.
 712   string normalized_candidate =
 713       NormalizeUTF8::NormalizeDecimalDigits(candidate);
 714   vector<string> formatted_number_groups;
 715   GetNationalNumberGroups(phone_number, NULL,  // Use default formatting pattern
 716                           &formatted_number_groups);
 717   if (checker->Run(phone_util_, phone_number, normalized_candidate,
 718                    formatted_number_groups)) {
 719     return true;
 720   }
 721   // If this didn't pass, see if there are any alternate formats, and try them
 722   // instead.
 723   const PhoneMetadata* alternate_formats =
 724     alternate_formats_->GetAlternateFormatsForCountry(
 725         phone_number.country_code());
 726   if (alternate_formats) {
 727     for (RepeatedPtrField<NumberFormat>::const_iterator it =
 728              alternate_formats->number_format().begin();
 729          it != alternate_formats->number_format().end(); ++it) {
 730       formatted_number_groups.clear();
 731       GetNationalNumberGroups(phone_number, &*it, &formatted_number_groups);
 732       if (checker->Run(phone_util_, phone_number, normalized_candidate,
 733                        formatted_number_groups)) {
 734         return true;
 735       }
 736     }
 737   }
 738   return false;
 739 }
 740
 741 // Helper method to get the national-number part of a number, formatted without
 742 // any national prefix, and return it as a set of digit blocks that would be
 743 // formatted together.
 744 void PhoneNumberMatcher::GetNationalNumberGroups(
 745     const PhoneNumber& number,
 746     const NumberFormat* formatting_pattern,
 747     vector<string>* digit_blocks) const {
 748   string rfc3966_format;
 749   if (!formatting_pattern) {
 750     // This will be in the format +CC-DG;ext=EXT where DG represents groups of
 751     // digits.
 752     phone_util_.Format(number, PhoneNumberUtil::RFC3966, &rfc3966_format);
 753     // We remove the extension part from the formatted string before splitting
 754     // it into different groups.
 755     size_t end_index = rfc3966_format.find(';');
 756     if (end_index == string::npos) {
 757       end_index = rfc3966_format.length();
 758     }
 759     // The country-code will have a '-' following it.
 760     size_t start_index = rfc3966_format.find('-') + 1;
 761     SplitStringUsing(rfc3966_format.substr(start_index,
 762                                            end_index - start_index),
 763                      "-", digit_blocks);
 764   } else {
 765     // We format the NSN only, and split that according to the separator.
 766     string national_significant_number;
 767     phone_util_.GetNationalSignificantNumber(number,
 768                                              &national_significant_number);
 769     phone_util_.FormatNsnUsingPattern(national_significant_number,
 770                                       *formatting_pattern,
 771                                       PhoneNumberUtil::RFC3966,
 772                                       &rfc3966_format);
 773     SplitStringUsing(rfc3966_format, "-", digit_blocks);
 774   }
 775 }
 776
 777 bool PhoneNumberMatcher::IsNationalPrefixPresentIfRequired(
 778     const PhoneNumber& number) const {
 779   // First, check how we deduced the country code. If it was written in
 780   // international format, then the national prefix is not required.
 781   if (number.country_code_source() != PhoneNumber::FROM_DEFAULT_COUNTRY) {
 782     return true;
 783   }
 784   string phone_number_region;
 785   phone_util_.GetRegionCodeForCountryCode(
 786       number.country_code(), &phone_number_region);
 787   const PhoneMetadata* metadata =
 788       phone_util_.GetMetadataForRegion(phone_number_region);
 789   if (!metadata) {
 790     return true;
 791   }
 792   // Check if a national prefix should be present when formatting this number.
 793   string national_number;
 794   phone_util_.GetNationalSignificantNumber(number, &national_number);
 795   const NumberFormat* format_rule =
 796       phone_util_.ChooseFormattingPatternForNumber(metadata->number_format(),
 797                                                    national_number);
 798   // To do this, we check that a national prefix formatting rule was present and
 799   // that it wasn't just the first-group symbol ($1) with punctuation.
 800   if (format_rule && !format_rule->national_prefix_formatting_rule().empty()) {
 801     if (format_rule->national_prefix_optional_when_formatting()) {
 802       // The national-prefix is optional in these cases, so we don't need to
 803       // check if it was present.
 804       return true;
 805     }
 806     if (phone_util_.FormattingRuleHasFirstGroupOnly(
 807         format_rule->national_prefix_formatting_rule())) {
 808       // National Prefix not needed for this number.
 809       return true;
 810     }
 811     // Normalize the remainder.
 812     string raw_input_copy(number.raw_input());
 813     // Check if we found a national prefix and/or carrier code at the start of
 814     // the raw input, and return the result.
 815     phone_util_.NormalizeDigitsOnly(&raw_input_copy);
 816     return phone_util_.MaybeStripNationalPrefixAndCarrierCode(
 817         *metadata,
 818         &raw_input_copy,
 819         NULL);  // Don't need to keep the stripped carrier code.
 820   }
 821   return true;
 822 }
 823
 824 bool PhoneNumberMatcher::AllNumberGroupsAreExactlyPresent(
 825     const PhoneNumberUtil& util,
 826     const PhoneNumber& phone_number,
 827     const string& normalized_candidate,
 828     const vector<string>& formatted_number_groups) const {
 829   const scoped_ptr<RegExpInput> candidate_number(
 830       reg_exps_->regexp_factory_->CreateInput(normalized_candidate));
 831   vector<string> candidate_groups;
 832   string digit_block;
 833   while (reg_exps_->capturing_ascii_digits_pattern_->FindAndConsume(
 834              candidate_number.get(),
 835              &digit_block)) {
 836     candidate_groups.push_back(digit_block);
 837   }
 838
 839   // Set this to the last group, skipping it if the number has an extension.
 840   int candidate_number_group_index =
 841       phone_number.has_extension() ? candidate_groups.size() - 2
 842                                    : candidate_groups.size() - 1;
 843   // First we check if the national significant number is formatted as a block.
 844   // We use find and not equals, since the national significant number may be
 845   // present with a prefix such as a national number prefix, or the country code
 846   // itself.
 847   string national_significant_number;
 848   util.GetNationalSignificantNumber(phone_number,
 849                                     &national_significant_number);
 850   if (candidate_groups.size() == 1 ||
 851       candidate_groups.at(candidate_number_group_index).find(
 852           national_significant_number) != string::npos) {
 853     return true;
 854   }
 855   // Starting from the end, go through in reverse, excluding the first group,
 856   // and check the candidate and number groups are the same.
 857   for (int formatted_number_group_index =
 858            (formatted_number_groups.size() - 1);
 859        formatted_number_group_index > 0 &&
 860        candidate_number_group_index >= 0;
 861        --formatted_number_group_index, --candidate_number_group_index) {
 862     if (candidate_groups.at(candidate_number_group_index) !=
 863         formatted_number_groups.at(formatted_number_group_index)) {
 864       return false;
 865     }
 866   }
 867   // Now check the first group. There may be a national prefix at the start, so
 868   // we only check that the candidate group ends with the formatted number
 869   // group.
 870   return (candidate_number_group_index >= 0 &&
 871           HasSuffixString(candidate_groups.at(candidate_number_group_index),
 872                           formatted_number_groups.at(0)));
 873 }
 874
 875 // static
 876 bool PhoneNumberMatcher::ContainsMoreThanOneSlashInNationalNumber(
 877     const PhoneNumber& number,
 878     const string& candidate,
 879     const PhoneNumberUtil& util) {
 880   size_t first_slash_in_body = candidate.find('/');
 881   if (first_slash_in_body == string::npos) {
 882     // No slashes, this is okay.
 883     return false;
 884   }
 885   // Now look for a second one.
 886   size_t second_slash_in_body = candidate.find('/', first_slash_in_body + 1);
 887   if (second_slash_in_body == string::npos) {
 888     // Only one slash, this is okay.
 889     return false;
 890   }
 891
 892   // If the first slash is after the country calling code, this is permitted.
 893   if (number.country_code_source() == PhoneNumber::FROM_NUMBER_WITH_PLUS_SIGN ||
 894       number.country_code_source() ==
 895           PhoneNumber::FROM_NUMBER_WITHOUT_PLUS_SIGN) {
 896     string normalized_country_code =
 897         candidate.substr(0, first_slash_in_body);
 898     util.NormalizeDigitsOnly(&normalized_country_code);
 899     if (normalized_country_code == SimpleItoa(number.country_code())) {
 900       // Any more slashes and this is illegal.
 901       return candidate.find('/', second_slash_in_body + 1) != string::npos;
 902     }
 903   }
 904   return true;
 905 }
 906
 907 }  // namespace phonenumbers
 908 }  // namespace i18n