前回のブログでは、過去の検索ワードを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を利用してユーザーの登録した非表示キーワードを読み込み、フィルターをかける部分の変更や複数キーワードの登録などについてまとめます。

2017-11-01

大規模ソフトウェアを手探る Chromeのソースコードとドキュメントをひたすら漁る

大規模ソフトウェアを手探る

Chromeの膨大なソースコードから変更するクラスを見つける

Chromeをビルドできたところでいよいよ実際にコードの変更を行なっていきます。今回私たちが追加しようとした機能はChromeの上部にある検索ボックスに表示される検索履歴に単語フィルターをかける（つまり特定の単語が含まれる検索履歴は表示しない）というものでした。そこで私たちの考えたアイディアとしては「入力に従って検索ボックス情報を更新しているモジュール上で、特定の単語が含まれる検索履歴は更新するデータに追加しないようにする」もしくは「特定の単語が含まれる検索ワードは検索履歴のデータに保存されないように」しようと言うものでした。最初は検索ボックス内でヒストリー(過去の検索履歴)を読み出してautocompleteの候補を作成しているクラスでちょっとif文追加するだけの簡単なお仕事かな〜と楽観的に考えていたのですが、現実はそこまで甘くはありませんでした…

いきなりChrome code searchの限界に直面する

まず最初は前回紹介したChrome Code Searchで検索をかけます。とりあえず「history search」で検索をかけてみる…

f:id:akaringo030402:20171008085025p:plain — Chrome code searchでの「history search」検索結果

4400件wwwwwww

これを全部見ていくのはしんどそう… とりあえずいきなり適当な単語でcode searchはあんまりよくないと言うことに気がつき（それはそう）、まずどういったモジュールがあの検索ボックスの自動補完に対応しているのか、Chromeのドキュメントから調べていくことにしました。
Chromium (Chrome Browser, Chrome OS)の開発者向けドキュメント (design doc) は公式ホームペーシ、The Chromium ProjectのFor Developers>Design Documentsから検索できます。
Google検索していたらChromeの上部にある検索ボックスはomniboxと呼ばれることがわかったので、このomnibox関連のdesign docを調べていくことにしました。

omnibox関連のドキュメントをとりあえずぐぐりまくる

公式のDesign Docsのうち、まず注目したのはOmnibox: History Providerについてのドキュメントです。

One of the autocomplete providers for the omnibox (the HistoryQuickProvider, HQP for short) serves up autocomplete candidates from the profile's history database. ふむふむ…autocomplete providersなるものが自動補完候補をユーザープロファイルのDBから取得していることがわかります。またこのautocomplete providersにはいくつか種類があることも読み取れます。

次はDesign Docではないのですが、一般向けのOmniboxの説明をしたドキュメントを見つけました。これによると、Omniboxの自動補完は以下のタイプに分類できるようです。

Search for... This searches for the typed query - this will be the topmost and default item if the input looks like a search string.
URL If the input (after auto-complete, if applicable) looks like a URL, this will repeat the user's input and be the default, top-most item.
Previous URLs If the input matches a previous URL, those URLs will be shown here.
Nav Suggest Uses the user's default search provider to suggest URLs based on the user's input.
Search Suggest Uses the user's default search provider to suggest search terms based on the user's input.
History Results Shows the number of entries in the user's history that match the given input - selecting this item will take the user to the history results page for their given search term.

これを見た感じ検索ワードの履歴を返しているのはHistory Resultsみたいですね…History Resultに関連してそうなSearchProviderクラスが見つかりました。

とりあえずSearchProviderクラスを変更してみる

SearchHistoryクラスを見ていくと、ScoreHistoryResultsという関数が、過去の検索履歴のうち入力文字列とマッチするHistoryResultsついて、関連度スコアrelevanceをつけてそれに基づいてソートしていることわかりました。ScoreHistoryResults自体はSearchProvider::SearchHistoryResultHelperという別のヘルパー関数を呼んで、実際に自動補完候補のスコア付などを行なっています。

とりあえず、この関数の中でHistoryResultsから、検索文字列があるキーワードと一致する時にscored_resutsに追加しないようにするように書き換えて見ました。

