Word2Vecモデルをスクラッチで実装してみる ② 基本のNeural Netの実装

このブログは情報系を勉強する女子大生 Advent Calendar 2017 - Qiitaの17日目の記事です。

内容としては Word2Vecモデルをスクラッチで実装してみる ① そもそもWord2Vecって? - あさりさんの作業日記 の記事の続きになります。
前回はざっくりWord2Vecモデルがどんなものか説明したので、いよいよ実装してみようと思います。
基本的にNumpyを使って実装しました。ちなみに諸事情によりPython2系です。
実際にモデルをStanford Sentiment Treebankのデータで学習させた結果を二次元状にプロットすると 以下の感じになります。

f:id:akaringo030402:20171231151856p:plain

(結果が微妙???キニシナイキニシナイ)

実装にあたっては前回も紹介したスタンフォード大学CS224n: Natural Language Processing with Deep Learningの授業資料や授業課題を参考にしています。
とても良い授業なのでお正月に暇な方は見てみてください〜 :)

ニューラルネットワーク自体の説明については、自分が拙く行うよりもネットや教科書でとてもわかりやすくまとめてくださっている方がたくさんいるので割愛します。
個人的に日本語でネットで読めるものだと 愛媛大学の村上研究室のニューラルネットワークについての記事の第3, 4, 5章 がわかりやすいと思いました。

この記事では実装や勾配計算、勾配の確認などをざっくりさらっていきたいと思います('-'*)

基本のNeural Netを実装してみる

今回は隠れ層が一層のみのニューラルネットワークを実装してみます。 f:id:akaringo030402:20171231160255p:plain

活性化関数にはシグモイド関数を、出力層にはソフトマックス関数、コスト関数は交差エントロピー損失を用います。
この記事ではまずソフトマックス関数、シグモイド関数、交差エントロピー関数について実装と勾配を計算した後、 順伝播、逆伝播部分の実装を行なって最後に実際に逆伝播の実装に誤りがないか、gradient chekingを行う構成になっています。

ソフトマックス関数を実装する

まずソフトマックス関数を実装してみます。
ソフトマックス関数とは  n次元実数ベクトル  x=(x_1,\ \ldots,\ x_n) を受け取って 以下を満たす  n次元実数ベクトル  y = (y_1,\  \ldots,\ y_n) を返す関数です。

{\displaystyle
 y_k =  \frac{\exp{(a_k)}}{\sum_{i=1}^n \exp{(a_i)}}
}

式からもわかるようにソフトマックス関数には

  1.  0 \leq y_i \leq 1
  2.  \sum_{i=1} ^ n y_i = 1

という性質があり、分類問題をニューラルネットワークで解く場合に、出力層の活性化関数として用いられます。
例えば手書き文字画像からその文字が実際にどの数字を指しているのか当てるmnist問題では、 入力が実際に0から9のどの数字になりそうかの確率を出力し、最も確率の高い数字を予測として出力します。
この場合出力層で最後の隠れ層の出力結果をsoftmax関数に通すことで、「全体の合計が1になるかつそれぞれが0から1の間の数字になる」10次元の実数ベクトルが 帰ってくるので、その中で値が最大になるy_iのインデクスが分類予測結果になります。

とりあえず実装してみる

とりあえずnumpyを使ってこのsoftmax関数を実装してみます。

def softmax(x):
  e_x = np.exp(x)
  sum_e_x = np.sum(e_x)
  x = e_x / sum_e_x
  return x

これみるとちょっとゾワってしません??ちなみにこのコードで適当にsoftmax(np.array([1, 3, 4, 5, 1000]))と入れて実行してみると オーバーフローのために出力値が不定値になっていることがわかります。

__main__:2: RuntimeWarning: overflow encountered in exp
__main__:4: RuntimeWarning: invalid value encountered in true_divide
array([  0.,   0.,   0.,   0.,  nan])

ちなみにsoftmax(np.array([1, 3,4, 5, 10]))を実行すると、softmax関数によって合計が1になるような実数値のベクトルが出力されていることがわかります。

array([  1.22157447e-04,   9.02628229e-04,   2.45359791e-03,
         6.66957062e-03,   9.89852046e-01])

理由としてはとてもシンプルで、 \exp{(x)} がxが大きくなると簡単に数値がオーバーフローして不定値になってしまうためです。
試しにnp.exp(1000)を計算してみるとオーバーフローが発生していることが確認できます。

>>> np.exp(1000)
__main__:1: RuntimeWarning: overflow encountered in exp

オーバーフローをしないよう最大値を引く

この対策としてよく行われるのが、あらかじめ入力として与えられた実数値ベクトルにおける最大値を引区という方法で、数式で表すと以下のような計算を行うことになります。
ソフトマックス関数の入力に対して定数オフセットを追加しても(この場合は入力から最大の値を引いても)結果は不変になります。

 \exp{(ab)} = \exp{(a)} \exp{(b)}だったりすることを利用して工学部なのでざっくりと計算してみると、実際に定数 Cを追加した場合も出力結果は不変であることがわかります。

{\displaystyle
 y_k' =  \frac{\exp{(a_k +  C)}}{\sum_{i=1}^n \exp{(a_i + C)}} = \frac{\exp{(C)} \exp{(a_k)}}{\exp{(C)} \sum \exp{(a_i)}} = \frac{\exp{(a_k)}}{\sum \exp{(a_i)}} = y_k
}

実際に入力から最大値を引いたソフトマックス関数をnumpyで実装してみると以下の通りになります。今後のことも考えて、 入力が n次元のベクトルの場合と n \times mマトリックスである場合両方実装します。

def softmax(x):
    x = x.astype(np.float64)

    if len(x.shape) > 1:
        # Matrix
        e_x = np.exp(x.T - x.max(1))
        x = e_x / e_x.sum(axis=0)
        x = x.T
    else:
        # Vector
        e_x = np.exp(x - np.max(x))
        x = e_x / e_x.sum(axis=0)

    return x

シグモイド関数及び勾配を計算して実装してみる

次に活性化関数のシグモイド関数の実装について考えてみます。
シグモイド関数は以下の式で表され、 (-\infty ,\infty )\rightarrow (0,1) の単調増加連続関数で、1つの変曲点を持つ実関数(つまり どんな大きな入力が与えられても、小さな入力が与えられても出力結果が0から1の間の実数になる)です。

{\displaystyle
 \sigma (x) =  \frac{1}{1 + \exp{(-x)}}
}

ソフトマックスの時と同様、numpyを使って実装してみると以下のようになります。

def sigmoid(x):
   x = np.array(x, dtype=np.float128)
   s = 1.0 / (1 + np.exp(-x))
   return s

学習中のオーバーフロー対策としてとりあえずnp.float128で キャスティングしているのですが良い子は真似しないでください。
シグモイド関数でのオーバーフロー対策としては値をクリッピングする(np.float64で表現できる値より大きくなる場合は強制的に値を打ち止める)やscipy.special.explitを使う方法があるみたいです。

このシグモイド関数の勾配についても実装します。
シグモイド関数の勾配は商の微分公式など使って計算でき、シグモイド関数の勾配はシグモイド関数の値と1からその値を引いた値との積で表せることがわかります。

{\displaystyle
 \sigma' (x) =  \frac{-(- \exp{(-x)})}{(1 + \exp{(-x)})^ 2} =  \frac{\exp{(-x)}}{(1 + \exp{(-x)})^ 2} =  \frac{1}{(1 + \exp{(-x)})} \frac{\exp{(-x)}}{1 + \exp{(-x)}} = \sigma(x)(1 - \sigma(x))
}

このためシグモイド関数の実装はこんな感じでとてもシンプルに書くことができます。

def sigmoid_grad(s):
    ds = s * (1 - s)
    return ds

コスト関数(交差エントロピー損失)の勾配を計算して実装する

コスト関数として用いる交差エントロピー損失についても、実装と勾配の計算を行います。
交差エントロピー損失についての説明及びなぜ交差エントロピー損失を使うべきかなどは本やブログで詳細な説明を行っている方もいるのでここでは割愛します。

yを正解ラベル、\hat{y}を予測された結果とすると、交差エントロピー関数は以下のように定義されます。

{\displaystyle
 CE (y, \hat{y}) =  -\sum_{i} y_i \log{(\hat{y_i})}
}

今回は出力層にsoftmax関数を使っているので  \hat{y} = softmax{(\theta)}となります。

def cross_entropy_loss(y, y_hat): 
   # y = labels, y_hat = softmax(theta)
   cross_extropy_loss = -1 * np.sum(y * np.log(y_hat))
   return cross_extropy_loss

この交差エントロピー損失について、入力\thetaについての勾配を計算すると

{\displaystyle
 \frac{\partial CE (y, \hat{y})}{{\partial \theta}} =  \hat{{\bf y}} - {\bf y}
}

となるため、単純に正解ラベルと出力結果との差を計算すれば良いことがわかります。

隠れ層一層のニューラルネットワークの勾配を計算する

上で計算・実装したものも組み合わせながら、「隠れ層が1つのニューラルネット」を実装していきます。

f:id:akaringo030402:20171231160255p:plain

まず順伝播部の実装を行います。 上の図のh 及び\hat{y} については次の式で表すことができます。

{\displaystyle
 {\bf h} = {\rm sigmoid}({\bf xW_1} + b_1), \ \hat{{\bf y}} = {\rm softmax} ({\bf hW_2} + b_2)
}

{\bf W_i, b_i} (i=1,2) については二層のウェイト及びバイアスを示しています。

まず入力データ、初期パラメータ、入力層・隠れ層・出力層のデータを入力とし、隠れ層及び出力層の出力を返す forward_pop()という関数として実装します。

def forward_prop(data, params, dimensions):
   # dataは入力データ(x)
   # dimentionsがそれぞれの層の次元を表している。
   # paramsは各パラメータの初期値。
   # params = np.random.randn((dimensions[0] + 1) * dimensions[1] + (dimensions[1] + 1) * dimensions[2], ) などで初期化
   # Dxが入力層の次元、Hが隠れ層の次元、Dyが出力層の次元
   ofs = 0
   Dx, H, Dy = (dimensions[0], dimensions[1], dimensions[2])

   W1 = np.reshape(params[ofs:ofs+ Dx * H], (Dx, H)) # W1.shape = (Dx, H)
   ofs += Dx * H
   b1 = np.reshape(params[ofs:ofs + H], (1, H)) # b1.shape = (1, H)
   ofs += H
   W2 = np.reshape(params[ofs:ofs + H * Dy], (H, Dy)) # W2.shape = (H, Dy)
   ofs += H * Dy
   b2 = np.reshape(params[ofs:ofs + Dy], (1, Dy)) # b1.shape = (1, Dy)

   h = sigmoid(np.dot(data, W1) + b1) # h.shape = (N, h)
   y_hat = softmax(np.dot(h, W2) + b2) # y_hat.shape = (N, Dy)
   
   return h, y_hat

dataは(N, Dx)の行列で与えられ、paramsは((Dx + 1) * Dx + (H + 1) * Dy, 1)の乱数ベクトルでまとめて与えています。
順伝播を計算する際はこのparamsをそれぞれ適切な形にnp.reshape()でreshapeした後、ドット積・加算などを行い、 先ほど実装したsigmoid, softmaxなどの関数を持ちいてy, y_hatを求めます。

これで順伝播の計算ができたので、逆伝播についても計算して実装してみます。

{\bf z_1} = {\bf xW_1} + b_1, {\bf z_2} = {\bf xW_2} + b_2 とおき、コスト関数の入力xについての微分を順に後ろから計算していきます。
基本的には合成関数の微分を使って

{\displaystyle
 \frac{\partial CE (y, \hat{y})}{{\partial {\bf x}}} = \frac{\partial CE (y, \hat{y})}{{\partial {\bf z_2}}}
 \frac{\partial {\bf z_2}}{{\partial{\bf  h}}} \frac{\partial {\bf h}}{{\partial {\bf z_1}}} \frac{\partial {\bf z_1}}{{\partial {\bf x}}}
}

を計算していくだけなのですが、一気にやると間違えそうなので一つ一つ微分を計算していきます ('-'*)
(一応ベクトルは太字で区別するようにしているのですが、面倒になって太字化し忘れているところがあるかもしれません。年明けに直します…)

まず交差エントロピー損失関数のz_2についての微分を計算すると、これは上で求めた {\displaystyle
 \frac{\partial CE (y, \hat{y})}{{\partial \theta}} =  \hat{{\bf y}} - {\bf y}
} をそのまま使えば良いので、

{\displaystyle
 {\bf \delta_1} = \frac{\partial CE}{\partial {\bf z_2}} = \hat{{\bf y}} - {\bf y}
} となります。

を使ってコスト関数の隠れ層の出力{\bf h}に対する微分を計算すると

{\displaystyle
 {\bf \delta_2}  = \frac{\partial CE (y, \hat{y})}{{\partial {\bf h}}} = \delta_1 \frac{\partial z_2}{{\partial {\bf h}}} = \delta_1W_2^{\mathrm{T}} =  (\hat{{\bf y}} - {\bf y}) {\bf W_2}^{\mathrm{T}}
}

となります。さらに合成関数の微分を進めていって交差エントロピー関数のxについての微分を計算していきます。

