Implement Bookmark Autocomplete Provider

chrome/browser/autocomplete/bookmark_provider_unittest.cc

+// 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 "chrome/browser/autocomplete/bookmark_provider.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "base/memory/ref_counted.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/utf_string_conversions.h"
+#include "chrome/browser/autocomplete/autocomplete_provider.h"
+#include "chrome/browser/autocomplete/autocomplete_provider_listener.h"
+#include "chrome/browser/bookmarks/bookmark_model.h"
+#include "chrome/browser/bookmarks/bookmark_model_factory.h"
+#include "chrome/test/base/testing_profile.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// The bookmark corpus against which we will simulate searches.
+struct BookmarksTestInfo {
+  std::string title;
+  std::string url;
+} bookmark_provider_test_data[] = {
+  { "abc def", "http://www.catsanddogs.com/a" },
+  { "abcde", "http://www.catsanddogs.com/b" },
+  { "abcdef", "http://www.catsanddogs.com/c" },
+  { "a definition", "http://www.catsanddogs.com/d" },
+  { "carry carbon carefully", "http://www.catsanddogs.com/e" },
+  { "ghi jkl", "http://www.catsanddogs.com/f" },
+  { "jkl ghi", "http://www.catsanddogs.com/g" },
+  { "abcdefghijklmnopqrstuvwx bcdefghijklmnopqrstuvwxy "
+    "cdefghijklmnopqrstuvwxyz defghijklmnopqrstuvwxyz01",
+    "http://www.catsanddogs.com/h" },
+};
+
+class BookmarkProviderTest : public testing::Test,
+                             public AutocompleteProviderListener {
+ public:
+  BookmarkProviderTest() : model_(new BookmarkModel(NULL)) {}
+
+  // AutocompleteProviderListener: Not called.
+  virtual void OnProviderUpdate(bool updated_matches) OVERRIDE {}
+
+ protected:
+  virtual void SetUp() OVERRIDE;
+  virtual void TearDown() OVERRIDE;
+
+  scoped_ptr<TestingProfile> profile_;
+  scoped_ptr<BookmarkModel> model_;
+  scoped_refptr<BookmarkProvider> provider_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(BookmarkProviderTest);
+};
+
+void BookmarkProviderTest::SetUp() {
+  profile_.reset(new TestingProfile());
+  DCHECK(profile_.get());
+  provider_ = new BookmarkProvider(this, profile_.get());
+  DCHECK(provider_);
+  provider_->set_bookmark_model_for_testing(model_.get());
+
+  const BookmarkNode* other_node = model_->other_node();
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(bookmark_provider_test_data); ++i) {
+    const BookmarksTestInfo& cur(bookmark_provider_test_data[i]);
+    const GURL url(cur.url);
+    model_->AddURL(other_node, other_node->child_count(),
+                   ASCIIToUTF16(cur.title), url);
+  }
+}
+
+void BookmarkProviderTest::TearDown() {
+}
+
+// Structures and functions supporting the BookmarkProviderTest.Positions
+// unit test.
+
+struct TestBookmarkPosition {
+  TestBookmarkPosition(size_t begin, size_t end)
+      : begin(begin), end(end) {}
+  size_t begin;
+  size_t end;
+};
+typedef std::vector<TestBookmarkPosition> TestBookmarkPositions;
+
+// Comparison function for sorting search terms by descending length.
+bool TestBookmarkPositionsEqual(const TestBookmarkPosition& pos_a,
+                                const TestBookmarkPosition& pos_b) {
+  return pos_a.begin == pos_b.begin && pos_a.end == pos_b.end;
+}
+
+// Convience function to make comparing ACMatchClassifications against the
+// test expectations structure easier.
+TestBookmarkPositions PositionsFromAutocompleteMatch(
+    const AutocompleteMatch& match) {
+  TestBookmarkPositions positions;
+  bool started = false;
+  size_t start = 0;
+  for (AutocompleteMatch::ACMatchClassifications::const_iterator
+       i = match.description_class.begin();
+       i != match.description_class.end(); ++i) {
+    if (i->style & AutocompleteMatch::ACMatchClassification::MATCH) {
+      // We have found the start of a match.
+      EXPECT_FALSE(started);
+      started = true;
+      start = i->offset;
+    } else if (started) {
+      // We have found the end of a match.
+      started = false;
+      positions.push_back(TestBookmarkPosition(start, i->offset));
+      start = 0;
+    }
+  }
+  // Record the final position if the last match goes to the end of the
+  // candidate string.
+  if (started)
+    positions.push_back(TestBookmarkPosition(start, match.description.size()));
+  return positions;
+}
+
+// Convience function to make comparing test expectations structure against the
+// actual ACMatchClassifications easier.
+TestBookmarkPositions PositionsFromExpectations(
+    const size_t expectations[9][2], int* score) {
+  TestBookmarkPositions positions;
+  size_t i = 0;
+  // The array is zero-terminated in the [1]th element.
+  while (expectations[i][1]) {
+    positions.push_back(
+        TestBookmarkPosition(expectations[i][0], expectations[i][1]));
+    ++i;
+  }
+  if (score)
+    *score = static_cast<int>(expectations[i][0]);
+  return positions;
+}
+
+TEST_F(BookmarkProviderTest, PositionsAndScores) {
+  // Simulate searches.
+  // Description of |positions|:
+  //   The first index represents the collection of positions for each expected
+  //   match. The count of the actual subarrays in each instance of |query_data|
+  //   must equal |match_count|. The second index represents each expected
+  //   match position. The third index represents the |start| and |end| of the
+  //   expected match's position within the |test_data|. This array must be
+  //   terminated by an entry with a value of '0' for |end| and the expected
+  //   score for |begin|. If the score is zero then do not test the score for
+  //   the match.
+  // Example:
+  //   Consider the line for 'def' below:
+  //     {"def", 2, {{{4, 7}, {XXX, 0}}, {{2, 5}, {11, 14}, {XXX, 0}}}},
+  //   There are two expected matches:
+  //     0. {{4, 7}, {XXX, 0}}
+  //     1. {{2, 5}, {11 ,14}, {XXX, 0}}
+  //   For the first match, [0], there is one match within the bookmark's title
+  //   expected, {4, 7}, which maps to the 'def' within "abc def". The expected
+  //   score is XXX. The second match, [1], indicates that two matches are
+  //   expected within the bookmark title "a definite definition". In each case,
+  //   the {score, 0} indicates the end of the subarray. Or:
+  //                 Match #1            Match #2
+  //                 ------------------  ----------------------------
+  //                  Pos1    Term        Pos1    Pos2      Term
+  //                  ------  --------    ------  --------  --------
+  //     {"def", 2, {{{4, 7}, {XXX, 0}}, {{2, 5}, {11, 14}, {XXX, 0}}}},
+  //
+  struct QueryData {
+    const std::string query;
+    const size_t match_count;
+    const size_t positions[99][9][2];
+  } query_data[] = {
+    // This first set is primarily for position detection validation.
+    {"abc",                   3, {{{0, 3}, {0, 0}},
+                                  {{0, 3}, {0, 0}},
+                                  {{0, 3}, {0, 0}}}},
+    {"abcde",                 3, {{{0, 5}, {1199, 0}},
+                                  {{0, 5}, {1149, 0}},
+                                  {{0, 5}, {914, 0}}}},
+    {"foo bar",               0, {{{0, 0}}}},
+    {"fooey bark",            0, {{{0, 0}}}},
+    {"def",                   3, {{{2, 5}, {0, 0}},
+                                  {{4, 7}, {0, 0}},
+                                  {{75, 78}, {902, 0}}}},
+    {"ghi jkl",               2, {{{0, 3}, {4, 7}, {0, 0}},
+                                  {{0, 3}, {4, 7}, {0, 0}}}},
+    // NB: GetBookmarksWithTitlesMatching(...) uses exact match for "a".
+    {"a",                     1, {{{0, 1}, {0, 0}}}},
+    {"a d",                   0, {{{0, 0}}}},
+    {"carry carbon",          1, {{{0, 5}, {6, 12}, {0, 0}}}},
+    // Quoted terms are single terms.
+    {"\"carry carbon\"",      1, {{{0, 12}, {0, 0}}}},
+    {"\"carry carbon\" care", 1, {{{0, 12}, {13, 17}, {0, 0}}}},
+    // Quoted terms require complete word matches.
+    {"\"carry carbo\"",       0, {{{0, 0}}}},
+    // NB: GetBookmarksWithTitlesMatching(...) sorts the match positions.
+    {"carbon carry",          1, {{{0, 5}, {6, 12}, {0, 0}}}},
+    {"arbon",                 0, {{{0, 0}}}},
+    {"ar",                    0, {{{0, 0}}}},
+    {"arry",                  0, {{{0, 0}}}},
+    // This next set is for scoring validation of single term matches.
+    // To hand-calculate the expected scores, as has been done below, use the
+    // following formula:
+    //
+    //   factor = match_len / title_len * (title_len - match_pos) / title_len
+    //
+    // Round factor down then multiply by 299, the available score range.
+    // Finally, add 900, the base score.
+    {"abcdefghijklmnopqrstuvwx",   1, {{{0, 24}, {971, 0}}}},
+    {"bcdefghijklmnopqrstuvwxy",   1, {{{25, 49}, {953, 0}}}},
+    {"cdefghijklmnopqrstuvwxyz",   1, {{{50, 74}, {935, 0}}}},
+    {"defghijklmnopqrstuvwxyz01",  1, {{{75, 100}, {918, 0}}}},
+    // This next set is for scoring validation of multiple term matches.
+    // To hand-calculate the expected scores, as has been done below, use the
+    // formula above to calculate a factor for each term match, calculate the
+    // sum of all factors, round the resulting factor down, multiply by
+    // 299 and add 900.
+    {"abcdefghijklmnopqrstuvwx bcdefghijklmnopqrstuvwxy",
+     1, {{{0, 24}, {25, 49}, {1025, 0}}}},
+    {"abcdefghijklmnopqrstuvwx cdefghijklmnopqrstuvwxyz",
+     1, {{{0, 24}, {50, 74}, {1007, 0}}}},
+    {"abcdefghijklmnopqrstuvwx defghijklmnopqrstuvwxyz01",
+     1, {{{0, 24}, {75, 100}, {990, 0}}}},
+    {"bcdefghijklmnopqrstuvwxy cdefghijklmnopqrstuvwxyz",
+     1, {{{25, 49}, {50, 74}, {989, 0}}}},
+    {"bcdefghijklmnopqrstuvwxy defghijklmnopqrstuvwxyz01",
+     1, {{{25, 49}, {75, 100}, {972, 0}}}},
+    {"cdefghijklmnopqrstuvwxyz defghijklmnopqrstuvwxyz01",
+     1, {{{50, 74}, {75, 100}, {954, 0}}}},
+  };
+
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(query_data); ++i) {
+    AutocompleteInput input(ASCIIToUTF16(query_data[i].query),
+                            string16(), false, false,  false,
+                            AutocompleteInput::ALL_MATCHES);
+    provider_->Start(input, false);
+    const ACMatches& matches(provider_->matches());
+    // Validate number of results is as expected.
+    EXPECT_EQ(query_data[i].match_count, matches.size());
+    if (query_data[i].match_count != matches.size()) {
+      // Log the actual matches to aid in diagnosis.
+      LOG(ERROR) << "One or more of the following were unexpected:";
+      for (ACMatches::const_iterator j = matches.begin(); j != matches.end();
+           ++j)
+        LOG(ERROR) << "  '" << j->description << "'";
+      LOG(ERROR) << "For the search term: '" << query_data[i].query << "'";
+    }
+    // Validate positions within each match and final score is as expected.
+    for (size_t j = 0; j < matches.size(); ++j) {
+      // Collect the expected positions as a vector, collect the match's
+      // classifications for match positions as a vector, then compare.
+      int expected_score = 0;
+      TestBookmarkPositions expected_positions(
+          PositionsFromExpectations(query_data[i].positions[j],
+          &expected_score));
+      TestBookmarkPositions actual_positions(
+          PositionsFromAutocompleteMatch(matches[j]));
+      EXPECT_TRUE(std::equal(expected_positions.begin(),
+                             expected_positions.end(),
+                             actual_positions.begin(),
+                             TestBookmarkPositionsEqual))
+            << " for match[" << j << "] ('" << matches[j].description
+            << "') for query[" << i
+            << "] ('" << query_data[i].query << "').";
+      if (expected_score != 0)
+        EXPECT_EQ(expected_score, matches[j].relevance)
+            << " for match[" << j << "] ('" << matches[j].description
+            << "') for query[" << i
+            << "] ('" << query_data[i].query << "').";
+    }
+  }
+}