大規模ソフトウェアを手探る 検索ボックスにおける自動補完・サジェスチョンのデータの流れを追う

前回のブログでは、過去の検索ワードをDBから取ってきて自動補完を行うクラスに返すSearchProviderクラスを見つけてフィルター機能を実装してみたものの、実際の自動補完候補にフィルターしたはずのワードが残ってしまうと言う謎現象に遭遇しました。 今回ではこの問題を解消し、C++側の実装変更を完了するまでをまとめたいと思います。

データの流れを追う

SearchProviderクラスから流れてくるデータではデータのフィルタリングができているのに、Omniboxには補完候補として表れることから、SearchProvider以外のクラスからこのデータが供給されているのではないかと考え、まず自動補完のデータがどういった流れで受け渡されているのかを調べることにしました。

gdbブレークポイントを設定してみたり、エラーのバックトレース結果をみたり、地道にコードをサーチしたりして、Omniboxでユーザーが入力するたびに、AutocompleteControllerというクラスが各Providerからデータを集めて自動補完候補autocomplete_matchesを集め、このAutocompleteResultsクラスにこのマッチしたデータを渡すと、このAutocompleteResultsクラスで関連度に基づいてこのmatchesをソートし、重複を排除してControllerに渡し、AutocompleteControllerがこの結果に基づいてOmniboxのサジェスチョンを更新していることがわかりました。f:id:akaringo030402:20171101194051p:plain 実際には他にもHistoryQuickProviderなどいくつかのproviderからAutocompleteControllerに自動補完候補が提供されているのですが、図では省略しています。

前回の変更ではいくつかのProviderのうち、「検索時のクエリのうち、入力文字列にマッチするものを候補として返す」SearchProviderの結果から禁止したいキーワードとマッチするものを除くようにしていました。 図の中の赤いデータが表示したくないキーワードを含む検索履歴のデータを表しています。SearchProviderでこの特定のキーワードを含む検索履歴を除いても、全てのProviderから供給された結果を集めると、その中に消したい履歴が残り続けています。 f:id:akaringo030402:20171101194132p:plain

一旦、AutocompleteControllerの中で色々なProviderを集めている部分のコードを確認してみます。

AutocompleteController::AutocompleteController(...) {
  provider_types &= ~OmniboxFieldTrial::GetDisabledProviderTypes();

  if (provider_types & AutocompleteProvider::TYPE_BOOKMARK)
    providers_.push_back(new BookmarkProvider(provider_client_.get()));
  if (provider_types & AutocompleteProvider::TYPE_BUILTIN)
    providers_.push_back(new BuiltinProvider(provider_client_.get()));
  if (provider_types & AutocompleteProvider::TYPE_HISTORY_QUICK)
    providers_.push_back(new HistoryQuickProvider(provider_client_.get()));
  if (provider_types & AutocompleteProvider::TYPE_HISTORY_URL) {
    history_url_provider_ =
        new HistoryURLProvider(provider_client_.get(), this);
    providers_.push_back(history_url_provider_);
  }
  if (provider_types & AutocompleteProvider::TYPE_KEYWORD) {
    keyword_provider_ = new KeywordProvider(provider_client_.get(), this);
    providers_.push_back(keyword_provider_);
  }
  if (provider_types & AutocompleteProvider::TYPE_SEARCH) {
    search_provider_ = new SearchProvider(provider_client_.get(), this);
    providers_.push_back(search_provider_);
  }
  if (provider_types & AutocompleteProvider::TYPE_SHORTCUTS)
    providers_.push_back(new ShortcutsProvider(provider_client_.get()));
  if (provider_types & AutocompleteProvider::TYPE_ZERO_SUGGEST) {
    zero_suggest_provider_ = ZeroSuggestProvider::Create(
        provider_client_.get(), history_url_provider_, this);
    if (zero_suggest_provider_)
      providers_.push_back(zero_suggest_provider_);
  }
  ...
}

8種類のProviderからデータを集めていることがわかります。 おそらくこのうちのどれかのProviderがキーワードを含む検索履歴をSearchProviderとは別のProviderから供給されているのではないかと仮説を立て、それぞれのProviderについてどんな結果を返しているのか検証をしてみました。 Chrome Browserのいわゆるprintfデバッグをする際には、個人的にLOG(INFO) <<を使うことがおすすめです。 使用の仕方はC++のstd::coutとだいたい同じです。