{\displaystyle
 {\bf \delta_3}  = \frac{\partial CE}{{\partial {\bf z_1}}} = \delta_2 \frac{\partial {\bf h}}{{\partial {\bf z_1}}} = \delta_2 \circ ( \sigma(x)(1 - \sigma(x))
}

{\displaystyle
 \frac{\partial CE (y, \hat{y})}{{\partial {\bf x}}} = \delta_3 \frac{\partial {\bf z_1}}{{\partial {\bf x}}} = \delta_3 {\bf W_1}^{\mathrm{T}}
}

これで必要な計算はできたので、逆伝播についても実装してみます。先ほどのforward_prop()とまとめて一つの関数にします。

def forward_backward_prop(data, labels, params, dimensions):
    ofs = 0
    Dx, H, Dy = (dimensions[0], dimensions[1], dimensions[2])
    ### forward propagation
    W1 = np.reshape(params[ofs:ofs+ Dx * H], (Dx, H))
    ofs += Dx * H
    b1 = np.reshape(params[ofs:ofs + H], (1, H))
    ofs += H
    W2 = np.reshape(params[ofs:ofs + H * Dy], (H, Dy))
    ofs += H * Dy
    b2 = np.reshape(params[ofs:ofs + Dy], (1, Dy))

    h = sigmoid(np.dot(data, W1) + b1)
    y_hat = softmax(np.dot(h, W2) + b2)

    ### backward propagation
    delta = y_hat - labels
    gradW2 = h.T.dot(delta)
    gradb2 = np.sum(delta, axis = 0)
    delta = delta.dot(W2.T) * sigmoid_grad(h)
    gradW1 = data.T.dot(delta)
    gradb1 = np.sum(delta, axis = 0)

    ### cost_function
    cross_extropy_loss = -1 * np.sum(labels * np.log(y_hat))
    cost = cross_extropy_loss

    ### Stack gradients
    grad = np.concatenate((gradW1.flatten(), gradb1.flatten(),
        gradW2.flatten(), gradb2.flatten()))

    return cost, grad

一応これで基本のニューラルネットワークの実装ができました!

gradient checkingで実装が間違っていないか確かめる

今回については手計算でできる勾配計算が多いのですが、それでもだんだん量が増えてきて ちょっと本当に実装があっているのか不安になってきますよね…
そういう時はちゃんとgradient checkingをして 勾配計算の実装にミスがないかどうか確かめるのが大事です。

gradient checkingとはあるi番目に着目して以下の近似式で勾配を求め、その結果とbackpropで求めた勾配がだいたい一致するかを 確かめる作業です。

{\displaystyle
 \frac{\partial J(\theta)}{{\partial {\theta_i}}} = \frac{J(\theta_i + h) -J(\theta_i - h) }{2\times h}
}

これが大幅にbackpropの結果とずれてたら、『あっ…(察し)』とどこかで実装がずれていることがわかるので、特に大規模なネットワークを自分で全部書くときは役に立つのかもしれない

実際にこれを実装してみます。

def gradcheck_naive(f, x):
    rndstate = random.getstate()
    random.setstate(rndstate)

    fx, grad = f(x) # Evaluate function value at original point
    h = 1e-4

    # xの全ての次元についてgradient checkingを行う
    it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])
    count = 0
    while not it.finished:
        count+=1
        ix = it.multi_index

        # 近似により勾配を求める。
        x[ix] += h
        random.setstate(rndstate)
        fx_plus_h,_ = f(x)
        random.setstate(rndstate)
        x[ix] -= 2*h
        fx_minus_h,_ = f(x)
        x[ix] += h
        numgrad = (fx_plus_h - fx_minus_h) / (2*h)

        # backpropの計算結果と近似した結果の差異を比較する。
        reldiff = abs(numgrad - grad[ix]) / max(1, abs(numgrad), abs(grad[ix]))
        print reldiff

        if reldiff > 1e-5:
            print "Gradient check failed."
            return
        it.iternext() # つぎのdimentionへ

    print "Gradient check passed!"

これで先ほどのforward_backward_prop()に適当なデータを入れて計算がちゃんとできているか確かめてみます。

def sanity_check():
    N = 20
    dimensions = [10, 5, 10]
    data = np.random.randn(N, dimensions[0]) 
    labels = np.zeros((N, dimensions[2]))
    for i in xrange(N):
        labels[i, random.randint(0,dimensions[2]-1)] = 1

    params = np.random.randn((dimensions[0] + 1) * dimensions[1] + (
        dimensions[1] + 1) * dimensions[2], )

    print params.shape
    gradcheck_naive(lambda params:
        forward_backward_prop(data, labels, params, dimensions), params)

実行してみると、

9.49366951697e-11
2.59475394025e-10
...
4.01561339736e-10
5.21833463139e-11
7.50241228166e-11
Gradient check passed!

