// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/omnibox/browser/shortcuts_provider.h"

#include <stddef.h>

#include <algorithm>
#include <cmath>
#include <map>
#include <utility>
#include <vector>

#include "base/i18n/case_conversion.h"
#include "base/logging.h"
#include "base/metrics/histogram.h"
#include "base/stl_util.h"
#include "base/strings/strcat.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_util.h"
#include "base/strings/utf_string_conversions.h"
#include "base/time/time.h"
#include "base/trace_event/trace_event.h"
#include "components/history/core/browser/history_service.h"
#include "components/omnibox/browser/autocomplete_i18n.h"
#include "components/omnibox/browser/autocomplete_input.h"
#include "components/omnibox/browser/autocomplete_match.h"
#include "components/omnibox/browser/autocomplete_provider_client.h"
#include "components/omnibox/browser/autocomplete_result.h"
#include "components/omnibox/browser/history_provider.h"
#include "components/omnibox/browser/match_compare.h"
#include "components/omnibox/browser/omnibox_field_trial.h"
#include "components/omnibox/browser/url_prefix.h"
#include "components/prefs/pref_service.h"
#include "components/search_engines/template_url_service.h"
#include "components/url_formatter/url_fixer.h"
#include "third_party/metrics_proto/omnibox_input_type.pb.h"
#include "url/third_party/mozilla/url_parse.h"

namespace {

class DestinationURLEqualsURL {
 public:
  explicit DestinationURLEqualsURL(const GURL& url) : url_(url) {}
  bool operator()(const AutocompleteMatch& match) const {
    return match.destination_url == url_;
  }

 private:
  const GURL url_;
};

// ShortcutMatch holds sufficient information about a single match from the
// shortcut database to allow for destination deduping and relevance sorting.
// After those stages the top matches are converted to the more heavyweight
// AutocompleteMatch struct.  Avoiding constructing the larger struct for
// every such match can save significant time when there are many shortcut
// matches to process.
struct ShortcutMatch {
  ShortcutMatch(int relevance,
                const GURL& stripped_destination_url,
                const ShortcutsDatabase::Shortcut* shortcut)
      : relevance(relevance),
        stripped_destination_url(stripped_destination_url),
        shortcut(shortcut),
        contents(shortcut->match_core.contents),
        type(static_cast<AutocompleteMatch::Type>(shortcut->match_core.type)) {}

  int relevance;
  // To satisfy |CompareWithDemoteByType<>::operator()|.
  size_t subrelevance = 0;
  GURL stripped_destination_url;
  const ShortcutsDatabase::Shortcut* shortcut;
  base::string16 contents;
  AutocompleteMatch::Type type;

  AutocompleteMatch::Type GetDemotionType() const { return type; }
};

// Sorts |matches| by destination, taking into account demotions based on
// |page_classification| when resolving ties about which of several
// duplicates to keep.  The matches are also deduplicated.
void SortAndDedupMatches(
    metrics::OmniboxEventProto::PageClassification page_classification,
    std::vector<ShortcutMatch>* matches) {
  // Sort matches such that duplicate matches are consecutive.
  std::sort(matches->begin(), matches->end(),
            DestinationSort<ShortcutMatch>(page_classification));

  // Erase duplicate matches. Duplicate matches are those with
  // stripped_destination_url fields equal and non empty.
  matches->erase(
      std::unique(matches->begin(), matches->end(),
                  [](const ShortcutMatch& elem1, const ShortcutMatch& elem2) {
                    return !elem1.stripped_destination_url.is_empty() &&
                           (elem1.stripped_destination_url ==
                            elem2.stripped_destination_url);
                  }),
      matches->end());
}

}  // namespace

const int ShortcutsProvider::kShortcutsProviderDefaultMaxRelevance = 1199;

ShortcutsProvider::ShortcutsProvider(AutocompleteProviderClient* client)
    : AutocompleteProvider(AutocompleteProvider::TYPE_SHORTCUTS),
      client_(client),
      initialized_(false) {
  scoped_refptr<ShortcutsBackend> backend = client_->GetShortcutsBackend();
  if (backend) {
    backend->AddObserver(this);
    if (backend->initialized())
      initialized_ = true;
  }
}