SearchProvider::ScoreHistoryResultsHelper(const HistoryResults& results,
                                          bool base_prevent_inline_autocomplete,
                                          bool input_multiple_words,
                                          const base::string16& input_text,
                                          bool is_keyword) {
  ...
  // resultsは過去の検索履歴のうち入力文字列とマッチするものを全て取り出している。
  for (HistoryResults::const_iterator i(results.begin()); i != results.end();
       ++i) {
   ...
    SearchSuggestionParser::SuggestResult history_suggestion(
        trimmed_suggestion, AutocompleteMatchType::SEARCH_HISTORY, 0,
        trimmed_suggestion, base::string16(), base::string16(),
        base::string16(), base::string16(), nullptr, std::string(),
        std::string(), is_keyword, relevance, false, false, trimmed_input);
    history_suggestion.set_received_after_last_keystroke(false);
    // scored_resultsにキーワードとマッチしていない時のみ追加する。
    // 変更ここから
    if (base::EqualsASCII(history_suggestions.suggestion(), “harry”)  == false){
        scored_results.insert(insertion_position, history_suggestion);
    }
    // 変更ここまで
  }
  ...
}

よしこれでひとまずフィルター機能は実装できたはず…...と思うも、search_providerの返す結果では"harry"が消えているのに表示される結果には"harry"が残っていると言う謎の事態に......

次回のブログではSearchProviderから供給されるデータに対してフィルターをかけるだけではなぜダメだったのか、OmniboxのAutocompleteのデータフローを追いながら原因を解明していきます。

2017-11-01

大規模ソフトウェア(Chromium)を手探る導入・ビルド編

大規模ソフトウェアを手探る

このブログは電気系3年生後期実験の大規模ソフトウェアを手探るの最終報告ブログです。

「大規模ソフトウェアを手探る」とは？

