Comparar las peticiones con las reglas
Por qué importa Un bloqueador comprueba cada una de las peticiones que hace una página, a menudo más de cien por página, contra decenas de miles de reglas. Si esa comprobación es lenta, todas las páginas se sienten lentas, y la gente desactiva el bloqueador. Rápido y correcto es lo que hace que la protección se pueda usar.
Dos tareas: la respuesta correcta, y rápido
Piensa en una biblioteca con 5.000 libros. Para encontrar uno, no leerías todos los lomos desde la primera estantería. Vas a la sección correcta y luego a la estantería correcta. Un bloqueador debería hacer lo mismo: saltar directamente a las pocas reglas que podrían coincidir, y comprobar solo esas.
Este ejercicio se corrige por las dos cosas. Las pruebas cuentan cuántas veces tu decide llama a rule_matches para una petición, y el límite es de 20 comprobaciones con 5.000 reglas cargadas. Contamos comprobaciones en lugar de cronometrarte, así que un teléfono lento y un portátil rápido se corrigen igual.
Paso 1: los comodines
Comodín: un símbolo que representa "cualquier carácter". En las listas de filtros es *, así que /beacon/*/hit coincide con /beacon/42/hit y con /beacon/abc/hit.
Divide el patrón en cada * y luego busca los trozos en el texto, en orden, cada uno después del 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) devuelve dónde empieza piece, buscando solo a partir de la posición pos, o -1 si no está. Ten en cuenta que en las listas de filtros ? y . son caracteres normales, así que no uses una expresión regular ni fnmatch, que los tratan como especiales.
Paso 2: una regla contra una petición
rule_matches(rule, url, third_party) responde sí o no para una regla:
- Una regla con
third_partyactivado nunca coincide con una petición propia. - Una regla de dominio
adco.examplecoincide con el hostadco.exampleo con cualquier host que termine en.adco.example. El punto importa:notadco.examplees otra persona. - Una regla de patrón coincide cuando
wildcard_in(value, url.lower())es verdadero.
Paso 3: un índice, para comprobar solo unas pocas reglas
Índice: una estructura que se construye una vez y que te permite encontrar cosas sin buscar en todo, como el índice al final de un libro. Aquí: un diccionario que va del nombre del host a las reglas de ese host.
Un diccionario de Python encuentra una clave en un solo paso, tenga las claves que tenga. Así que construye, una vez:
index = {"domains": {"adco.example": [rule, ...], ...},
"patterns": [rule, rule, ...]}Para una petición a img.adco.example, busca todas las terminaciones del host: img.adco.example, adco.example, example. Son tres búsquedas en lugar de 5.000 comprobaciones. Añade las pocas reglas de patrón (los bloqueadores reales también las indexan, por un trozo corto de texto que deben contener; nosotros las guardamos en una lista normal).
Paso 4: decidir, con las excepciones ganando
Comprueba cada candidata. Si alguna regla que coincide es una excepción, la respuesta es "allow", y punto. Si no, si coincidió alguna regla de bloqueo, "block"; si no coincidió nada, "allow". Las excepciones existen porque las listas a veces atrapan cosas que un sitio necesita de verdad, como cdn.example, que sirve una biblioteca inofensiva.
Una idea equivocada muy común
"Más reglas significa un bloqueador más lento." Con un buen índice, no: buscar un host en un diccionario cuesta más o menos lo mismo con 50 reglas que con 50.000. Lo que hace lento a un bloqueador es comprobar las reglas una a una.
Pruébalo Cuando pases, cambia decide para que recorra todas las reglas de la lista (sin índice) y vuelve a ejecutar las pruebas. La prueba del límite falla con una cuenta de unas 5.000. Ese número es el trabajo que tu índice ahorra en cada petición de cada página.
En otros lenguajes
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
}Resumen
- Patrones con comodines: divide en
*y busca los trozos en orden. - Las reglas de dominio coinciden con el host o con cualquier subdominio, comparando etiqueta a etiqueta.
- Un índice (un diccionario por host) significa unas pocas búsquedas en lugar de miles de comprobaciones.
- Una excepción que coincide siempre gana a una regla de bloqueo.
Escribe cuatro funciones. wildcard_in(pattern, text): True cuando todos los trozos de pattern entre los signos * aparecen en text en orden. rule_matches(rule, url, third_party): True cuando un diccionario de regla (de la lección anterior) coincide con la petición. build_index(rules): organiza las reglas como quieras para que decide pueda saltarse la mayoría. decide(index, url, third_party): devuelve "block" o "allow", con cualquier excepción que coincida ganando, llamando a rule_matches como mucho 20 veces por petición cuando hay 5.000 reglas cargadas.
¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección
Este ejercicio se abre pronto
Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.
Este navegador está bloqueando las cookies de learn.floati.life, así que las lecciones que terminaste aquí no se pueden abrir en orden. Permite las cookies de este sitio y recarga.