Temario Lección 47 de 156 · Construye un bloqueador
Construye un bloqueador

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 -> False

text.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_party activado nunca coincide con una petición propia.
  • Una regla de dominio adco.example coincide con el host adco.example o con cualquier host que termine en .adco.example. El punto importa: notadco.example es 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.
Tu turno

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.