components/query_parser/snippet_unittest.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "components/query_parser/snippet.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/strings/string_split.h"
  10 #include "base/strings/string_util.h"
  11 #include "base/strings/utf_string_conversions.h"
  12 #include "testing/gtest/include/gtest/gtest.h"
  13
  14 namespace query_parser {
  15 namespace {
  16
  17 // A sample document to compute snippets of.
  18 // The \x bits after the first "Google" are UTF-8 of U+2122 TRADE MARK SIGN,
  19 // and are useful for verifying we don't screw up in UTF-8/UTF-16 conversion.
  20 const char* kSampleDocument = "Google\xe2\x84\xa2 Terms of Service "
  21 "Welcome to Google! "
  22 "1. Your relationship with Google "
  23 "1.1 Your use of Google's products, software, services and web sites "
  24 "(referred to collectively as the \"Services\" in this document and excluding "
  25 "any services provided to you by Google under a separate written agreement) "
  26 "is subject to the terms of a legal agreement between you and Google. "
  27 "\"Google\" means Google Inc., whose principal place of business is at 1600 "
  28 "Amphitheatre Parkway, Mountain View, CA 94043, United States. This document "
  29 "explains how the agreement is made up, and sets out some of the terms of "
  30 "that agreement.";
  31 };
  32
  33 // Thai sample taken from http://www.google.co.th/intl/th/privacy.html
  34 // TODO(jungshik) : Add more samples (e.g. Hindi) after porting
  35 // ICU 4.0's character iterator changes to our copy of ICU 3.8 to get
  36 // grapheme clusters in Indic scripts handled more reasonably.
  37 const char* kThaiSample = "Google \xE0\xB9\x80\xE0\xB8\x81\xE0\xB9\x87"
  38 "\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7"
  39 "\xE0\xB8\xA1 \xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9"
  40 "\xE0\xB8\xA5\xE0\xB8\xAA\xE0\xB9\x88\xE0\xB8\xA7\xE0\xB8\x99\xE0\xB8\x9A"
  41 "\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8\x84\xE0\xB8\xA5 \xE0\xB9\x80\xE0\xB8\xA1"
  42 "\xE0\xB8\xB7\xE0\xB9\x88\xE0\xB8\xAD\xE0\xB8\x84\xE0\xB8\xB8\xE0\xB8\x93"
  43 "\xE0\xB8\xA5\xE0\xB8\x87\xE0\xB8\x97\xE0\xB8\xB0\xE0\xB9\x80\xE0\xB8\x9A"
  44 "\xE0\xB8\xB5\xE0\xB8\xA2\xE0\xB8\x99\xE0\xB9\x80\xE0\xB8\x9E\xE0\xB8\xB7"
  45 "\xE0\xB9\x88\xE0\xB8\xAD\xE0\xB9\x83\xE0\xB8\x8A\xE0\xB9\x89\xE0\xB8\x9A"
  46 "\xE0\xB8\xA3\xE0\xB8\xB4\xE0\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3\xE0\xB8\x82"
  47 "\xE0\xB8\xAD\xE0\xB8\x87 Google \xE0\xB8\xAB\xE0\xB8\xA3\xE0\xB8\xB7"
  48 "\xE0\xB8\xAD\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89\xE0\xB8\x82\xE0\xB9\x89"
  49 "\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5\xE0\xB8\x94\xE0\xB8\xB1"
  50 "\xE0\xB8\x87\xE0\xB8\x81\xE0\xB8\xA5\xE0\xB9\x88\xE0\xB8\xB2\xE0\xB8\xA7"
  51 "\xE0\xB9\x82\xE0\xB8\x94\xE0\xB8\xA2\xE0\xB8\xAA\xE0\xB8\xA1\xE0\xB8\xB1"
  52 "\xE0\xB8\x84\xE0\xB8\xA3\xE0\xB9\x83\xE0\xB8\x88 \xE0\xB9\x80\xE0\xB8\xA3"
  53 "\xE0\xB8\xB2\xE0\xB8\xAD\xE0\xB8\xB2\xE0\xB8\x88\xE0\xB8\xA3\xE0\xB8\xA7"
  54 "\xE0\xB8\xA1\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9"
  55 "\xE0\xB8\xA5\xE0\xB8\xAA\xE0\xB9\x88\xE0\xB8\xA7\xE0\xB8\x99\xE0\xB8\x9A"
  56 "\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8\x84\xE0\xB8\xA5\xE0\xB8\x97\xE0\xB8\xB5"
  57 "\xE0\xB9\x88\xE0\xB9\x80\xE0\xB8\x81\xE0\xB9\x87\xE0\xB8\x9A\xE0\xB8\xA3"
  58 "\xE0\xB8\xA7\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\xA1\xE0\xB8\x88"
  59 "\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\x84\xE0\xB8\xB8\xE0\xB8\x93\xE0\xB9\x80"
  60 "\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\xB1\xE0\xB8\x9A"
  61 "\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5"
  62 "\xE0\xB8\x88\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xB4"
  63 "\xE0\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3\xE0\xB8\xAD\xE0\xB8\xB7\xE0\xB9\x88"
  64 "\xE0\xB8\x99\xE0\xB8\x82\xE0\xB8\xAD\xE0\xB8\x87 Google \xE0\xB8\xAB"
  65 "\xE0\xB8\xA3\xE0\xB8\xB7\xE0\xB8\xAD\xE0\xB8\x9A\xE0\xB8\xB8\xE0\xB8\x84"
  66 "\xE0\xB8\x84\xE0\xB8\xA5\xE0\xB8\x97\xE0\xB8\xB5\xE0\xB9\x88\xE0\xB8\xAA"
  67 "\xE0\xB8\xB2\xE0\xB8\xA1 \xE0\xB9\x80\xE0\xB8\x9E\xE0\xB8\xB7\xE0\xB9\x88"
  68 "\xE0\xB8\xAD\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89\xE0\xB8\x9C\xE0\xB8\xB9"
  69 "\xE0\xB9\x89\xE0\xB9\x83\xE0\xB8\x8A\xE0\xB9\x89\xE0\xB9\x84\xE0\xB8\x94"
  70 "\xE0\xB9\x89\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB8\x9B\xE0\xB8\xA3"
  71 "\xE0\xB8\xB0\xE0\xB8\xAA\xE0\xB8\x9A\xE0\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3"
  72 "\xE0\xB8\x93\xE0\xB9\x8C\xE0\xB8\x97\xE0\xB8\xB5\xE0\xB9\x88\xE0\xB8\x94"
  73 "\xE0\xB8\xB5\xE0\xB8\x82\xE0\xB8\xB6\xE0\xB9\x89\xE0\xB8\x99 \xE0\xB8\xA3"
  74 "\xE0\xB8\xA7\xE0\xB8\xA1\xE0\xB8\x97\xE0\xB8\xB1\xE0\xB9\x89\xE0\xB8\x87"
  75 "\xE0\xB8\x9B\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB9\x81\xE0\xB8\x95"
  76 "\xE0\xB9\x88\xE0\xB8\x87\xE0\xB9\x80\xE0\xB8\x99\xE0\xB8\xB7\xE0\xB9\x89"
  77 "\xE0\xB8\xAD\xE0\xB8\xAB\xE0\xB8\xB2\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89"
  78 "\xE0\xB9\x80\xE0\xB8\xAB\xE0\xB8\xA1\xE0\xB8\xB2\xE0\xB8\xB0\xE0\xB8\xAA"
  79 "\xE0\xB8\xB3\xE0\xB8\xAB\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB8\x84"
  80 "\xE0\xB8\xB8\xE0\xB8\x93";
  81
  82 // Comparator for sorting by the first element in a pair.
  83 bool ComparePair1st(const Snippet::MatchPosition& a,
  84                     const Snippet::MatchPosition& b) {
  85   return a.first < b.first;
  86 }
  87
  88 // For testing, we'll compute the match positions manually instead of using
  89 // sqlite's FTS matching.  BuildSnippet returns the snippet for matching
  90 // |query| against |document|.  Matches are surrounded by "**".
  91 base::string16 BuildSnippet(const std::string& document,
  92                             const std::string& query) {
  93   // This function assumes that |document| does not contain
  94   // any character for which lowercasing changes its length. Further,
  95   // it's assumed that lowercasing only the ASCII-portion works for
  96   // |document|. We need to add more test cases and change this function
  97   // to be more generic depending on how we deal with 'folding for match'
  98   // in history.
  99   const std::string document_folded = StringToLowerASCII(std::string(document));
 100
 101   std::vector<std::string> query_words;
 102   base::SplitString(query, ' ', &query_words);
 103
 104   // Manually construct match_positions of the document.
 105   Snippet::MatchPositions match_positions;
 106   match_positions.clear();
 107   for (std::vector<std::string>::iterator qw = query_words.begin();
 108        qw != query_words.end(); ++qw) {
 109     // Insert all instances of this word into match_pairs.
 110     size_t ofs = 0;
 111     while ((ofs = document_folded.find(*qw, ofs)) != std::string::npos) {
 112       match_positions.push_back(std::make_pair(ofs, ofs + qw->size()));
 113       ofs += qw->size();
 114     }
 115   }
 116   // Sort match_positions in order of increasing offset.
 117   std::sort(match_positions.begin(), match_positions.end(), ComparePair1st);
 118
 119   // Compute the snippet.
 120   Snippet snippet;
 121   snippet.ComputeSnippet(match_positions, document);
 122
 123   // Now "highlight" all matches in the snippet with **.
 124   base::string16 star_snippet;
 125   Snippet::MatchPositions::const_iterator match;
 126   size_t pos = 0;
 127   for (match = snippet.matches().begin();
 128        match != snippet.matches().end(); ++match) {
 129     star_snippet += snippet.text().substr(pos, match->first - pos);
 130     star_snippet += base::UTF8ToUTF16("**");
 131     star_snippet += snippet.text().substr(match->first,
 132                                           match->second - match->first);
 133     star_snippet += base::UTF8ToUTF16("**");
 134     pos = match->second;
 135   }
 136   star_snippet += snippet.text().substr(pos);
 137
 138   return star_snippet;
 139 }
 140
 141 TEST(Snippets, SimpleQuery) {
 142   ASSERT_EQ(" ... eferred to collectively as the \"Services\" in this "
 143             "**document** and excluding any services provided to you by "
 144             "Goo ...  ... way, Mountain View, CA 94043, United States. This "
 145             "**document** explains how the agreement is made up, and sets "
 146             "o ... ",
 147             base::UTF16ToUTF8(BuildSnippet(kSampleDocument, "document")));
 148 }
 149
 150 // Test that two words that are near each other don't produce two elided bits.
 151 TEST(Snippets, NearbyWords) {
 152   ASSERT_EQ(" ... lace of business is at 1600 Amphitheatre Parkway, "
 153             "**Mountain** **View**, CA 94043, United States. This "
 154             "document explains  ... ",
 155             base::UTF16ToUTF8(BuildSnippet(kSampleDocument, "mountain view")));
 156 }
 157
 158 // The above tests already test that we get byte offsets correct, but here's
 159 // one that gets the "TM" in its snippet.
 160 TEST(Snippets, UTF8) {
 161   ASSERT_EQ(" ... ogle\xe2\x84\xa2 Terms of Service Welcome to Google! "
 162             "1. Your **relationship** with Google 1.1 Your use of Google's "
 163             "products, so ... ",
 164             base::UTF16ToUTF8(BuildSnippet(kSampleDocument, "relationship")));
 165 }
 166
 167 TEST(Snippets, ThaiUTF8) {
 168   // There are 3 instances of '\u0E43\u0E2B\u0E49'
 169   // (\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89) in kThaiSample.
 170   // The 1st is more than |kSniipetContext| graphemes away from the
 171   // 2nd while the 2nd and 3rd are within that window. However, with
 172   // the 2nd match added, the snippet goes over the size limit so that
 173   // the snippet ends right before the 3rd match.
 174   ASSERT_EQ(" ... "
 175             "\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7"
 176             "\xE0\xB8\xA1 \xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8"
 177             "\xA1\xE0\xB8\xB9\xE0\xB8\xA5\xE0\xB8\xAA\xE0\xB9\x88\xE0\xB8"
 178             "\xA7\xE0\xB8\x99\xE0\xB8\x9A\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8"
 179             "\x84\xE0\xB8\xA5 \xE0\xB9\x80\xE0\xB8\xA1\xE0\xB8\xB7\xE0"
 180             "\xB9\x88\xE0\xB8\xAD\xE0\xB8\x84\xE0\xB8\xB8\xE0\xB8\x93\xE0"
 181             "\xB8\xA5\xE0\xB8\x87\xE0\xB8\x97\xE0\xB8\xB0\xE0\xB9\x80\xE0"
 182             "\xB8\x9A\xE0\xB8\xB5\xE0\xB8\xA2\xE0\xB8\x99\xE0\xB9\x80\xE0"
 183             "\xB8\x9E\xE0\xB8\xB7\xE0\xB9\x88\xE0\xB8\xAD\xE0\xB9\x83\xE0"
 184             "\xB8\x8A\xE0\xB9\x89\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xB4\xE0"
 185             "\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3\xE0\xB8\x82\xE0\xB8\xAD\xE0"
 186             "\xB8\x87 Google \xE0\xB8\xAB\xE0\xB8\xA3\xE0\xB8\xB7\xE0\xB8"
 187             "\xAD**\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89**\xE0\xB8\x82\xE0"
 188             "\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5\xE0"
 189             "\xB8\x94\xE0\xB8\xB1\xE0\xB8\x87\xE0\xB8\x81\xE0\xB8\xA5\xE0"
 190             "\xB9\x88\xE0\xB8\xB2\xE0\xB8\xA7\xE0\xB9\x82\xE0\xB8\x94\xE0"
 191             "\xB8\xA2\xE0\xB8\xAA\xE0\xB8\xA1\xE0\xB8\xB1\xE0\xB8\x84\xE0"
 192             "\xB8\xA3\xE0\xB9\x83\xE0\xB8\x88 \xE0\xB9\x80\xE0\xB8\xA3"
 193             "\xE0\xB8\xB2\xE0\xB8\xAD\xE0\xB8\xB2\xE0\xB8\x88\xE0\xB8\xA3"
 194             "\xE0\xB8\xA7\xE0\xB8\xA1\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD"
 195             "\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5\xE0\xB8\xAA\xE0\xB9\x88"
 196             "\xE0\xB8\xA7\xE0\xB8\x99\xE0\xB8\x9A\xE0\xB8\xB8\xE0\xB8\x84"
 197             "\xE0\xB8\x84\xE0\xB8\xA5\xE0\xB8\x97\xE0\xB8\xB5\xE0\xB9\x88"
 198             "\xE0\xB9\x80\xE0\xB8\x81\xE0\xB9\x87\xE0\xB8\x9A\xE0\xB8\xA3"
 199             "\xE0\xB8\xA7\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\xA1"
 200             "\xE0\xB8\x88\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\x84\xE0\xB8\xB8"
 201             "\xE0\xB8\x93\xE0\xB9\x80\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xB2"
 202             "\xE0\xB8\x81\xE0\xB8\xB1\xE0\xB8\x9A ...  ... \xE0\xB8\x82"
 203             "\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5"
 204             "\xE0\xB8\x88\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\x9A\xE0\xB8\xA3"
 205             "\xE0\xB8\xB4\xE0\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3\xE0\xB8\xAD"
 206             "\xE0\xB8\xB7\xE0\xB9\x88\xE0\xB8\x99\xE0\xB8\x82\xE0\xB8\xAD"
 207             "\xE0\xB8\x87 Google \xE0\xB8\xAB\xE0\xB8\xA3\xE0\xB8\xB7\xE0"
 208             "\xB8\xAD\xE0\xB8\x9A\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8\x84\xE0"
 209             "\xB8\xA5\xE0\xB8\x97\xE0\xB8\xB5\xE0\xB9\x88\xE0\xB8\xAA\xE0"
 210             "\xB8\xB2\xE0\xB8\xA1 \xE0\xB9\x80\xE0\xB8\x9E\xE0\xB8\xB7"
 211             "\xE0\xB9\x88\xE0\xB8\xAD**\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9"
 212             "\x89**\xE0\xB8\x9C\xE0\xB8\xB9\xE0\xB9\x89\xE0\xB9\x83\xE0"
 213             "\xB8\x8A\xE0\xB9\x89\xE0\xB9\x84\xE0\xB8\x94\xE0\xB9\x89\xE0"
 214             "\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB8\x9B\xE0\xB8\xA3\xE0"
 215             "\xB8\xB0\xE0\xB8\xAA\xE0\xB8\x9A\xE0\xB8\x81\xE0\xB8\xB2\xE0"
 216             "\xB8\xA3\xE0\xB8\x93\xE0\xB9\x8C\xE0\xB8\x97\xE0\xB8\xB5\xE0"
 217             "\xB9\x88\xE0\xB8\x94\xE0\xB8\xB5\xE0\xB8\x82\xE0\xB8\xB6\xE0"
 218             "\xB9\x89\xE0\xB8\x99 \xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\xA1"
 219             "\xE0\xB8\x97\xE0\xB8\xB1\xE0\xB9\x89\xE0\xB8\x87\xE0\xB8\x9B"
 220             "\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB9\x81\xE0\xB8\x95"
 221             "\xE0\xB9\x88\xE0\xB8\x87\xE0\xB9\x80\xE0\xB8\x99\xE0\xB8\xB7"
 222             "\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xAB\xE0\xB8\xB2",
 223             base::UTF16ToUTF8(BuildSnippet(kThaiSample,
 224                                      "\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89")));
 225 }
 226
 227 TEST(Snippets, ExtractMatchPositions) {
 228   struct TestData {
 229     const std::string offsets_string;
 230     const size_t expected_match_count;
 231     const size_t expected_matches[10];
 232   } data[] = {
 233     { "0 0 1 2 0 0 4 1 0 0 1 5",            1,     { 1, 6 } },
 234     { "0 0 1 4 0 0 2 1",                    1,     { 1, 5 } },
 235     { "0 0 4 1 0 0 2 1",                    2,     { 2, 3, 4, 5 } },
 236     { "0 0 0 1",                            1,     { 0, 1 } },
 237     { "0 0 0 1 0 0 0 2",                    1,     { 0, 2 } },
 238     { "0 0 1 1 0 0 1 2",                    1,     { 1, 3 } },
 239     { "0 0 1 2 0 0 4 3 0 0 3 1",            1,     { 1, 7 } },
 240     { "0 0 1 4 0 0 2 5",                    1,     { 1, 7 } },
 241     { "0 0 1 2 0 0 1 1",                    1,     { 1, 3 } },
 242     { "0 0 1 1 0 0 5 2 0 0 10 1 0 0 3 10",  2,     { 1, 2, 3, 13 } },
 243   };
 244   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(data); ++i) {
 245     Snippet::MatchPositions matches;
 246     Snippet::ExtractMatchPositions(data[i].offsets_string, "0", &matches);
 247     EXPECT_EQ(data[i].expected_match_count, matches.size());
 248     for (size_t j = 0; j < data[i].expected_match_count; ++j) {
 249       EXPECT_EQ(data[i].expected_matches[2 * j], matches[j].first);
 250       EXPECT_EQ(data[i].expected_matches[2 * j + 1], matches[j].second);
 251     }
 252   }
 253 }
 254
 255 }  // namespace query_parser