common/protobuf/kudu/gutil/strings/util.cc (807 lines of code) (raw):

// // Copyright (C) 1999-2005 Google, Inc. // // TODO(user): visit each const_cast. Some of them are no longer necessary // because last Single Unix Spec and grte v2 are more const-y. #include "gutil/strings/util.h" #include <assert.h> #include <stdarg.h> #include <stdio.h> #include <string.h> #include <time.h> // for FastTimeToBuffer() #include <algorithm> using std::copy; using std::max; using std::min; using std::reverse; using std::sort; using std::swap; #include <string> using std::string; #include <vector> using std::vector; #include <common/logging.h> #include "gutil/logging-inl.h" #include "gutil/strings/ascii_ctype.h" #include "gutil/strings/numbers.h" #include "gutil/strings/stringpiece.h" #include "gutil/stl_util.h" // for string_as_array, STLAppendToString #include "gutil/utf/utf.h" #ifdef OS_WINDOWS #ifdef min // windows.h defines this to something silly #undef min #endif #endif // Use this instead of gmtime_r if you want to build for Windows. // Windows doesn't have a 'gmtime_r', but it has the similar 'gmtime_s'. // TODO(user): Probably belongs in //base:time_support.{cc|h}. static struct tm* PortableSafeGmtime(const time_t* timep, struct tm* result) { #ifdef OS_WINDOWS return gmtime_s(result, timep) == 0 ? result : NULL; #else return gmtime_r(timep, result); #endif // OS_WINDOWS } char* strnstr(const char* haystack, const char* needle, size_t haystack_len) { if (*needle == '\0') { return const_cast<char*>(haystack); } size_t needle_len = strlen(needle); char* where; while ((where = strnchr(haystack, *needle, haystack_len)) != nullptr) { if (where - haystack + needle_len > haystack_len) { return nullptr; } if (strncmp(where, needle, needle_len) == 0) { return where; } haystack_len -= where + 1 - haystack; haystack = where + 1; } return nullptr; } const char* strnprefix(const char* haystack, int haystack_size, const char* needle, int needle_size) { if (needle_size > haystack_size) { return nullptr; } else { if (strncmp(haystack, needle, needle_size) == 0) { return haystack + needle_size; } else { return nullptr; } } } const char* strncaseprefix(const char* haystack, int haystack_size, const char* needle, int needle_size) { if (needle_size > haystack_size) { return nullptr; } else { if (strncasecmp(haystack, needle, needle_size) == 0) { return haystack + needle_size; } else { return nullptr; } } } char* strcasesuffix(char* str, const char* suffix) { const int lenstr = strlen(str); const int lensuffix = strlen(suffix); char* strbeginningoftheend = str + lenstr - lensuffix; if (lenstr >= lensuffix && 0 == strcasecmp(strbeginningoftheend, suffix)) { return (strbeginningoftheend); } else { return (nullptr); } } const char* strnsuffix(const char* haystack, int haystack_size, const char* needle, int needle_size) { if (needle_size > haystack_size) { return nullptr; } else { const char* start = haystack + haystack_size - needle_size; if (strncmp(start, needle, needle_size) == 0) { return start; } else { return nullptr; } } } const char* strncasesuffix(const char* haystack, int haystack_size, const char* needle, int needle_size) { if (needle_size > haystack_size) { return nullptr; } else { const char* start = haystack + haystack_size - needle_size; if (strncasecmp(start, needle, needle_size) == 0) { return start; } else { return nullptr; } } } char* strchrnth(const char* str, const char& c, int n) { if (str == nullptr) return nullptr; if (n <= 0) return const_cast<char*>(str); const char* sp; int k = 0; for (sp = str; *sp != '\0'; sp ++) { if (*sp == c) { ++k; if (k >= n) break; } } return (k < n) ? nullptr : const_cast<char*>(sp); } char* AdjustedLastPos(const char* str, char separator, int n) { if ( str == nullptr ) return nullptr; const char* pos = nullptr; if ( n > 0 ) pos = strchrnth(str, separator, n); // if n <= 0 or separator appears fewer than n times, get the last occurrence if ( pos == nullptr) pos = strrchr(str, separator); return const_cast<char*>(pos); } // ---------------------------------------------------------------------- // Misc. routines // ---------------------------------------------------------------------- bool IsAscii(const char* str, int len) { const char* end = str + len; while (str < end) { if (!ascii_isascii(*str++)) { return false; } } return true; } // ---------------------------------------------------------------------- // StringReplace() // Give me a string and two patterns "old" and "new", and I replace // the first instance of "old" in the string with "new", if it // exists. If "replace_all" is true then call this repeatedly until it // fails. RETURN a new string, regardless of whether the replacement // happened or not. // ---------------------------------------------------------------------- string StringReplace(const StringPiece& s, const StringPiece& oldsub, const StringPiece& newsub, bool replace_all) { string ret; StringReplace(s, oldsub, newsub, replace_all, &ret); return ret; } // ---------------------------------------------------------------------- // StringReplace() // Replace the "old" pattern with the "new" pattern in a string, // and append the result to "res". If replace_all is false, // it only replaces the first instance of "old." // ---------------------------------------------------------------------- void StringReplace(const StringPiece& s, const StringPiece& oldsub, const StringPiece& newsub, bool replace_all, string* res) { if (oldsub.empty()) { res->append(s.data(), s.length()); // If empty, append the given string. return; } StringPiece::size_type start_pos = 0; StringPiece::size_type pos; do { pos = s.find(oldsub, start_pos); if (pos == StringPiece::npos) { break; } res->append(s.data() + start_pos, pos - start_pos); res->append(newsub.data(), newsub.length()); // Start searching again after the "old". start_pos = pos + oldsub.length(); } while (replace_all); res->append(s.data() + start_pos, s.length() - start_pos); } // ---------------------------------------------------------------------- // GlobalReplaceSubstring() // Replaces all instances of a substring in a string. Does nothing // if 'substring' is empty. Returns the number of replacements. // // NOTE: The string pieces must not overlap s. // ---------------------------------------------------------------------- int GlobalReplaceSubstring(const StringPiece& substring, const StringPiece& replacement, string* s) { CHECK(s != nullptr); if (s->empty() || substring.empty()) return 0; string tmp; int num_replacements = 0; size_t pos = 0; for (size_t match_pos = s->find(substring.data(), pos, substring.length()); match_pos != string::npos; pos = match_pos + substring.length(), match_pos = s->find(substring.data(), pos, substring.length())) { ++num_replacements; // Append the original content before the match. tmp.append(*s, pos, match_pos - pos); // Append the replacement for the match. tmp.append(replacement.begin(), replacement.end()); } // Append the content after the last match. If no replacements were made, the // original string is left untouched. if (num_replacements > 0) { tmp.append(*s, pos, s->length() - pos); s->swap(tmp); } return num_replacements; } //--------------------------------------------------------------------------- // RemoveStrings() // Remove the strings from v given by the (sorted least -> greatest) // numbers in indices. // Order of v is *not* preserved. //--------------------------------------------------------------------------- void RemoveStrings(vector<string>* v, const vector<int>& indices) { assert(v); assert(indices.size() <= v->size()); // go from largest index to smallest so that smaller indices aren't // invalidated for (int lcv = indices.size() - 1; lcv >= 0; --lcv) { #ifndef NDEBUG // verify that indices is sorted least->greatest if (indices.size() >= 2 && lcv > 0) // use LT and not LE because we should never see repeat indices CHECK_LT(indices[lcv-1], indices[lcv]); #endif assert(indices[lcv] >= 0); assert(indices[lcv] < v->size()); swap((*v)[indices[lcv]], v->back()); v->pop_back(); } } // ---------------------------------------------------------------------- // gstrcasestr is a case-insensitive strstr. Eventually we should just // use the GNU libc version of strcasestr, but it isn't compiled into // RedHat Linux by default in version 6.1. // // This function uses ascii_tolower() instead of tolower(), for speed. // ---------------------------------------------------------------------- char *gstrcasestr(const char* haystack, const char* needle) { char c, sc; size_t len; if ((c = *needle++) != 0) { c = ascii_tolower(c); len = strlen(needle); do { do { if ((sc = *haystack++) == 0) return nullptr; } while (ascii_tolower(sc) != c); } while (strncasecmp(haystack, needle, len) != 0); haystack--; } // This is a const violation but strstr() also returns a char*. return const_cast<char*>(haystack); } // ---------------------------------------------------------------------- // gstrncasestr is a case-insensitive strnstr. // Finds the occurence of the (null-terminated) needle in the // haystack, where no more than len bytes of haystack is searched. // Characters that appear after a '\0' in the haystack are not searched. // // This function uses ascii_tolower() instead of tolower(), for speed. // ---------------------------------------------------------------------- const char *gstrncasestr(const char* haystack, const char* needle, size_t len) { char c, sc; if ((c = *needle++) != 0) { c = ascii_tolower(c); size_t needle_len = strlen(needle); do { do { if (len-- <= needle_len || 0 == (sc = *haystack++)) return nullptr; } while (ascii_tolower(sc) != c); } while (strncasecmp(haystack, needle, needle_len) != 0); haystack--; } return haystack; } // ---------------------------------------------------------------------- // gstrncasestr is a case-insensitive strnstr. // Finds the occurence of the (null-terminated) needle in the // haystack, where no more than len bytes of haystack is searched. // Characters that appear after a '\0' in the haystack are not searched. // // This function uses ascii_tolower() instead of tolower(), for speed. // ---------------------------------------------------------------------- char *gstrncasestr(char* haystack, const char* needle, size_t len) { return const_cast<char *>(gstrncasestr(static_cast<const char *>(haystack), needle, len)); } // ---------------------------------------------------------------------- // gstrncasestr_split performs a case insensitive search // on (prefix, non_alpha, suffix). // ---------------------------------------------------------------------- char *gstrncasestr_split(const char* str, const char* prefix, char non_alpha, const char* suffix, size_t n) { int prelen = prefix == nullptr ? 0 : strlen(prefix); int suflen = suffix == nullptr ? 0 : strlen(suffix); // adjust the string and its length to avoid unnessary searching. // an added benefit is to avoid unnecessary range checks in the if // statement in the inner loop. if (suflen + prelen >= n) return nullptr; str += prelen; n -= prelen; n -= suflen; const char* where = nullptr; // for every occurance of non_alpha in the string ... while ((where = static_cast<const char*>( memchr(str, non_alpha, n))) != nullptr) { // ... test whether it is followed by suffix and preceded by prefix if ((!suflen || strncasecmp(where + 1, suffix, suflen) == 0) && (!prelen || strncasecmp(where - prelen, prefix, prelen) == 0)) { return const_cast<char*>(where - prelen); } // if not, advance the pointer, and adjust the length according n -= (where + 1) - str; str = where + 1; } return nullptr; } // ---------------------------------------------------------------------- // strcasestr_alnum is like a case-insensitive strstr, except that it // ignores non-alphanumeric characters in both strings for the sake of // comparison. // // This function uses ascii_isalnum() instead of isalnum() and // ascii_tolower() instead of tolower(), for speed. // // E.g. strcasestr_alnum("i use google all the time", " !!Google!! ") // returns pointer to "google all the time" // ---------------------------------------------------------------------- char *strcasestr_alnum(const char *haystack, const char *needle) { const char *haystack_ptr; const char *needle_ptr; // Skip non-alnums at beginning while ( !ascii_isalnum(*needle) ) if ( *needle++ == '\0' ) return const_cast<char*>(haystack); needle_ptr = needle; // Skip non-alnums at beginning while ( !ascii_isalnum(*haystack) ) if ( *haystack++ == '\0' ) return nullptr; haystack_ptr = haystack; while ( *needle_ptr != '\0' ) { // Non-alnums - advance while ( !ascii_isalnum(*needle_ptr) ) if ( *needle_ptr++ == '\0' ) return const_cast<char *>(haystack); while ( !ascii_isalnum(*haystack_ptr) ) if ( *haystack_ptr++ == '\0' ) return nullptr; if ( ascii_tolower(*needle_ptr) == ascii_tolower(*haystack_ptr) ) { // Case-insensitive match - advance needle_ptr++; haystack_ptr++; } else { // No match - rollback to next start point in haystack haystack++; while ( !ascii_isalnum(*haystack) ) if ( *haystack++ == '\0' ) return nullptr; haystack_ptr = haystack; needle_ptr = needle; } } return const_cast<char *>(haystack); } // ---------------------------------------------------------------------- // CountSubstring() // Return the number times a "substring" appears in the "text" // NOTE: this function's complexity is O(|text| * |substring|) // It is meant for short "text" (such as to ensure the // printf format string has the right number of arguments). // DO NOT pass in long "text". // ---------------------------------------------------------------------- int CountSubstring(StringPiece text, StringPiece substring) { CHECK_GT(substring.length(), 0); int count = 0; StringPiece::size_type curr = 0; while (StringPiece::npos != (curr = text.find(substring, curr))) { ++count; ++curr; } return count; } // ---------------------------------------------------------------------- // strstr_delimited() // Just like strstr(), except it ensures that the needle appears as // a complete item (or consecutive series of items) in a delimited // list. // // Like strstr(), returns haystack if needle is empty, or NULL if // either needle/haystack is NULL. // ---------------------------------------------------------------------- const char* strstr_delimited(const char* haystack, const char* needle, char delim) { if (!needle || !haystack) return nullptr; if (*needle == '\0') return haystack; int needle_len = strlen(needle); while (true) { // Skip any leading delimiters. while (*haystack == delim) ++haystack; // Walk down the haystack, matching every character in the needle. const char* this_match = haystack; int i = 0; for (; i < needle_len; i++) { if (*haystack != needle[i]) { // We ran out of haystack or found a non-matching character. break; } ++haystack; } // If we matched the whole needle, ensure that it's properly delimited. if (i == needle_len && (*haystack == '\0' || *haystack == delim)) { return this_match; } // No match. Consume non-delimiter characters until we run out of them. while (*haystack != delim) { if (*haystack == '\0') return nullptr; ++haystack; } } LOG(FATAL) << "Unreachable statement"; return nullptr; } // ---------------------------------------------------------------------- // Older versions of libc have a buggy strsep. // ---------------------------------------------------------------------- char* gstrsep(char** stringp, const char* delim) { char *s; const char *spanp; int c, sc; char *tok; if ((s = *stringp) == nullptr) return nullptr; tok = s; while (true) { c = *s++; spanp = delim; do { if ((sc = *spanp++) == c) { if (c == 0) s = nullptr; else s[-1] = 0; *stringp = s; return tok; } } while (sc != 0); } return nullptr; /* should not happen */ } void FastStringAppend(string* s, const char* data, int len) { STLAppendToString(s, data, len); } // TODO(user): add a microbenchmark and revisit // the optimizations done here. // // Several converters use this table to reduce // division and modulo operations. extern const char two_ASCII_digits[100][2]; const char two_ASCII_digits[100][2] = { {'0', '0'}, {'0', '1'}, {'0', '2'}, {'0', '3'}, {'0', '4'}, {'0', '5'}, {'0', '6'}, {'0', '7'}, {'0', '8'}, {'0', '9'}, {'1', '0'}, {'1', '1'}, {'1', '2'}, {'1', '3'}, {'1', '4'}, {'1', '5'}, {'1', '6'}, {'1', '7'}, {'1', '8'}, {'1', '9'}, {'2', '0'}, {'2', '1'}, {'2', '2'}, {'2', '3'}, {'2', '4'}, {'2', '5'}, {'2', '6'}, {'2', '7'}, {'2', '8'}, {'2', '9'}, {'3', '0'}, {'3', '1'}, {'3', '2'}, {'3', '3'}, {'3', '4'}, {'3', '5'}, {'3', '6'}, {'3', '7'}, {'3', '8'}, {'3', '9'}, {'4', '0'}, {'4', '1'}, {'4', '2'}, {'4', '3'}, {'4', '4'}, {'4', '5'}, {'4', '6'}, {'4', '7'}, {'4', '8'}, {'4', '9'}, {'5', '0'}, {'5', '1'}, {'5', '2'}, {'5', '3'}, {'5', '4'}, {'5', '5'}, {'5', '6'}, {'5', '7'}, {'5', '8'}, {'5', '9'}, {'6', '0'}, {'6', '1'}, {'6', '2'}, {'6', '3'}, {'6', '4'}, {'6', '5'}, {'6', '6'}, {'6', '7'}, {'6', '8'}, {'6', '9'}, {'7', '0'}, {'7', '1'}, {'7', '2'}, {'7', '3'}, {'7', '4'}, {'7', '5'}, {'7', '6'}, {'7', '7'}, {'7', '8'}, {'7', '9'}, {'8', '0'}, {'8', '1'}, {'8', '2'}, {'8', '3'}, {'8', '4'}, {'8', '5'}, {'8', '6'}, {'8', '7'}, {'8', '8'}, {'8', '9'}, {'9', '0'}, {'9', '1'}, {'9', '2'}, {'9', '3'}, {'9', '4'}, {'9', '5'}, {'9', '6'}, {'9', '7'}, {'9', '8'}, {'9', '9'} }; static inline void PutTwoDigits(int i, char* p) { DCHECK_GE(i, 0); DCHECK_LT(i, 100); p[0] = two_ASCII_digits[i][0]; p[1] = two_ASCII_digits[i][1]; } char* FastTimeToBuffer(time_t s, char* buffer) { if (s == 0) { time(&s); } struct tm tm; if (PortableSafeGmtime(&s, &tm) == nullptr) { // Error message must fit in 30-char buffer. memcpy(buffer, "Invalid:", sizeof("Invalid:")); FastInt64ToBufferLeft(s, buffer+strlen(buffer)); return buffer; } // strftime format: "%a, %d %b %Y %H:%M:%S GMT", // but strftime does locale stuff which we do not want // plus strftime takes > 10x the time of hard code const char* weekday_name = "Xxx"; switch (tm.tm_wday) { default: { DLOG(FATAL) << "tm.tm_wday: " << tm.tm_wday; } break; case 0: weekday_name = "Sun"; break; case 1: weekday_name = "Mon"; break; case 2: weekday_name = "Tue"; break; case 3: weekday_name = "Wed"; break; case 4: weekday_name = "Thu"; break; case 5: weekday_name = "Fri"; break; case 6: weekday_name = "Sat"; break; } const char* month_name = "Xxx"; switch (tm.tm_mon) { default: { DLOG(FATAL) << "tm.tm_mon: " << tm.tm_mon; } break; case 0: month_name = "Jan"; break; case 1: month_name = "Feb"; break; case 2: month_name = "Mar"; break; case 3: month_name = "Apr"; break; case 4: month_name = "May"; break; case 5: month_name = "Jun"; break; case 6: month_name = "Jul"; break; case 7: month_name = "Aug"; break; case 8: month_name = "Sep"; break; case 9: month_name = "Oct"; break; case 10: month_name = "Nov"; break; case 11: month_name = "Dec"; break; } // Write out the buffer. memcpy(buffer+0, weekday_name, 3); buffer[3] = ','; buffer[4] = ' '; PutTwoDigits(tm.tm_mday, buffer+5); buffer[7] = ' '; memcpy(buffer+8, month_name, 3); buffer[11] = ' '; int32 year = tm.tm_year + 1900; PutTwoDigits(year/100, buffer+12); PutTwoDigits(year%100, buffer+14); buffer[16] = ' '; PutTwoDigits(tm.tm_hour, buffer+17); buffer[19] = ':'; PutTwoDigits(tm.tm_min, buffer+20); buffer[22] = ':'; PutTwoDigits(tm.tm_sec, buffer+23); // includes ending NUL memcpy(buffer+25, " GMT", 5); return buffer; } // ---------------------------------------------------------------------- // strdup_with_new() // strndup_with_new() // // strdup_with_new() is the same as strdup() except that the memory // is allocated by new[] and hence an exception will be generated // if out of memory. // // strndup_with_new() is the same as strdup_with_new() except that it will // copy up to the specified number of characters. This function // is useful when we want to copy a substring out of a string // and didn't want to (or cannot) modify the string // ---------------------------------------------------------------------- char* strdup_with_new(const char* the_string) { if (the_string == nullptr) return nullptr; else return strndup_with_new(the_string, strlen(the_string)); } char* strndup_with_new(const char* the_string, int max_length) { if (the_string == nullptr) return nullptr; auto result = new char[max_length + 1]; result[max_length] = '\0'; // terminate the string because strncpy might not return strncpy(result, the_string, max_length); } // ---------------------------------------------------------------------- // ScanForFirstWord() // This function finds the first word in the string "the_string" given. // A word is defined by consecutive !ascii_isspace() characters. // If no valid words are found, // return NULL and *end_ptr will contain junk // else // return the beginning of the first word and // *end_ptr will store the address of the first invalid character // (ascii_isspace() or '\0'). // // Precondition: (end_ptr != NULL) // ---------------------------------------------------------------------- const char* ScanForFirstWord(const char* the_string, const char** end_ptr) { CHECK(end_ptr != nullptr) << ": precondition violated"; if (the_string == nullptr) // empty string return nullptr; const char* curr = the_string; while ((*curr != '\0') && ascii_isspace(*curr)) // skip initial spaces ++curr; if (*curr == '\0') // no valid word found return nullptr; // else has a valid word const char* first_word = curr; // now locate the end of the word while ((*curr != '\0') && !ascii_isspace(*curr)) ++curr; *end_ptr = curr; return first_word; } // ---------------------------------------------------------------------- // AdvanceIdentifier() // This function returns a pointer past the end of the longest C-style // identifier that is a prefix of str or NULL if str does not start with // one. A C-style identifier begins with an ASCII letter or underscore // and continues with ASCII letters, digits, or underscores. // ---------------------------------------------------------------------- const char *AdvanceIdentifier(const char *str) { // Not using isalpha and isalnum so as not to rely on the locale. // We could have used ascii_isalpha and ascii_isalnum. char ch = *str++; if (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_')) return nullptr; while (true) { ch = *str; if (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9') || ch == '_')) return str; str++; } } // ---------------------------------------------------------------------- // IsIdentifier() // This function returns true if str is a C-style identifier. // A C-style identifier begins with an ASCII letter or underscore // and continues with ASCII letters, digits, or underscores. // ---------------------------------------------------------------------- bool IsIdentifier(const char *str) { const char *end = AdvanceIdentifier(str); return end && *end == '\0'; } static bool IsWildcard(Rune character) { return character == '*' || character == '?'; } // Move the strings pointers to the point where they start to differ. template <typename CHAR, typename NEXT> static void EatSameChars(const CHAR** pattern, const CHAR* pattern_end, const CHAR** string, const CHAR* string_end, NEXT next) { const CHAR* escape = nullptr; while (*pattern != pattern_end && *string != string_end) { if (!escape && IsWildcard(**pattern)) { // We don't want to match wildcard here, except if it's escaped. return; } // Check if the escapement char is found. If so, skip it and move to the // next character. if (!escape && **pattern == '\\') { escape = *pattern; next(pattern, pattern_end); continue; } // Check if the chars match, if so, increment the ptrs. const CHAR* pattern_next = *pattern; const CHAR* string_next = *string; Rune pattern_char = next(&pattern_next, pattern_end); if (pattern_char == next(&string_next, string_end) && pattern_char != Runeerror && pattern_char <= Runemax) { *pattern = pattern_next; *string = string_next; } else { // Uh ho, it did not match, we are done. If the last char was an // escapement, that means that it was an error to advance the ptr here, // let's put it back where it was. This also mean that the MatchPattern // function will return false because if we can't match an escape char // here, then no one will. if (escape) { *pattern = escape; } return; } escape = nullptr; } } template <typename CHAR, typename NEXT> static void EatWildcard(const CHAR** pattern, const CHAR* end, NEXT next) { while (*pattern != end) { if (!IsWildcard(**pattern)) return; next(pattern, end); } } template <typename CHAR, typename NEXT> static bool MatchPatternT(const CHAR* eval, const CHAR* eval_end, const CHAR* pattern, const CHAR* pattern_end, int depth, NEXT next) { const int kMaxDepth = 16; if (depth > kMaxDepth) return false; // Eat all the matching chars. EatSameChars(&pattern, pattern_end, &eval, eval_end, next); // If the string is empty, then the pattern must be empty too, or contains // only wildcards. if (eval == eval_end) { EatWildcard(&pattern, pattern_end, next); return pattern == pattern_end; } // Pattern is empty but not string, this is not a match. if (pattern == pattern_end) return false; // If this is a question mark, then we need to compare the rest with // the current string or the string with one character eaten. const CHAR* next_pattern = pattern; next(&next_pattern, pattern_end); if (pattern[0] == '?') { if (MatchPatternT(eval, eval_end, next_pattern, pattern_end, depth + 1, next)) return true; const CHAR* next_eval = eval; next(&next_eval, eval_end); if (MatchPatternT(next_eval, eval_end, next_pattern, pattern_end, depth + 1, next)) return true; } // This is a *, try to match all the possible substrings with the remainder // of the pattern. if (pattern[0] == '*') { // Collapse duplicate wild cards (********** into *) so that the // method does not recurse unnecessarily. http://crbug.com/52839 EatWildcard(&next_pattern, pattern_end, next); while (eval != eval_end) { if (MatchPatternT(eval, eval_end, next_pattern, pattern_end, depth + 1, next)) return true; eval++; } // We reached the end of the string, let see if the pattern contains only // wildcards. if (eval == eval_end) { EatWildcard(&pattern, pattern_end, next); if (pattern != pattern_end) return false; return true; } } return false; } struct NextCharUTF8 { Rune operator()(const char** p, const char* end) { Rune c; int offset = charntorune(&c, *p, static_cast<int>(end - *p)); *p += offset; return c; } }; bool MatchPattern(const StringPiece& eval, const StringPiece& pattern) { return MatchPatternT(eval.data(), eval.data() + eval.size(), pattern.data(), pattern.data() + pattern.size(), 0, NextCharUTF8()); } // ---------------------------------------------------------------------- // FindTagValuePair // Given a string of the form // <something><attr_sep><tag><tag_value_sep><value><attr_sep>...<string_term> // where the part before the first attr_sep is optional, // this function extracts the first tag and value, if any. // The function returns true if successful, in which case "tag" and "value" // are set to point to the beginning of the tag and the value, respectively, // and "tag_len" and "value_len" are set to the respective lengths. // ---------------------------------------------------------------------- bool FindTagValuePair(const char* arg_str, char tag_value_separator, char attribute_separator, char string_terminal, char **tag, int *tag_len, char **value, int *value_len) { char* in_str = const_cast<char*>(arg_str); // For msvc8. if (in_str == nullptr) return false; char tv_sep_or_term[3] = {tag_value_separator, string_terminal, '\0'}; char attr_sep_or_term[3] = {attribute_separator, string_terminal, '\0'}; // Look for beginning of tag *tag = strpbrk(in_str, attr_sep_or_term); // If string_terminal is '\0', strpbrk won't find it but return null. if (*tag == nullptr || **tag == string_terminal) *tag = in_str; else (*tag)++; // Move past separator // Now look for value... char *tv_sep_pos = strpbrk(*tag, tv_sep_or_term); if (tv_sep_pos == nullptr || *tv_sep_pos == string_terminal) return false; // ...and end of value char *attr_sep_pos = strpbrk(tv_sep_pos, attr_sep_or_term); *tag_len = tv_sep_pos - *tag; *value = tv_sep_pos + 1; if (attr_sep_pos != nullptr) *value_len = attr_sep_pos - *value; else *value_len = strlen(*value); return true; } void UniformInsertString(string* s, int interval, const char* separator) { const size_t separator_len = strlen(separator); if (interval < 1 || // invalid interval s->empty() || // nothing to do separator_len == 0) // invalid separator return; int num_inserts = (s->size() - 1) / interval; // -1 to avoid appending at end if (num_inserts == 0) // nothing to do return; string tmp; tmp.reserve(s->size() + num_inserts * separator_len + 1); for (int i = 0; i < num_inserts ; ++i) { // append this interval tmp.append(*s, i * interval, interval); // append a separator tmp.append(separator, separator_len); } // append the tail const size_t tail_pos = num_inserts * interval; tmp.append(*s, tail_pos, s->size() - tail_pos); s->swap(tmp); } void InsertString(string *const s, const vector<uint32> &indices, char const *const separator) { const unsigned num_indices(indices.size()); if (num_indices == 0) { return; // nothing to do... } const unsigned separator_len(strlen(separator)); if (separator_len == 0) { return; // still nothing to do... } string tmp; const unsigned s_len(s->size()); tmp.reserve(s_len + separator_len * num_indices); vector<uint32>::const_iterator const ind_end(indices.end()); auto ind_pos(indices.begin()); uint32 last_pos(0); while (ind_pos != ind_end) { const uint32 pos(*ind_pos); DCHECK_GE(pos, last_pos); DCHECK_LE(pos, s_len); tmp.append(s->substr(last_pos, pos - last_pos)); tmp.append(separator); last_pos = pos; ++ind_pos; } tmp.append(s->substr(last_pos)); s->swap(tmp); } //------------------------------------------------------------------------ // FindNth() // return index of nth occurrence of c in the string, // or string::npos if n > number of occurrences of c. // (returns string::npos = -1 if n <= 0) //------------------------------------------------------------------------ int FindNth(StringPiece s, char c, int n) { size_t pos = string::npos; for ( int i = 0; i < n; ++i ) { pos = s.find_first_of(c, pos + 1); if ( pos == StringPiece::npos ) { break; } } return pos; } //------------------------------------------------------------------------ // ReverseFindNth() // return index of nth-to-last occurrence of c in the string, // or string::npos if n > number of occurrences of c. // (returns string::npos if n <= 0) //------------------------------------------------------------------------ int ReverseFindNth(StringPiece s, char c, int n) { if ( n <= 0 ) { return static_cast<int>(StringPiece::npos); } size_t pos = s.size(); for ( int i = 0; i < n; ++i ) { // If pos == 0, we return StringPiece::npos right away. Otherwise, // the following find_last_of call would take (pos - 1) as string::npos, // which means it would again search the entire input string. if (pos == 0) { return static_cast<int>(StringPiece::npos); } pos = s.find_last_of(c, pos - 1); if ( pos == string::npos ) { break; } } return pos; } namespace strings { // FindEol() // Returns the location of the next end-of-line sequence. StringPiece FindEol(StringPiece s) { for (size_t i = 0; i < s.length(); ++i) { if (s[i] == '\n') { return StringPiece(s.data() + i, 1); } if (s[i] == '\r') { if (i+1 < s.length() && s[i+1] == '\n') { return StringPiece(s.data() + i, 2); } else { return StringPiece(s.data() + i, 1); } } } return StringPiece(s.data() + s.length(), 0); } } // namespace strings //------------------------------------------------------------------------ // OnlyWhitespace() // return true if string s contains only whitespace characters //------------------------------------------------------------------------ bool OnlyWhitespace(const StringPiece& s) { for (const auto& c : s) { if ( !ascii_isspace(c) ) return false; } return true; } string PrefixSuccessor(const StringPiece& prefix) { // We can increment the last character in the string and be done // unless that character is 255, in which case we have to erase the // last character and increment the previous character, unless that // is 255, etc. If the string is empty or consists entirely of // 255's, we just return the empty string. bool done = false; string limit(prefix.data(), prefix.size()); int index = limit.length() - 1; while (!done && index >= 0) { if (limit[index] == 255) { limit.erase(index); index--; } else { limit[index]++; done = true; } } if (!done) { return ""; } else { return limit; } } string ImmediateSuccessor(const StringPiece& s) { // Return the input string, with an additional NUL byte appended. string out; out.reserve(s.size() + 1); out.append(s.data(), s.size()); out.push_back('\0'); return out; } void FindShortestSeparator(const StringPiece& start, const StringPiece& limit, string* separator) { // Find length of common prefix size_t min_length = min(start.size(), limit.size()); size_t diff_index = 0; while ((diff_index < min_length) && (start[diff_index] == limit[diff_index])) { diff_index++; } if (diff_index >= min_length) { // Handle the case where either string is a prefix of the other // string, or both strings are identical. start.CopyToString(separator); return; } if (diff_index+1 == start.size()) { // If the first difference is in the last character, do not bother // incrementing that character since the separator will be no // shorter than "start". start.CopyToString(separator); return; } if (start[diff_index] == 0xff) { // Avoid overflow when incrementing start[diff_index] start.CopyToString(separator); return; } separator->assign(start.data(), diff_index); separator->push_back(start[diff_index] + 1); if (*separator >= limit) { // Never pick a separator that causes confusion with "limit" start.CopyToString(separator); } } int SafeSnprintf(char *str, size_t size, const char *format, ...) { va_list printargs; va_start(printargs, format); int ncw = vsnprintf(str, size, format, printargs); va_end(printargs); return (ncw < size && ncw >= 0) ? ncw : 0; } bool GetlineFromStdioFile(FILE* file, string* str, char delim) { str->erase(); while (true) { if (feof(file) || ferror(file)) { return false; } int c = getc(file); if (c == EOF) return false; if (c == delim) return true; str->push_back(c); } } namespace { template <typename CHAR> size_t lcpyT(CHAR* dst, const CHAR* src, size_t dst_size) { for (size_t i = 0; i < dst_size; ++i) { if ((dst[i] = src[i]) == 0) // We hit and copied the terminating NULL. return i; } // We were left off at dst_size. We over copied 1 byte. Null terminate. if (dst_size != 0) dst[dst_size - 1] = 0; // Count the rest of the |src|, and return it's length in characters. while (src[dst_size]) ++dst_size; return dst_size; } } // namespace size_t strings::strlcpy(char* dst, const char* src, size_t dst_size) { return lcpyT<char>(dst, src, dst_size); }