diff options
Diffstat (limited to 'Source/WebKit/android/content')
-rw-r--r-- | Source/WebKit/android/content/PhoneEmailDetector.cpp | 369 | ||||
-rw-r--r-- | Source/WebKit/android/content/PhoneEmailDetector.h | 75 | ||||
-rw-r--r-- | Source/WebKit/android/content/address_detector.cpp | 938 | ||||
-rw-r--r-- | Source/WebKit/android/content/address_detector.h | 131 | ||||
-rw-r--r-- | Source/WebKit/android/content/content_detector.cpp | 86 | ||||
-rw-r--r-- | Source/WebKit/android/content/content_detector.h | 103 |
6 files changed, 1702 insertions, 0 deletions
diff --git a/Source/WebKit/android/content/PhoneEmailDetector.cpp b/Source/WebKit/android/content/PhoneEmailDetector.cpp new file mode 100644 index 0000000..d188c0b --- /dev/null +++ b/Source/WebKit/android/content/PhoneEmailDetector.cpp @@ -0,0 +1,369 @@ +/* + * Copyright (C) 2011 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#undef WEBKIT_IMPLEMENTATION +#undef LOG + +#include "base/utf_string_conversions.h" +#include "net/base/escape.h" +#include "PhoneEmailDetector.h" +#include "WebString.h" + +#define LOG_TAG "PhoneNumberDetector" +#include <cutils/log.h> + +#define PHONE_PATTERN "(200) /-.\\ 100 -. 0000" + +static const char kTelSchemaPrefix[] = "tel:"; +static const char kEmailSchemaPrefix[] = "mailto:"; + +void FindReset(FindState* state); +void FindResetNumber(FindState* state); +FoundState FindPartialNumber(const UChar* chars, unsigned length, + FindState* s); +struct FindState; + +static FoundState FindPartialEMail(const UChar* , unsigned length, FindState* ); +static bool IsDomainChar(UChar ch); +static bool IsMailboxChar(UChar ch); + +PhoneEmailDetector::PhoneEmailDetector() + : m_foundResult(FOUND_NONE) +{ +} + +bool PhoneEmailDetector::FindContent(const string16::const_iterator& begin, + const string16::const_iterator& end, + size_t* start_pos, + size_t* end_pos) +{ + FindReset(&m_findState); + m_foundResult = FindPartialNumber(begin, end - begin, &m_findState); + if (m_foundResult == FOUND_COMPLETE) + m_prefix = kTelSchemaPrefix; + else { + FindReset(&m_findState); + m_foundResult = FindPartialEMail(begin, end - begin, &m_findState); + m_prefix = kEmailSchemaPrefix; + } + *start_pos = m_findState.mStartResult; + *end_pos = m_findState.mEndResult; + return m_foundResult == FOUND_COMPLETE; +} + +std::string PhoneEmailDetector::GetContentText(const WebKit::WebRange& range) +{ + if (m_foundResult == FOUND_COMPLETE) { + if (m_prefix == kTelSchemaPrefix) + return UTF16ToUTF8(m_findState.mStore); + else + return UTF16ToUTF8(range.toPlainText()); + } + return std::string(); +} + +GURL PhoneEmailDetector::GetIntentURL(const std::string& content_text) +{ + return GURL(m_prefix + + EscapeQueryParamValue(content_text, true)); +} + +void FindReset(FindState* state) +{ + memset(state, 0, sizeof(FindState)); + state->mCurrent = ' '; + FindResetNumber(state); +} + +void FindResetNumber(FindState* state) +{ + state->mOpenParen = false; + state->mPattern = (char*) PHONE_PATTERN; + state->mStorePtr = state->mStore; +} + +FoundState FindPartialNumber(const UChar* chars, unsigned length, + FindState* s) +{ + char* pattern = s->mPattern; + UChar* store = s->mStorePtr; + const UChar* start = chars; + const UChar* end = chars + length; + const UChar* lastDigit = 0; + string16 search16(chars, length); + std::string searchSpace = UTF16ToUTF8(search16); + do { + bool initialized = s->mInitialized; + while (chars < end) { + if (initialized == false) { + s->mBackTwo = s->mBackOne; + s->mBackOne = s->mCurrent; + } + UChar ch = s->mCurrent = *chars; + do { + char patternChar = *pattern; + switch (patternChar) { + case '2': + if (initialized == false) { + s->mStartResult = chars - start; + initialized = true; + } + case '0': + case '1': + if (ch < patternChar || ch > '9') + goto resetPattern; + *store++ = ch; + pattern++; + lastDigit = chars; + goto nextChar; + case '\0': + if (WTF::isASCIIDigit(ch) == false) { + *store = '\0'; + goto checkMatch; + } + goto resetPattern; + case ' ': + if (ch == patternChar) + goto nextChar; + break; + case '(': + if (ch == patternChar) { + s->mStartResult = chars - start; + initialized = true; + s->mOpenParen = true; + } + goto commonPunctuation; + case ')': + if ((ch == patternChar) ^ s->mOpenParen) + goto resetPattern; + default: + commonPunctuation: + if (ch == patternChar) { + pattern++; + goto nextChar; + } + } + } while (++pattern); // never false + nextChar: + chars++; + } + break; +resetPattern: + if (s->mContinuationNode) + return FOUND_NONE; + FindResetNumber(s); + pattern = s->mPattern; + store = s->mStorePtr; + } while (++chars < end); +checkMatch: + if (WTF::isASCIIDigit(s->mBackOne != '1' ? s->mBackOne : s->mBackTwo)) { + return FOUND_NONE; + } + *store = '\0'; + s->mStorePtr = store; + s->mPattern = pattern; + s->mEndResult = lastDigit - start + 1; + char pState = pattern[0]; + return pState == '\0' ? FOUND_COMPLETE : pState == '(' || (WTF::isASCIIDigit(pState) && WTF::isASCIIDigit(pattern[-1])) ? + FOUND_NONE : FOUND_PARTIAL; +} + +FoundState FindPartialEMail(const UChar* chars, unsigned length, + FindState* s) +{ + // the following tables were generated by tests/browser/focusNavigation/BrowserDebug.cpp + // hand-edit at your own risk + static const int domainTwoLetter[] = { + 0x02df797c, // a followed by: [cdefgilmnoqrstuwxz] + 0x036e73fb, // b followed by: [abdefghijmnorstvwyz] + 0x03b67ded, // c followed by: [acdfghiklmnorsuvxyz] + 0x02005610, // d followed by: [ejkmoz] + 0x001e00d4, // e followed by: [ceghrstu] + 0x00025700, // f followed by: [ijkmor] + 0x015fb9fb, // g followed by: [abdefghilmnpqrstuwy] + 0x001a3400, // h followed by: [kmnrtu] + 0x000f7818, // i followed by: [delmnoqrst] + 0x0000d010, // j followed by: [emop] + 0x0342b1d0, // k followed by: [eghimnprwyz] + 0x013e0507, // l followed by: [abcikrstuvy] + 0x03fffccd, // m followed by: [acdghklmnopqrstuvwxyz] + 0x0212c975, // n followed by: [acefgilopruz] + 0x00001000, // o followed by: [m] + 0x014e3cf1, // p followed by: [aefghklmnrstwy] + 0x00000001, // q followed by: [a] + 0x00504010, // r followed by: [eouw] + 0x032a7fdf, // s followed by: [abcdeghijklmnortvyz] + 0x026afeec, // t followed by: [cdfghjklmnoprtvwz] + 0x03041441, // u followed by: [agkmsyz] + 0x00102155, // v followed by: [aceginu] + 0x00040020, // w followed by: [fs] + 0x00000000, // x + 0x00180010, // y followed by: [etu] + 0x00401001, // z followed by: [amw] + }; + + static char const* const longDomainNames[] = { + "\x03" "ero" "\x03" "rpa", // aero, arpa + "\x02" "iz", // biz + "\x02" "at" "\x02" "om" "\x03" "oop", // cat, com, coop + NULL, // d + "\x02" "du", // edu + NULL, // f + "\x02" "ov", // gov + NULL, // h + "\x03" "nfo" "\x02" "nt", // info, int + "\x03" "obs", // jobs + NULL, // k + NULL, // l + "\x02" "il" "\x03" "obi" "\x05" "useum", // mil, mobi, museum + "\x03" "ame" "\x02" "et", // name, net + "\x02" "rg", // , org + "\x02" "ro", // pro + NULL, // q + NULL, // r + NULL, // s + "\x05" "ravel", // travel + NULL, // u + NULL, // v + NULL, // w + NULL, // x + NULL, // y + NULL, // z + }; + + const UChar* start = chars; + const UChar* end = chars + length; + while (chars < end) { + UChar ch = *chars++; + if (ch != '@') + continue; + const UChar* atLocation = chars - 1; + // search for domain + ch = *chars++ | 0x20; // convert uppercase to lower + if (ch < 'a' || ch > 'z') + continue; + while (chars < end) { + ch = *chars++; + if (IsDomainChar(ch) == false) + goto nextAt; + if (ch != '.') + continue; + UChar firstLetter = *chars++ | 0x20; // first letter of the domain + if (chars >= end) + return FOUND_NONE; // only one letter; must be at least two + firstLetter -= 'a'; + if (firstLetter > 'z' - 'a') + continue; // non-letter followed '.' + int secondLetterMask = domainTwoLetter[firstLetter]; + ch = *chars | 0x20; // second letter of the domain + ch -= 'a'; + if (ch >= 'z' - 'a') + continue; + bool secondMatch = (secondLetterMask & 1 << ch) != 0; + const char* wordMatch = longDomainNames[firstLetter]; + int wordIndex = 0; + while (wordMatch != NULL) { + int len = *wordMatch++; + char match; + do { + match = wordMatch[wordIndex]; + if (match < 0x20) + goto foundDomainStart; + if (chars[wordIndex] != match) + break; + wordIndex++; + } while (true); + wordMatch += len; + if (*wordMatch == '\0') + break; + wordIndex = 0; + } + if (secondMatch) { + wordIndex = 1; + foundDomainStart: + chars += wordIndex; + if (chars < end) { + ch = *chars; + if (ch != '.') { + if (IsDomainChar(ch)) + goto nextDot; + } else if (chars + 1 < end && IsDomainChar(chars[1])) + goto nextDot; + } + // found domain. Search backwards from '@' for beginning of email address + s->mEndResult = chars - start; + chars = atLocation; + if (chars <= start) + goto nextAt; + ch = *--chars; + if (ch == '.') + goto nextAt; // mailbox can't end in period + do { + if (IsMailboxChar(ch) == false) { + chars++; + break; + } + if (chars == start) + break; + ch = *--chars; + } while (true); + UChar firstChar = *chars; + if (firstChar == '.' || firstChar == '@') // mailbox can't start with period or be empty + goto nextAt; + s->mStartResult = chars - start; + return FOUND_COMPLETE; + } + nextDot: + ; + } +nextAt: + chars = atLocation + 1; + } + return FOUND_NONE; +} + +bool IsDomainChar(UChar ch) +{ + static const unsigned body[] = {0x03ff6000, 0x07fffffe, 0x07fffffe}; // 0-9 . - A-Z a-z + ch -= 0x20; + if (ch > 'z' - 0x20) + return false; + return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0; +} + +bool IsMailboxChar(UChar ch) +{ + // According to http://en.wikipedia.org/wiki/Email_address + // ! # $ % & ' * + - . / 0-9 = ? + // A-Z ^ _ + // ` a-z { | } ~ + static const unsigned body[] = {0xa3ffecfa, 0xc7fffffe, 0x7fffffff}; + ch -= 0x20; + if (ch > '~' - 0x20) + return false; + return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0; +} diff --git a/Source/WebKit/android/content/PhoneEmailDetector.h b/Source/WebKit/android/content/PhoneEmailDetector.h new file mode 100644 index 0000000..b61de62 --- /dev/null +++ b/Source/WebKit/android/content/PhoneEmailDetector.h @@ -0,0 +1,75 @@ +/* + * Copyright (C) 2011 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "content/content_detector.h" +#include "PlatformString.h" + +#define NAVIGATION_MAX_PHONE_LENGTH 14 + +struct FindState { + int mStartResult; + int mEndResult; + char* mPattern; + UChar mStore[NAVIGATION_MAX_PHONE_LENGTH + 1]; + UChar* mStorePtr; + UChar mBackOne; + UChar mBackTwo; + UChar mCurrent; + bool mOpenParen; + bool mInitialized; + bool mContinuationNode; +}; + +enum FoundState { + FOUND_NONE, + FOUND_PARTIAL, + FOUND_COMPLETE +}; + +// Searches for phone numbers (US only) or email addresses based off of the navcache code +class PhoneEmailDetector : public ContentDetector { +public: + PhoneEmailDetector(); + virtual ~PhoneEmailDetector() {} + +private: + // Implementation of ContentDetector. + virtual bool FindContent(const string16::const_iterator& begin, + const string16::const_iterator& end, + size_t* start_pos, + size_t* end_pos); + + virtual std::string GetContentText(const WebKit::WebRange& range); + virtual GURL GetIntentURL(const std::string& content_text); + virtual size_t GetMaximumContentLength() { + return NAVIGATION_MAX_PHONE_LENGTH * 4; + } + + DISALLOW_COPY_AND_ASSIGN(PhoneEmailDetector); + + FindState m_findState; + FoundState m_foundResult; + const char* m_prefix; +}; diff --git a/Source/WebKit/android/content/address_detector.cpp b/Source/WebKit/android/content/address_detector.cpp new file mode 100644 index 0000000..504d37a --- /dev/null +++ b/Source/WebKit/android/content/address_detector.cpp @@ -0,0 +1,938 @@ +/* + * Copyright (C) 2012 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +// Magic pretend-to-be-a-chromium-build flags +#undef WEBKIT_IMPLEMENTATION +#undef LOG + +#include "content/address_detector.h" + +#include <bitset> + +#include "base/utf_string_conversions.h" +#include "net/base/escape.h" +#include "WebString.h" + +#include <wtf/HashSet.h> +#include <wtf/Noncopyable.h> +#include <wtf/text/StringHash.h> +#include <wtf/text/WTFString.h> + +namespace { + +// Prefix used for geographical address intent URIs. +static const char kAddressSchemaPrefix[] = "geo:0,0?q="; + +// Maximum text length to be searched for address detection. +static const size_t kMaxAddressLength = 500; + +// Minimum number of words in an address after the house number +// before a state is expected to be found. +// A value too high can miss short addresses. +const size_t kMinAddressWords = 3; + +// Maximum number of words allowed in an address between the house number +// and the state, both not included. +const size_t kMaxAddressWords = 12; + +// Maximum number of lines allowed in an address between the house number +// and the state, both not included. +const size_t kMaxAddressLines = 5; + +// Maximum length allowed for any address word between the house number +// and the state, both not included. +const size_t kMaxAddressNameWordLength = 25; + +// Maximum number of words after the house number in which the location name +// should be found. +const size_t kMaxLocationNameDistance = 4; + +// Number of digits for a valid zip code. +const size_t kZipDigits = 5; + +// Number of digits for a valid zip code in the Zip Plus 4 format. +const size_t kZipPlus4Digits = 9; + +// Maximum number of digits of a house number, including possible hyphens. +const size_t kMaxHouseDigits = 5; + +// Additional characters used as new line delimiters. +const char16 kNewlineDelimiters[] = { + ',', + '*', + 0x2022, // Unicode bullet +}; + +char16 SafePreviousChar(const string16::const_iterator& it, + const string16::const_iterator& begin) { + if (it == begin) + return ' '; + return *(it - 1); +} + +char16 SafeNextChar(const string16::const_iterator& it, + const string16::const_iterator& end) { + if (it == end) + return ' '; + return *(it + 1); +} + +bool WordLowerCaseEqualsASCII(string16::const_iterator word_begin, + string16::const_iterator word_end, const char* ascii_to_match) { + for (string16::const_iterator it = word_begin; it != word_end; + ++it, ++ascii_to_match) { + if (!*ascii_to_match || base::ToLowerASCII(*it) != *ascii_to_match) + return false; + } + return *ascii_to_match == 0 || *ascii_to_match == ' '; +} + +bool LowerCaseEqualsASCIIWithPlural(string16::const_iterator word_begin, + string16::const_iterator word_end, const char* ascii_to_match, + bool allow_plural) { + for (string16::const_iterator it = word_begin; it != word_end; + ++it, ++ascii_to_match) { + if (!*ascii_to_match && allow_plural && *it == 's' && it + 1 == word_end) + return true; + + if (!*ascii_to_match || base::ToLowerASCII(*it) != *ascii_to_match) + return false; + } + return *ascii_to_match == 0; +} + +} // anonymous namespace + + +AddressDetector::AddressDetector() { +} + +AddressDetector::~AddressDetector() { +} + +std::string AddressDetector::GetContentText(const WebKit::WebRange& range) { + // Get the address and replace unicode bullets with commas. + string16 address_16 = CollapseWhitespace(range.toPlainText(), false); + std::replace(address_16.begin(), address_16.end(), + static_cast<char16>(0x2022), static_cast<char16>(',')); + return UTF16ToUTF8(address_16); +} + +GURL AddressDetector::GetIntentURL(const std::string& content_text) { + return GURL(kAddressSchemaPrefix + + EscapeQueryParamValue(content_text, true)); +} + +size_t AddressDetector::GetMaximumContentLength() { + return kMaxAddressLength; +} + +bool AddressDetector::FindContent(const string16::const_iterator& begin, + const string16::const_iterator& end, size_t* start_pos, size_t* end_pos) { + HouseNumberParser house_number_parser; + + // Keep going through the input string until a potential house number is + // detected. Start tokenizing the following words to find a valid + // street name within a word range. Then, find a state name followed + // by a valid zip code for that state. Also keep a look for any other + // possible house numbers to continue from in case of no match and for + // state names not followed by a zip code (e.g. New York, NY 10000). + const string16 newline_delimiters = kNewlineDelimiters; + const string16 delimiters = kWhitespaceUTF16 + newline_delimiters; + for (string16::const_iterator it = begin; it != end; ) { + Word house_number; + if (!house_number_parser.Parse(it, end, &house_number)) + return false; + + String16Tokenizer tokenizer(house_number.end, end, delimiters); + tokenizer.set_options(String16Tokenizer::RETURN_DELIMS); + + std::vector<Word> words; + words.push_back(house_number); + + bool found_location_name = false; + bool continue_on_house_number = true; + size_t next_house_number_word = 0; + size_t num_lines = 1; + + // Don't include the house number in the word count. + size_t next_word = 1; + for (; next_word <= kMaxAddressWords + 1; ++next_word) { + + // Extract a new word from the tokenizer. + if (next_word == words.size()) { + do { + if (!tokenizer.GetNext()) + return false; + + // Check the number of address lines. + if (tokenizer.token_is_delim() && newline_delimiters.find( + *tokenizer.token_begin()) != string16::npos) { + ++num_lines; + } + } while (tokenizer.token_is_delim()); + + if (num_lines > kMaxAddressLines) + break; + + words.push_back(Word(tokenizer.token_begin(), tokenizer.token_end())); + } + + // Check the word length. If too long, don't try to continue from + // the next house number as no address can hold this word. + const Word& current_word = words[next_word]; + DCHECK_GT(std::distance(current_word.begin, current_word.end), 0); + size_t current_word_length = std::distance( + current_word.begin, current_word.end); + if (current_word_length > kMaxAddressNameWordLength) { + continue_on_house_number = false; + break; + } + + // Check if the new word is a valid house number. + // This is used to properly resume parsing in case the maximum number + // of words is exceeded. + if (next_house_number_word == 0 && + house_number_parser.Parse(current_word.begin, current_word.end, NULL)) { + next_house_number_word = next_word; + continue; + } + + // Look for location names in the words after the house number. + // A range limitation is introduced to avoid matching + // anything that starts with a number before a legitimate address. + if (next_word <= kMaxLocationNameDistance && + IsValidLocationName(current_word)) { + found_location_name = true; + continue; + } + + // Don't count the house number. + if (next_word > kMinAddressWords) { + // Looking for the state is likely to add new words to the list while + // checking for multi-word state names. + size_t state_first_word = next_word; + size_t state_last_word, state_index; + if (FindStateStartingInWord(&words, state_first_word, &state_last_word, + &tokenizer, &state_index)) { + + // A location name should have been found at this point. + if (!found_location_name) + break; + + // Explicitly exclude "et al", as "al" is a valid state code. + if (current_word_length == 2 && words.size() > 2) { + const Word& previous_word = words[state_first_word - 1]; + if (previous_word.end - previous_word.begin == 2 && + LowerCaseEqualsASCII(previous_word.begin, previous_word.end, + "et") && + LowerCaseEqualsASCII(current_word.begin, current_word.end, + "al")) + break; + } + + // Extract one more word from the tokenizer if not already available. + size_t zip_word = state_last_word + 1; + if (zip_word == words.size()) { + do { + if (!tokenizer.GetNext()) { + // Zip is optional + *start_pos = words[0].begin - begin; + *end_pos = words[state_last_word].end - begin; + return true; + } + } while (tokenizer.token_is_delim()); + words.push_back(Word(tokenizer.token_begin(), + tokenizer.token_end())); + } + + // Check the parsing validity and state range of the zip code. + next_word = state_last_word; + if (!IsZipValid(words[zip_word], state_index)) + continue; + + *start_pos = words[0].begin - begin; + *end_pos = words[zip_word].end - begin; + return true; + } + } + } + + // Avoid skipping too many words because of a non-address number + // at the beginning of the contents to parse. + if (continue_on_house_number && next_house_number_word > 0) { + it = words[next_house_number_word].begin; + } else { + DCHECK(!words.empty()); + next_word = std::min(next_word, words.size() - 1); + it = words[next_word].end; + } + } + + return false; +} + +bool AddressDetector::HouseNumberParser::IsPreDelimiter( + char16 character) { + return character == ':' || IsPostDelimiter(character); +} + +bool AddressDetector::HouseNumberParser::IsPostDelimiter( + char16 character) { + return IsWhitespace(character) || strchr(",\"'", character); +} + +void AddressDetector::HouseNumberParser::RestartOnNextDelimiter() { + ResetState(); + for (; it_ != end_ && !IsPreDelimiter(*it_); ++it_) {} +} + +void AddressDetector::HouseNumberParser::AcceptChars(size_t num_chars) { + size_t offset = std::min(static_cast<size_t>(std::distance(it_, end_)), + num_chars); + it_ += offset; + result_chars_ += offset; +} + +void AddressDetector::HouseNumberParser::SkipChars(size_t num_chars) { + it_ += std::min(static_cast<size_t>(std::distance(it_, end_)), num_chars); +} + +void AddressDetector::HouseNumberParser::ResetState() { + num_digits_ = 0; + result_chars_ = 0; +} + +bool AddressDetector::HouseNumberParser::CheckFinished(Word* word) const { + // There should always be a number after a hyphen. + if (result_chars_ == 0 || SafePreviousChar(it_, begin_) == '-') + return false; + + if (word) { + word->begin = it_ - result_chars_; + word->end = it_; + } + return true; +} + +bool AddressDetector::HouseNumberParser::Parse( + const string16::const_iterator& begin, + const string16::const_iterator& end, Word* word) { + it_ = begin_ = begin; + end_ = end; + ResetState(); + + // Iterations only used as a fail-safe against any buggy infinite loops. + size_t iterations = 0; + size_t max_iterations = end - begin + 1; + for (; it_ != end_ && iterations < max_iterations; ++iterations) { + + // Word finished case. + if (IsPostDelimiter(*it_)) { + if (CheckFinished(word)) + return true; + else if (result_chars_) + ResetState(); + + SkipChars(1); + continue; + } + + // More digits. There should be no more after a letter was found. + if (IsAsciiDigit(*it_)) { + if (num_digits_ >= kMaxHouseDigits) { + RestartOnNextDelimiter(); + } else { + AcceptChars(1); + ++num_digits_; + } + continue; + } + + if (IsAsciiAlpha(*it_)) { + // Handle special case 'one'. + if (result_chars_ == 0) { + if (it_ + 3 <= end_ && LowerCaseEqualsASCII(it_, it_ + 3, "one")) + AcceptChars(3); + else + RestartOnNextDelimiter(); + continue; + } + + // There should be more than 1 character because of result_chars. + DCHECK_GT(result_chars_, 0U); + DCHECK_NE(it_, begin_); + char16 previous = SafePreviousChar(it_, begin_); + if (IsAsciiDigit(previous)) { + // Check cases like '12A'. + char16 next = SafeNextChar(it_, end_); + if (IsPostDelimiter(next)) { + AcceptChars(1); + continue; + } + + // Handle cases like 12a, 1st, 2nd, 3rd, 7th. + if (IsAsciiAlpha(next)) { + char16 last_digit = previous; + char16 first_letter = base::ToLowerASCII(*it_); + char16 second_letter = base::ToLowerASCII(next); + bool is_teen = SafePreviousChar(it_ - 1, begin_) == '1' && + num_digits_ == 2; + + switch (last_digit - '0') { + case 1: + if ((first_letter == 's' && second_letter == 't') || + (first_letter == 't' && second_letter == 'h' && is_teen)) { + AcceptChars(2); + continue; + } + break; + + case 2: + if ((first_letter == 'n' && second_letter == 'd') || + (first_letter == 't' && second_letter == 'h' && is_teen)) { + AcceptChars(2); + continue; + } + break; + + case 3: + if ((first_letter == 'r' && second_letter == 'd') || + (first_letter == 't' && second_letter == 'h' && is_teen)) { + AcceptChars(2); + continue; + } + break; + + case 0: + // Explicitly exclude '0th'. + if (num_digits_ == 1) + break; + + case 4: + case 5: + case 6: + case 7: + case 8: + case 9: + if (first_letter == 't' && second_letter == 'h') { + AcceptChars(2); + continue; + } + break; + + default: + NOTREACHED(); + } + } + } + + RestartOnNextDelimiter(); + continue; + } + + if (*it_ == '-' && num_digits_ > 0) { + AcceptChars(1); + ++num_digits_; + continue; + } + + RestartOnNextDelimiter(); + SkipChars(1); + } + + if (iterations >= max_iterations) + return false; + + return CheckFinished(word); +} + +bool AddressDetector::FindStateStartingInWord(WordList* words, + size_t state_first_word, size_t* state_last_word, + String16Tokenizer* tokenizer, size_t* state_index) { + + // Bitmasks containing the allowed suffixes for 2-letter state codes. + static const int state_two_letter_suffix[23] = { + 0x02060c00, // A followed by: [KLRSZ]. + 0x00000000, // B. + 0x00084001, // C followed by: [AOT]. + 0x00000014, // D followed by: [CE]. + 0x00000000, // E. + 0x00001800, // F followed by: [LM]. + 0x00100001, // G followed by: [AU]. + 0x00000100, // H followed by: [I]. + 0x00002809, // I followed by: [ADLN]. + 0x00000000, // J. + 0x01040000, // K followed by: [SY]. + 0x00000001, // L followed by: [A]. + 0x000ce199, // M followed by: [ADEHINOPST]. + 0x0120129c, // N followed by: [CDEHJMVY]. + 0x00020480, // O followed by: [HKR]. + 0x00420001, // P followed by: [ARW]. + 0x00000000, // Q. + 0x00000100, // R followed by: [I]. + 0x0000000c, // S followed by: [CD]. + 0x00802000, // T followed by: [NX]. + 0x00080000, // U followed by: [T]. + 0x00080101, // V followed by: [AIT]. + 0x01200101 // W followed by: [AIVY]. + }; + + // Accumulative number of states for the 2-letter code indexed by the first. + static const int state_two_letter_accumulative[24] = { + 0, 5, 5, 8, 10, 10, 12, 14, + 15, 19, 19, 21, 22, 32, 40, 43, + 46, 46, 47, 49, 51, 52, 55, 59 + }; + + // State names sorted alphabetically with their lengths. + // There can be more than one possible name for a same state if desired. + static const struct StateNameInfo { + const char* string; + char first_word_length; + char length; + char state_index; // Relative to two-character code alphabetical order. + } state_names[59] = { + { "alabama", 7, 7, 1 }, { "alaska", 6, 6, 0 }, + { "american samoa", 8, 14, 3 }, { "arizona", 7, 7, 4 }, + { "arkansas", 8, 8, 2 }, + { "california", 10, 10, 5 }, { "colorado", 8, 8, 6 }, + { "connecticut", 11, 11, 7 }, { "delaware", 8, 8, 9 }, + { "district of columbia", 8, 20, 8 }, + { "federated states of micronesia", 9, 30, 11 }, { "florida", 7, 7, 10 }, + { "guam", 4, 4, 13 }, { "georgia", 7, 7, 12 }, + { "hawaii", 6, 6, 14 }, + { "idaho", 5, 5, 16 }, { "illinois", 8, 8, 17 }, { "indiana", 7, 7, 18 }, + { "iowa", 4, 4, 15 }, + { "kansas", 6, 6, 19 }, { "kentucky", 8, 8, 20 }, + { "louisiana", 9, 9, 21 }, + { "maine", 5, 5, 24 }, { "marshall islands", 8, 16, 25 }, + { "maryland", 8, 8, 23 }, { "massachusetts", 13, 13, 22 }, + { "michigan", 8, 8, 26 }, { "minnesota", 9, 9, 27 }, + { "mississippi", 11, 11, 30 }, { "missouri", 8, 8, 28 }, + { "montana", 7, 7, 31 }, + { "nebraska", 8, 8, 34 }, { "nevada", 6, 6, 38 }, + { "new hampshire", 3, 13, 35 }, { "new jersey", 3, 10, 36 }, + { "new mexico", 3, 10, 37 }, { "new york", 3, 8, 39 }, + { "north carolina", 5, 14, 32 }, { "north dakota", 5, 12, 33 }, + { "northern mariana islands", 8, 24, 29 }, + { "ohio", 4, 4, 40 }, { "oklahoma", 8, 8, 41 }, { "oregon", 6, 6, 42 }, + { "palau", 5, 5, 45 }, { "pennsylvania", 12, 12, 43 }, + { "puerto rico", 6, 11, 44 }, + { "rhode island", 5, 5, 46 }, + { "south carolina", 5, 14, 47 }, { "south dakota", 5, 12, 48 }, + { "tennessee", 9, 9, 49 }, { "texas", 5, 5, 50 }, + { "utah", 4, 4, 51 }, + { "vermont", 7, 7, 54 }, { "virgin islands", 6, 14, 53 }, + { "virginia", 8, 8, 52 }, + { "washington", 10, 10, 55 }, { "west virginia", 4, 13, 57 }, + { "wisconsin", 9, 9, 56 }, { "wyoming", 7, 7, 58 } + }; + + // Accumulative number of states for sorted names indexed by the first letter. + // Required a different one since there are codes that don't share their + // first letter with the name of their state (MP = Northern Mariana Islands). + static const int state_names_accumulative[24] = { + 0, 5, 5, 8, 10, 10, 12, 14, + 15, 19, 19, 21, 22, 31, 40, 43, + 46, 46, 47, 49, 51, 52, 55, 59 + }; + + DCHECK_EQ(state_names_accumulative[arraysize(state_names_accumulative) - 1], + static_cast<int>(ARRAYSIZE_UNSAFE(state_names))); + + const Word& first_word = words->at(state_first_word); + int length = first_word.end - first_word.begin; + if (length < 2 || !IsAsciiAlpha(*first_word.begin)) + return false; + + // No state names start with x, y, z. + char16 first_letter = base::ToLowerASCII(*first_word.begin); + if (first_letter > 'w') + return false; + + DCHECK(first_letter >= 'a'); + int first_index = first_letter - 'a'; + + // Look for two-letter state names. + if (length == 2 && IsAsciiAlpha(*(first_word.begin + 1))) { + char16 second_letter = base::ToLowerASCII(*(first_word.begin + 1)); + DCHECK(second_letter >= 'a'); + + int second_index = second_letter - 'a'; + if (!(state_two_letter_suffix[first_index] & (1 << second_index))) + return false; + + std::bitset<32> previous_suffixes = state_two_letter_suffix[first_index] & + ((1 << second_index) - 1); + *state_last_word = state_first_word; + *state_index = state_two_letter_accumulative[first_index] + + previous_suffixes.count(); + return true; + } + + // Look for full state names by their first letter. Discard by length. + for (int state = state_names_accumulative[first_index]; + state < state_names_accumulative[first_index + 1]; ++state) { + if (state_names[state].first_word_length != length) + continue; + + bool state_match = false; + size_t state_word = state_first_word; + for (int pos = 0; true; ) { + if (!WordLowerCaseEqualsASCII(words->at(state_word).begin, + words->at(state_word).end, &state_names[state].string[pos])) + break; + + pos += words->at(state_word).end - words->at(state_word).begin + 1; + if (pos >= state_names[state].length) { + state_match = true; + break; + } + + // Ran out of words, extract more from the tokenizer. + if (++state_word == words->size()) { + do { + if (!tokenizer->GetNext()) + break; + } while (tokenizer->token_is_delim()); + words->push_back(Word(tokenizer->token_begin(), tokenizer->token_end())); + } + } + + if (state_match) { + *state_last_word = state_word; + *state_index = state_names[state].state_index; + return true; + } + } + + return false; +} + +bool AddressDetector::IsZipValid(const Word& word, size_t state_index) { + size_t length = word.end - word.begin; + if (length != kZipDigits && length != kZipPlus4Digits + 1) + return false; + + for (string16::const_iterator it = word.begin; it != word.end; ++it) { + size_t pos = it - word.begin; + if (IsAsciiDigit(*it) || (*it == '-' && pos == kZipDigits)) + continue; + return false; + } + return IsZipValidForState(word, state_index); +} + +bool AddressDetector::IsZipValidForState(const Word& word, size_t state_index) +{ + enum USState { + AP = -4, // AP (military base in the Pacific) + AA = -3, // AA (military base inside the US) + AE = -2, // AE (military base outside the US) + XX = -1, // (not in use) + AK = 0, // AK Alaska + AL = 1, // AL Alabama + AR = 2, // AR Arkansas + AS = 3, // AS American Samoa + AZ = 4, // AZ Arizona + CA = 5, // CA California + CO = 6, // CO Colorado + CT = 7, // CT Connecticut + DC = 8, // DC District of Columbia + DE = 9, // DE Delaware + FL = 10, // FL Florida + FM = 11, // FM Federated States of Micronesia + GA = 12, // GA Georgia + GU = 13, // GU Guam + HI = 14, // HI Hawaii + IA = 15, // IA Iowa + ID = 16, // ID Idaho + IL = 17, // IL Illinois + IN = 18, // IN Indiana + KS = 19, // KS Kansas + KY = 20, // KY Kentucky + LA = 21, // LA Louisiana + MA = 22, // MA Massachusetts + MD = 23, // MD Maryland + ME = 24, // ME Maine + MH = 25, // MH Marshall Islands + MI = 26, // MI Michigan + MN = 27, // MN Minnesota + MO = 28, // MO Missouri + MP = 29, // MP Northern Mariana Islands + MS = 30, // MS Mississippi + MT = 31, // MT Montana + NC = 32, // NC North Carolina + ND = 33, // ND North Dakota + NE = 34, // NE Nebraska + NH = 35, // NH New Hampshire + NJ = 36, // NJ New Jersey + NM = 37, // NM New Mexico + NV = 38, // NV Nevada + NY = 39, // NY New York + OH = 40, // OH Ohio + OK = 41, // OK Oklahoma + OR = 42, // OR Oregon + PA = 43, // PA Pennsylvania + PR = 44, // PR Puerto Rico + PW = 45, // PW Palau + RI = 46, // RI Rhode Island + SC = 47, // SC South Carolina + SD = 48, // SD South Dakota + TN = 49, // TN Tennessee + TX = 50, // TX Texas + UT = 51, // UT Utah + VA = 52, // VA Virginia + VI = 53, // VI Virgin Islands + VT = 54, // VT Vermont + WA = 55, // WA Washington + WI = 56, // WI Wisconsin + WV = 57, // WV West Virginia + WY = 58, // WY Wyoming + }; + + static const USState stateForZipPrefix[] = { + // 0 1 2 3 4 5 6 7 8 9 + XX, XX, XX, XX, XX, NY, PR, PR, VI, PR, // 000-009 + MA, MA, MA, MA, MA, MA, MA, MA, MA, MA, // 010-019 + MA, MA, MA, MA, MA, MA, MA, MA, RI, RI, // 020-029 + NH, NH, NH, NH, NH, NH, NH, NH, NH, ME, // 030-039 + ME, ME, ME, ME, ME, ME, ME, ME, ME, ME, // 040-049 + VT, VT, VT, VT, VT, MA, VT, VT, VT, VT, // 050-059 + CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, // 060-069 + NJ, NJ, NJ, NJ, NJ, NJ, NJ, NJ, NJ, NJ, // 070-079 + NJ, NJ, NJ, NJ, NJ, NJ, NJ, NJ, NJ, NJ, // 080-089 + AE, AE, AE, AE, AE, AE, AE, AE, AE, XX, // 090-099 + NY, NY, NY, NY, NY, NY, NY, NY, NY, NY, // 100-109 + NY, NY, NY, NY, NY, NY, NY, NY, NY, NY, // 110-119 + NY, NY, NY, NY, NY, NY, NY, NY, NY, NY, // 120-129 + NY, NY, NY, NY, NY, NY, NY, NY, NY, NY, // 130-139 + NY, NY, NY, NY, NY, NY, NY, NY, NY, NY, // 140-149 + PA, PA, PA, PA, PA, PA, PA, PA, PA, PA, // 150-159 + PA, PA, PA, PA, PA, PA, PA, PA, PA, PA, // 160-169 + PA, PA, PA, PA, PA, PA, PA, PA, PA, PA, // 170-179 + PA, PA, PA, PA, PA, PA, PA, PA, PA, PA, // 180-189 + PA, PA, PA, PA, PA, PA, PA, DE, DE, DE, // 190-199 + DC, VA, DC, DC, DC, DC, MD, MD, MD, MD, // 200-209 + MD, MD, MD, XX, MD, MD, MD, MD, MD, MD, // 210-219 + VA, VA, VA, VA, VA, VA, VA, VA, VA, VA, // 220-229 + VA, VA, VA, VA, VA, VA, VA, VA, VA, VA, // 230-239 + VA, VA, VA, VA, VA, VA, VA, WV, WV, WV, // 240-249 + WV, WV, WV, WV, WV, WV, WV, WV, WV, WV, // 250-259 + WV, WV, WV, WV, WV, WV, WV, WV, WV, XX, // 260-269 + NC, NC, NC, NC, NC, NC, NC, NC, NC, NC, // 270-279 + NC, NC, NC, NC, NC, NC, NC, NC, NC, NC, // 280-289 + SC, SC, SC, SC, SC, SC, SC, SC, SC, SC, // 290-299 + GA, GA, GA, GA, GA, GA, GA, GA, GA, GA, // 300-309 + GA, GA, GA, GA, GA, GA, GA, GA, GA, GA, // 310-319 + FL, FL, FL, FL, FL, FL, FL, FL, FL, FL, // 320-329 + FL, FL, FL, FL, FL, FL, FL, FL, FL, FL, // 330-339 + AA, FL, FL, XX, FL, XX, FL, FL, XX, FL, // 340-349 + AL, AL, AL, XX, AL, AL, AL, AL, AL, AL, // 350-359 + AL, AL, AL, AL, AL, AL, AL, AL, AL, AL, // 360-369 + TN, TN, TN, TN, TN, TN, TN, TN, TN, TN, // 370-379 + TN, TN, TN, TN, TN, TN, MS, MS, MS, MS, // 380-389 + MS, MS, MS, MS, MS, MS, MS, MS, GA, GA, // 390-399 + KY, KY, KY, KY, KY, KY, KY, KY, KY, KY, // 400-409 + KY, KY, KY, KY, KY, KY, KY, KY, KY, XX, // 410-419 + KY, KY, KY, KY, KY, KY, KY, KY, XX, XX, // 420-429 + OH, OH, OH, OH, OH, OH, OH, OH, OH, OH, // 430-439 + OH, OH, OH, OH, OH, OH, OH, OH, OH, OH, // 440-449 + OH, OH, OH, OH, OH, OH, OH, OH, OH, OH, // 450-459 + IN, IN, IN, IN, IN, IN, IN, IN, IN, IN, // 460-469 + IN, IN, IN, IN, IN, IN, IN, IN, IN, IN, // 470-479 + MI, MI, MI, MI, MI, MI, MI, MI, MI, MI, // 480-489 + MI, MI, MI, MI, MI, MI, MI, MI, MI, MI, // 490-499 + IA, IA, IA, IA, IA, IA, IA, IA, IA, IA, // 500-509 + IA, IA, IA, IA, IA, IA, IA, XX, XX, XX, // 510-519 + IA, IA, IA, IA, IA, IA, IA, IA, IA, XX, // 520-529 + WI, WI, WI, XX, WI, WI, XX, WI, WI, WI, // 530-539 + WI, WI, WI, WI, WI, WI, WI, WI, WI, WI, // 540-549 + MN, MN, XX, MN, MN, MN, MN, MN, MN, MN, // 550-559 + MN, MN, MN, MN, MN, MN, MN, MN, XX, DC, // 560-569 + SD, SD, SD, SD, SD, SD, SD, SD, XX, XX, // 570-579 + ND, ND, ND, ND, ND, ND, ND, ND, ND, XX, // 580-589 + MT, MT, MT, MT, MT, MT, MT, MT, MT, MT, // 590-599 + IL, IL, IL, IL, IL, IL, IL, IL, IL, IL, // 600-609 + IL, IL, IL, IL, IL, IL, IL, IL, IL, IL, // 610-619 + IL, XX, IL, IL, IL, IL, IL, IL, IL, IL, // 620-629 + MO, MO, XX, MO, MO, MO, MO, MO, MO, MO, // 630-639 + MO, MO, XX, XX, MO, MO, MO, MO, MO, MO, // 640-649 + MO, MO, MO, MO, MO, MO, MO, MO, MO, XX, // 650-659 + KS, KS, KS, XX, KS, KS, KS, KS, KS, KS, // 660-669 + KS, KS, KS, KS, KS, KS, KS, KS, KS, KS, // 670-679 + NE, NE, XX, NE, NE, NE, NE, NE, NE, NE, // 680-689 + NE, NE, NE, NE, XX, XX, XX, XX, XX, XX, // 690-699 + LA, LA, XX, LA, LA, LA, LA, LA, LA, XX, // 700-709 + LA, LA, LA, LA, LA, XX, AR, AR, AR, AR, // 710-719 + AR, AR, AR, AR, AR, AR, AR, AR, AR, AR, // 720-729 + OK, OK, XX, TX, OK, OK, OK, OK, OK, OK, // 730-739 + OK, OK, XX, OK, OK, OK, OK, OK, OK, OK, // 740-749 + TX, TX, TX, TX, TX, TX, TX, TX, TX, TX, // 750-759 + TX, TX, TX, TX, TX, TX, TX, TX, TX, TX, // 760-769 + TX, XX, TX, TX, TX, TX, TX, TX, TX, TX, // 770-779 + TX, TX, TX, TX, TX, TX, TX, TX, TX, TX, // 780-789 + TX, TX, TX, TX, TX, TX, TX, TX, TX, TX, // 790-799 + CO, CO, CO, CO, CO, CO, CO, CO, CO, CO, // 800-809 + CO, CO, CO, CO, CO, CO, CO, XX, XX, XX, // 810-819 + WY, WY, WY, WY, WY, WY, WY, WY, WY, WY, // 820-829 + WY, WY, ID, ID, ID, ID, ID, ID, ID, XX, // 830-839 + UT, UT, UT, UT, UT, UT, UT, UT, XX, XX, // 840-849 + AZ, AZ, AZ, AZ, XX, AZ, AZ, AZ, XX, AZ, // 850-859 + AZ, XX, XX, AZ, AZ, AZ, XX, XX, XX, XX, // 860-869 + NM, NM, NM, NM, NM, NM, XX, NM, NM, NM, // 870-879 + NM, NM, NM, NM, NM, TX, XX, XX, XX, NV, // 880-889 + NV, NV, XX, NV, NV, NV, XX, NV, NV, XX, // 890-899 + CA, CA, CA, CA, CA, CA, CA, CA, CA, XX, // 900-909 + CA, CA, CA, CA, CA, CA, CA, CA, CA, CA, // 910-919 + CA, CA, CA, CA, CA, CA, CA, CA, CA, XX, // 920-929 + CA, CA, CA, CA, CA, CA, CA, CA, CA, CA, // 930-939 + CA, CA, CA, CA, CA, CA, CA, CA, CA, CA, // 940-949 + CA, CA, CA, CA, CA, CA, CA, CA, CA, CA, // 950-959 + CA, CA, AP, AP, AP, AP, AP, HI, HI, GU, // 960-969 + OR, OR, OR, OR, OR, OR, OR, OR, OR, OR, // 970-979 + WA, WA, WA, WA, WA, WA, WA, XX, WA, WA, // 980-989 + WA, WA, WA, WA, WA, AK, AK, AK, AK, AK, // 990-999 + }; + + if (!word.begin || !word.end || (word.end - word.begin) < 3) + return false; + const char16* zipPtr = word.begin; + if (zipPtr[0] < '0' || zipPtr[0] > '9' || + zipPtr[1] < '0' || zipPtr[1] > '9' || + zipPtr[2] < '0' || zipPtr[2] > '9') + return false; + + int zip = zipPtr[0] - '0'; + zip *= 10; + zip += zipPtr[1] - '0'; + zip *= 10; + zip += zipPtr[2] - '0'; + return stateForZipPrefix[zip] == (int) state_index; +} + +static const char* s_rawStreetSuffixes[] = { + "allee", "alley", "ally", "aly", + "anex", "annex", "anx", "arc", "arcade", "av", "ave", "aven", "avenu", + "avenue", "avn", "avnue", "bayoo", "bayou", "bch", "beach", "bend", + "bg", "bgs", "blf", "blfs", "bluf", "bluff", "bluffs", "blvd", "bnd", + "bot", "bottm", "bottom", "boul", "boulevard", "boulv", "br", "branch", + "brdge", "brg", "bridge", "brk", "brks", "brnch", "brook", "brooks", + "btm", "burg", "burgs", "byp", "bypa", "bypas", "bypass", "byps", "byu", + "camp", "canyn", "canyon", "cape", "causeway", "causway", "cen", "cent", + "center", "centers", "centr", "centre", "cir", "circ", "circl", + "circle", "circles", "cirs", "ck", "clb", "clf", "clfs", "cliff", + "cliffs", "club", "cmn", "cmp", "cnter", "cntr", "cnyn", "common", + "cor", "corner", "corners", "cors", "course", "court", "courts", "cove", + "coves", "cp", "cpe", "cr", "crcl", "crcle", "crecent", "creek", "cres", + "crescent", "cresent", "crest", "crk", "crossing", "crossroad", + "crscnt", "crse", "crsent", "crsnt", "crssing", "crssng", "crst", "crt", + "cswy", "ct", "ctr", "ctrs", "cts", "curv", "curve", "cv", "cvs", "cyn", + "dale", "dam", "div", "divide", "dl", "dm", "dr", "driv", "drive", + "drives", "drs", "drv", "dv", "dvd", "est", "estate", "estates", "ests", + "exp", "expr", "express", "expressway", "expw", "expy", "ext", + "extension", "extensions", "extn", "extnsn", "exts", "fall", "falls", + "ferry", "field", "fields", "flat", "flats", "fld", "flds", "fls", + "flt", "flts", "ford", "fords", "forest", "forests", "forg", "forge", + "forges", "fork", "forks", "fort", "frd", "frds", "freeway", "freewy", + "frg", "frgs", "frk", "frks", "frry", "frst", "frt", "frway", "frwy", + "fry", "ft", "fwy", "garden", "gardens", "gardn", "gateway", "gatewy", + "gatway", "gdn", "gdns", "glen", "glens", "gln", "glns", "grden", + "grdn", "grdns", "green", "greens", "grn", "grns", "grov", "grove", + "groves", "grv", "grvs", "gtway", "gtwy", "harb", "harbor", "harbors", + "harbr", "haven", "havn", "hbr", "hbrs", "height", "heights", "hgts", + "highway", "highwy", "hill", "hills", "hiway", "hiwy", "hl", "hllw", + "hls", "hollow", "hollows", "holw", "holws", "hrbor", "ht", "hts", + "hvn", "hway", "hwy", "inlet", "inlt", "is", "island", "islands", + "isle", "isles", "islnd", "islnds", "iss", "jct", "jction", "jctn", + "jctns", "jcts", "junction", "junctions", "junctn", "juncton", "key", + "keys", "knl", "knls", "knol", "knoll", "knolls", "ky", "kys", "la", + "lake", "lakes", "land", "landing", "lane", "lanes", "lck", "lcks", + "ldg", "ldge", "lf", "lgt", "lgts", "light", "lights", "lk", "lks", + "ln", "lndg", "lndng", "loaf", "lock", "locks", "lodg", "lodge", "loop", + "loops", "mall", "manor", "manors", "mdw", "mdws", "meadow", "meadows", + "medows", "mews", "mill", "mills", "mission", "missn", "ml", "mls", + "mnr", "mnrs", "mnt", "mntain", "mntn", "mntns", "motorway", "mount", + "mountain", "mountains", "mountin", "msn", "mssn", "mt", "mtin", "mtn", + "mtns", "mtwy", "nck", "neck", "opas", "orch", "orchard", "orchrd", + "oval", "overpass", "ovl", "park", "parks", "parkway", "parkways", + "parkwy", "pass", "passage", "path", "paths", "pike", "pikes", "pine", + "pines", "pk", "pkway", "pkwy", "pkwys", "pky", "pl", "place", "plain", + "plaines", "plains", "plaza", "pln", "plns", "plz", "plza", "pne", + "pnes", "point", "points", "port", "ports", "pr", "prairie", "prarie", + "prk", "prr", "prt", "prts", "psge", "pt", "pts", "rad", "radial", + "radiel", "radl", "ramp", "ranch", "ranches", "rapid", "rapids", "rd", + "rdg", "rdge", "rdgs", "rds", "rest", "ridge", "ridges", "riv", "river", + "rivr", "rnch", "rnchs", "road", "roads", "route", "row", "rpd", "rpds", + "rst", "rte", "rue", "run", "rvr", "shl", "shls", "shoal", "shoals", + "shoar", "shoars", "shore", "shores", "shr", "shrs", "skwy", "skyway", + "smt", "spg", "spgs", "spng", "spngs", "spring", "springs", "sprng", + "sprngs", "spur", "spurs", "sq", "sqr", "sqre", "sqrs", "sqs", "squ", + "square", "squares", "st", "sta", "station", "statn", "stn", "str", + "stra", "strav", "strave", "straven", "stravenue", "stravn", "stream", + "street", "streets", "streme", "strm", "strt", "strvn", "strvnue", + "sts", "sumit", "sumitt", "summit", "ter", "terr", "terrace", + "throughway", "tpk", "tpke", "tr", "trace", "traces", "track", "tracks", + "trafficway", "trail", "trails", "trak", "trce", "trfy", "trk", "trks", + "trl", "trls", "trnpk", "trpk", "trwy", "tunel", "tunl", "tunls", + "tunnel", "tunnels", "tunnl", "turnpike", "turnpk", "un", "underpass", + "union", "unions", "uns", "upas", "valley", "valleys", "vally", "vdct", + "via", "viadct", "viaduct", "view", "views", "vill", "villag", + "village", "villages", "ville", "villg", "villiage", "vis", "vist", + "vista", "vl", "vlg", "vlgs", "vlly", "vly", "vlys", "vst", "vsta", + "vw", "vws", "walk", "walks", "wall", "way", "ways", "well", "wells", + "wl", "wls", "wy", "xing", "xrd", + 0, +}; + +bool AddressDetector::IsValidLocationName(const Word& word) { + using namespace WTF; + static HashSet<String> streetNames; + if (!streetNames.size()) { + const char** suffixes = s_rawStreetSuffixes; + while (const char* suffix = *suffixes) { + int index = suffix[0] - 'a'; + streetNames.add(suffix); + suffixes++; + } + } + char16 first_letter = base::ToLowerASCII(*word.begin); + if (first_letter > 'z' || first_letter < 'a') + return false; + int index = first_letter - 'a'; + int length = std::distance(word.begin, word.end); + if (*word.end == '.') + length--; + String value(word.begin, length); + return streetNames.contains(value.lower()); +} diff --git a/Source/WebKit/android/content/address_detector.h b/Source/WebKit/android/content/address_detector.h new file mode 100644 index 0000000..be34375 --- /dev/null +++ b/Source/WebKit/android/content/address_detector.h @@ -0,0 +1,131 @@ +/* + * Copyright (C) 2012 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef CONTENT_RENDERER_ANDROID_ADDRESS_DETECTOR_H_ +#define CONTENT_RENDERER_ANDROID_ADDRESS_DETECTOR_H_ +#pragma once + +#include "build/build_config.h" // Needed for OS_ANDROID + +#if defined(OS_ANDROID) + +#include <vector> + +#include "base/string_tokenizer.h" +#include "base/string_util.h" +#include "content/content_detector.h" + +// Finds a geographical address (currently US only) in the given text string. +class AddressDetector : public ContentDetector { + public: + AddressDetector(); + virtual ~AddressDetector(); + + // Implementation of ContentDetector. + virtual bool FindContent(const string16::const_iterator& begin, + const string16::const_iterator& end, + size_t* start_pos, + size_t* end_pos) OVERRIDE; + + private: + friend class AddressDetectorTest; + + virtual std::string GetContentText(const WebKit::WebRange& range) OVERRIDE; + virtual GURL GetIntentURL(const std::string& content_text) OVERRIDE; + virtual size_t GetMaximumContentLength() OVERRIDE; + + // Internal structs and classes. Required to be visible by the unit tests. + struct Word { + string16::const_iterator begin; + string16::const_iterator end; + + Word() {} + Word(const string16::const_iterator& begin_it, + const string16::const_iterator& end_it) + : begin(begin_it), + end(end_it) { + DCHECK(begin_it <= end_it); + } + }; + + class HouseNumberParser { + public: + HouseNumberParser() {} + + bool Parse(const string16::const_iterator& begin, + const string16::const_iterator& end, + Word* word); + + private: + static inline bool IsPreDelimiter(char16 character); + static inline bool IsPostDelimiter(char16 character); + inline void RestartOnNextDelimiter(); + + inline bool CheckFinished(Word* word) const; + inline void AcceptChars(size_t num_chars); + inline void SkipChars(size_t num_chars); + inline void ResetState(); + + // Iterators to the beginning, current position and ending of the string + // being currently parsed. + string16::const_iterator begin_; + string16::const_iterator it_; + string16::const_iterator end_; + + // Number of digits found in the current result candidate. + size_t num_digits_; + + // Number of characters previous to the current iterator that belong + // to the current result candidate. + size_t result_chars_; + + DISALLOW_COPY_AND_ASSIGN(HouseNumberParser); + }; + + typedef std::vector<Word> WordList; + typedef StringTokenizerT<string16, string16::const_iterator> + String16Tokenizer; + + static bool FindStateStartingInWord(WordList* words, + size_t state_first_word, + size_t* state_last_word, + String16Tokenizer* tokenizer, + size_t* state_index); + + static bool IsValidLocationName(const Word& word); + static bool IsZipValid(const Word& word, size_t state_index); + static bool IsZipValidForState(const Word& word, size_t state_index); + + DISALLOW_COPY_AND_ASSIGN(AddressDetector); +}; + +#endif // defined(OS_ANDROID) + +#endif // CONTENT_RENDERER_ANDROID_ADDRESS_DETECTOR_H_ diff --git a/Source/WebKit/android/content/content_detector.cpp b/Source/WebKit/android/content/content_detector.cpp new file mode 100644 index 0000000..b29a457 --- /dev/null +++ b/Source/WebKit/android/content/content_detector.cpp @@ -0,0 +1,86 @@ +/* + * Copyright (C) 2012 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +// Magic pretend-to-be-a-chromium-build flags +#undef WEBKIT_IMPLEMENTATION +#undef LOG + +#include "content/content_detector.h" + +#include "public/android/WebDOMTextContentWalker.h" +#include "public/android/WebHitTestInfo.h" + +using WebKit::WebDOMTextContentWalker; +using WebKit::WebRange; + +ContentDetector::Result ContentDetector::FindTappedContent( + const WebKit::WebHitTestInfo& hit_test) { + WebKit::WebRange range = FindContentRange(hit_test); + if (range.isNull()) + return Result(); + + std::string text = GetContentText(range); + GURL intent_url = GetIntentURL(text); + return Result(range, text, intent_url); +} + +WebRange ContentDetector::FindContentRange( + const WebKit::WebHitTestInfo& hit_test) { + WebDOMTextContentWalker content_walker(hit_test, GetMaximumContentLength()); + string16 content = content_walker.content(); + if (content.empty()) + return WebRange(); + + size_t selected_offset = content_walker.hitOffsetInContent(); + for (size_t start_offset = 0; start_offset < content.length();) { + size_t relative_start, relative_end; + if (!FindContent(content.begin() + start_offset, + content.end(), &relative_start, &relative_end)) { + break; + } else { + size_t content_start = start_offset + relative_start; + size_t content_end = start_offset + relative_end; + DCHECK(content_end <= content.length()); + + if (selected_offset >= content_start && selected_offset < content_end) { + WebRange range = content_walker.contentOffsetsToRange( + content_start, content_end); + DCHECK(!range.isNull()); + return range; + } else { + start_offset += relative_end; + } + } + } + + return WebRange(); +} diff --git a/Source/WebKit/android/content/content_detector.h b/Source/WebKit/android/content/content_detector.h new file mode 100644 index 0000000..041cbc9 --- /dev/null +++ b/Source/WebKit/android/content/content_detector.h @@ -0,0 +1,103 @@ +/* + * Copyright (C) 2012 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef CONTENT_RENDERER_ANDROID_CONTENT_DETECTOR_H_ +#define CONTENT_RENDERER_ANDROID_CONTENT_DETECTOR_H_ +#pragma once + +#include "build/build_config.h" // Needed for OS_ANDROID + +#if defined(OS_ANDROID) + +#include "base/string_util.h" +#include "googleurl/src/gurl.h" +#include "public/WebRange.h" + +namespace WebKit { +class WebHitTestInfo; +} + +// Base class for text-based content detectors. +class ContentDetector { + public: + + // Holds the content detection results. + struct Result { + bool valid; // Flag indicating if the result is valid. + WebKit::WebRange range; // Range describing the content boundaries. + std::string text; // Processed text of the content. + GURL intent_url; // URL of the intent that should process this content. + + Result() : valid(false) {} + + Result(const WebKit::WebRange& range, + const std::string& text, + const GURL& intent_url) + : valid(true), + range(range), + text(text), + intent_url(intent_url) {} + }; + + virtual ~ContentDetector() {} + + // Returns a WebKit range delimiting the contents found around the tapped + // position. If no content is found a null range will be returned. + Result FindTappedContent(const WebKit::WebHitTestInfo& hit_test); + + protected: + // Parses the input string defined by the begin/end iterators returning true + // if the desired content is found. The start and end positions relative to + // the input iterators are returned in start_pos and end_pos. + // The end position is assumed to be non-inclusive. + virtual bool FindContent(const string16::const_iterator& begin, + const string16::const_iterator& end, + size_t* start_pos, + size_t* end_pos) = 0; + + // Extracts and processes the text of the detected content. + virtual std::string GetContentText(const WebKit::WebRange& range) = 0; + + // Returns the intent URL that should process the content, if any. + virtual GURL GetIntentURL(const std::string& content_text) = 0; + + // Returns the maximum length of text to be extracted around the tapped + // position in order to search for content. + virtual size_t GetMaximumContentLength() = 0; + + ContentDetector() {} + WebKit::WebRange FindContentRange(const WebKit::WebHitTestInfo& hit_test); + + DISALLOW_COPY_AND_ASSIGN(ContentDetector); +}; + +#endif // defined(OS_ANDROID) + +#endif // CONTENT_RENDERER_ANDROID_CONTENT_DETECTOR_H_ |