東大工学部電気系3年生は3~6個のテーマの実験を行うことが必修となっており、「大規模ソフトウェアを手探る」とは田浦健二郎先生による「演習レベルの小さなプログラムが作れること」と，「実用規模のプログラムが作れること」のギャップを埋める (ための知識と経験を得ることを目的に、1〜数百万行のオープンソースソフトウェアをソースからビルドし新しい機能を加えたりします。
今回私たちのチームでは、みんなが使う大規模なものをやりたいという気持ちと、個人的にChromeのBlink周りの開発をしたことがあったのでChromiumをテーマに選びました。

そもそもChromiumとは

GoogleのブラウザであるChromeを使っている方も多いのではないでしょうか。ChromiumとはオープンソースソフトウェアとしてChromeを見たときの名称です。

Chromium（クロミウム）はオープンソースのウェブブラウザのプロジェクト名で、Google Chromeはこのソースコードを引き抜いて開発されたものである。 -- Chromium - Wikipedia

ちなみにChromiumがどのくらい大規模かというと、英語圏の質問投稿サイトQuoraの質問How many lines of code is Google Chrome?によると、2012年の時点で400~500万行のコードが存在しているみたいです。

4,490,488 lines of code, 5,448,668 lines with comments included, spread over 21,367 unique files.

現在の正確なChromiumのソースコード行数については見つけられていないのですが、この数字だけでも私たちが普段使っているブラウザがどれほど大きく複雑なものかわかります。

このブログ記事について

この「大規模ソフトウェアを手探る」実験では、一般的な実験レポートの代わりにこういったブログ形式でのレポートの提出が推奨さえています。
私たちもChromiumという(超)大規模ソフトウェアをて探るにあたって、かなり昨年の方の丁寧なブログレポートが参考になったため、できるだけ詳細にどういった作業を行っていったのか、何に途中つまづいたのかをまとめています。
Chromiumのソースをいじってみたいという方以外だともしかしたら少し冗長かもしれませんが、今後「大規模ソフトウェアを手探る」でChromiumをやりたい方、もしくは趣味でChromiumをゴニョゴニョしたい方の参考になれば嬉しいです。

今回の実験で実装しようと思った機能

今回の実装しようと思った機能はChromeの上部にでる検索ボックス上に入力に応じて現れる過去の履歴やサーチエンジンの検索サジェスチョンから、指定したキーワードを含む過去の検索履歴を表示しないようにする機能です。この検索ボックスのことはOmniboxというChromium BrowserのComponentです。

スライドを投影している時やペアプロの時にChrome検索を開いた時に表示したくないような検索履歴がサジェストされることがあるという話を聞いた(見た)のと、なんとなく面白そうだからというこれまた雑な理由で決めたのですが、結果的にBrowserのコアの部分からフロントエンドまで、またC++からJavaScriptの世界でどうやりとりがされているか等を知ることができ、とても勉強になりました。

大まかな作業スケジュールとブログ記事リスト

以下が大まかな作業スケジュールになります。できるだけ来年以降大規模ソフトウェアを手探る人に参考になるように細かく書いたら長くなったのでブログ記事を分割しました。

1 ~ 2日目 : gnuplotに機能を追加する全体での実習、チーム決め等、ソースコードのフェッチ、ビルド等。
3 ~ 4日目 : 検索履歴からの自動補完を行なっているクラス(SearchProvider)を特定。
大規模ソフトウェアを手探る Chromeのソースコードとドキュメントをひたすら漁る - あさりさんの作業日記
5日目 : キーワードフィルター機能実装
大規模ソフトウェアを手探る検索ボックスにおける自動補完・サジェスチョンのデータの流れを追う - あさりさんの作業日記
6 ~ 7 日目 : User Profileに新たに非表示キーワードを保持する項目を追加。複数キーワードをフィルタリングするための変更追加。またブラウザの設定画面で非表示キーワードを入力できるようにWebUIを変更
大規模ソフトウェア(Chromium)を手探る user profileに設定を追加する - あさりさんの作業日記
 大規模ソフトウェア(Chromium)を手探る - 設定画面(settings)を手探る1 - - elechoのぶろぐ
 大規模ソフトウェア(Chromium)を手探る - 設定画面(settings)を手探る2 - - elechoのぶろぐ
8日目 : 新たに追加された設定画面用のCallbackHandlerクラスを追加。
大規模ソフトウェア(Chromium)を手探る callbackハンドラを追加する・全体の感想 - あさりさんの作業日記
9日目 : バグの修正と余分なコメント等の削除
10日目 : 発表 docs.google.com

まずはビルドから

とはいうもののまずビルドができないと話になりません。この記事では開発を始める前のChromiumのソースコードを引っ張ってきて手元のPCでビルドするまでをまとめたいと思います。今回のチームメンバーはみんなLinux(Ubuntu)を使用していたので、ChromiumのLinux向けコンパイル、ビルドのイントラクションを参考にしました。基本的には順に従って行けばいいのですが、いくつかハマりポイントがあったのでそれも含めて追っていきます。

depot_toolsをインストールする

depot_toolsはソースコードのチェックアウトや依存パッケージのダウンロードなどの、Chromiumのビルドやコントリビュートに必要な機能を提供してくれます。

$ git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
$ export PATH="$PATH:/path/to/depot_tools"

Chromiumのソースコードを取ってくる

Chromiumのソースコードを取ってきます。まず適当な場所にChromium作業用のディレクトリを作りましょう。今回は~/crというディレクトリ以下ににChromiumソースを落としてくることを想定しています。

$ mkdir ~/cr && cd cr

次に、先ほどインストールしてきたdepot_toolsのfetchというツールを使ってコードと依存ライブラリをチェックアウトします(ローカルに持ってきます)。

$ fetch --nohooks--no-history chromium

基本的には--no-historyオプションをつけることをオススメします。--no-historyをつけないと、レポジトリの全ての履歴を取ってくるので時間もストレージも倍くらいかかります… --no-historyをつけた場合はだいたい30分程度でコードがチェックアウトできます。

hookを走らせる

フェッチが完了したらChromium特有のhooksを走らせて必要な追加バイナリをインストールします。ただUbuntuの場合、この前にフェッチしてきたsrc/以下でbuild/install-build-deps.shを走らせる必要があります。これ公式だとあまり大きく書いてないので見落としがちですが、先にこちらを走らせないと「dependenciesがないよ！」って怒られます。

$ cd src
$ build/install-build-deps.sh
$ gclient runhooks

ビルドのためのセットアップをする

必要なダウンロードが終わりました…！いよいよビルドしていきましょう。まず、セットアップをします。

$ gn gen out/Default

次にいよいよninjaでコンパイルし、実行ファイルをRunします。

$ ninja -C out/Default chrome
$ out/Default/chrome

学科の8コアのマシンでだいたい5時間程度で完了しました…さすが大規模ソフトウェア... ~~電気系3年生は実験の前にビルドまで終らせてから来ような、初回にやることがなくなるからな~~ ここまででChromeのビルドが完了しました。ここまでは割とトラブルなくできると思います。次回からは実際に検索フィルター機能を追加するための手順を順にまとめていきます。

Chrome開発に当たって便利なもの

Chrome code search
Chromiumのコードの検索ができる。個人的にはhistory, xsearch(referenceやcall hierarchy)がすごい便利だと思いました。
The Chromium Project For Developers Design Documents
Chromeの様々な機能や全体のアーキテクチャのdesign documents(設計書、機能書)が集まっています。500万行以上あるコードから自分の変更したい機能に関わる部分をcode searchのみで発掘するのはなかなか厳しいので、こういったdesign documentsを見て関連するモジュールの実装等を参考にするといいかもしれません。