void ShortcutsProvider::Start(const AutocompleteInput& input,
                              bool minimal_changes) {
  TRACE_EVENT0("omnibox", "ShortcutsProvider::Start");
  matches_.clear();

  if (input.from_omnibox_focus() ||
      (input.type() == metrics::OmniboxInputType::EMPTY) ||
      input.text().empty() || !initialized_)
    return;

  base::TimeTicks start_time = base::TimeTicks::Now();
  GetMatches(input);
  if (input.text().length() < 6) {
    base::TimeTicks end_time = base::TimeTicks::Now();
    std::string name = "ShortcutsProvider.QueryIndexTime." +
                       base::NumberToString(input.text().size());
    base::HistogramBase* counter = base::Histogram::FactoryGet(
        name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag);
    counter->Add(static_cast<int>((end_time - start_time).InMilliseconds()));
  }
}

void ShortcutsProvider::DeleteMatch(const AutocompleteMatch& match) {
  // Copy the URL since deleting from |matches_| will invalidate |match|.
  GURL url(match.destination_url);
  DCHECK(url.is_valid());

  // When a user deletes a match, they probably mean for the URL to disappear
  // out of history entirely. So nuke all shortcuts that map to this URL.
  scoped_refptr<ShortcutsBackend> backend =
      client_->GetShortcutsBackendIfExists();
  if (backend)  // Can be NULL in Incognito.
    backend->DeleteShortcutsWithURL(url);

  base::EraseIf(matches_, DestinationURLEqualsURL(url));
  // NOTE: |match| is now dead!

  // Delete the match from the history DB. This will eventually result in a
  // second call to DeleteShortcutsWithURL(), which is harmless.
  history::HistoryService* const history_service = client_->GetHistoryService();
  DCHECK(history_service);
  history_service->DeleteURLs({url});
}

ShortcutsProvider::~ShortcutsProvider() {
  scoped_refptr<ShortcutsBackend> backend =
      client_->GetShortcutsBackendIfExists();
  if (backend)
    backend->RemoveObserver(this);
}

void ShortcutsProvider::OnShortcutsLoaded() {
  initialized_ = true;
}

void ShortcutsProvider::GetMatches(const AutocompleteInput& input) {
  scoped_refptr<ShortcutsBackend> backend =
      client_->GetShortcutsBackendIfExists();
  if (!backend)
    return;
  // Get the URLs from the shortcuts database with keys that partially or
  // completely match the search term.
  base::string16 term_string(base::i18n::ToLower(input.text()));
  DCHECK(!term_string.empty());

  int max_relevance;
  if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance(
          input.current_page_classification(), &max_relevance))
    max_relevance = kShortcutsProviderDefaultMaxRelevance;
  TemplateURLService* template_url_service = client_->GetTemplateURLService();
  const base::string16 fixed_up_input(FixupUserInput(input).second);

  std::vector<ShortcutMatch> shortcut_matches;
  for (auto it = FindFirstMatch(term_string, backend.get());
       it != backend->shortcuts_map().end() &&
       base::StartsWith(it->first, term_string, base::CompareCase::SENSITIVE);
       ++it) {
    // Don't return shortcuts with zero relevance.
    int relevance = CalculateScore(term_string, it->second, max_relevance);
    if (relevance) {
      const ShortcutsDatabase::Shortcut& shortcut = it->second;
      GURL stripped_destination_url(AutocompleteMatch::GURLToStrippedGURL(
          shortcut.match_core.destination_url, input, template_url_service,
          shortcut.match_core.keyword));
      shortcut_matches.push_back(
          ShortcutMatch(relevance, stripped_destination_url, &it->second));
    }
  }
  // Remove duplicates.  This is important because it's common to have multiple
  // shortcuts pointing to the same URL, e.g., ma, mai, and mail all pointing
  // to mail.google.com, so typing "m" will return them all.  If we then simply
  // clamp to provider_max_matches_ and let the SortAndDedupMatches take care of
  // collapsing the duplicates, we'll effectively only be returning one match,
  // instead of several possibilities.
  //
  // Note that while removing duplicates, we don't populate a match's
  // |duplicate_matches| field--duplicates don't need to be preserved in the
  // matches because they are only used for deletions, and this provider
  // deletes matches based on the URL.
  SortAndDedupMatches(input.current_page_classification(), &shortcut_matches);

  // Find best matches.
  std::partial_sort(
      shortcut_matches.begin(),
      shortcut_matches.begin() +
          std::min(provider_max_matches_, shortcut_matches.size()),
      shortcut_matches.end(),
      [](const ShortcutMatch& elem1, const ShortcutMatch& elem2) {
        // Ensure a stable sort by sorting equal-relevance matches
        // alphabetically.
        return elem1.relevance == elem2.relevance
                   ? elem1.contents < elem2.contents
                   : elem1.relevance > elem2.relevance;
      });
  if (shortcut_matches.size() > provider_max_matches_) {
    shortcut_matches.erase(shortcut_matches.begin() + provider_max_matches_,
                           shortcut_matches.end());
  }
  // Create and initialize autocomplete matches from shortcut matches.
  // Also guarantee that all relevance scores are decreasing (but do not assign
  // any scores below 1).
  matches_.reserve(shortcut_matches.size());
  for (ShortcutMatch& match : shortcut_matches) {
    max_relevance = std::min(max_relevance, match.relevance);
    matches_.push_back(ShortcutToACMatch(*match.shortcut, max_relevance, input,
                                         fixed_up_input, term_string));
    if (max_relevance > 1)
      --max_relevance;
  }
}

