Comparar requisições com regras
Por que isso importa Um bloqueador confere cada requisição que uma página faz, muitas vezes mais de cem por página, contra dezenas de milhares de regras. Se essa conferência for lenta, toda página parece lenta, e as pessoas desligam o bloqueador. Rápido e correto é o que torna a proteção usável.
Dois trabalhos: a resposta certa, rápido
Pense numa biblioteca com 5.000 livros. Para achar um, você não leria cada lombada a partir da primeira estante. Você vai até a seção certa, depois até a prateleira certa. Um bloqueador deveria fazer o mesmo: pular direto para as poucas regras que poderiam corresponder e conferir só essas.
Este exercício é avaliado nas duas coisas. Os testes contam quantas vezes o seu decide chama rule_matches para uma requisição, e o orçamento é de 20 verificações com 5.000 regras carregadas. Contamos verificações em vez de cronometrar você, então um celular lento e um notebook rápido são avaliados do mesmo jeito.
Passo 1: curingas
Curinga: um símbolo que representa "quaisquer caracteres". Nas listas de filtros é o *, então /beacon/*/hit corresponde a /beacon/42/hit e a /beacon/abc/hit.
Divida o padrão em cada * e depois encontre os pedaços no texto, em ordem, cada um depois do anterior:
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 -> Falsetext.find(piece, pos) retorna onde piece começa, procurando só a partir da posição pos, ou -1 se não estiver lá. Repare que, nas listas de filtros, ? e . são caracteres comuns, então não use uma expressão regular nem fnmatch, que os tratam como especiais.
Passo 2: uma regra contra uma requisição
rule_matches(rule, url, third_party) responde sim ou não para uma regra:
- Uma regra com
third_partydefinido nunca corresponde a uma requisição de primeira parte. - Uma regra de domínio
adco.examplecorresponde ao hostadco.exampleou a qualquer host que termine em.adco.example. O ponto importa:notadco.exampleé outra pessoa. - Uma regra de padrão corresponde quando
wildcard_in(value, url.lower())é verdadeiro.
Passo 3: um índice, para conferir só algumas regras
Índice: uma estrutura construída uma vez que permite encontrar coisas sem procurar em tudo, como o índice no fim de um livro. Aqui: um dict do nome do host para as regras daquele host.
Um dict do Python encontra uma chave num único passo, não importa quantas chaves ele tenha. Então construa, uma vez:
index = {"domains": {"adco.example": [rule, ...], ...},
"patterns": [rule, rule, ...]}Para uma requisição a img.adco.example, procure cada terminação do host: img.adco.example, adco.example, example. São três consultas em vez de 5.000 verificações. Adicione as poucas regras de padrão (bloqueadores reais também as indexam, por um pedacinho de texto que elas precisam conter; nós as mantemos numa lista simples).
Passo 4: decidir, com as exceções vencendo
Confira cada candidata. Se alguma regra que corresponde for uma exceção, a resposta é "allow", e ponto final. Senão, se alguma regra de bloqueio correspondeu, "block"; se nada correspondeu, "allow". As exceções existem porque as listas às vezes pegam coisas de que um site realmente precisa, como cdn.example, que serve uma biblioteca inofensiva.
Um equívoco comum
"Mais regras significa um bloqueador mais lento." Com um bom índice, não: procurar um host num dict custa mais ou menos o mesmo com 50 regras ou com 50.000. O que deixa um bloqueador lento é conferir as regras uma por uma.
Experimente Depois de passar, mude decide para percorrer todas as regras da lista (sem índice) e rode os testes de novo. O teste de orçamento falha com uma contagem de cerca de 5.000. Esse número é o trabalho que o seu índice economiza em cada requisição de cada página.
Em outras linguagens
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
}Resumo
- Padrões com curinga: divida em
*e encontre os pedaços em ordem. - Regras de domínio correspondem ao host ou a qualquer subdomínio, comparando rótulo por rótulo.
- Um índice (um dict por host) significa poucas consultas em vez de milhares de verificações.
- Uma exceção que corresponde sempre vence uma regra de bloqueio.
Escreva quatro funções. wildcard_in(pattern, text): True quando os pedaços de pattern entre os sinais * aparecem todos em text, em ordem. rule_matches(rule, url, third_party): True quando um dict de regra (da lição anterior) corresponde à requisição. build_index(rules): organize as regras do jeito que quiser, para que decide possa pular a maioria delas. decide(index, url, third_party): retorne "block" ou "allow", com qualquer exceção que corresponda vencendo, chamando rule_matches no máximo 20 vezes por requisição quando 5.000 regras estão carregadas.
Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição
Este exercício abre em breve
Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.
Este navegador está bloqueando cookies para learn.floati.life, então as lições que você terminou aqui não podem abrir em ordem. Permita cookies para este site e recarregue.