Match requests against rules

Two jobs: right answer, quickly

Think of a library with 5,000 books. To find one, you would not read every spine from the first shelf. You go to the right section, then the right shelf. A blocker should do the same: jump straight to the few rules that could match, and check only those.

This exercise is graded on both. The tests count how many times your decide calls rule_matches for one request, and the budget is 20 checks with 5,000 rules loaded. We count checks instead of timing you, so a slow phone and a fast laptop are graded the same way.

Step 1: wildcards

Split the pattern at each *, then find the pieces in the text, in order, each one after the last:

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) returns where piece starts, looking only from position pos, or -1 if it is not there. Note that in filter lists ? and . are ordinary characters, so do not use a regular expression or fnmatch, which treat them as special.

Step 2: one rule against one request

rule_matches(rule, url, third_party) answers yes or no for one rule:

• A rule with third_party set never matches a first-party request.
• A domain rule adco.example matches the host adco.example or any host ending in .adco.example. The dot matters: notadco.example is someone else.
• A pattern rule matches when wildcard_in(value, url.lower()) is true.

Step 3: an index, so you check only a few rules

A Python dict finds a key in one step, however many keys it holds. So build, once:

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

For a request to img.adco.example, look up every ending of the host: img.adco.example, adco.example, example. That is three look-ups instead of 5,000 checks. Add the few pattern rules (real blockers index those too, by a short piece of text they must contain; we keep them in a plain list).

Step 4: decide, with exceptions winning

Check each candidate. If any matching rule is an exception, the answer is "allow", full stop. Otherwise, if any block rule matched, "block"; if nothing matched, "allow". Exceptions exist because lists sometimes catch things a site truly needs, such as cdn.example, which serves a harmless library.

A common misconception

"More rules means a slower blocker." With a good index, no: looking up a host in a dict costs about the same with 50 rules or 50,000. What slows a blocker down is checking rules one by one.

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);
}

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
}