真犯人が判明

N時間に渡るデバッグの結果、フィルターをかけたはずの検索ワードを返しているProviderが判明しました。 真犯人は ShortcutProvider でした。

工工工エエエエエエェェェェェェ(゚Д゚)ェェェェェェエエエエエエ工工工

なんと一番無害そうというか関係なさそうなProviderが、実は禁止キーワード文字列をAutocompleteProviderに返していました…... ShortcutProviderクラスのコードをみてみると、

// Provider of recently autocompleted links. Provides autocomplete suggestions
// from previously selected suggestions. The more often a user selects a
// suggestion for a given search term the higher will be that suggestion's
// ranking for future uses of that search term.
class ShortcutsProvider : public AutocompleteProvider,
                          public ShortcutsBackend::ShortcutsBackendObserver {...}

つまり、SearchProviderでキーワードと一致するサジェスチョンを除いても、ShortcutProviderが最近の検索履歴からキーワードと一致しているサジェスチョンをAutocompleteProviderに流していたということです…… f:id:akaringo030402:20171101194213p:plain

え、RecentlySearchedHistoryProviderとかにすればよくね????ShortcutProviderて命名から想像できなくね????ネーミングおかしくね?????

ということで、原因はこのShortcutProviderから、別のDBから最近の検索履歴データが供給されていたというものでした。 チームでの話し合いの結果、SearchProvider、ShortcutProviderに対して個々にキーワードフィルターをかけるより、全てのProviderの結果をまとめ、重複を除いてソートした後にフィルターをかけた方比較回数を減らせるのではないかと考え、 SortAndDedupMatches()というAutocompleteResultクラスの関数でフィルターをかけることにしました。 f:id:akaringo030402:20171101194249p:plain 変更後のコードは以下のようになります。

void AutocompleteResult::SortAndDedupMatches(
    metrics::OmniboxEventProto::PageClassification page_classification,
    ACMatches* matches) {
  // Sort matches such that duplicate matches are consecutive.
  matches->sort(DestinationSort<AutocompleteMatch>(page_classification));
  // Set duplicate_matches for the first match before erasing duplicate
  // matches.
  for (ACMatches::iterator i(matches->begin()); i != matches->end(); ++i) {
    for (auto j = std::next(i);
         j != matches->end() && AutocompleteMatch::DestinationsEqual(*i, *j);
         ++j) {
      AutocompleteMatch& dup_match(*j);
      i->duplicate_matches.insert(i->duplicate_matches.end(),
                                  dup_match.duplicate_matches.begin(),
                                  dup_match.duplicate_matches.end());
      dup_match.duplicate_matches.clear();
      i->duplicate_matches.push_back(dup_match);
    }
  }
  // Erase duplicate matches.
  matches->unique(AutocompleteMatch::DestinationsEqual);

// 変更ここから
  for (auto itr=matches->begin(); itr!=matches->end();){
     bool be_removed = itr->type == AutocompleteMatchType::HISTORY_TITLE ||
            itr->type == AutocompleteMatchType::HISTORY_BODY ||
            itr->type ==  AutocompleteMatchType::SEARCH_HISTORY ||
            itr->type == AutocompleteMatchType::SEARCH_SUGGEST_TAIL; 
     if (be_removed && base::EqualsASCII(itr->contents, "PokemonGo") == true){
        itr = matches->erase(itr);
     } else {
    itr++;
     }
  }
// 変更ここまで
}

単に非表示キーワードを含む全てのサジェスチョンをeraceしてしまうと、普段使いのときに特定のキーワードに関連した検索をしようとしても補完されないので、不便になってしまいますよね。 そこで今回はbe_removedというbool変数を導入して、補完のタイプがSearchHistory及びそれを自動補完したもの(過去のユーザーの検索ワードに基づいたサジェスチョン)、もしくはHistoryBody(過去に閲覧したURL履歴の本文)に 非表示キーワードが含まれる時のみ、 自動補完の候補から除くことにしました。

これでOmniboxのキーワードフィルタリング機能が完成しました!!
ただこれだとC++ソースコードでキーワードをハードコーディングしているだけなので、次回以降、User Profileを利用してユーザーの登録した非表示キーワードを読み込み、 フィルターをかける部分の変更や複数キーワードの登録などについてまとめます。