/*
 * Copyright 2010 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// Author: jmarantz@google.com (Joshua Marantz)

#include "pagespeed/kernel/base/string_util.h"

#include <algorithm>
#include <cstddef>
#include <cstdlib>
#include <vector>

#include "pagespeed/kernel/base/string.h"

namespace net_instaweb {

bool StringToDouble(const char* in, double* out) {
  char* endptr;
  *out = strtod(in, &endptr);
  if (endptr != in) {
    while (IsHtmlSpace(*endptr)) ++endptr;
  }
  // Ignore range errors from strtod.  The values it
  // returns on underflow and overflow are the right
  // fallback in a robust setting.
  return *in != '\0' && *endptr == '\0';
}

GoogleString StrCat(StringPiece a, StringPiece b) {
  GoogleString res;
  res.reserve(a.size() + b.size());
  a.AppendToString(&res);
  b.AppendToString(&res);
  return res;
}
GoogleString StrCat(StringPiece a, StringPiece b, StringPiece c) {
  GoogleString res;
  res.reserve(a.size() + b.size() + c.size());
  a.AppendToString(&res);
  b.AppendToString(&res);
  c.AppendToString(&res);
  return res;
}
GoogleString StrCat(StringPiece a, StringPiece b, StringPiece c,
                    StringPiece d) {
  GoogleString res;
  res.reserve(a.size() + b.size() + c.size() + d.size());
  a.AppendToString(&res);
  b.AppendToString(&res);
  c.AppendToString(&res);
  d.AppendToString(&res);
  return res;
}
GoogleString StrCat(StringPiece a, StringPiece b, StringPiece c, StringPiece d,
                    StringPiece e) {
  GoogleString res;
  res.reserve(a.size() + b.size() + c.size() + d.size() + e.size());
  a.AppendToString(&res);
  b.AppendToString(&res);
  c.AppendToString(&res);
  d.AppendToString(&res);
  e.AppendToString(&res);
  return res;
}
GoogleString StrCat(StringPiece a, StringPiece b, StringPiece c, StringPiece d,
                    StringPiece e, StringPiece f) {
  GoogleString res;
  res.reserve(a.size() + b.size() + c.size() + d.size() + e.size() + f.size());
  a.AppendToString(&res);
  b.AppendToString(&res);
  c.AppendToString(&res);
  d.AppendToString(&res);
  e.AppendToString(&res);
  f.AppendToString(&res);
  return res;
}
GoogleString StrCat(StringPiece a, StringPiece b, StringPiece c, StringPiece d,
                    StringPiece e, StringPiece f, StringPiece g) {
  GoogleString res;
  res.reserve(a.size() + b.size() + c.size() + d.size() + e.size() + f.size() +
              g.size());
  a.AppendToString(&res);
  b.AppendToString(&res);
  c.AppendToString(&res);
  d.AppendToString(&res);
  e.AppendToString(&res);
  f.AppendToString(&res);
  g.AppendToString(&res);
  return res;
}
GoogleString StrCat(StringPiece a, StringPiece b, StringPiece c, StringPiece d,
                    StringPiece e, StringPiece f, StringPiece g,
                    StringPiece h) {
  GoogleString res;
  res.reserve(a.size() + b.size() + c.size() + d.size() + e.size() + f.size() +
              g.size() + h.size());
  a.AppendToString(&res);
  b.AppendToString(&res);
  c.AppendToString(&res);
  d.AppendToString(&res);
  e.AppendToString(&res);
  f.AppendToString(&res);
  g.AppendToString(&res);
  h.AppendToString(&res);
  return res;
}

namespace internal {

GoogleString StrCatNineOrMore(const StringPiece* a, ...) {
  GoogleString res;

  va_list args;
  va_start(args, a);
  size_t size = a->size();
  while (const StringPiece* arg = va_arg(args, const StringPiece*)) {
    size += arg->size();
  }
  res.reserve(size);
  va_end(args);
  va_start(args, a);
  a->AppendToString(&res);
  while (const StringPiece* arg = va_arg(args, const StringPiece*)) {
    arg->AppendToString(&res);
  }
  va_end(args);
  return res;
}

}  // namespace internal

void StrAppend(GoogleString* target, StringPiece a, StringPiece b) {
  target->reserve(target->size() +
                  a.size() + b.size());
  a.AppendToString(target);
  b.AppendToString(target);
}
void StrAppend(GoogleString* target, StringPiece a, StringPiece b,
               StringPiece c) {
  target->reserve(target->size() +
                  a.size() + b.size() + c.size());
  a.AppendToString(target);
  b.AppendToString(target);
  c.AppendToString(target);
}
void StrAppend(GoogleString* target, StringPiece a, StringPiece b,
               StringPiece c, StringPiece d) {
  target->reserve(target->size() +
                  a.size() + b.size() + c.size() + d.size());
  a.AppendToString(target);
  b.AppendToString(target);
  c.AppendToString(target);
  d.AppendToString(target);
}
void StrAppend(GoogleString* target, StringPiece a, StringPiece b,
               StringPiece c, StringPiece d, StringPiece e) {
  target->reserve(target->size() +
                  a.size() + b.size() + c.size() + d.size() + e.size());
  a.AppendToString(target);
  b.AppendToString(target);
  c.AppendToString(target);
  d.AppendToString(target);
  e.AppendToString(target);
}
void StrAppend(GoogleString* target, StringPiece a, StringPiece b,
               StringPiece c, StringPiece d, StringPiece e, StringPiece f) {
  target->reserve(target->size() +
                  a.size() + b.size() + c.size() + d.size() + e.size() +
                  f.size());
  a.AppendToString(target);
  b.AppendToString(target);
  c.AppendToString(target);
  d.AppendToString(target);
  e.AppendToString(target);
  f.AppendToString(target);
}
void StrAppend(GoogleString* target, StringPiece a, StringPiece b,
               StringPiece c, StringPiece d, StringPiece e, StringPiece f,
               StringPiece g) {
  target->reserve(target->size() +
                  a.size() + b.size() + c.size() + d.size() + e.size() +
                  f.size() + g.size());
  a.AppendToString(target);
  b.AppendToString(target);
  c.AppendToString(target);
  d.AppendToString(target);
  e.AppendToString(target);
  f.AppendToString(target);
  g.AppendToString(target);
}
void StrAppend(GoogleString* target, StringPiece a, StringPiece b,
               StringPiece c, StringPiece d, StringPiece e, StringPiece f,
               StringPiece g, StringPiece h) {
  target->reserve(target->size() +
                  a.size() + b.size() + c.size() + d.size() + e.size() +
                  f.size() + g.size() + h.size());
  a.AppendToString(target);
  b.AppendToString(target);
  c.AppendToString(target);
  d.AppendToString(target);
  e.AppendToString(target);
  f.AppendToString(target);
  g.AppendToString(target);
  h.AppendToString(target);
}
void StrAppend(GoogleString* target, StringPiece a, StringPiece b,
               StringPiece c, StringPiece d, StringPiece e, StringPiece f,
               StringPiece g, StringPiece h, StringPiece i) {
  target->reserve(target->size() +
                  a.size() + b.size() + c.size() + d.size() + e.size() +
                  f.size() + g.size() + h.size() + i.size());
  a.AppendToString(target);
  b.AppendToString(target);
  c.AppendToString(target);
  d.AppendToString(target);
  e.AppendToString(target);
  f.AppendToString(target);
  g.AppendToString(target);
  h.AppendToString(target);
  i.AppendToString(target);
}

void SplitStringPieceToVector(StringPiece sp, StringPiece separators,
                              StringPieceVector* components,
                              bool omit_empty_strings) {
  size_t prev_pos = 0;
  size_t pos = 0;
  while ((pos = sp.find_first_of(separators, pos)) != StringPiece::npos) {
    if (!omit_empty_strings || (pos > prev_pos)) {
      components->push_back(sp.substr(prev_pos, pos - prev_pos));
    }
    ++pos;
    prev_pos = pos;
  }
  if (!omit_empty_strings || (prev_pos < sp.size())) {
    components->push_back(sp.substr(prev_pos, prev_pos - sp.size()));
  }
}

void SplitStringUsingSubstr(StringPiece full, StringPiece substr,
                            StringPieceVector* result) {
  StringPiece::size_type begin_index = 0;
  while (true) {
    const StringPiece::size_type end_index = full.find(substr, begin_index);
    if (end_index == StringPiece::npos) {
      const StringPiece term = full.substr(begin_index);
      result->push_back(term);
      return;
    }
    const StringPiece term = full.substr(begin_index, end_index - begin_index);
    if (!term.empty()) {
      result->push_back(term);
    }
    begin_index = end_index + substr.size();
  }
}

void BackslashEscape(StringPiece src, StringPiece to_escape,
                     GoogleString* dest) {
  dest->reserve(dest->size() + src.size());
  for (const char *p = src.data(), *end = src.data() + src.size();
       p != end; ++p) {
    if (to_escape.find(*p) != StringPiece::npos) {
      dest->push_back('\\');
    }
    dest->push_back(*p);
  }
}

GoogleString CEscape(StringPiece src) {
  int len = src.length();
  const char* read = src.data();
  const char* end = read + len;
  int used = 0;
  char* dest = new char[len * 4 + 1];
  for (; read != end; ++read) {
    unsigned char ch = static_cast<unsigned char>(*read);
    switch (ch) {
      case '\n': dest[used++] = '\\'; dest[used++] = 'n'; break;
      case '\r': dest[used++] = '\\'; dest[used++] = 'r'; break;
      case '\t': dest[used++] = '\\'; dest[used++] = 't'; break;
      case '\"': dest[used++] = '\\'; dest[used++] = '\"'; break;
      case '\'': dest[used++] = '\\'; dest[used++] = '\''; break;
      case '\\': dest[used++] = '\\'; dest[used++] = '\\'; break;
      default:
        if (ch < 32 || ch >= 127) {
          base::snprintf(dest + used, 5, "\\%03o", ch);  // NOLINT
          used += 4;
        } else {
          dest[used++] = ch;
        }
        break;
    }
  }
  GoogleString final(dest, used);
  delete[] dest;
  return final;
}

// From src/third_party/protobuf/src/google/protobuf/stubs/strutil.h
// but we don't need any other aspect of protobufs so we don't want to
// incur the link cost.
bool HasPrefixString(StringPiece str, StringPiece prefix) {
  return str.starts_with(prefix);
}

// From src/third_party/protobuf/src/google/protobuf/stubs/strutil.h
// but we don't need any other aspect of protobufs so we don't want to
// incur the link cost.
void UpperString(GoogleString* s) {
  GoogleString::iterator end = s->end();
  for (GoogleString::iterator i = s->begin(); i != end; ++i) {
    *i = UpperChar(*i);
  }
}

void LowerString(GoogleString* s) {
  GoogleString::iterator end = s->end();
  for (GoogleString::iterator i = s->begin(); i != end; ++i) {
    *i = LowerChar(*i);
  }
}

// ----------------------------------------------------------------------
// GlobalReplaceSubstring()
//    Replaces all instances of a substring in a string.  Returns the
//    number of replacements.
//
//    NOTE: The string pieces must not overlap s.
// ----------------------------------------------------------------------
int GlobalReplaceSubstring(StringPiece substring, StringPiece replacement,
                           GoogleString* s) {
  CHECK(s != NULL);
  if (s->empty())
    return 0;
  GoogleString tmp;
  int num_replacements = 0;
  size_t pos = 0;
  for (size_t match_pos = s->find(substring.data(), pos, substring.length());
       match_pos != GoogleString::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;
}

// Erase shortest substrings in string bracketed by left and right.
int GlobalEraseBracketedSubstring(StringPiece left, StringPiece right,
                                  GoogleString* string) {
  int deletions = 0;
  size_t keep_start = 0;
  size_t keep_end = string->find(left.data(), keep_start, left.size());
  if (keep_end == GoogleString::npos) {
    // Fast path without allocation for no occurrences of left.
    return 0;
  }
  GoogleString result;
  result.reserve(string->size());
  while (keep_end != GoogleString::npos) {
    result.append(*string, keep_start, keep_end - keep_start);
    keep_start =
        string->find(right.data(), keep_end + left.size(), right.size());
    if (keep_start == GoogleString::npos) {
      keep_start = keep_end;
      break;
    }
    keep_start += right.size();
    ++deletions;
    keep_end = string->find(left.data(), keep_start, left.size());
  }
  result.append(*string, keep_start, string->size() - keep_start);
  string->swap(result);
  string->reserve(string->size());  // shrink_to_fit, C++99-style
  return deletions;
}

GoogleString JoinStringStar(const ConstStringStarVector& vector,
                            StringPiece delim) {
  GoogleString result;

  if (vector.size() > 0) {
    // Precompute resulting length so we can reserve() memory in one shot.
    int length = delim.size() * (vector.size() - 1);
    for (ConstStringStarVector::const_iterator iter = vector.begin();
         iter < vector.end(); ++iter) {
      length += (*iter)->size();
    }
    result.reserve(length);

    // Now combine everything.
    for (ConstStringStarVector::const_iterator iter = vector.begin();
         iter < vector.end(); ++iter) {
      if (iter != vector.begin()) {
        result.append(delim.data(), delim.size());
      }
      result.append(**iter);
    }
  }

  return result;
}

bool StringCaseStartsWith(StringPiece str, StringPiece prefix) {
  return ((str.size() >= prefix.size()) &&
          (0 == StringCaseCompare(prefix, str.substr(0, prefix.size()))));
}

bool StringCaseEndsWith(StringPiece str, StringPiece suffix) {
  return ((str.size() >= suffix.size()) &&
          (0 == StringCaseCompare(suffix,
                                  str.substr(str.size() - suffix.size()))));
}

bool StringEqualConcat(StringPiece str, StringPiece first, StringPiece second) {
  return (str.size() == first.size() + second.size()) &&
      str.starts_with(first) && str.ends_with(second);
}

StringPiece PieceAfterEquals(StringPiece piece) {
  size_t index = piece.find("=");
  if (index != piece.npos) {
    ++index;
    StringPiece ret = piece;
    ret.remove_prefix(index);
    TrimWhitespace(&ret);
    return ret;
  }
  return StringPiece(piece.data(), 0);
}

int CountCharacterMismatches(StringPiece s1, StringPiece s2) {
  int s1_length = s1.size();
  int s2_length = s2.size();
  int mismatches = 0;
  for (int i = 0, n = std::min(s1_length, s2_length); i < n; ++i) {
    mismatches += s1[i] != s2[i];
  }
  return mismatches + std::abs(s1_length - s2_length);
}

void ParseShellLikeString(StringPiece input,
                          std::vector<GoogleString>* output) {
  output->clear();
  for (size_t index = 0; index < input.size();) {
    const char ch = input[index];
    if (ch == '"' || ch == '\'') {
      // If we see a quoted section, treat it as a single item even if there are
      // spaces in it.
      const char quote = ch;
      ++index;  // skip open quote
      output->push_back("");
      GoogleString& part = output->back();
      for (; index < input.size() && input[index] != quote; ++index) {
        if (input[index] == '\\') {
          ++index;  // skip backslash
          if (index >= input.size()) {
            break;
          }
        }
        part.push_back(input[index]);
      }
      ++index;  // skip close quote
    } else if (!IsHtmlSpace(ch)) {
      // Without quotes, items are whitespace-separated.
      output->push_back("");
      GoogleString& part = output->back();
      for (; index < input.size() && !IsHtmlSpace(input[index]); ++index) {
        part.push_back(input[index]);
      }
    } else {
      // Ignore whitespace (outside of quotes).
      ++index;
    }
  }
}

int CountSubstring(StringPiece text, StringPiece substring) {
  int number_of_occurrences = 0;
  size_t pos = 0;
  for (size_t match_pos = text.find(substring, pos);
       match_pos != StringPiece::npos;
       pos = match_pos + 1, match_pos = text.find(substring, pos)) {
    number_of_occurrences++;
  }
  return number_of_occurrences;
}

stringpiece_ssize_type FindIgnoreCase(
    StringPiece haystack, StringPiece needle) {
  stringpiece_ssize_type pos = 0;
  while (haystack.size() >= needle.size()) {
    if (StringCaseStartsWith(haystack, needle)) {
      return pos;
    }
    ++pos;
    haystack.remove_prefix(1);
  }
  return StringPiece::npos;
}


// In-place StringPiece whitespace trimming.  This mutates the StringPiece.
bool TrimLeadingWhitespace(StringPiece* str) {
  // We use stringpiece_ssize_type to avoid signedness problems.
  stringpiece_ssize_type size = str->size();
  stringpiece_ssize_type trim = 0;
  while (trim != size && IsHtmlSpace(str->data()[trim])) {
    ++trim;
  }
  str->remove_prefix(trim);
  return (trim > 0);
}

bool TrimTrailingWhitespace(StringPiece* str) {
  // We use stringpiece_ssize_type to avoid signedness problems.
  stringpiece_ssize_type rightmost = str->size();
  while (rightmost != 0 && IsHtmlSpace(str->data()[rightmost - 1])) {
    --rightmost;
  }
  if (rightmost != str->size()) {
    str->remove_suffix(str->size() - rightmost);
    return true;
  }
  return false;
}

bool TrimWhitespace(StringPiece* str) {
  // We *must* trim *both* leading and trailing spaces, so we use the
  // non-shortcut bitwise | on the boolean results.
  return TrimLeadingWhitespace(str) | TrimTrailingWhitespace(str);
}

namespace {

bool TrimCasePattern(StringPiece pattern, StringPiece* str) {
  bool did_something = false;
  if (StringCaseStartsWith(*str, pattern)) {
    str->remove_prefix(pattern.size());
    did_something = true;
  }
  if (StringCaseEndsWith(*str, pattern)) {
    str->remove_suffix(pattern.size());
    did_something = false;
  }
  return did_something;
}

}  // namespace

void TrimQuote(StringPiece* str) {
  TrimWhitespace(str);
  if (str->starts_with("\"") || str->starts_with("'")) {
    str->remove_prefix(1);
  }
  if (str->ends_with("\"") || str->ends_with("'")) {
    str->remove_suffix(1);
  }
  TrimWhitespace(str);
}

void TrimUrlQuotes(StringPiece* str) {
  TrimWhitespace(str);

  bool cont = true;

  // Unwrap a string with an arbitrary nesting of real and URL percent-encoded
  // quotes.  We do this one layer at a time, always removing backslashed
  // quotes before removing un-backslashed quotes.
  while (cont) {
    cont = (TrimCasePattern("%5C%27", str) ||    // \"
            TrimCasePattern("%5C%22", str) ||    // \'
            TrimCasePattern("%27", str) ||       // "
            TrimCasePattern("%22", str) ||       // '
            TrimCasePattern("\"", str) ||
            TrimCasePattern("'", str));
  }
  TrimWhitespace(str);
}

// TODO(jmarantz): This is a very slow implementation.  But strncasecmp
// will fail test StringCaseTest.Locale.  If this shows up as a performance
// bottleneck then an SSE implementation would be better.
int StringCaseCompare(StringPiece s1, StringPiece s2) {
  for (int i = 0, n = std::min(s1.size(), s2.size()); i < n; ++i) {
    unsigned char c1 = UpperChar(s1[i]);
    unsigned char c2 = UpperChar(s2[i]);
    if (c1 < c2) {
      return -1;
    } else if (c1 > c2) {
      return 1;
    }
  }
  if (s1.size() < s2.size()) {
    return -1;
  } else if (s1.size() > s2.size()) {
    return 1;
  }
  return 0;
}

bool MemCaseEqual(const char* s1, size_t size1, const char* s2, size_t size2) {
  if (size1 != size2) {
    return false;
  }
  for (; size1 != 0; --size1, ++s1, ++s2) {
    if (UpperChar(*s1) != UpperChar(*s2)) {
      return false;
    }
  }
  return true;
}

bool SplitStringPieceToIntegerVector(StringPiece src, StringPiece separators,
                                     std::vector<int>* ints) {
  StringPieceVector values;
  SplitStringPieceToVector(
      src, separators, &values, true /* omit_empty_strings */);
  ints->clear();
  int v;
  for (int i = 0, n = values.size(); i < n; ++i) {
    if (StringToInt(values[i], &v)) {
      ints->push_back(v);
    } else {
      ints->clear();
      return false;
    }
  }
  return true;
}

}  // namespace net_instaweb