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" },
+  { "frankly frankly frank", "http://www.catsanddogs.com/h" },
+  { "abcdefghijklmnopqrstuvwx bcdefghijklmnopqrstuvwxy "
+    "cdefghijklmnopqrstuvwxyz defghijklmnopqrstuvwxyz01",
+    "http://www.catsanddogs.com/i" },
+};
+
+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;
+
+  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);
+  }
+}
+
+// Structures and functions supporting the BookmarkProviderTest.Positions
+// unit test.
+
+struct TestBookmarkPosition {
+  TestBookmarkPosition(size_t begin, size_t end)
+      : begin(begin), end(end) {}
+
+  // Log the positions for unit test diagnostics.

[Peter Kasting, 2012/10/10 18:29:06]

Nit: Is this a comment about the class as a whole?  In which case it should be
above the class.

[mrossetti, 2012/10/15 19:22:46]

Removed leftovers.

On 2012/10/10 18:29:06, Peter Kasting wrote:

+
+  size_t begin;
+  size_t end;
+};
+typedef std::vector<TestBookmarkPosition> TestBookmarkPositions;
+
+void DumpTestBookmarkPositions(const char* title,
+                               const TestBookmarkPositions& positions) {
+  LOG(WARNING) << title << ":";

[Peter Kasting, 2012/10/10 18:29:06]

Using LOG(WARNING) directly doesn't seem right.  Can we maybe return a string
instead, so that the caller can do something more like:

EXPECT_TRUE(...) << "EXPECTED: " << BookmarkPositions(...) << "ACTUAL: " <<
BookmarkPositions(...);

[mrossetti, 2012/10/15 19:22:46]

Great idea! Done.

On 2012/10/10 18:29:06, Peter Kasting wrote:

+  for (TestBookmarkPositions::const_iterator i = positions.begin();
+       i != positions.end(); ++i) {
+    LOG(WARNING) << "{" << i->begin << ", " << i->end << "}";
+  }
+}
+
+// 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) {

[Peter Kasting, 2012/10/10 18:29:06]

Nit: One arg per line

[mrossetti, 2012/10/15 19:22:46]

Done.

+  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}}}},
+    // 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}}}},
+    // 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}}}},
+    // This next set is for scoring validation of single term matches.

[Peter Kasting, 2012/10/10 18:29:06]

I would really rather not expect precise scores from the scoring algorithm. 
This will break any time anyone makes a change to the algorithm for good or ill,
and people will just blindly paste the new values in.

Instead can we write the test so it expects more general conditions, things like
"longer matches score higher than shorter ones" and the like?  These will
require less maintenance but be more likely to actually catch regressions.

[mrossetti, 2012/10/15 19:22:46]

Okay. Done.

On 2012/10/10 18:29:06, Peter Kasting wrote:

+    // 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
+    //
+    // Multiply 299, the available score range, by the factor and round down.
+    // 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}}}},
+    // This set uses duplicated search terms.
+    {"frank",                 1, {{{0, 5}, {8, 13}, {16, 21}, {1032, 0}}}},
+    {"frankly",               1, {{{0, 7}, {8, 15}, {1061, 0}}}},
+    {"frankly frankly",       1, {{{0, 7}, {8, 15}, {1061, 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]));
+      bool positions_equal = std::equal(expected_positions.begin(),
+                                        expected_positions.end(),
+                                        actual_positions.begin(),
+                                        TestBookmarkPositionsEqual);
+      EXPECT_TRUE(positions_equal)
+            << " for match[" << j << "] ('" << matches[j].description
+            << "') for query[" << i
+            << "] ('" << query_data[i].query << "').";
+      if (!positions_equal) {
+        DumpTestBookmarkPositions("EXPECTED", expected_positions);
+        DumpTestBookmarkPositions("ACTUAL", actual_positions);
+      }
+      if (expected_score != 0)
+        EXPECT_EQ(expected_score, matches[j].relevance)
+            << " for match[" << j << "] ('" << matches[j].description
+            << "') for query[" << i
+            << "] ('" << query_data[i].query << "').";
+    }
+  }
+}