とほぼ差がないことがわかります。基本のニューラルネットの実装については大丈夫そうですね (◍ ´꒳` ◍)b

とりあえず今回までで基本のニューラルネットの勾配計算だったりをして実装してみるところまでできました。
次回(三が日までにはかけるように頑張ります…)は実際に今回実装したものをベースに、skip-gramやnegative samplingを実装して 実際に日本語wikipedia記事で単語ベクトルを作成してみたいと思います。

Women Techmakers Scholarship 2017に応募とその後!

このブログは情報系を勉強する女子大生 Advent Calendar 2017 - Qiitaの23日目の記事です。

今回は私がWomen Techmakersという、Googleによる情報系を専攻する女子学生向けのScholarshipプログラムに応募した時の話、 また選出された後のどう行った活動をしているかについて紹介してみたいと思います。

Women Techmakers Scholarshipとは

Woman Techmakers Scholarshipとは、Googleによる情報系もしくは関連する分野を専攻する情報系の女子学生向けの奨学金制度であり、 APEC, North America, Europe/Africa/Middle Eastの三つのリージョンごとに奨学生を選出し、奨学金の支給やアウトリーチ活動(後述)への支援を行うものです。

www.womentechmakers.com

私は昨年日本から選出された奨学生の方と元々知り合いだったこと、昨年Google検索チームでインターンした時のメンターがこのプログラムに少し関わっていて応募を勧められたこともあり、WTM APEC 2017に応募し、無事選出されました。
実際にScholar向けのretreatプログラムに参加してみたり日本に戻ってきた後日本から選出された他の奨学生と関わる中で色々刺激を受けたので、 もし今情報系に関連する分野(関連するの定義が難しいですが、必ずしも〜情報だけでなく数学、物理専攻寄りの方もいました)を専攻するなら応募してみるといいと思います!

りらちゃんが少し前のアドベントカレンダーの記事でプログラムの概要やretreat当日の詳細を書いてくれているので、興味のある方はこちらも見てみてください!

lila-lila.hatenablog.com

Women Techmakers Scholarshipの選考プロセス

昨年までは面接も選考のプロセスに含まれていたのですが、今年は書類選考のみでした。

Application Requirementsとして公式に掲載されているものは以下のようになります。これを全て提出すると応募が完了し、だいたい2ヵ月後くらいに選出されたか否かの連絡を受けます。

  • General background information (includes contact information and information about your current and intended institutions)
  • Current resumeAcademic transcripts from your current and prior institutions (if you have earned a prior degree)Responses to four essay questions(英文の成績証明書)
  • Current resume (英文の履歴書)
  • Responses to four essay questions(DiversityやOutreach Activitiesについての質問に200~500語程度で回答する)

General background informationはGoogle Formに自分の国籍だったりを入力する程度で、またCurrent resumeAcademic transcriptsについては東大の工学部の場合は英文の成績証明書が即日発行できるので、特に問題なく準備できました。
個人的にちょっと面倒だったのがCurrent ResumeとResponses to four essay questionsで、問題のなさそうな範囲でどんなことをしたのかを書いていこうと思います。

Resume(英文履歴書)の作成

応募にあたっては英文履歴書を用意する必要があります。また、Google STEPなどのプログラムでも英文履歴書での応募が推奨されています。 少し日本の履歴書と書き方やフォーマットが違ったりするので、「English Resume Software Engineer Intern」などで検索をかけると情報系の学部生の書くresumeがだいたいどう言った内容を含んでいるのかちょっこと見ることができると思います。

ただ正直日本からの応募者は例年そんなに多くないので、あまり気負わずにとりあえず書いて応募すればいいと思います!

とりあえず書いてみる

自分がresumeを作成するときは情報系の強いアメリカの大学の出しているresumeの書き方資料みたいなものを参考にしていました。

またresumeを作成するにあたって昔はWordやGoogle Docで作成していたのですが、「できるだけ見やすい」けど「デザイン的にもちょっとおしゃれ」かつ「プロっぽく見える()」をうまく両立しようと色々試行錯誤した結果、最近はもっぱらLaTexで作成しています。
また、resumeを書くときはオンラインでコンパイルができて共同編集も可能なOverleafを使用しています。(知り合いに添削してもらうこともあるため、これについても後述します)
Overleafについては様々なresume, CV(ちょっと長めの履歴書みたいなもの)が公開されているため、おしゃれで見やすいフォーマットを見つけてそれをベースにすると簡単に綺麗なresumeが作れます!

www.overleaf.com

ちなみに自分の最近のお気に入りのフォーマットはDeedy Resume - LaTeX Template on Overleafというフォーマットです。

添削してもらう

いったんresumeが作成できたら、できれば英語ネィティブ(かつソフトウェアエンジニアや情報系リサーチャーなどだとなお良い)の知り合いに添削してもらうと良いと思います。
私は昔このタイプの別のプログラムでとりあえず書いたまま提出したら書類で落とされた苦い経験があったので、今回は昨年のインターンの時のメンターに大体の添削をしてもらった後、アメリカの大学を卒業してソフトウェアエンジニアをしている友達、何度か進路の相談にのってくれたリサーチエンジニアの方に添削をお願いしました。
3人ともコンピュータサイエンス界のDiversityなどについて問題意識を抱えていてタイプだったので、もう一つのエッセイの方も色々コメントをくれてとても勉強になりました。

個人的にとても参考になったのが昨年のメンターからのコメントで、以下に引用しておきます。

I think for this scholarship you should expand your resume a bit, and include more details in the following sections:
Leadership, Awards, Research, Education
Since it is a scholarship program, leadership and prior awards will probably be the best topics to expand on for the program. I also think that you should expand 2-3 bullet dots for these leadership programs.

Leadershipというのは、例えば「女子中高生向けのプログラミング講座のメンターをした」「女性エンジニアと話す座談会を開催した」など、 今回の「情報科学分野における男女格差を是正する」ことを目的とするような活動や、もしサークルなどに所属していればそれを書けばいいと思います。
私は当時東大の女子学生向けのハッカソンの運営チーム兼学生メンターをしていたこと等を書きました。
こう言った目的に関連しなくても、例えばサークルの代表をしていた等、ボランティアをした等もリーダーシップ活動に含めればいいと思います。

Awardsについては過去の受賞歴(ハッカソン, プログラミング大会, 学会での受賞etc...)などを書ければ良いと思います。retreatで話したこの中にはICPCの参加経験のある子やプロダクトアイディアの世界大会に出ていた子もいました。

resumeは宗教があるみたいですがCVと違って基本的には1ページに収めることがよしとされるため、インターンのために作成したresumeをそのまま使い回すのではなく、 1ページから出ない範囲でscholarshipの応募では何を自分が伝えるべきかを考える必要がちょっとあるかもしれません。

自分の場合インターンの応募時にだす履歴書は Deedy Resume - LaTeX Template on Overleafのフォーマットをそのまま使用してCourseWorksやSkillsなどもできるだけ明確に書くようにしているのですが、 WTMについてはこれらの項目をごっそり飛ばしてDouble ColumnをSingle Columnにして 「Education, Leadership, Experience, Awards」の4点に絞った構成にしました。

Responses to four essay questionsの作成

essay questionsについては年ごとに多少変動すると思うのですが、基本的には「なぜ自分がこの奨学金に応募したいと思ったのか」「これまで女性であることで不利な状況になったと感じたことがあるか」「仮にリサースがあればどのようなアウトリーチ活動*1をしたいか」などが聞かれると思います。

自分はこれについてもざっと書いた後に人に添削してもらって曖昧な点をもっと具体的にしたり、表現をより適切なものに変えたりしました。

こう書くとなんか大変そうですが、ぶっちゃけ他の国と比べて日本からの応募者は少なくて倍率低めだと思うのであまり気負わずに普段ちょっと嫌だなと感じたこと、 こうすればいいのになと思うことをつらつら書くといいと思います!

こんな感じで応募してまだかなまだかなって思いながら結果を待っていると今年は7月頃に「Scholarに選んだよ!」ってメールが届きました。わーい。

https://scontent-nrt1-1.xx.fbcdn.net/v/t31.0-8/19956978_639652226231778_6702459863260857983_o.jpg?oh=9165f80c1cdcd13b7aef9bfd88467d07&oe=5ABAE178

WTMのその後の話

WTMのretreatなどの詳細は Google Women Techmakers Scholarshipってなあに? - りらのひとりごとをぜひ読んでみてください!自分はWTM終了後に行なったことやその後のScholarたちとの交流について書いていこうと思います。

アウトリーチ活動について

WTMのScholarはその後「情報科学分野におけるDiversityの改善に貢献するような活動」(以下、アウトリーチ活動と呼びます)をGoogleの支援を受けて行うことも期待されています。
自分は年内はあまり多くの時間を取れなかったので、引き続き東大女子ハッカソンの運営や来年の準備を行なったり、 同じく東大からのScholarのKaviさんが主催した女子向け競技プログラミング勉強会でスタッフをしたり、Qiitaの情報科学を勉強する女子大生アドベントカレンダーを開始したりしています。

f:id:akaringo030402:20171222131321j:plain
東大女子向けハッカソンでメンターをした時のもの

正直なところ、アウトリーチ活動に積極的に参加することについて「そんなことに時間を使う前にまずエンジニアとしてのスキルを磨くべきではないか」「エンジニアとしての自信がないからそういう活動に逃げているのではないか」と自問自答していた時期もありました。
でもやっぱりこういうイベントに関わったり主催してみて「プログラミングが楽しいと思った!」「もっと勉強してみたいと思った!」「普段男性ばかりで寂しかったから女の子のエンジニアとたくさん会えて楽しかった!」という声を聞くと、少しでも情報科学に興味があるけど躊躇ってしまっているような女の子の背中を押せたかなとうれしく思います。
りらちゃんの記事にもありましたが、「まだ未熟な自分がロールモデルなんて、前に立つなんて」と日和らずに、「私がロールモデルにならなきゃ、誰かを励ませるような存在にならなきゃ」って思うことも大切だなあと思っています。

他のScholarとのその後の関わりについて

WTM Scholarshipの特長として、情報科学を勉強する女子学生を支援するだけでなく、コミュニティ、ネットワークを作ることも主要な目的と据えていることです。そのため過去のScholarやプログラムに関わっているGoogleのエンジニア等の数百人規模のSlackやFacebookグループがあり、そこで様々な交流ができます。

Community
An online network with fellow scholars program participants designed to share resources, support the global community of women in tech and collaborate on projects to make continued impact.

また同じ年のScholarとは割とretreatで仲良くなれるので、その後も相手が日本に旅行に来た時にあったり、自分が相手の国行く時にあったりと行った交流も盛んです。
自分はretreatの時のルームメイトがシンガポール人の子で、「シンガポールに来るときは私が最高の旅行プラン立ててあげるから絶対教えてね!」と言われています笑。

また日本から選出されたScholar同士はやはり場所が近いので普段から「どんなアウトリーチ活動をすべきか」のミーティングをしたり、忘年会を開催したりと交流が盛んです。
自分があまり男性の方が圧倒的に多数派という環境に学科に入るまで体験したことがなかったため、 ごくたまにストレスを感じてしまうこともあり、そういう時にScholarの修士の先輩とスタバで悩みを聞いてもらったりもしました。

こんな感じでScholarとして選ばれた後もとってもいい友情だったりいいメンターだったりを見つけられるので、本当にWTMはおすすめです!! 来年の応募はまだ始まっていないと思うのですが、今年と同じであれば3, 4月くらいから始まると思うので、気になる方はぜひ応募してみてください :)

*1:一般的には福祉などの分野における地域社会への奉仕活動をさすのですが、情報科学系で用いられるときはgender bias/imbalance, racial bias/imbalanceを解消するために行う活動をさしていることが多いように感じます

大学の実験でChromiumに勝手に機能を追加してみた話

これは Chromium Browserアドベントカレンダーの15日目の記事です。
この記事では所属する電子情報工学科の実験でChromiumに「指定したキーワードを含む特定の検索履歴のみ非表示にする」という機能を勝手に実装した時の体験をつらつら書いて行きたいと思います。
学科の先輩で現在Blink-Workerチームにいらっしゃるamiq11さんが在学中にこの実験のTAをされていたこともあって声をかけていただきました。 プロの方々によるとても素敵な記事ばかりが並ぶ中で恐縮ですが、「ちょっと勉強がてらChromiumソースコードをとりあえず読んでみて、何かちょっとした機能を加えてみたい、改造したい」な ニッチな人々の参考になれば嬉しいです…!

なんで大学の実験でChromium

東大工学部電気系3年生は3〜6個のテーマの実験を行うことが必修となっており、私は今学期、他の二つの実験と併せて田浦健二郎先生による「大規模ソフトウェアを手探る」実験を履修しました。
この実験は「演習レベルの小さなプログラムが作れること」と、「実用規模のプログラムが作れること」のギャップを埋める (ための知識と経験を得る)ことを目的に、1〜数百万行のオープンソースソフトウェアをソースからビルドし新しい機能を加えたりします。
Chromiumの他にFirefoxJavaScriptエンジン、SpiderMonkeyや最近そのリッチな自動補完などで人気なfish shellを題材にした班もあり、 実際に本家にPRを出して変更がマージされたりしています。

実験で追加した機能

今回私の班が実装したのは、「Chromiumの設定画面で非表示キーワードを設定すると、Chromium上部の検索ボックスの自動補完候補からそのキーワードを含む過去の検索履歴を除く」というものです。
弊学科でスライド投影中にブラウザを起動してうっかり気まずい検索履歴を表示しちゃう方がよくいるという完全に内輪ネタから始まったので深い理由はないです。 Chrome上部の検索ボックスの正式名称は「Omnibox」といい、ユーザーの入力に従って、「過去に検索した検索クエリ」「過去に閲覧したページのURL」「Google検索で人気の検索」など様々なタイプの自動補完候補をサジェストしてくれています。

f:id:akaringo030402:20171202164136p:plain:w400

ちなみにsafariだとこんな感じ。Chromeでは様々なタイプの自動補完候補が並べられて表示されるのに対し、 safariはそれぞれの自動補完候補のタイプ別にセクションを分けているのがわかりますね。 f:id:akaringo030402:20171202164126p:plain:w400

今回はどう初心者がChromiumのソースからビルドして数百万行あるChromiumソースコードから変更したい箇所を見つけ、 機能を追加していくのかを書きたいと思います。
この実験では、実験レポートの代わりにブログ記事を提出可能というルールがあるため、 もしより詳細な内容(というか悪戦苦闘の様子)が知りたい奇特な方がいらっしゃれば下にそれぞれのステップと対応する、提出した記事の一覧を貼ったのでのぞいてみてください(゚▽゚*)

変更した内容 ブログ記事
ビルドする 大規模ソフトウェア(Chromium)を手探る 導入・ビルド編 - あさりさんの作業日記
ソースコードとドキュメントを手探る 大規模ソフトウェアを手探る Chromeのソースコードとドキュメントをひたすら漁る - あさりさんの作業日記
検索ボックスのデータの流れを追い、自動補完候補にキーワードフィルターをかける 大規模ソフトウェアを手探る 検索ボックスにおける自動補完・サジェスチョンのデータの流れを追う - あさりさんの作業日記
user profileに新しい設定項目を追加 大規模ソフトウェア(Chromium)を手探る user profileに設定を追加する - あさりさんの作業日記
設定画面に非表示キーワードを新しく追加するための新たなWebUIをつける 大規模ソフトウェア(Chromium)を手探る - 設定画面(settings)を手探る1 - - elechoのぶろぐ
入力した情報をuser profileに引き渡すためのcall backハンドラを実装する 大規模ソフトウェア(Chromium)を手探る callbackハンドラを追加する・全体の感想 - あさりさんの作業日記

ソースコードを(文字通り)手探る

実装する方法として、当初は以下の二つのアイディアを考えました。

  1. 入力に従って検索ボックスの自動補完情報を更新しているモジュール上で、特定の単語が含まれる検索履歴は自動補完候補から弾くようにする。
  2. 特定の単語が含まれる検索ワードはそもそも検索履歴DBに保存されないようにする。

そもそもデータにすら残さないのってどうなんだ?ということで、方針1で実装進めて行くことにしました。

Design Docを探してみる

Chromium Browser初日の記事で紹介いただいているように、 Chromiumには強力なコードサーチページがあります。ただ土地勘のない初心者が数百万行以上とも言われるChromiumソースコードをいきなりそれっぽいキーワードでサーチする/目grepしようとすると、 果てしない壁にぶつかります。
もし趣味で手探ってみたい!という方がいれば、まず関連するDesign Docsを検索し、自分がいじってみたいモジュールはどれか、ソースコードはどのディレクトリにありそうか、ある程度目処をつけることをオススメします(自分の教訓です)。
Chromium (Chrome Browser, Chrome OS)の開発者向けドキュメント (design doc) は公式ホームページ、The Chromium ProjectのFor Developers>Design Documentsから検索できます。
ここでOmniboxで検索をかけてみると、Omnibox: History Provider - The Chromium Projectsというドキュメントに以下のような記述があるのを確認できます。

One of the autocomplete providers for the omnibox (the HistoryQuickProvider, HQP for short) serves up autocomplete candidates from the profile's history database. As the user starts typing into the omnibox, the HQP performs a search in its index of significant historical visits for the term or terms which have been typed.

HistoryProvider自体は過去の検索履歴から入力文字列とマッチしてそうなエントリを返すので、今回の「ユーザーの過去に入力した検索文字列」をOmniboxに供給している訳ではないのですが、 上の記述から自動補完候補は様々な種類のプロバイダからユーザーの検索履歴DBから供給されていること、ユーザーの入力に応じて入力文字列とマッチした過去の履歴を補完候補としてサジェストしているのが推測できます。

またChromeのUser Experiment関連のドキュメント、Omnibox - The Chromium Projectsをみると、いわゆる「ユーザーが検索の際に実際に入力した文字列に基づくサジェスチョン」はSearch Suggestというタイプに分類されているとわかります。 SearchProviderみたいな名前がついてそう………ざっくりですがだいたい目処がついてきました。

実際にコードをちょっといじってみる

Chrome Code SearchでSearchProviderクラスがどこにあるかちょっと調べてみると、 src/components/omnibox/browser/search_provider.cc で実際にSearchProviderクラスが実際に定義されていることがわかります。

最初は単純にこのSearchProviderの中でキーワードフィルターをかければいいのでは??と安易に考え、とりあえずある文字列とサジェスチョンが一致する場合は自動補完候補から除き、実際にサジェスチョンから消えるか確認してみることにしました。

SearchProvider::ScoreHistoryResultsHelper(...) {
    SearchSuggestionParser::SuggestResults scored_results;
    if (base::EqualsASCII(history_suggestions.suggestion(), “hogehoge”)  == false){
      scored_results.insert(insertion_position, history_suggestion);
    }
    return scored_result;
}

結果 : 普通に自動補完に出てきたwwwwww

どうやら単純にProvider側でとりあえず弾く、という実装だけでは不十分だったようなので、 ちゃんと自動補完のデータがどう流れてきているのか、デバッカで追ってみることにしました。

自動補完のデータの流れを追ってみる

地道にデバックやエラーのバックトレース結果をみると、Omniboxの自動補完候補は

  1. まず下図の右手側にあるそれぞれのProviderが入力とマッチするデータをprofileなどからそれぞれ取ってくる
  2. Controllerクラスがこれらすべての自動補完候補をAutocomoleteMatchesにまとめる(この結果が図のmatches_)
  3. 関連度等に基づいてこの自動補完候補をソートする(この結果が図のautcocomplete_result_)
  4. ソートされた結果が新たな自動補完候補として更新される

f:id:akaringo030402:20171101194213p:plain
自動補完候補データの流れ

の流れで提供されていることがわかりました。

次に、一個一個プロバイダから自動補完データを渡している部分をコメントアウトする頭の悪い感じの作業をしてSearchProviderの候補から確かに除いたはずの 非表示キーワード自動補完がどこから流れてきたのか検証してみると、実はShortcutProviderというクラスから弾いたはずのデータが供給されていることがわかりました。

Providerの中でも一番下に示された意味ありげなShortcutProviderというProviderクラス、当初はあまりちゃんとマークしていなかったのですが、 このクラスのヘッダーファイルを見てみると以下の記述があります。

// 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 {...}

"Provider of recently autocompleted links. Provides autocomplete suggestions from previously selected suggestions. "

ん??????

つまりこれをみると、最近サジェストされ、ユーザーが実際に検索した候補のデータを別のDBに保存し、そこからデータを供給していることがわかりました。 こうすると例えSearchProvider側であるキーワードを含むものを自動補完候補から除いても、こちらのProvider側が読み込んでいるDBにすでに 非表示キーワードを含んだ履歴が残されていると、こちらからデータが供給されてしまうことがわかります。

f:id:akaringo030402:20171101194249p:plain
AutocompleteControllerクラスでデータをソートする前にフィルターをかけるよう実装を変更

それぞれの個々のProviderにフィルターをかけるような実装でもよかったのかもしれませんが、自動補完として集められた結果に割と重複が多いことからも無駄が多いのではないか?という指摘をTAの方にいただいきました。 そこで以下のように、全ての補完候補をまとめて重複を除いた後、非表示キーワードを含むないしは非表示キーワードと一致する自動補完結果については除外するように変更を加えました。
後述するUser Profileの情報を読み込んで非表示キーワードが設定されていた場合にはSortAndCullWithKeyword()関数を呼び、このSortAndCullWithKeyword()は非表示キーワードを含むかどうかfind()で判定し、のぞいた後に SortAndCull()という候補のソートを行う関数に渡しています。

bool IsRemovableTypeFromMatch(AutocompleteMatchType::Type type) {
  return type == AutocompleteMatchType::HISTORY_TITLE ||
         type == AutocompleteMatchType::HISTORY_BODY ||
         type == AutocompleteMatchType::SEARCH_HISTORY ||
         type == AutocompleteMatchType::SEARCH_SUGGEST_TAIL;
}

}  // namespace

void AutocompleteResult::SortAndCullWithKeyword(
    const AutocompleteInput& input,
    TemplateURLService* template_url_service,
    const std::string& keyword) {
  std::vector<base::string16> restricted_keywords =
      TokenizesKeywordsStringToKeywordsVec(keyword);
  const base::string16& input_text = input.text();
  matches_.erase(
      std::remove_if(
          matches_.begin(), matches_.end(),
          [&restricted_keywords, &input_text](const AutocompleteMatch& match) {
            bool removable = IsRemovableTypeFromMatch(match.type);
            if (removable) {
              base::string16 match_text = base::ToLowerASCII(match.contents);
              for (auto& restricted_keyword : restricted_keywords) {
                // Omniboxの入力文字列と一致しないかつ表示したくないキーワードを含む検索候補を除くように書き換える。
                if (input_text != match_text &&
                    match_text.find(restricted_keyword) !=
                        base::string16::npos) {
                  return true;
                }
              }
            }
            return false;
          }),
      matches_.end());

  SortAndCull(input, template_url_service);
}

IsRemovableTypeFromMatch()は自動補完候補がユーザーの過去の検索に基づくものであるかどうか判定し、過去の検索クエリや訪問履歴に基づいた自動補完データ出会った場合のみ、 非表示キーワードを含む自動補完候補を候補から除きます。
これは「自動補完候補のうち、キーワードを含むものは全て除く」とすると普段の検索でGoogle検索で人気のキーワードに基づく自動補完候補なども消去されてしまうために、普段の利用で不便が生じそうと考えたためです。
余談ですが、kRestrictedKeywordについてはカンマ区切りにすれば複数キーワードも指定可にしており、TokenizesKeywordsStringToKeywordsVec(keyword)でtokenizeをしています。

User Profileに非表示キーワードを追加する

上の変更で指定されたキーワードを含む自動補完候補フィルタリングについては機能するようになりました。あとは非表示したいキーワードをChromeの通用の設定画面で追加できるようにしたあと、 User Profileに保存してC++側から参照できるように変更を加えます。

Preferenceに非表示キーワードを追加する

ユーザーの登録したChromiumの設定はUser Profileのpreferenceに保存され、それぞれに固有のkey(pref_name)によって識別されます。 preferecesに任意の設定について追加したい場合には、

  1. PrefNamesクラスで新しく設定したいpreferenceのnameとデフォルト値を登録する。
  2. ProfileImplクラスのRegisterProfilePrefsd()という関数でこのpreferenceを登録する。

というステップでProfileにこの新しいpreferenceの値がストアされるようになり、PrefServiceを呼ぶことで、C++のプログラムから参照できるようになります。

www.chromium.org

preferenceへの新たな項目の追加はchrome/common/pref_names.h及びchrome/common/pref_names.cppに以下のように追加します。

まずkRestrictedKeywordchrome/common/pref_names.hで宣言します。

namespace prefs {
// Profile prefs. Please add Local State prefs below instead.
...
extern const char kRestrictedKeyword[];
}  // namespace prefs

次に、cpp側でUI(JavaScript)側からこのpreferenceを参照する時に必要なpref_nameを登録します。ここに格納される値はデフォルト値ではなくてキーとして使われる識別子です。

namespace prefs {
// *************** PROFILE PREFS ***************
// These are attached to the user profile
...
const char kRestrictedKeyword[] = "RestrictedKeyword";
}  // namespace prefs

最後にProfileImplクラスのRegisterProfilePrefsd()という関数でこのpreferenceを登録します。ちなみにこれをやらないと実行時にコアダンプします。

 // RegisterProfilePrefsd()というvoid関数でpreferenceの登録が行われている
void ProfileImpl::RegisterProfilePrefs(
    user_prefs::PrefRegistrySyncable* registry) {
  registry->RegisterBooleanPref(prefs::kSavingBrowserHistoryDisabled, false);
...
  registry->RegisterStringPref(prefs::kRestrictedKeyword, std::string());
}

AutocompleteController側からPrefServiceを呼び出す

ユーザーのpreferencesを取得するためには、PrefServiceをservice clientから呼ぶ必要があります。 自動補完候補のソートを行なっているAutocompleteResultクラスは、service clientに順ずるものに直接はアクセスできないため、AutocompleteController側でkRestrictedKeywordを取得し、SortAndCullWithKeyword()関数に渡す形で実装することにしました。

void AutocompleteController::UpdateResult(
    bool regenerate_result,
    bool force_notify_default_match_changed) {
  PrefService* prefs = provider_client_->GetPrefs();
  const std::string keyword = prefs->GetString(prefs::kRestrictedKeyword);
  // 非表示キーワードが設定されていた時はSortAndCullWithKeyword()を、
  // そうでない時は通常のSortAndCull()を呼ぶ。
  if (keyword) {
    result_.SortAndCullWithKeyword(input_, template_url_service_, keyword);
  } else {
    result_.SortAndCull(input_, template_url_service_);
  }
...
}

設定画面に非表示キーワード登録欄を追加する

ここまでの変更でpreferenceの情報を取得し、登録された任意の一つもしくは複数のキーワードを含む自動補完候補のフィルタリンリング機能の実装が完了しました。
あとは実際にChromeのデフォルトの設定画面に非表示キーワードを登録できるようにUIを変更すれば完成です。

WebUIを変更する

まず設定画面のHTML, JavaScriptファイルを追加ないし変更をして、非表示キーワードを登録するセクションを追加します。
WebUIの変更については同じチームのelechoくんが以下の記事で詳細にまとめていくれているので興味がある方はelechoくんの記事も呼んでください :)

elecho.hatenablog.com elecho.hatenablog.com

ChromeのWebUIの変更については以下のドキュメントが参考になりました。

www.chromium.org

ドキュメントにもあるように、WebUIの変更にはWebUIページの作成だけでなく、リソースへの追加、ルーティングの設定等、多くのファイルの変更が必要となり、 どこか忘れると正しく表示されなかったりして、またデバックもいい方法がわからず苦労しました…
ChromeでのいいWebUIのデバッグ方法が知りたいなとちょっと思いました。

実際にChrome Settingsにキーワード登録セクションを追加しました。(画像は授業内でのデモ用に設定画面の一番上に非表示キーワード登録セクションを追加してみます)

f:id:akaringo030402:20171211104724p:plain

callbackハンドラを追加する

ドキュメントにも紹介されていますが、新たに追加したWebUIからC++モジュールの情報を参照したり、JavaScript側でのsettingsでの変更をC++のPrefServiceを用いてuser profileに追加するためには、 メッセージコールバックハンドラを追加する方法が推奨されている(みたいです)。

You probably want your new WebUI page to be able to do something or get information from the C++ world. For this, we use message callback handlers. Let's say that we don't trust the Javascript engine to be able to add two integers together (since we know that it uses floating point values internally). We could add a callback handler to perform integer arithmetic for us.

ここについては特に手探りで行なった部分も多く、誤りなどあるかもしれませんが、以下のような手順でcallbackハンドラクラスを追加しました。

  1. handlerクラス(h, cppファイル)を追加する。
  2. MessageCallbackを登録し、JavaScriptで呼ばれる関数名と対応するC++プログラムでの関数名を決める
  3. 実際に呼ばれるC++の関数の動作を定義する
  4. 追加したハンドラを新しくビルドターゲットに追加する

handlerクラスを追加する

新しくmessage callback handlerを追加する場合にはchrome/browser/ui/webui/settings/以下にsettings_restricted_keyword_pages_handler.hsettings_restricted_keyword_pages_handler.cppファイルを加え、設定画面の別のセクションのcallback handlerを参考に実装しました。
RestrictedKeywordHandlerクラスのヘッダファイルはこんな感じ。

class RestrictedKeywordHandler : public SettingsPageUIHandler,
                            public ui::TableModelObserver {
 public:
  explicit RestrictedKeywordHandler(content::WebUI* webui);
  ~RestrictedKeywordHandler() override;

  // SettingsPageUIHandler:
  void RegisterMessages() override;
  void OnJavascriptAllowed() override;
  void OnJavascriptDisallowed() override;

  // ui::TableModelObserver:
  void OnModelChanged() override;
  void OnItemsChanged(int start, int length) override;
  void OnItemsAdded(int start, int length) override;
  void OnItemsRemoved(int start, int length) override;

 private:
  PrefChangeRegistrar pref_change_registrar_;
  CustomHomePagesTableModel restricted_custom_page_table_model_;
  DISALLOW_COPY_AND_ASSIGN(RestrictedKeywordHandler);
 };

MessageCallbackを登録する

callback handlerクラスで定義されたC++の関数をMessageCallbackに登録することで、JavaScriptから指定した関数名で呼べばregisterしたC++の関数が呼ばれるようになります。
今回はprefs::kRestrictedKeywordを追加する関数setRestrictedKeyword、またユーザーが設定画面を開いた時に今の設定値を見えるようにJavaScriptに情報を渡すための関数getRestrictedKeywordを追加します。
先ほど作成したsettings_restricted_keyword_pages_handler.cppRestrictedKeywordHandler::RegisterMessages()で登録を行います。

void RestrictedKeywordHandler::RegisterMessages() {
  if (Profile::FromWebUI(web_ui())->IsOffTheRecord())
    return;
  web_ui()->RegisterMessageCallback("setRestrictedKeyword",
                 base::Bind(&RestrictedKeywordHandler::HandleSetRestrictedKeyword,
                            base::Unretained(this)));
  web_ui()->RegisterMessageCallback("getRestrictedKeyword",
                            base::Bind(&RestrictedKeywordHandler::HandleGetRestrictedKeyword,
                                       base::Unretained(this)));
}

実際に実行されるC++関数を追加する

実際にuser profileを取得して登録されたキーワードの情報を取り出したり、設定画面でキーワードが登録された際にpreferenceを変更する関数をsettings_restricted_keyword_pages_handler.cppに実装していきます。HandleAddRestrictedKeyword()ではWebUIからProfileを取得し、JavaScript側から渡されたvalue(新しく追加されたキーワード)をprefs::kRestrictedKeywordにセットします。また、 C++側でpreferenceから現在のキーワードを取得し、JavaScriptにcallbackを返すためのHandleGetRestrictedKeyword()関数も追加します。

void RestrictedKeywordHandler::HandleAddRestrictedKeyword(const base::ListValue* args) {
  std::string pref_name;
  args->GetString(0, &pref_name);
  const base::Value* value;
  args->Get(1, &value);
  PrefService* prefs = Profile::FromWebUI(web_ui())->GetPrefs();
  prefs->SetString(prefs::kRestrictedKeyword, value->GetString());
}

void RestrictedKeywordHandler::HandleGetRestrictedKeyword(const base::ListValue* args) {
  CHECK_EQ(1U, args->GetSize());
  const base::Value* callback_id;
  CHECK(args->Get(0, &callback_id));
  AllowJavascript();
  ResolveJavascriptCallback(*callback_id, base::Value(GetRestrictedKeyword()));
}

std::string RestrictedKeywordHandler::GetRestrictedKeyword() {
  std::string RestrictedKeyword;
  PrefService* prefs = Profile::FromWebUI(web_ui())->GetPrefs();
  RestrictedKeyword = prefs->GetString(prefs::kRestrictedKeyword);
  return RestrictedKeyword;
}

ビルドターゲットに追加する

新しくsourcesを追加する時はgnファイルに追加したファイルへのパスを登録をし、ビルドターゲットに追加します。
通常はchrome/browser/ui/BUILD.gnにccファイルとhファイルへのパスを追加するのみですが、 設定画面の変更については別にSettingPagesHandlerとしてchrome/browser/ui/webui/settings/md_settings_ui.ccに以下のように追加する必要がありました。
この辺りについては類似するクラスを参照しながら必要そうな変更にあたりをつけていきました。

#include "chrome/browser/ui/webui/settings/settings_restricted_keyword_pages_handler.h"

MdSettingsUI::MdSettingsUI(content::WebUI* web_ui)
    : content::WebUIController(web_ui),
      WebContentsObserver(web_ui->GetWebContents()) {
   ...
   AddSettingsPageUIHandler(base::MakeUnique<RestrictedKeywordHandler>(web_ui));
   ...
}

まとめ

短い時間でしたが、Chromiumソースコードをコードサーチやdesign docをフル活用して手探る中で、 ブラウザでのざまざまなプロセスの動きやC++世界とJavaScriptの世界でどうやりとりがなされているか、またChromiumでのWebUIの構成など 様々なことが学べました。
Chromiumに実際にコミットしなくても、「こんな機能できないかな…!!」くらいの気持ちで色々いじってみるととても勉強になるので 年末年始暇な方などは遊んでみてください〜 :)

Word2Vecモデルをスクラッチで実装してみる ① そもそもWord2Vecって?

この記事は情報系を勉強する女子大生 Advent Calendar 2017 - Qiitaの9日目の記事です。
実は春休みにインターン自然言語処理のプロジェクトをやって以来この領域が好きで、 今回はそのきっかけになった単語ベクトルの話をしていこうと思います(・x・)

※B3が趣味で書いているだけなので曖昧な説明、「数学的にアレ」な部分が散見されると思うのですが見つけた場合は優しくコメントいただけるととっても嬉しいです...

ちなみにつらつら書くだけより実際に実装してみたほうが頭に入りそうだな〜ということで3つの記事に分けて 基本のモデルを追うところからPythonで実際に実装するところまでやるつもりです!
最初2回は情報系を勉強する女子大生 Advent Calendar 2017 - Qiitaに、最後1回は自分の所属する東大電気電子電子情報工学科のアドベントカレンダーeeic (東京大学工学部電気電子・電子情報工学科) Advent Calendar 2017 - Qiitaに載せるつもりなので、興味があればそちらもみてみてください〜

今回の記事を書くにあたってスタンフォード大学CS224N:Deep Learning for NLPの授業を参考にしています。
授業スライド、参考資料、課題、講義ビデオ全てネット上で公開されているので、自然言語処理における深層学習に興味がある方はぜひ見てみてくださいヾ(@°▽°@)ノ

単語の意味をどう表現するか

自然言語はそのままでは深層学習や機械学習モデルに入力として入れることはできず、なんらかの形でコンピュータが理解できる形で単語の意味を教えていかなくてはいけません。
一番シンプルなのは単語ごとになんらかのカテゴリだったり特性(good, negative, positive...etc)のラベルを振っていくとかができそうです。
About WordNet - WordNet - About WordNetは英単語がsynsetと呼ばれる同義語のグループに分類され、簡単な定義や、他の同義語のグループとの関係が記述されています。
NLTKという自然言語処理でよく使われるPythonのライブラリでこのWordNetのためのインテーフェイスがあり、以下の感じで「panda」のhypernym(上位語)が取得できます。

from nltk.corpus import wordnet as wn
panda = wn.synset('panda.n.01')
hyper = lambda s:s.hypernyms()
list(panda.closure(hyper))

ちなみに結果はこんな感じ。

[Synset('procyonid.n.01'), Synset('carnivore.n.01'), Synset('placental.n.01'), Synset('mammal.n.01'), Synset('vertebrate.n.01'), Synset('chordate.n.01'), Synset('animal.n.01'), Synset('organism.n.01'), Synset('living_thing.n.01'), Synset('whole.n.02'), Synset('object.n.01'), Synset('physical_entity.n.01'), Synset('entity.n.01')]

procyonid(アライグマ科), carnivore(肉食動物), placental(有胎盤類), mammal(哺乳類), vertebrate(脊椎動物), chordate(脊索動物), animal(動物), organism(生体)m living_thing(生き物), whole(全体), object(物体)...
うん、上位語は正しそう!が、こんな感じのラベリングとか概念定義を存在する全単語にやるのはちょっと現実的に厳しそうです……
また同義語に対して細かい意味の違いを表現できないのではないかという指摘もされています。さすがにこれじゃ厳しい、ということで次に出てきたのがOne hotな単語表現でした。

One hotによる局所的な表現

例えばあるデータセットにN単語含まれるならばN次元のベクトルを作り、そのベクトルの中でt番目だけ1を立て、残りは全て零とするOne hot表現が用いられていました。 例えばもし異なる10単語が登場する文章が与えられた時、文章中に登場するhotelとmotelという単語はそれぞれ以下のように表現されることになります。

{\displaystyle 
  W_{hotel} =
    \begin{pmatrix}
      0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0
    \end{pmatrix}
}
{\displaystyle 
  W_{motel} =
    \begin{pmatrix}
      0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0
    \end{pmatrix}
}

このような表現は何が問題なのでしょう?まずこの表現だと、もし単語数が数百万、数千万…と増えていくと、巨大で疎ベクトルが必要になり、計算コストもメモリも心配になります。

また、これ内積をちょっと計算してみると

{\displaystyle 
    \begin{pmatrix}
      0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0
    \end{pmatrix} ^T 
    \begin{pmatrix}
      0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0
    \end{pmatrix} = 0
}

直交しており、類似度が全くないとなってしまうことがわかります。motel, hotelという類似語についてのベクトル表現のはずなのに、類似度の概念をOne hotベクトルでは全く捉えることができないために失われてしまいます。これもあまり望ましくないですよね…

分散的な単語表現とは

単語の意味をより密なベクトル表現を使って単語を表現できないか、という考えがここから出てきます。例えば、1万の単語をそのままOne hotベクトルで表すと1万次元が必要になるけど、 これを100~300くらいの密なベクトルにできれば、コストを減らすこともできそうだし、単語間の類似性ももうちょっとちゃんと捉えられそうです。
こういった単語のベクトル表現を「分散的な単語表現」と呼びます。ここで大事になってくるのが、 distributional hypothesis(意味的に近い単語は同じ文章に出現するはずだ)というもので、Word2Vec, Glove, fastText等の著名なモデルではこの考えを元にしています。

分散的な単語表現の基本的な考え方

基本的にはあるwordとその周辺のcontext words(もし"I love dogs and cats"という文章があり、"dogs"というwordに着目するならcontextは"I", "love", "and", "cats"ということになります)の間の条件付き確率を求め、これをコーパス中の全ての単語に対して行い、全体での目的関数を最大化するようパラメータを調節します。

....よくわからないですね !!!! ということで分散的な単語表現を行うモデルのうち、おそらく一番有名なWord2Vecというモデルに焦点を当てて何を具体的に計算しているのか、考えてみます。

Word2Vecとは

Word2Vecモデルとは上で書いたような「単語を密なベクトルでいい感じに表現する」モデルの代表的なものの一つであり、米グーグル(当時)の研究者であるトマス・ミコロフ氏により提案されました。
queen - woman = king」の例を耳にしたことのある方も多いのではないでしょうか。
密なベクトル表現により文章に含まれる単語同士の類似度や、単語間での加算・減算などができるようになり、 またニューラルネットワークの入力の素性に利用できるようになったことで、ディープラーニング自然言語処理への応用が 進んだとも言われています。

Word2Vecのメインの二つのアルゴリズムに、前後の単語からある単語を予測する「CBoW」と、ある単語から周辺の単語を予測する「Skip-gram」があり、この二つがあるのですが、CBoWについて書いている最中にスタバwifiが切断された結果書きかけの記事が吹き飛んで萎えたので今回はとりあえずSkip-gramにフォーカスを当てたいと思います。

Skip-gram

Skip-gramはCBoWの逆の方向で考え、単語(word)からその周辺単語(context)を予測します。
例えば{"I", "love", "playing", "tennis", "pizza", "eating", "am"}のような単語が与えられた時、"I love playing tennis", "I love pizza"は文章として自然ですが、 "I am pizza"や"I tennis"はちょっと気持ち悪いですよね。
これが私たちが無意識に「"pizza"という単語が与えらられた時にはおそらく周りには"like", "eating"などの動詞がくるの」「"I"という主格代名詞の直後にいきなり"tennis"や"pizza"などの普通名詞が 登場するのはおかしい」と、ある単語からその単語が使われそうな文脈を予測しているためです。 Skip Gramではこんな感じで、ある単語{\displaystyle W_t}が与えられた時、 その周辺(context)にはどんな単語がくるべきかを条件付き確率で表します。
例えばbankingという単語を中心に考えてみます。

f:id:akaringo030402:20171208142840p:plain
wordとcontext
ここで"m window word"という表現が出てきていると思うのですが、windowとは、「ある単語から前後m単語までは周辺にある単語として解釈するよ!」ということを表しています。なので {\displaystyle m = 100} とすればある単語の前後100単語までは周辺単語と解釈することもできるのですが、実際私たちがある単語について考える時、ここまで離れた関係で考えたりはしないと思うので、windowサイズはそこまで大きく設定はされません。

上の例だとbankingとcrisisっていう単語は割と一緒に出てきそうなので、{\displaystyle p(crisis|banking)}とかは確率として高くなるようになってほしいですね。
{\displaystyle p(into|banking)}はおそらくありうるとは思うのですが、{\displaystyle p(crisis|banking)}よりは発生頻度が低くないなりそうなので、確率としてはやや低くなりそうです。

じゃあ実際にこの条件付き確率はどうやって計算し、また「こういう使い方はありえそう」というものをより高くするために、パラメータはどう調整するのでしょう。

Word2Vecでは次のようにソフトマックスでモデル化します。

{\displaystyle 
 p(w_o|w_c) = \frac{\exp{(u_o^Tv_c)}}{\sum_{w=1}^V \exp{(u_w^Tv_c)}}
}

{\displaystyle w_o}は中心の単語{\displaystyle w_c}の周辺の単語を表ており、{\displaystyle v_c}{\displaystyle w_c}の単語ベクトル、{\displaystyle u_o}は出力ベクトルを表ています。
{\displaystyle V}コーパス(学習に使う文章)に含まれる全ての単語を表ており、このように周辺単語{\displaystyle w_o}の出力ベクトル{\displaystyle u_o}{\displaystyle v_c}内積をとり、 それを正規化することで、{\displaystyle w_o}{\displaystyle w_c}が共起する確率を求めます。

目的関数は、ある中心の単語を考えた時、実際にその周囲に出現した単語の条件付き確率の同時確率を最大化すれば良いので、以下のような目的関数を考えます。

{\displaystyle 
 J(\theta)= \prod_{t=1}^T  \prod_{im \leq j \leq m, j \neq 0} p(w_{t+j} | w_t)
}

このままだとちょっと計算しにくいので、対数尤度関数をとって、かつマイナスをかけて以下のような関数にします。

{\displaystyle 
 J(\theta)= - \frac{1}{T} \sum_{t=1}^T  \sum_{-m \leq j \leq m, j \neq 0} \log{p(w_{t+j} | w_t)}
}

ここで{\theta}は全ての最適化可能なパラメータを意味しています。

あとはパラメータをいい感じに最適化してこの関数を最小化するだけです! 実際にどう最適化するのかなどは次の記事で紹介しようと思います。今回はざっくりSkip-gramが何をしているのかが伝わればうれしいです :)

なんでこれ面白いと思ったの

※ここからは完全に個人的な私見です | _・)チラッ

自分の場合単語ベクトルの話が個人的に自然言語処理おもしろい!ってなった最初のきっかけの一つだったような気がします。

ある単語から周りにこんな単語がきそうだと予測する」(skip-gram)や「周辺の単語から中心の単語はこんな感じだろうと思う」(CBoW)の考え方って割と私たちが普段文章を読むときになんとなくやっている行動に近いなと思いました。
子供の頃小説を読んでいるときに特定の漢字が読めないときやTOEFLなどの英語の試験でわからない単語が出てきたとき、前後を読んで「多分この単語はこんな意味だろう」と予測を立てたり、文章を組み立てるときに「この単語と一緒に使われるべきはこれだな」って考えたりしませんか?
これを上のように数式できちんとモデル化して、しかも割と人間が見ても「あ、確かにその単語同士は似ているよね」「確かにその単語とその単語引くとそうなりそう!」みたいな関係性をきちんと捉えられるのってすごい面白いな〜(ふわ〜)と個人的には思っているので、今回記事を書いて見ました。
ざっくりと曖昧な説明でごめんなさいなのですが、少しでもへ〜って思っていただけたらうれしいです。

ハッカソンのススメ

このブログは 情報系を勉強する女子大生 Advent Calendar 2017 - Qiitaの一日目の記事です。

ハッカソンとは

情報系の勉強をしているならなんとなく「ハッカソン」という言葉だけは聞いたことがあるのではないでしょうか。簡単にいうと、「ある決まった短い時間でゼロからアイディア出し、プロダクトの実装を行いピッチ、デモを行い成果を競い合うイベント」です。

「旅行」「家庭」など、ゆるくお題を与えられているものもあれば、「モバイルアプリ」など技術やプラットフォームを制限したもの(SPA-JAM)、また面白ければなんでも好きなものを作っても良いというハッカソン(Yahoo HackDay)もあります。

spajam.jp

hackday.jp

1ヶ月など中長期の開発コンペとの比較して際立つのが、「アイディアをじっくりと議論をする時間は(基本的には)ない」「とにかく拙速でも機能を実装仕切ることが大切」「1 ~ 10分のごく短い時間ピッチでアイディアを伝え、実装したもののデモンストレーションをしなくてはいけない」等だと思います。こう書くとちょっと難しそうですが、一種のお祭り騒ぎみたいな感じですごく楽しいので、今回ハッカソンを布教するための記事を書くことにしました。

ハッカソンに出ると何がいいの?

ハッカソン メリット」とかググると色々な記事がヒットすると思いますが、個人的にハッカソンを出て感じた 「まだ実務経験がそれほどあるわけではない大学生エンジニアが感じるハッカソンのメリット」をいくつかあげたいと思います。

限られた時間の中でチーム開発をする体験ができる

事前開発が可能なケースもありますが、基本的にハッカソンは1~2日の短い時間でゼロから実装をしなくてはいけない場合がほとんどです。 そのため、チームで「期限までにどのようなスケジュールで開発を進めるか」「実装はどう分担するか」「どの機能を優先して実装し、余裕があったら実装する機能はどれか」 を決めて開発を進めていきます。
また分担をしながら効率的に機能実装を進めるためには、Gitなどのツールをきちんと使いこなす必要があります。
普段の大学の課題を進めるだけでは、スケシュールを決められている中でのgitを用いたチーム開発を進めることはあまり多くはないと思うので、 こういったハッカソンなどに参加すると勉強になります。
また時間が限られているために、ライブラリ、API、訓練済みのモデルを上手く活用することも 大きな鍵になってきます。既存のツールのドキュメントやリファレンスをざっと読み、実際に活用できそうか考え、試して、 使えそうならプロダクトに組み入れるといったフローもハッカソンで経験できました。

自分のプロダクトを簡潔に伝える練習ができる

ハッカソンでは大抵最終日にハッカソン中に開発したプロダクトの数分間ピッチを行います。 大会にもよると思うのですが、私がこれまで出た大会では1分半~3分しかピッチ時間のないものがほとんどでした。
この時間ではゆっくりとシステム構成の説明している時間はもちろんなく、「解決したい問題は何か」 「この問題をどう解決しているのか」「実際に機能するのか(デモ)」などを簡潔に、しかし重要な点はしっかりと伝わるように話さなくてはいけません。
こういったピッチの経験は「何を、どうやって相手に伝えればわかってもらえるのか」を理解する上でとてもいい経験になりました。
また個人的には、繰り返し人前でピッチをすると少しだけ以前より場慣れするので、昔ほどプレゼンテーションに対して上がらなくなりました。 (今でもそこまで得意ではないのですが…)

企業の人、他大学のエンジニアの人と知り合うことができる

特に大学生限定のハッカソン(HackUJPHacksなど)では、自分の専攻、大学だけでなく 他大の人と懇親会などで関わる機会があります。技術力のある人、面白いアイディアを持っていた人など、同年代の様々な人と知り合えるのでとても刺激になります。
またハッカソンは企業が協賛していることが多く、企業の方に自分のプロダクトを見てもらったり、懇親会で話を伺うことができ、 進路を考えたりする上でも参考になります。また企業賞などを受賞をするとその後もランチのお誘いであったり、インターンの声をかけていただりもするので結構おいしいと思います…!

とにかく楽しい!

と言いつつ、個人的にハッカソンのいいところって友達とアイディアから実装まで、1日で作っちゃうお祭り感かなと思います。 毎回ハッカソンに出るときはほぼ徹夜になってしまうことも多いのですが、コーヒー、レッドブルと一緒にやお菓子と食べながらたまに冗談を言いながら開発したりするのは毎回とても楽しいです。

わたしのハッカソン体験談

私もそこまでたくさん出ているわけではないのですが、JPHacks 2016, 2017の東京大会と本選、またHackDay 2016にほぼ同じメンバーで出場しました。最初は学科に入ってすぐの時期にSlackで「ハッカソン出たい人募集」といった投稿を学科の同級生(今のチームメイト)がして、それに反応した5人くらいでチームを組みました。
ハッカソン一緒に出る友達がいない…」という声をたまに聞きますが、こんな感じで「とりあえず学科の人に声をかけてみる」「会場でぼっちの人とチームを組む」などもできると思うので、どんどん参加してみましょう( •̀ᄇ• ́)ﻭ✧

私は基本的に全てでクライアント(iOS)開発と、たまにちょっとデザインを触ったりしていました。 以下は過去のハッカソンで製作したものになります。

github.com

github.com

github.com

FreshFridge, Migaは二つとも全国規模の学生ハッカソンであるJPHacksの際に開発したものであり、 「家庭からの食品の廃棄を減らす」「夜道での女性を狙った犯罪を予防、被害を軽減する」など社会問題にフォーカスしたものになっています。
これは裏技(?)なのですが、「問題解決」を重視する大会では何らかの社会問題を重視したもの、「面白さ」を重視する大会ではネタに突っ走るなどある程度大会の趣旨とテーマを寄せると評価されやすいと思います。( •̀ᄇ• ́)ﻭ✧

FreshFridgeの時はほぼ初対面のメンバーで開発を始めたので最初は色々苦労したのですが、 色々なライブラリ、APIの活用やデバイスを用いたサービス開発をする中でとても多くの学びを得ることができました。ただgitの使い方で最初ミスをしまくったので事前にもっと勉強しておけばよかったなあと思います…
もしこれからハッカソンに参加しようと思っている人がいるなら本やサイトなどでチーム開発の仕方をマスターしておくとスムーズに開発できると思います。個人的には「GitHub実践入門」がわかりやすくておすすめです!

GitHub実践入門 ~Pull Requestによる開発の変革 (WEB+DB PRESS plus)

GitHub実践入門 ~Pull Requestによる開発の変革 (WEB+DB PRESS plus)

またMigaの時は逆にもう1年経ってよく知っているメンバーだけに、事前開発期間はあったのですがはあまり緊張感が持てず開発などはせず、 またテーマが迷走した結果、当日テーマ決めをしてようやく夕方から開発が開始できたので、とてもヒヤヒヤしました…
ちなみに前日時点でのテーマ決めはこんな感じでだいぶ迷走していました… f:id:akaringo030402:20171122135224j:plain

事前開発が可能な大会に出る時はちゃんと早めから準備をするといいと思います。

どちらも色々とトラブルはありましたが、結果的にFreshFridge, Migaとも全国大会に出場でき、いくつかのスポンサー賞やイノベーター認定をいただくことができました。

f:id:akaringo030402:20171122213202j:plain

テーマッテッダイジ…………

ハッカソンの紹介

ハッカソンの情報については毎年まとめてくださっている方がいるので、「ハッカソン 2017」とかでググると割とまとまった情報がゲットできると思います。またSPA JAMHackDayJPHacksなどは毎年開催しているので、公式サイトをこまめにチェックするといいと思います!

qiita.com

女子向けハッカソンの紹介

と言いつつ、こういったハッカソンっていわゆる「ガチプロ」が多くて最初は敷居が高く感じてしまいますよね…
個人的には女子向け/初心者向けハッカソンにまず出場してみて、ハッカソンってどんなものか体験してみるといいと思います。

私は東大Girlsハッカソンという、東大女子限定のハッカソンの運営に今年関わっていました。 スポンサーの方やメンターの方からの手厚いサポート、Progateなどのオンライン学習サービスの無料利用権などもあり、まだ開発経験がそこまで多くないけどハッカソン出てみたい!もっとプログラミング勉強してみたい! という方には本当にオススメです!

www.todaishimbun.org

大学以外にも、女性限定の開発コミュニティが主催する女性限定ハッカソン等もあるので、探してみるといいと思います!

さあとりあえずハッカソン出てみよう!

大規模ソフトウェア(Chromium)を手探る callbackハンドラを追加する・全体の感想

elechoくんのブログでChromeでWebUI Interfaceを追加するときの大まかな流れがわかったと思います。 Chromeに新しくWebUI Interfacesを追加するときの手順は公式に簡潔なガイドラインがあります。

www.chromium.org

Creating a Chrome WebUI interface is simple yet involves changing a number of files.

とあるように、ちょっとした画面(今回の場合は設定画面のセクション一つ)追加するにも割とたくさんのファイルを変更する必要があります… 知ってたらUIの大きな変更が必要な機能は追加しなかった気がする…...

このブログでは特にcallback Handkerを追加するときの手順にフォーカスして紹介したいと思います。 ユーザーがキーワードを設定したときにコールバック関数を読んでprefs::kRestrictedKeywordでストアされるキーワードの値を更新するためには、JavaScriptの世界(WebUI)からC++の世界(Chromeのコア)へ情報を送る必要があります。こういった場合、一番手っ取り早いのがcallback handllerを追加する方法です。 f:id:akaringo030402:20171025114952p:plain

AddRestrictedKeywordのためのcallbackハンドラを追加する

Chromeでcallbackハンドラを追加する手順は以下のようになります。

  1. src/chrome/browser/ui/webui/以下に新しくhandlerクラス(h, cppファイル)を追加する。
  2. MessageCallbackを登録し、JavaScriptで呼ばれる関数名と対応するC++プログラムでの関数名を決める
  3. 実際に呼ばれるC++プログラムの関数の動作を定義する
  4. 追加したハンドラを新しくビルドターゲットに追加する

1. 新しくRestrictedKeywordHandlerクラスを追加する。

まず新しくHandlerクラスをchrome/browser/ui/webui/settings/以下に作成します。 settings_restricted_keyword_pages_handler.hsettings_restricted_keyword_pages_handler.cppというファイルを追加しました。 まずは同じくwebui/settings/以下のsettings_startup_pages_handler.{h,cpp}を参考にそれっぽく書いて見ます。

  • settings_restricted_keyword_pages_handler.h
#ifndef CHROME_BROWSER_UI_WEBUI_SETTINGS_SETTINGS_RESTRICTED_KEYWORD_HANDLER_H_
#define CHROME_BROWSER_UI_WEBUI_SETTINGS_SETTINGS_RESTRICTED_KEYWORD_HANDLER_H_
#include "base/macros.h"
#include "chrome/browser/ui/webui/settings/custom_home_pages_table_model.h"
#include "chrome/browser/ui/webui/settings/settings_page_ui_handler.h"
#include "components/prefs/pref_change_registrar.h"
#include "ui/base/models/table_model_observer.h"

namespace base {
class ListValue;
}

namespace content {
class WebUI;
}

namespace settings {
// Chrome browser startup settings handler.
class RestrictedKeywordHandler : public SettingsPageUIHandler,
                            public ui::TableModelObserver {
 public:
  explicit RestrictedKeywordHandler(content::WebUI* webui);
  ~RestrictedKeywordHandler() override;

  // SettingsPageUIHandler:
  void RegisterMessages() override;
  void OnJavascriptAllowed() override;
  void OnJavascriptDisallowed() override;

  // ui::TableModelObserver:
  void OnModelChanged() override;
  void OnItemsChanged(int start, int length) override;
  void OnItemsAdded(int start, int length) override;
  void OnItemsRemoved(int start, int length) override;

 private:
  PrefChangeRegistrar pref_change_registrar_;
  CustomHomePagesTableModel restricted_custom_page_table_model_;
  DISALLOW_COPY_AND_ASSIGN(RestrictedKeywordHandler);
 };

} //namespace settings

#endif // CHROME_BROWSER_UI_WEBUI_SETTINGS_SETTINGS_RESTRICTED_KEYWORD_HANDLER_H_
  • settings_restricted_keyword_pages_handler.cpp
#include "chrome/browser/ui/webui/settings/settings_restricted_keyword_pages_handler.h"
#include <memory>
#include <string>
#include <utility>
#include <vector>
#include "chrome/browser/prefs/session_startup_pref.h"
#include "chrome/browser/profiles/profile.h"
#include "chrome/browser/ui/webui/settings_utils.h"
#include "chrome/common/pref_names.h"
#include "components/prefs/pref_service.h"
#include "content/public/browser/web_ui.h"
#include "url/gurl.h"

namespace settings {
RestrictedKeywordHandler::RestrictedKeywordHandler(content::WebUI* webui)
    : restricted_custom_page_table_model_(Profile::FromWebUI(webui)) {
}

RestrictedKeywordHandler::~RestrictedKeywordHandler() {
}

void RestrictedKeywordHandler::RegisterMessages() {
}

void RestrictedKeywordHandler::OnJavascriptAllowed() {
  restricted_custom_page_table_model_.SetObserver(this);
  PrefService* prefService = Profile::FromWebUI(web_ui())->GetPrefs();
  SessionStartupPref pref = SessionStartupPref::GetStartupPref(prefService);
  pref_change_registrar_.Init(prefService);
}

void RestrictedKeywordHandler::OnJavascriptDisallowed() {
  restricted_custom_page_table_model_.SetObserver(nullptr);
  pref_change_registrar_.RemoveAll();
}

void RestrictedKeywordHandler::OnModelChanged() {
  base::ListValue startup_pages;
  int page_count = restricted_custom_page_table_model_.RowCount();
  std::vector<GURL> urls = restricted_custom_page_table_model_.GetURLs();
  for (int i = 0; i < page_count; ++i) {
    std::unique_ptr<base::DictionaryValue> entry(new base::DictionaryValue());
    entry->SetString("title", restricted_custom_page_table_model_.GetText(i, 0));
    entry->SetString("url", urls[i].spec());
    entry->SetString("tooltip",
                     restricted_custom_page_table_model_.GetTooltip(i));
    entry->SetInteger("modelIndex", i);
    startup_pages.Append(std::move(entry));
  }
  FireWebUIListener("update-startup-pages", startup_pages);
}

void RestrictedKeywordHandler::OnItemsChanged(int start, int length) {
  OnModelChanged();
}

void RestrictedKeywordHandler::OnItemsAdded(int start, int length) {
  OnModelChanged();
}

void RestrictedKeywordHandler::OnItemsRemoved(int start, int length) {
  OnModelChanged();
}

} // namespace settings

2. callback関数を登録する。

C++で書かれた関数を名前と一緒にそれとなくregisterすることで、JavaScriptから指定した関数名で呼んであげればregisterした関数が呼ばれるようになります。また、その際にJavaScriptからcallbackを渡してあげれば、C++からそのcallbackを呼ぶことも可能です。
今回はprefs::kRestrictedKeywordを追加する関数setRestrictedKeyword、またユーザーが設定画面を開いた時に今の設定値を見えるようにJavaScriptに情報を渡すための関数getRestrictedKeywordを追加します。 メッセージコールバックの追加のためには、先ほど作成したsettings_restricted_keyword_pages_handler.cppRestrictedKeywordHandler::RegisterMessages()で登録を行います。

void RestrictedKeywordHandler::RegisterMessages() {
  if (Profile::FromWebUI(web_ui())->IsOffTheRecord())
    return;
  web_ui()->RegisterMessageCallback("addRestrictedKeyword",
                 base::Bind(&RestrictedKeywordHandler::HandleAddRestrictedKeyword,
                            base::Unretained(this)));
  web_ui()->RegisterMessageCallback("getRestrictedKeyword",
                            base::Bind(&RestrictedKeywordHandler::HandleGetRestrictedKeyword,
                                       base::Unretained(this)));
}

3. 実際に呼ばれる関数を宣言、定義する

登録した関数を実際に宣言、定義します。

  • settings_restricted_keyword_pages_handler.h
 public:
  explicit RestrictedKeywordHandler(content::WebUI* webui);
  ~RestrictedKeywordHandler() override;
  // 追加ここから
  void HandleAddRestrictedKeyword(const base::ListValue* args);
  void HandleGetRestrictedKeyword(const base::ListValue* args);
  std::string GetRestrictedKeyword(void);
  // 追加ここまで

cpp側で追加する関数を定義します。

  • settings_restricted_keyword_pages_handler.cpp
// 追加ここから
void RestrictedKeywordHandler::HandleAddRestrictedKeyword(const base::ListValue* args) {
  std::string pref_name;
  args->GetString(0, &pref_name);
  const base::Value* value;
  args->Get(1, &value);
  PrefService* prefs = Profile::FromWebUI(web_ui())->GetPrefs();
  prefs->SetString(prefs::kRestrictedKeyword, value->GetString());
}
void RestrictedKeywordHandler::HandleGetRestrictedKeyword(const base::ListValue* args) {
  CHECK_EQ(1U, args->GetSize());
  const base::Value* callback_id;
  CHECK(args->Get(0, &callback_id));
  AllowJavascript();
  ResolveJavascriptCallback(*callback_id, base::Value(GetRestrictedKeyword()));
}
std::string RestrictedKeywordHandler::GetRestrictedKeyword() {
  std::string RestrictedKeyword;
  PrefService* prefs = Profile::FromWebUI(web_ui())->GetPrefs();
  RestrictedKeyword = prefs->GetString(prefs::kRestrictedKeyword);
  return RestrictedKeyword;
}
// 追加ここまで

4. 追加したハンドラを新しくビルドターゲットに追加する

新しくsourcesを追加する時はgnファイルに追加したファイルへのパスを登録をする必要があります。 chrome/browser/ui/BUILD.gnファイルの他のsettings関連のハンドラが記述されている所の下に以下のように追加します。

      "webui/settings/settings_restricted_keyword_pages_handler.cc",
      "webui/settings/settings_restricted_keyword_pages_handler.h",

また、今回の変更の場合はこれだけでなく、SettingPagesHandlerとして新しく登録しないと正しくHandlerといて登録されないのでそちらも追加します。 chrome/browser/ui/webui/settings/md_settings_ui.ccを以下のように変更します。

// 変更ここから
#include "chrome/browser/ui/webui/settings/settings_restricted_keyword_pages_handler.h"
// 変更ここまで

MdSettingsUI::MdSettingsUI(content::WebUI* web_ui)
    : content::WebUIController(web_ui),
      WebContentsObserver(web_ui->GetWebContents()) {
  ...
  AddSettingsPageUIHandler(base::MakeUnique<OnStartupHandler>(profile));
  AddSettingsPageUIHandler(base::MakeUnique<PeopleHandler>(profile));
  AddSettingsPageUIHandler(base::MakeUnique<ProfileInfoHandler>(profile));
  AddSettingsPageUIHandler(base::MakeUnique<ProtocolHandlersHandler>());
  AddSettingsPageUIHandler(
      base::MakeUnique<SafeBrowsingHandler>(profile->GetPrefs()));
  AddSettingsPageUIHandler(base::MakeUnique<SearchEnginesHandler>(profile));
  AddSettingsPageUIHandler(base::MakeUnique<SiteSettingsHandler>(profile));
  AddSettingsPageUIHandler(base::MakeUnique<StartupPagesHandler>(web_ui));
  // 変更ここから
  AddSettingsPageUIHandler(base::MakeUnique<RestrictedKeywordHandler>(web_ui));
  // 変更ここまで
}

elechoくんの変更と合わせて、以上で設定画面から一つないし複数のキーワードを設定し、 検索ボックスにそれらの非表示キーワードを含む自動補完候補を表示させない機能の実装が完了しました!!

全体の感想

実装した機能自体はかなりネタ的に決めたものでした。

ですが手探るに当たって、Chromium Browserの大きな部品の一つであるOmniboxがどう実装されているのか、また自動補完のデータはどういうデータフローで供給されてきているのか、JavaScriptで記述されたWebUIとブラウザのコアの部分の間で情報がどうやり取りされているか、JavaScriptで呼ばれたcallback関数がC++側でどう実行されるかなど、多くのことを知ることができとても興味深かったです。

超大規模ソフトウェアならではの苦労も色々ありましたが(ビルドが終わらない、変更すべき箇所がどこかわからない等)、そういった経験もとても勉強になりました。

また私の適当な思いつきに付き合ってくれた同じチームのお二人にはとても感謝しています。本当に手探り状態でちゃんと期限内に終わるか不安だった時期もありましたが、二人と色々議論しながらこういう実装にしようここはこうしようと話すのがとても楽しかったです。

来年以降Chromiumを手探ってくれるEEICの後輩のみなさんは頑張ってください :)

大規模ソフトウェア(Chromium)を手探る user profileに設定を追加する

前回までのブログで任意のキーワードを含む検索結果に基づく自動補完を除くことができるようになりました。 今回はChromeのUI側で変更されたキーワードをuser profileで保存し、C++側のOmniboxの自動補完を行なっているクラスでこのデータを呼べるように変更します。
昨年(2016年度)の「大規模ソフトウェアを手探る」でChromiumを題材にしていた方がuser profileへの追加をした際のステップを丁寧に説明してくださっており、実装の際にとても参考になりました。

fizzy-yuya.hatenablog.com

Preferenceに表示したくないキーワードのデータを追加する

実際にキーワードフィルターをかける場合にはChromeの設定画面でユーザーのよって登録されたキーワードのデータを取ってきてフィルターをかける必要があります。ユーザーの登録したChromiumの設定はUser Profileに保存され、それぞれに固有のkey(pref_name)によって識別されます。

preferecesに任意の設定について追加したい場合には、

  1. PrefNamesクラスで新しく設定したいpreferenceのnameとデフォルト値を登録する。
  2. ProfileImplクラスのRegisterProfilePrefsd()という関数でこのpreferenceを登録する。

というステップでProfileにこの新しいpreferenceの値がストアされるようになり、PrefServiceを呼ぶことで、C++のプログラムから参照できるようになります。

詳しい説明は公式を参照してください。

まずchrome/common/pref_names.hに追加したいpreferenceの項目を追加します。今回はとりあえず全てのpreferenceの最後に新しくkRestrictedKeywordという項目を追加しました。

namespace prefs {
// Profile prefs. Please add Local State prefs below instead.
extern const char kChildAccountStatusKnown[];
...
// 変更ここから
extern const char kRestrictedKeyword[];
// 変更ここまで
}  // namespace prefs

これで宣言はできたので、cpp側でUI(JavaScript)側からこのpreferenceを参照する時に必要なpref_nameを登録します。ここに格納される値はデフォルト値ではなくてキーとして使われる識別子であることに注意してください。1

namespace prefs {
// *************** PROFILE PREFS ***************
// These are attached to the user profile
...
// 変更ここから
const char kRestrictedKeyword[] = "RestrictedKeyword";
// 変更ここまで
}  // namespace prefs

上のドキュメントにも書いてある通り、 pref_names.{h,cc}で定義された新たなpreferenceはchrome /browser/profiles/profile_impl.ccで登録される必要があります。

 // RegisterProfilePrefsd()というvoid関数でpreferenceの登録が行われている
void ProfileImpl::RegisterProfilePrefs(
    user_prefs::PrefRegistrySyncable* registry) {
  registry->RegisterBooleanPref(prefs::kSavingBrowserHistoryDisabled, false);
...
 // 変更ここから
  registry->RegisterStringPref(prefs::kRestrictedKeyword, std::string());
// 変更ここまで
}

デフォルトの値を設定したい場合にはRegisterStringPref()の二つ目の引数で設定ができ、例えばregistry->RegisterStringPref(prefs::kRestrictedKeyword, "foobarhoge");とすればユーザーによって制限したキーワードが設定されるまで、"foobarhoge"がkRestrictedKeywordのデフォルト値として、foobarhogeを含む検索結果が表示されないようになります。

これでuser profileに新しいpreferenceを追加することができたので、いよいよC++側からpreferenceの情報を取得して自動補完候補にフィルターをかける機能を実装しようと思います。

AutocompleteControllerからUser profileを参照する

ユーザーのpreferencesを取得するためには、PrefServiceをservice clientから呼ぶ必要があります。 前回のブログの実装では実質的に自動補完の候補をソートし、重複を除く関数であるSortAndDedup()というAutocompleteResultクラスの関数の中でフィルター機能を実装しました。

ただこの実装方法を用いると、AutocompleteResultクラスがservice clientに順ずるものにアクセスできないため、この関数を呼び出しているAutocompleteController側から何らかの方法でkRestrictedKeywordの情報を渡す必要があります。 AutocompleteControllerはSortAndCull()という関数を経由して間接的にSortAndDedup()関数を読んでいます。

SortAndCull()関数がconst string kRestrictedKeywordという引数を追加で取るように変更することも考えたのですが、Call Hierarchyをチェックしたところ 15 occurrencesだった(つまり15箇所で呼ばれている)ため、 全部変更するのちょっとめんどくさいな...ということで、新たにSortAndCullWithKeyword()という関数をAutocompleteResultクラスに追加し、keywordが存在する場合にはこちらの関数が呼ばれるように変更しました。

まず、関数の宣言をヘッダーファイルに追加します。

  void SortAndCull(const AutocompleteInput& input,
                   TemplateURLService* template_url_service);
  // 変更ここから
  void SortAndCullWithKeyword(const AutocompleteInput& input,
                              TemplateURLService* template_url_service,
                              const std::string& keyword);
  // 変更ここまで

次に、新たに追加したSortAndCullWithKeyword()をcppファイルで定義します。基本的にはオリジナルのSortAndCull()関数を内部で呼びつつ、 keywordに従ってフィルターをかけています。フィルターをかけるに当たって、入力文字列とマッチした自動補完候補のベクターであるmatchesの先頭がdefault_matchとして保持されていなくてはいけないので、最後にdefault_matchを設定し直しています。

// SortAndCull()関数の次にSortAndCullWithKeyword()関数を追加する。
// 変更ここから
void AutocompleteResult::SortAndCullWithKeyword(
    const AutocompleteInput& input,
    TemplateURLService* template_url_service,
    const std::string& keyword) {
  // デフォルトのSortAndCullを呼ぶ
  SortAndCull(input, template_url_service);

  // キーワードフィルターをかける
  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, keyword) == true) {
      itr = matches_.erase(itr);
    } else {
      itr++;
    }
  }

  // default_match_を設定し直す
  default_match_ = matches_.begin();
}
// 変更ここまで

最後に、AutocompleteController側からSortAndCullWIth()の代わりにSortAndCullWithKeyword()を呼び、preferencesにストアされているkRestrictedKeywordを渡すように書き換えます。

void AutocompleteController::UpdateResult(
    bool regenerate_result,
    bool force_notify_default_match_changed) {
  TRACE_EVENT0("omnibox", "AutocompleteController::UpdateResult");
  const bool last_default_was_valid = result_.default_match() != result_.end();
  // The following three variables are only set and used if
  // |last_default_was_valid|.
  base::string16 last_default_fill_into_edit, last_default_keyword,
      last_default_associated_keyword;
  if (last_default_was_valid) {
    last_default_fill_into_edit = result_.default_match()->fill_into_edit;
    last_default_keyword = result_.default_match()->keyword;
    if (result_.default_match()->associated_keyword) {
      last_default_associated_keyword =
          result_.default_match()->associated_keyword->keyword;
    }
  }

  if (regenerate_result)
    result_.Reset();

  AutocompleteResult last_result;
  last_result.Swap(&result_);

  for (Providers::const_iterator i(providers_.begin());
       i != providers_.end(); ++i)
    result_.AppendMatches(input_, (*i)->matches());

  // 変更ここから 
  PrefService* prefs = provider_client_->GetPrefs();
  const std::string keyword = prefs->GetString(prefs::kRestrictedKeyword);
  // 非表示キーワードが設定されていた時はSortAndCullWithKeyword()を、
  // そうでない時は通常のSortAndCull()を呼ぶ。
  if (keyword) {
    result_.SortAndCullWithKeyword(input_, template_url_service_, keyword);
  } else {
    result_.SortAndCull(input_, template_url_service_);
  }
  // 変更ここまで

これでuser profile preferenceからユーザが設定したキーワードの情報を読み込み、Omniboxの自動補完候補に出したくないものを単語でフィルタリングできるようになりました。やったね。

ただこれだと、単一のキーワードに対してのみしかフィルタリング機能を使えないことになります。やっぱり複数のキーワードに対してフィルタリング機能を使いたいよね、ということになったので、キーワードをカンマで区切られた文字列で渡してもらい、それをtokenizeして複数のキーワードに対してフィルター機能を実装をするようにしました。

// 変更ここから
// tokenizeを行う関数を追加する
std::vector<std::string> TokenizesKeywordsStringToKeywordsVec(
    const std::string& keyword) {
  std::vector<std::string> tokens;
  std::size_t start = 0, end = 0;
  while ((end = keyword.find(',', start)) != std::string::npos) {
    tokens.push_back(keyword.substr(start, end - start));
    start = end + 1;
  }
  tokens.push_back(keyword.substr(start));
  return tokens;
}

void AutocompleteResult::SortAndCullWithKeyword(
    const AutocompleteInput& input,
    TemplateURLService* template_url_service,
    const std::string& keyword) {
  SortAndCull(input, template_url_service);

  std::vector<std::string> tokens =
      TokenizesKeywordsStringToKeywordsVec(keyword);
  for (auto i = tokens.begin(); i != tokens.end(); i++) {
    LOG(INFO) << *i << ' ';
    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, *i) == true) {
        itr = matches_.erase(itr);
      } else {
        itr++;
      }
    }
  }
  default_match_ = matches_.begin();
}
// 変更ここまで

また、この実装だとまだ「完全に一致キーワードと一致する検索履歴」しかフィルターがかけられず、また特に英語の場合は大文字小文字の区別がされてしまって 結果的にフィルターがうまくかからないケースもありえます。 そこで最後に以下のように変更を加えました。 またついでにmatches_から消去して良いか、matchTypeから判別する部分についても関数として切り出し、Tokenizeを行う関数、全てのアルファベットの入力文字列を小文字化する関数とともに無名名前空間に入れます。

// 変更ここまで
namespace { 

base::string16 NormalizeRestrictedKeyword(std::string s) {
  return base::ToLowerASCII(base::UTF8ToUTF16(std::move(s)));
}

std::vector<base::string16> TokenizesKeywordsStringToKeywordsVec(
    const std::string& keyword) {

std::vector<std::string> TokenizesKeywordsStringToKeywordsVec(
    const std::string& keyword) {
  std::vector<base::string16> tokens;
  std::size_t start = 0, end;
  while ((end = keyword.find(',', start)) != std::string::npos) {
  std::vector<base::string16> tokens;
  std::size_t start = 0, end;
  while ((end = keyword.find(',', start)) != std::string::npos) {
    tokens.push_back(
        NormalizeRestrictedKeyword(keyword.substr(start, end - start)));
    start = end + 1;
  }

  tokens.push_back(NormalizeRestrictedKeyword(keyword.substr(start)));
  return tokens;
}

    
bool IsRemovableTypeFromMatch(AutocompleteMatchType::Type type) {
  return type == AutocompleteMatchType::HISTORY_TITLE ||
         type == AutocompleteMatchType::HISTORY_BODY ||
         type == AutocompleteMatchType::SEARCH_HISTORY ||
         type == AutocompleteMatchType::SEARCH_SUGGEST_TAIL;
}

}  // namespace

void AutocompleteResult::SortAndCullWithKeyword(
    const AutocompleteInput& input,
    TemplateURLService* template_url_service,
    const std::string& keyword) {
  std::vector<base::string16> restricted_keywords =
      TokenizesKeywordsStringToKeywordsVec(keyword);
  matches_.erase(
      std::remove_if(
          matches_.begin(), matches_.end(),
          [&restricted_keywords](const AutocompleteMatch& match) {
            bool removable = IsRemovableTypeFromMatch(match.type);
            if (removable) {
              base::string16 match_text = base::ToLowerASCII(match.contents);
              for (auto& restricted_keyword : restricted_keywords) {
                if (match_text.find(restricted_keyword) !=
                        base::string16::npos) {
                  return true;
                }
              }
            }
            return false;
          }),
      matches_.end());

  SortAndCull(input, template_url_service);
}
// 変更ここまで

ただこの変更を加えて実行してみると、キーワードフィルタリング自体はできるのですが、なぜか「キーワードと入力文字列が完全一致した時にcrashする」という現象が発生するようになります…なぜだ… まずは王道、crashした時のback traceをみてみます。

Check failed: input.text().empty() != default_match_->
    allowed_to_be_default_match (0 vs. 0)fill_into_edit=ポケモンgo, provider=Search, input=pokemongo
#0 0x7f6fac40677d base::debug::StackTrace::StackTrace()
#1 0x7f6fac404b4c base::debug::StackTrace::StackTrace()
#2 0x7f6fac4962ba logging::LogMessage::~LogMessage()
#3 0x558c51544aee AutocompleteResult::SortAndCull()
#4 0x558c51540e13 AutocompleteResult::CopyOldMatches()
#5 0x558c538379e0 AutocompleteController::UpdateResult()
#6 0x558c53836882 AutocompleteController::Start()

この時はOmniboxの入力している最中に落ちているのでinput.text().empty() == falseとなっています。
そのため、本来ならばdefault_match_-> allowed_to_be_default_match == trueにならなくてはいのですが
default_match_->allowed_to_be_default_match == falseになっているためにDCHECK()で落ちているようです。 この謎のdefault_match_allowed_to_be_default_matchについて、少し調べてみます。

default_match_とallowed_to_be_default_matchについて調べる

default_matchについて、AutocompleteResultクラスには特にコメント等で詳細な記述がないため、 default_matchはAutocompleteMatchというクラスのインスタンスになるため、このクラスを定義するautocomplete_match.cppファイルでallowed_to_be_default_matchについての めぼしい記述がないか探してみます。 するとallowed_to_be_default_matchについて以下のような記述を発見しました。

  // If false, the omnibox should prevent this match from being the
  // default match.  Providers should set this to true only if the
  // user's input, plus any inline autocompletion on this match, would
  // lead the user to expect a navigation to this match's destination.
  // For example, with input "foo", a search for "bar" or navigation
  // to "bar.com" should not set this flag; a navigation to "foo.com"
  // should only set this flag if ".com" will be inline autocompleted;
  // and a navigation to "foo/" (an intranet host) or search for "foo"
  // should set this flag.
  bool allowed_to_be_default_match;

allowed_to_be_default_matchは様々なProviderから返される自動補完候補に対して、それがdefault_matchになりうるかなり得ないかを表しているようです。 またallowed_to_be_default_match == trueになるのは、ユーザーの入力そのもの、もしくは入力に対しインライン自動補完を加えた候補に対してのみらしいですね。 そのためfooとユーザーが入力する時にbarbar.comdefault_matchにはなり得ないものの、 foo.comfoodefault_matchとなり得るようです。

つまり、先ほどのバグの原因は
「入力文字列と表示されたくないキーワードが完全に一致するもしくは入力文字列がキーワードを含む時、ユーザーの入力をそのまま候補としてサジェストするmatch(基本的にはこれが一番優先度の高いautocomplete_matchとしてdefault_match_にセットされている)がキーワードフィルタリングによって除かれる。その結果、優先度が二番目以降の候補がSortAndCull()が呼ばれた後default_match_にセットされるが、優先度が二番目以降の候補はallowed_to_be_default_match == trueとなる条件を満たしていないことが多いため2、クラッシュする」
ことだったようです。
元々「Search For...」と呼ばれる、ユーザーの文字列をそのまま検索候補として表示するものについてはbool IsRemovableTypeFromMatch(AutocompleteMatchType::Type type)関数でチェックをかけ、除去されないようにしていたはずでした。
しかし、おそらく同じキーワードの候補重複を排除する際に、他のProviderから返される別の候補で上書きされた結果除去されてしまったようです。

そこで入力文字列と一致する自動補完候補についてはmatches_から除去しないよう、以下のようにコードを修正しました。

// 変更ここから
namespace {
base::string16 NormalizeRestrictedKeyword(std::string s) {
  return base::ToLowerASCII(base::UTF8ToUTF16(std::move(s)));
}

std::vector<base::string16> TokenizesKeywordsStringToKeywordsVec(
    const std::string& keyword) {
  std::vector<base::string16> tokens;
  std::size_t start = 0, end;
  while ((end = keyword.find(',', start)) != std::string::npos) {
  std::vector<base::string16> tokens;
  std::size_t start = 0, end;
  while ((end = keyword.find(',', start)) != std::string::npos) {
    tokens.push_back(
        NormalizeRestrictedKeyword(keyword.substr(start, end - start)));
    start = end + 1;
  }

  tokens.push_back(NormalizeRestrictedKeyword(keyword.substr(start)));
  return tokens;
}

    
bool IsRemovableTypeFromMatch(AutocompleteMatchType::Type type) {
  return type == AutocompleteMatchType::HISTORY_TITLE ||
         type == AutocompleteMatchType::HISTORY_BODY ||
         type == AutocompleteMatchType::SEARCH_HISTORY ||
         type == AutocompleteMatchType::SEARCH_SUGGEST_TAIL;
}

}  // namespace

void AutocompleteResult::SortAndCullWithKeyword(
    const AutocompleteInput& input,
    TemplateURLService* template_url_service,
    const std::string& keyword) {
  std::vector<base::string16> restricted_keywords =
      TokenizesKeywordsStringToKeywordsVec(keyword);
  const base::string16& input_text = input.text();
 // ラムダ式にOmniboxの入力ボックス内の文字列 input_textも一緒に渡す
  matches_.erase(
      std::remove_if(
          matches_.begin(), matches_.end(),
          [&restricted_keywords, &input_text](const AutocompleteMatch& match) {
            bool removable = IsRemovableTypeFromMatch(match.type);
            if (removable) {
              base::string16 match_text = base::ToLowerASCII(match.contents);
              for (auto& restricted_keyword : restricted_keywords) {
                // Omniboxの入力文字列と一致しないかつ表示したくないキーワードを含む検索候補を除くように書き換える。
                if (input_text != match_text &&
                    match_text.find(restricted_keyword) !=
                        base::string16::npos) {
                  return true;
                }
              }
            }
            return false;
          }),
      matches_.end());

  SortAndCull(input, template_url_service);
}
// 変更ここまで

これでユーザーの設定した複数キーワードに対しての検索履歴のフィルタリング機能の実装が完了しました。 あとはこのキーワードを設定する設定画面の追加及びJavaScriptの世界とC++の世界の間で情報をやり取りするためのHandlerクラスの追加等を行う必要があります。 これは次回以降のブログでまた説明します。

フィルタリング部分の変更まとめ

これまでに行なって変更を一覧にして載せておきます。

  • components/omnibox/browser/autocomplete_result.h
// 変更ここから
  void SortAndCullWithKeyword(const AutocompleteInput& input,
                              TemplateURLService* template_url_service,
                              const std::string& keyword);
// 変更ここまで
  • components/omnibox/browser/autocomplete_result.cpp
// 変更ここから
namespace {
base::string16 NormalizeRestrictedKeyword(std::string s) {
  return base::ToLowerASCII(base::UTF8ToUTF16(std::move(s)));
}

std::vector<base::string16> TokenizesKeywordsStringToKeywordsVec(
    const std::string& keyword) {
  std::vector<base::string16> tokens;
  std::size_t start = 0, end;
  while ((end = keyword.find(',', start)) != std::string::npos) {
  std::vector<base::string16> tokens;
  std::size_t start = 0, end;
  while ((end = keyword.find(',', start)) != std::string::npos) {
    tokens.push_back(
        NormalizeRestrictedKeyword(keyword.substr(start, end - start)));
    start = end + 1;
  }

  tokens.push_back(NormalizeRestrictedKeyword(keyword.substr(start)));
  return tokens;
}

    
bool IsRemovableTypeFromMatch(AutocompleteMatchType::Type type) {
  return type == AutocompleteMatchType::HISTORY_TITLE ||
         type == AutocompleteMatchType::HISTORY_BODY ||
         type == AutocompleteMatchType::SEARCH_HISTORY ||
         type == AutocompleteMatchType::SEARCH_SUGGEST_TAIL;
}

}  // namespace

void AutocompleteResult::SortAndCullWithKeyword(
    const AutocompleteInput& input,
    TemplateURLService* template_url_service,
    const std::string& keyword) {
  std::vector<base::string16> restricted_keywords =
      TokenizesKeywordsStringToKeywordsVec(keyword);
  const base::string16& input_text = input.text();
  matches_.erase(
      std::remove_if(
          matches_.begin(), matches_.end(),
          [&restricted_keywords, &input_text](const AutocompleteMatch& match) {
            bool removable = IsRemovableTypeFromMatch(match.type);
            if (removable) {
              base::string16 match_text = base::ToLowerASCII(match.contents);
              for (auto& restricted_keyword : restricted_keywords) {
                if (input_text != match_text &&
                    match_text.find(restricted_keyword) !=
                        base::string16::npos) {
                  return true;
                }
              }
            }
            return false;
          }),
      matches_.end());

  SortAndCull(input, template_url_service);
}
// 変更ここまで
namespace prefs {
...
// 変更ここから
extern const char kRestrictedKeyword[];
// 変更ここまで
}  // namespace prefs
  • chrome/common/pref_names.cpp
namespace prefs {
...
// 変更ここから
const char kRestrictedKeyword[] = "RestrictedKeyword";
// 変更ここまで
}  // namespace prefs
  • chrome/browser/profiles/profile_impl.cc
void ProfileImpl::RegisterProfilePrefs(
    user_prefs::PrefRegistrySyncable* registry) {
...
 // 変更ここから
  registry->RegisterStringPref(prefs::kRestrictedKeyword, std::string());
// 変更ここまで
}

  1. 頭の悪い人なので、最初ここにデフォルト値を設定しているんだと思っていました……

  2. (上の例で言うポケモンGOは意味的にはpokemongoと同値であっても、文字列としてはユーザーの入力と一致しないためdefault_matchとはなり得ない)