AutocompleteMatch ShortcutsProvider::ShortcutToACMatch(
    const ShortcutsDatabase::Shortcut& shortcut,
    int relevance,
    const AutocompleteInput& input,
    const base::string16& fixed_up_input_text,
    const base::string16 term_string) {
  DCHECK(!input.text().empty());
  AutocompleteMatch match;
  match.provider = this;
  match.relevance = relevance;
  match.deletable = true;
  match.fill_into_edit = shortcut.match_core.fill_into_edit;
  match.destination_url = shortcut.match_core.destination_url;
  DCHECK(match.destination_url.is_valid());
  match.document_type = static_cast<AutocompleteMatch::DocumentType>(
      shortcut.match_core.document_type);
  match.contents = shortcut.match_core.contents;
  match.contents_class = AutocompleteMatch::ClassificationsFromString(
      shortcut.match_core.contents_class);
  match.description = shortcut.match_core.description;
  match.description_class = AutocompleteMatch::ClassificationsFromString(
      shortcut.match_core.description_class);
  match.transition = ui::PageTransitionFromInt(shortcut.match_core.transition);
  match.type = static_cast<AutocompleteMatch::Type>(shortcut.match_core.type);
  match.keyword = shortcut.match_core.keyword;
  match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits);
  match.RecordAdditionalInfo("last access time", shortcut.last_access_time);
  match.RecordAdditionalInfo("original input text",
                             base::UTF16ToUTF8(shortcut.text));

  // Set |inline_autocompletion| and |allowed_to_be_default_match| if possible.
  // If the input is in keyword mode, navigation matches cannot be the default
  // match, and search query matches can only be the default match if their
  // keywords matches the input's keyword, as otherwise, default,
  // different-keyword matches may result in leaving keyword mode. Additionally,
  // if the match is a search query, check whether the user text is a prefix of
  // the query. If the match is a navigation, we assume the fill_into_edit looks
  // something like a URL, so we use URLPrefix::GetInlineAutocompleteOffset() to
  // try and strip off any prefixes that the user might not think would change
  // the meaning, but would otherwise prevent inline autocompletion. This
  // allows, for example, the input of "foo.c" to autocomplete to "foo.com" for
  // a fill_into_edit of "http://foo.com".
  const bool is_search_type = AutocompleteMatch::IsSearchType(match.type);

  DCHECK(is_search_type != match.keyword.empty());

  const bool keyword_matches =
      base::StartsWith(base::UTF16ToUTF8(input.text()),
                       base::StrCat({base::UTF16ToUTF8(match.keyword), " "}),
                       base::CompareCase::INSENSITIVE_ASCII);
  if (is_search_type) {
    const TemplateURL* template_url =
        client_->GetTemplateURLService()->GetDefaultSearchProvider();
    match.from_keyword =
        // Either the default search provider is disabled,
        !template_url ||
        // or the match is not from the default search provider,
        match.keyword != template_url->keyword() ||
        // or keyword mode was invoked explicitly and the keyword in the input
        // is also of the default search provider.
        (input.prefer_keyword() && keyword_matches);
  }
  // True if input is in keyword mode and the match is a URL suggestion or the
  // match has a different keyword.
  bool would_cause_leaving_keyword_mode =
      input.prefer_keyword() && !(is_search_type && keyword_matches);

  if (!would_cause_leaving_keyword_mode) {
    if (is_search_type) {
      if (match.fill_into_edit.size() >= input.text().size() &&
          std::equal(match.fill_into_edit.begin(),
                     match.fill_into_edit.begin() + input.text().size(),
                     input.text().begin(),
                     SimpleCaseInsensitiveCompareUCS2())) {
        match.inline_autocompletion =
            match.fill_into_edit.substr(input.text().length());
        match.allowed_to_be_default_match =
            !input.prevent_inline_autocomplete() ||
            match.inline_autocompletion.empty();
      }
    } else {
      const size_t inline_autocomplete_offset =
          URLPrefix::GetInlineAutocompleteOffset(
              input.text(), fixed_up_input_text, true, match.fill_into_edit);
      if (inline_autocomplete_offset != base::string16::npos) {
        match.inline_autocompletion =
            match.fill_into_edit.substr(inline_autocomplete_offset);
        match.SetAllowedToBeDefault(input);
      }
    }
  }

  // Try to mark pieces of the contents and description as matches if they
  // appear in |input.text()|.
  if (!term_string.empty()) {
    match.contents_class = ClassifyAllMatchesInString(
        term_string, match.contents, is_search_type, match.contents_class);
    match.description_class = ClassifyAllMatchesInString(
        term_string, match.description,
        /*text_is_search_query=*/false, match.description_class);
  }
  return match;
}

