blob: ac5516b7296c40059aa7cc6fe4146fd927e65afa [file] [log] [blame]
// Copyright 2014 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/bookmarks/core/browser/bookmark_index.h"
#include <algorithm>
#include <functional>
#include <iterator>
#include <list>
#include "base/i18n/case_conversion.h"
#include "base/logging.h"
#include "base/strings/string16.h"
#include "base/strings/utf_offset_string_conversions.h"
#include "components/bookmarks/core/browser/bookmark_client.h"
#include "components/bookmarks/core/browser/bookmark_match.h"
#include "components/bookmarks/core/browser/bookmark_node.h"
#include "components/bookmarks/core/browser/bookmark_utils.h"
#include "components/query_parser/query_parser.h"
#include "components/query_parser/snippet.h"
#include "third_party/icu/source/common/unicode/normalizer2.h"
typedef BookmarkClient::NodeTypedCountPair NodeTypedCountPair;
typedef BookmarkClient::NodeTypedCountPairs NodeTypedCountPairs;
namespace {
// Returns a normalized version of the UTF16 string |text|. If it fails to
// normalize the string, returns |text| itself as a best-effort.
base::string16 Normalize(const base::string16& text) {
UErrorCode status = U_ZERO_ERROR;
const icu::Normalizer2* normalizer2 =
icu::Normalizer2::getInstance(NULL, "nfkc", UNORM2_COMPOSE, status);
icu::UnicodeString unicode_text(
text.data(), static_cast<int32_t>(text.length()));
icu::UnicodeString unicode_normalized_text;
normalizer2->normalize(unicode_text, unicode_normalized_text, status);
if (U_FAILURE(status))
return text;
return base::string16(unicode_normalized_text.getBuffer(),
unicode_normalized_text.length());
}
// Sort functor for NodeTypedCountPairs. We sort in decreasing order of typed
// count so that the best matches will always be added to the results.
struct NodeTypedCountPairSortFunctor
: std::binary_function<NodeTypedCountPair, NodeTypedCountPair, bool> {
bool operator()(const NodeTypedCountPair& a,
const NodeTypedCountPair& b) const {
return a.second > b.second;
}
};
// Extract the const Node* stored in a BookmarkClient::NodeTypedCountPair.
struct NodeTypedCountPairExtractNodeFunctor
: std::unary_function<NodeTypedCountPair, const BookmarkNode*> {
const BookmarkNode* operator()(const NodeTypedCountPair& pair) const {
return pair.first;
}
};
} // namespace
// Used when finding the set of bookmarks that match a query. Each match
// represents a set of terms (as an interator into the Index) matching the
// query as well as the set of nodes that contain those terms in their titles.
struct BookmarkIndex::Match {
// List of terms matching the query.
std::list<Index::const_iterator> terms;
// The set of nodes matching the terms. As an optimization this is empty
// when we match only one term, and is filled in when we get more than one
// term. We can do this as when we have only one matching term we know
// the set of matching nodes is terms.front()->second.
//
// Use nodes_begin() and nodes_end() to get an iterator over the set as
// it handles the necessary switching between nodes and terms.front().
NodeSet nodes;
// Returns an iterator to the beginning of the matching nodes. See
// description of nodes for why this should be used over nodes.begin().
NodeSet::const_iterator nodes_begin() const;
// Returns an iterator to the beginning of the matching nodes. See
// description of nodes for why this should be used over nodes.end().
NodeSet::const_iterator nodes_end() const;
};
BookmarkIndex::NodeSet::const_iterator
BookmarkIndex::Match::nodes_begin() const {
return nodes.empty() ? terms.front()->second.begin() : nodes.begin();
}
BookmarkIndex::NodeSet::const_iterator BookmarkIndex::Match::nodes_end() const {
return nodes.empty() ? terms.front()->second.end() : nodes.end();
}
BookmarkIndex::BookmarkIndex(BookmarkClient* client,
bool index_urls,
const std::string& languages)
: client_(client),
languages_(languages),
index_urls_(index_urls) {
DCHECK(client_);
}
BookmarkIndex::~BookmarkIndex() {
}
void BookmarkIndex::Add(const BookmarkNode* node) {
if (!node->is_url())
return;
std::vector<base::string16> terms =
ExtractQueryWords(Normalize(node->GetTitle()));
for (size_t i = 0; i < terms.size(); ++i)
RegisterNode(terms[i], node);
if (index_urls_) {
terms = ExtractQueryWords(bookmark_utils::CleanUpUrlForMatching(
node->url(), languages_, NULL));
for (size_t i = 0; i < terms.size(); ++i)
RegisterNode(terms[i], node);
}
}
void BookmarkIndex::Remove(const BookmarkNode* node) {
if (!node->is_url())
return;
std::vector<base::string16> terms =
ExtractQueryWords(Normalize(node->GetTitle()));
for (size_t i = 0; i < terms.size(); ++i)
UnregisterNode(terms[i], node);
if (index_urls_) {
terms = ExtractQueryWords(bookmark_utils::CleanUpUrlForMatching(
node->url(), languages_, NULL));
for (size_t i = 0; i < terms.size(); ++i)
UnregisterNode(terms[i], node);
}
}
void BookmarkIndex::GetBookmarksMatching(const base::string16& input_query,
size_t max_count,
std::vector<BookmarkMatch>* results) {
const base::string16 query = Normalize(input_query);
std::vector<base::string16> terms = ExtractQueryWords(query);
if (terms.empty())
return;
Matches matches;
for (size_t i = 0; i < terms.size(); ++i) {
if (!GetBookmarksMatchingTerm(terms[i], i == 0, &matches))
return;
}
Nodes sorted_nodes;
SortMatches(matches, &sorted_nodes);
// We use a QueryParser to fill in match positions for us. It's not the most
// efficient way to go about this, but by the time we get here we know what
// matches and so this shouldn't be performance critical.
query_parser::QueryParser parser;
ScopedVector<query_parser::QueryNode> query_nodes;
parser.ParseQueryNodes(query, &query_nodes.get());
// The highest typed counts should be at the beginning of the results vector
// so that the best matches will always be included in the results. The loop
// that calculates result relevance in HistoryContentsProvider::ConvertResults
// will run backwards to assure higher relevance will be attributed to the
// best matches.
for (Nodes::const_iterator i = sorted_nodes.begin();
i != sorted_nodes.end() && results->size() < max_count;
++i)
AddMatchToResults(*i, &parser, query_nodes.get(), results);
}
void BookmarkIndex::SortMatches(const Matches& matches,
Nodes* sorted_nodes) const {
NodeSet nodes;
for (Matches::const_iterator i = matches.begin(); i != matches.end(); ++i) {
#if !defined(OS_ANDROID)
nodes.insert(i->nodes_begin(), i->nodes_end());
#else
// Work around a bug in the implementation of std::set::insert in the STL
// used on android (http://crbug.com/367050).
for (NodeSet::const_iterator n = i->nodes_begin(); n != i->nodes_end(); ++n)
nodes.insert(nodes.end(), *n);
#endif
}
sorted_nodes->reserve(sorted_nodes->size() + nodes.size());
if (client_->SupportsTypedCountForNodes()) {
NodeTypedCountPairs node_typed_counts;
client_->GetTypedCountForNodes(nodes, &node_typed_counts);
std::sort(node_typed_counts.begin(),
node_typed_counts.end(),
NodeTypedCountPairSortFunctor());
std::transform(node_typed_counts.begin(),
node_typed_counts.end(),
std::back_inserter(*sorted_nodes),
NodeTypedCountPairExtractNodeFunctor());
} else {
sorted_nodes->insert(sorted_nodes->end(), nodes.begin(), nodes.end());
}
}
void BookmarkIndex::AddMatchToResults(
const BookmarkNode* node,
query_parser::QueryParser* parser,
const query_parser::QueryNodeStarVector& query_nodes,
std::vector<BookmarkMatch>* results) {
// Check that the result matches the query. The previous search
// was a simple per-word search, while the more complex matching
// of QueryParser may filter it out. For example, the query
// ["thi"] will match the bookmark titled [Thinking], but since
// ["thi"] is quoted we don't want to do a prefix match.
query_parser::QueryWordVector title_words, url_words;
const base::string16 lower_title =
base::i18n::ToLower(Normalize(node->GetTitle()));
parser->ExtractQueryWords(lower_title, &title_words);
base::OffsetAdjuster::Adjustments adjustments;
if (index_urls_) {
parser->ExtractQueryWords(bookmark_utils::CleanUpUrlForMatching(
node->url(), languages_, &adjustments), &url_words);
}
query_parser::Snippet::MatchPositions title_matches, url_matches;
for (size_t i = 0; i < query_nodes.size(); ++i) {
const bool has_title_matches =
query_nodes[i]->HasMatchIn(title_words, &title_matches);
const bool has_url_matches = index_urls_ &&
query_nodes[i]->HasMatchIn(url_words, &url_matches);
if (!has_title_matches && !has_url_matches)
return;
query_parser::QueryParser::SortAndCoalesceMatchPositions(&title_matches);
if (index_urls_)
query_parser::QueryParser::SortAndCoalesceMatchPositions(&url_matches);
}
BookmarkMatch match;
if (lower_title.length() == node->GetTitle().length()) {
// Only use title matches if the lowercase string is the same length
// as the original string, otherwise the matches are meaningless.
// TODO(mpearson): revise match positions appropriately.
match.title_match_positions.swap(title_matches);
}
if (index_urls_) {
// Now that we're done processing this entry, correct the offsets of the
// matches in |url_matches| so they point to offsets in the original URL
// spec, not the cleaned-up URL string that we used for matching.
std::vector<size_t> offsets =
BookmarkMatch::OffsetsFromMatchPositions(url_matches);
base::OffsetAdjuster::UnadjustOffsets(adjustments, &offsets);
url_matches =
BookmarkMatch::ReplaceOffsetsInMatchPositions(url_matches, offsets);
match.url_match_positions.swap(url_matches);
}
match.node = node;
results->push_back(match);
}
bool BookmarkIndex::GetBookmarksMatchingTerm(const base::string16& term,
bool first_term,
Matches* matches) {
Index::const_iterator i = index_.lower_bound(term);
if (i == index_.end())
return false;
if (!query_parser::QueryParser::IsWordLongEnoughForPrefixSearch(term)) {
// Term is too short for prefix match, compare using exact match.
if (i->first != term)
return false; // No bookmarks with this term.
if (first_term) {
Match match;
match.terms.push_back(i);
matches->push_back(match);
return true;
}
CombineMatchesInPlace(i, matches);
} else if (first_term) {
// This is the first term and we're doing a prefix match. Loop through
// index adding all entries that start with term to matches.
while (i != index_.end() &&
i->first.size() >= term.size() &&
term.compare(0, term.size(), i->first, 0, term.size()) == 0) {
Match match;
match.terms.push_back(i);
matches->push_back(match);
++i;
}
} else {
// Prefix match and not the first term. Loop through index combining
// current matches in matches with term, placing result in result.
Matches result;
while (i != index_.end() &&
i->first.size() >= term.size() &&
term.compare(0, term.size(), i->first, 0, term.size()) == 0) {
CombineMatches(i, *matches, &result);
++i;
}
matches->swap(result);
}
return !matches->empty();
}
void BookmarkIndex::CombineMatchesInPlace(const Index::const_iterator& index_i,
Matches* matches) {
for (size_t i = 0; i < matches->size(); ) {
Match* match = &((*matches)[i]);
NodeSet intersection;
std::set_intersection(match->nodes_begin(), match->nodes_end(),
index_i->second.begin(), index_i->second.end(),
std::inserter(intersection, intersection.begin()));
if (intersection.empty()) {
matches->erase(matches->begin() + i);
} else {
match->terms.push_back(index_i);
match->nodes.swap(intersection);
++i;
}
}
}
void BookmarkIndex::CombineMatches(const Index::const_iterator& index_i,
const Matches& current_matches,
Matches* result) {
for (size_t i = 0; i < current_matches.size(); ++i) {
const Match& match = current_matches[i];
NodeSet intersection;
std::set_intersection(match.nodes_begin(), match.nodes_end(),
index_i->second.begin(), index_i->second.end(),
std::inserter(intersection, intersection.begin()));
if (!intersection.empty()) {
result->push_back(Match());
Match& combined_match = result->back();
combined_match.terms = match.terms;
combined_match.terms.push_back(index_i);
combined_match.nodes.swap(intersection);
}
}
}
std::vector<base::string16> BookmarkIndex::ExtractQueryWords(
const base::string16& query) {
std::vector<base::string16> terms;
if (query.empty())
return std::vector<base::string16>();
query_parser::QueryParser parser;
parser.ParseQueryWords(base::i18n::ToLower(query), &terms);
return terms;
}
void BookmarkIndex::RegisterNode(const base::string16& term,
const BookmarkNode* node) {
index_[term].insert(node);
}
void BookmarkIndex::UnregisterNode(const base::string16& term,
const BookmarkNode* node) {
Index::iterator i = index_.find(term);
if (i == index_.end()) {
// We can get here if the node has the same term more than once. For
// example, a bookmark with the title 'foo foo' would end up here.
return;
}
i->second.erase(node);
if (i->second.empty())
index_.erase(i);
}