シラバス レッスン 156 中 47 · ブロッカーを作る
ブロッカーを作る

リクエストを規則と照合する

なぜ大切か ブロッカーは、ページがするすべてのリクエスト、しばしば 1 ページで 100 以上を、何万もの規則と照らし合わせます。その確認が遅ければ、どのページも遅く感じられ、人はブロッカーをオフにします。速くて正しいことが、守りを使えるものにします。

2 つの仕事:正しい答えを、素早く

5,000 冊の本がある図書館を考えてください。1 冊を探すのに、最初の棚から背表紙をすべて読んだりはしません。正しい区画へ、それから正しい棚へ行きます。ブロッカーも同じことをすべきです。一致 しうる 少数の規則にまっすぐ飛び、それだけを確かめます。

この演習は両方で採点されます。テストは、ひとつのリクエストについて decide が rule_matches を何回呼ぶかを数え、5,000 の規則を読み込んだときの予算は 20 回の確認 です。時間を測る代わりに確認を数えるので、遅い電話も速いノートパソコンも同じように採点されます。

手順 1:ワイルドカード

ワイルドカード:「任意の文字」を表す記号です。フィルターの一覧では * なので、/beacon/*/hit は /beacon/42/hit にも /beacon/abc/hit にも一致します。

パターンを各 * で分割し、それから断片をテキストの中で、順に、それぞれ前のものの後ろで見つけます:

wildcard_in("*/collect?*cid=", "https://m.example/collect?x=1&cid=9")
# pieces: "/collect?" then "cid="  -> both found, in order -> True

wildcard_in("a*b", "b then a")
# "a" found at position 7, then no "b" after it -> False

text.find(piece, pos) は、位置 pos からだけ探して piece が始まる所を、なければ -1 を返します。フィルターの一覧では ? と . はふつうの文字なので、それを特別扱いする正規表現や fnmatch は使わないでください。

手順 2:ひとつの規則とひとつのリクエスト

rule_matches(rule, url, third_party) は、ひとつの規則についてはいかいいえで答えます:

  • third_party が設定された規則は、ファーストパーティのリクエストには決して一致しません。
  • ドメインの規則 adco.example は、ホスト adco.example か、.adco.example で終わる任意のホストに一致します。ドットが大事です。notadco.example は別の誰かです。
  • パターンの規則は、wildcard_in(value, url.lower()) が真のときに一致します。

手順 3:索引で、少数の規則だけを確かめる

索引:一度作れば、すべてを探さずに物を見つけられる構造で、本の後ろの索引のようなものです。ここでは、ホスト名からそのホストの規則への辞書です。

Python の辞書は、キーをいくつ持っていても、1 回の手順でキーを見つけます。だから一度だけ、これを作ります:

index = {"domains": {"adco.example": [rule, ...], ...},
         "patterns": [rule, rule, ...]}

img.adco.example へのリクエストなら、ホストのすべての末尾を引きます:img.adco.example、adco.example、example。5,000 回の確認の代わりに 3 回の検索です。少数のパターンの規則を加えます(本物のブロッカーは、それが含まなければならない短いテキストでそれも索引にしますが、ここではただのリストに保ちます)。

手順 4:決める、例外が勝つ

各候補を確かめます。一致する規則のどれかが例外なら、答えは "allow" で、それで終わりです。そうでなければ、ブロックの規則が一致すれば "block"、何も一致しなければ "allow" です。例外があるのは、無害なライブラリを配る cdn.example のような、サイトが本当に必要とするものを一覧がときどき捕まえてしまうからです。

よくある誤解

「規則が多いほどブロッカーは遅くなる」。良い索引があれば、そうはなりません。辞書でホストを引く費用は、規則が 50 でも 50,000 でもほぼ同じです。ブロッカーを遅くするのは、規則をひとつずつ確かめることです。

試してみよう 合格したら、decide を一覧のすべての規則をループするように(索引なしで)変え、もう一度テストを実行してください。予算のテストが、およそ 5,000 回という数で失敗します。その数が、どのページのどのリクエストでも索引が節約している仕事です。

ほかの言語では

JavaScript:

function wildcardIn(pattern, text) {
  let pos = 0;
  for (const piece of pattern.split("*")) {
    if (!piece) continue;
    const at = text.indexOf(piece, pos);
    if (at === -1) return false;
    pos = at + piece.length;
  }
  return true;
}

// Index: a Map from host to rules; look up each ending of the host.
function candidates(index, host) {
  const parts = host.split(".");
  const out = [];
  for (let i = 0; i < parts.length; i++) {
    out.push(...(index.domains.get(parts.slice(i).join(".")) || []));
  }
  return out.concat(index.patterns);
}

Go:

func wildcardIn(pattern, text string) bool {
    pos := 0
    for _, piece := range strings.Split(pattern, "*") {
        if piece == "" {
            continue
        }
        at := strings.Index(text[pos:], piece)
        if at < 0 {
            return false
        }
        pos += at + len(piece)
    }
    return true
}

まとめ

  • ワイルドカードのパターン:* で分割し、断片を順に見つけます。
  • ドメインの規則は、ホストか任意のサブドメインに、ラベル単位で比べて一致します。
  • 索引(ホストごとの辞書)があれば、何千回もの確認の代わりに少数の検索で済みます。
  • 一致する例外は、常にブロックの規則に勝ちます。
あなたの番

4 つの関数を書いてください。wildcard_in(pattern, text):* の記号の間の pattern の断片がすべて text に順に現れるとき True。rule_matches(rule, url, third_party):(前のレッスンの)規則の辞書ひとつがリクエストに一致するとき True。build_index(rules):decide がそのほとんどを飛ばせるよう、規則を好きなように整理します。decide(index, url, third_party):一致する例外が勝つようにして "block" か "allow" を返し、5,000 の規則を読み込んだとき、リクエストごとに rule_matches を最大 20 回呼びます。

このレッスンに問題を見つけましたか?報告する · このレッスンについて質問する

この演習はまもなく開きます

その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。