ShortcutsBackend::ShortcutMap::const_iterator ShortcutsProvider::FindFirstMatch(
    const base::string16& keyword,
    ShortcutsBackend* backend) {
  DCHECK(backend);
  auto it = backend->shortcuts_map().lower_bound(keyword);
  // Lower bound not necessarily matches the keyword, check for item pointed by
  // the lower bound iterator to at least start with keyword.
  return ((it == backend->shortcuts_map().end()) ||
          base::StartsWith(it->first, keyword, base::CompareCase::SENSITIVE))
             ? it
             : backend->shortcuts_map().end();
}

int ShortcutsProvider::CalculateScore(
    const base::string16& terms,
    const ShortcutsDatabase::Shortcut& shortcut,
    int max_relevance) {
  DCHECK(!terms.empty());
  DCHECK_LE(terms.length(), shortcut.text.length());

  // The initial score is based on how much of the shortcut the user has typed.
  // Using the square root of the typed fraction boosts the base score rapidly
  // as characters are typed, compared with simply using the typed fraction
  // directly. This makes sense since the first characters typed are much more
  // important for determining how likely it is a user wants a particular
  // shortcut than are the remaining continued characters.
  double base_score = max_relevance * sqrt(static_cast<double>(terms.length()) /
                                           shortcut.text.length());

  // Then we decay this by half each week.
  const double kLn2 = 0.6931471805599453;
  base::TimeDelta time_passed = base::Time::Now() - shortcut.last_access_time;
  // Clamp to 0 in case time jumps backwards (e.g. due to DST).
  double decay_exponent =
      std::max(0.0, kLn2 * static_cast<double>(time_passed.InMicroseconds()) /
                        base::Time::kMicrosecondsPerWeek);

  // We modulate the decay factor based on how many times the shortcut has been
  // used. Newly created shortcuts decay at full speed; otherwise, decaying by
  // half takes |n| times as much time, where n increases by
  // (1.0 / each 5 additional hits), up to a maximum of 5x as long.
  const double kMaxDecaySpeedDivisor = 5.0;
  const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0;
  double decay_divisor = std::min(
      kMaxDecaySpeedDivisor,
      (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) /
          kNumUsesPerDecaySpeedDivisorIncrement);

  return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) +
                          0.5);
}