Skip to content

Lightpanda: the headless browser designed for AI and automation

16.4 KB
Raw Blame
// Copyright (C) 2023-2026 Lightpanda (Selecy SAS)
//
// Francis Bouvier <[email protected]>
// Pierre Tachoire <[email protected]>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

//! Matching of a filter's URL pattern, once the type, party and `$domain=`
//! constraints have already passed. Everything here works on a lowercased,
//! fragment-stripped URL; `$match-case` only survives on /regex/ filters,
//! which never reach this file.

const std = @import("std");

const NetworkFilter = @import("NetworkFilter.zig");

/// The URL a request is matched against, with its hostname located once so
/// every filter can reuse the offsets.
pub const Url = struct {
    /// Lowercased, fragment stripped: what patterns, stored lowercased, walk.
    text: []const u8,
    /// Fragment stripped, case kept: what a regex reads, since `$match-case`
    /// is only meaningful on the original.
    raw: []const u8,
    host_start: u32,
    host_end: u32,

    pub fn hostname(self: Url) []const u8 {
        return self.text[self.host_start..self.host_end];
    }

    /// Locates the hostname inside `url`: after "scheme://", up to the port,
    /// path, query or end. Offsets, not a slice, because the matcher needs to
    /// resume the pattern right where the hostname stops.
    pub fn init(url: []const u8, raw: []const u8) Url {
        var start: usize = 0;
        if (std.mem.find(u8, url, "://")) |scheme| start = scheme + 3;

        var end = url.len;
        for (url[start..], start..) |c, i| {
            switch (c) {
                '/', '?', '#' => {
                    end = i;
                    break;
                },
                else => {},
            }
        }

        // "user:password@host"
        if (std.mem.findScalarLast(u8, url[start..end], '@')) |at| {
            start += at + 1;
        }

        // A ':' before the path is a port, unless we are inside an IPv6
        // literal's brackets.
        const host = url[start..end];
        var host_end = end;
        if (host.len > 0 and host[0] == '[') {
            if (std.mem.findScalar(u8, host, ']')) |close| {
                host_end = start + close + 1;
            }
        } else if (std.mem.findScalar(u8, host, ':')) |colon| {
            host_end = start + colon;
        }

        return .{
            .text = url,
            .raw = raw,
            .host_start = @intCast(start),
            .host_end = @intCast(host_end),
        };
    }
};

/// Whether `filter`'s pattern matches `url`. Only the pattern: the caller has
/// already decided the filter applies to this request.
pub fn matches(filter: *const NetworkFilter, url: Url) bool {
    switch (filter.kind) {
        // Option-only filters ("$script,domain=x") match any URL.
        .any => return true,
        // uBO tests the raw URL; the case-insensitive flag is on the pattern.
        .regex => return filter.regex.?.matches(url.raw),
        .hostname, .plain, .wildcard => {},
    }

    if (filter.hostname.len != 0) {
        var from: usize = 0;
        while (hostAnchor(url, filter.hostname, from)) |at| {
            if (filter.kind == .hostname) {
                const boundary = at == url.host_end or url.text[at] == '.' or
                    filter.hostname[filter.hostname.len - 1] == '.';
                if (boundary) {
                    if (!filter.require_separator) return true;
                    if (at == url.text.len) return true;
                    // `||host^|` pins the separator to the end of the URL.
                    if (isSeparator(url.text[at]) and
                        (!filter.right_anchor or at + 1 == url.text.len))
                    {
                        return true;
                    }
                }
            } else if (matchFrom(filter, url.text, at, filter.right_anchor)) {
                return true;
            }
            // The label this attempt started on cannot match again.
            from = at - filter.hostname.len - url.host_start + 1;
        }
        return false;
    }

    if (filter.hostname_anchor) {
        var i: usize = url.host_start;
        while (true) {
            if (matchFrom(filter, url.text, i, filter.right_anchor)) return true;
            const dot = std.mem.findScalarPos(u8, url.text[0..url.host_end], i, '.') orelse
                return false;
            i = dot + 1;
        }
    }

    if (filter.left_anchor) {
        return matchFrom(filter, url.text, 0, filter.right_anchor);
    }
    if (filter.kind == .plain) {
        if (filter.right_anchor) return std.mem.endsWith(u8, url.text, filter.pattern);
        return std.mem.find(u8, url.text, filter.pattern) != null;
    }

    var i: usize = 0;
    while (i <= url.text.len) : (i += 1) {
        if (matchFrom(filter, url.text, i, filter.right_anchor)) return true;
    }
    return false;
}

/// Finds `needle` starting on a label boundary of the request hostname at or
/// after `from` (an offset into the hostname), and returns the offset just
/// past it in the whole URL.
fn hostAnchor(url: Url, needle: []const u8, from: usize) ?usize {
    const host = url.hostname();
    var p = from;
    while (p <= host.len) {
        if (p == 0 or host[p - 1] == '.') {
            if (std.mem.startsWith(u8, host[p..], needle)) {
                return url.host_start + p + needle.len;
            }
        }
        const dot = std.mem.findScalarPos(u8, host, p, '.') orelse return null;
        p = dot + 1;
    }
    return null;
}

/// Matches the pattern starting exactly at `start`. `anchor_end` additionally
/// requires it to run to the end of the URL.
fn matchFrom(filter: *const NetworkFilter, url: []const u8, start: usize, anchor_end: bool) bool {
    if (filter.kind == .plain) {
        // No '*' and no '^': a byte comparison is the whole job.
        if (start + filter.pattern.len > url.len) return false;
        if (!std.mem.startsWith(u8, url[start..], filter.pattern)) return false;
        return !anchor_end or start + filter.pattern.len == url.len;
    }

    var it = std.mem.splitScalar(u8, filter.pattern, '*');
    var pos = matchSegment(it.first(), url, start) orelse return false;
    var pending = it.next();
    while (pending) |segment| {
        const following = it.next();
        if (following == null and anchor_end) {
            return matchSegmentAtEnd(segment, url, pos);
        }
        pos = findSegment(segment, url, pos) orelse return false;
        pending = following;
    }
    return !anchor_end or pos == url.len;
}

/// Matches one wildcard-free segment at `pos`, returning where it ends.
fn matchSegment(segment: []const u8, url: []const u8, pos: usize) ?usize {
    var i = pos;
    for (segment, 0..) |c, si| {
        if (i == url.len) {
            // A '^' at the very end of the pattern also matches the end of
            // the URL, consuming nothing.
            return if (c == '^' and si == segment.len - 1) i else null;
        }
        if (c == '^') {
            if (!isSeparator(url[i])) return null;
        } else if (url[i] != c) {
            return null;
        }
        i += 1;
    }
    return i;
}

/// Leftmost occurrence of `segment` at or after `from`; no backtracking, the
/// same simplification uBO and adblock-rust make.
fn findSegment(segment: []const u8, url: []const u8, from: usize) ?usize {
    var i = from;
    while (i <= url.len) : (i += 1) {
        if (matchSegment(segment, url, i)) |end| return end;
    }
    return null;
}

fn matchSegmentAtEnd(segment: []const u8, url: []const u8, from: usize) bool {
    var i = from;
    while (i <= url.len) : (i += 1) {
        if (matchSegment(segment, url, i)) |end| {
            if (end == url.len) return true;
        }
    }
    return false;
}

/// uBO's separator class: everything that cannot appear in a hostname or an unescaped path word.
fn isSeparator(c: u8) bool {
    if (std.ascii.isAlphanumeric(c)) return false;
    return switch (c) {
        '_', '%', '.', '-' => false,
        else => true,
    };
}

const testing = @import("../../testing.zig");

fn testMatch(arena: std.mem.Allocator, line: []const u8, url: []const u8) !bool {
    const filter = try NetworkFilter.parse(arena, line);
    return matches(&filter, .init(url, url));
}

test "adblock.pattern: hostname location" {
    var u: Url = .init("https://ads.example.com/x?y=1", "");
    try testing.expectString("ads.example.com", u.hostname());

    u = .init("https://ads.example.com:8443/x", "");
    try testing.expectString("ads.example.com", u.hostname());

    u = .init("https://example.com", "");
    try testing.expectString("example.com", u.hostname());

    u = .init("http://[::1]:9222/json", "");
    try testing.expectString("[::1]", u.hostname());

    // Credentials are not part of the host.
    u = .init("https://user:[email protected]/x", "");
    try testing.expectString("ads.example.com", u.hostname());

    // A pattern is matched against whatever it is given, even a bare path.
    u = .init("/relative/path", "");
    try testing.expectString("", u.hostname());
}

test "adblock.pattern: hostname filters cover subdomains" {
    var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    try testing.expect(try testMatch(arena, "||ads.example.com^", "https://ads.example.com/a"));
    try testing.expect(try testMatch(arena, "||ads.example.com^", "https://x.ads.example.com/a"));
    try testing.expect(!try testMatch(arena, "||ads.example.com^", "https://notads.example.com/a"));
    try testing.expect(!try testMatch(arena, "||ads.example.com^", "https://example.com/ads.example.com"));
}

test "adblock.pattern: caret-less hostname filters match the hostname or a subdomain" {
    var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    // The real EasyPrivacy shape "||coinimp.com$third-party": uBO reads it
    // as "||coinimp.com^", so "coinimp.com.evil.org" — evil.org's hostname,
    // not a subdomain of coinimp.com — is out.
    try testing.expect(try testMatch(arena, "||coinimp.com", "https://coinimp.com/miner.js"));
    try testing.expect(try testMatch(arena, "||coinimp.com", "https://sub.coinimp.com/x"));
    try testing.expect(try testMatch(arena, "||coinimp.com", "https://coinimp.com:8080/x"));
    try testing.expect(!try testMatch(arena, "||coinimp.com", "https://coinimp.com.evil.org/x"));
    try testing.expect(!try testMatch(arena, "||coinimp.com", "https://coinimp.community/miner.js"));

    // `||host|` is that same filter once more.
    try testing.expect(try testMatch(arena, "||coinimp.com|", "https://sub.coinimp.com/x"));
    try testing.expect(!try testMatch(arena, "||coinimp.com|", "https://coinimp.com.evil.org/x"));

    // `||host*` is NOT: uBO keeps a trailing '*' after a short run, and the
    // pattern stays a label-anchored prefix.
    try testing.expect(try testMatch(arena, "||coinimp.com*", "https://coinimp.com.evil.org/x"));
    try testing.expect(try testMatch(arena, "||coinimp.com*", "https://coinimp.community/miner.js"));

    // A filter hostname ending in '.' names no hostname; it stays a prefix
    // and carries its own boundary.
    try testing.expect(try testMatch(arena, "||adform.", "https://adform.net/banner"));
    try testing.expect(try testMatch(arena, "||adform.", "https://track.adform.co.uk/x"));
    try testing.expect(!try testMatch(arena, "||adform", "https://adformat.example/x"));
}

test "adblock.pattern: right-anchored hostname filters pin the URL end" {
    var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    // `||host^|`: the separator '^' must also be the end of the URL.
    try testing.expect(try testMatch(arena, "||ads.com^|", "https://ads.com"));
    try testing.expect(try testMatch(arena, "||ads.com^|", "https://ads.com/"));
    try testing.expect(!try testMatch(arena, "||ads.com^|", "https://ads.com/path/x"));
    try testing.expect(!try testMatch(arena, "||ads.com^|", "https://ads.com/?q=1"));
}

test "adblock.pattern: hostname-anchored patterns resume after the host" {
    var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    // The real shape from the report.
    try testing.expect(try testMatch(
        arena,
        "||youtube.com/pagead/",
        "https://www.youtube.com/pagead/lvz?ei=x",
    ));
    try testing.expect(!try testMatch(
        arena,
        "||youtube.com/pagead/",
        "https://www.youtube.com/watch?v=x",
    ));
    // The path is anchored to the end of the hostname, not searched for.
    try testing.expect(!try testMatch(
        arena,
        "||youtube.com/pagead/",
        "https://example.com/www.youtube.com/pagead/x",
    ));

    try testing.expect(try testMatch(
        arena,
        "||g.doubleclick.net/gampad/ads",
        "https://g.doubleclick.net/gampad/ads?env=vp",
    ));
    try testing.expect(!try testMatch(
        arena,
        "||g.doubleclick.net/gampad/ads",
        "https://g.doubleclick.net/pagead/ads",
    ));
}

test "adblock.pattern: wildcards" {
    var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    try testing.expect(try testMatch(
        arena,
        "||g.doubleclick.net/gampad/ads*%20web%20player",
        "https://g.doubleclick.net/gampad/ads?a=1&b=my%20web%20player",
    ));
    try testing.expect(!try testMatch(
        arena,
        "||g.doubleclick.net/gampad/ads*%20web%20player",
        "https://g.doubleclick.net/gampad/ads?a=1",
    ));

    // A '*' in the hostname region anchors to a label boundary.
    try testing.expect(try testMatch(arena, "||example.*/ads", "https://example.co.uk/ads/x"));
    try testing.expect(try testMatch(arena, "||example.*/ads", "https://www.example.com/ads/x"));
    try testing.expect(!try testMatch(arena, "||example.*/ads", "https://notexample.com/ads/x"));

    try testing.expect(try testMatch(arena, "/banner/*/img", "https://a.com/banner/x/img"));
}

test "adblock.pattern: separators" {
    var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    // '^' matches one separator...
    try testing.expect(try testMatch(arena, "||example.com/ads^", "https://example.com/ads?x=1"));
    try testing.expect(try testMatch(arena, "||example.com/ads^", "https://example.com/ads/x"));
    // ...or the end of the URL.
    try testing.expect(try testMatch(arena, "||example.com/ads^", "https://example.com/ads"));
    // Letters, digits, '_', '%', '.' and '-' are not separators.
    try testing.expect(!try testMatch(arena, "||example.com/ads^", "https://example.com/adsx"));
    try testing.expect(!try testMatch(arena, "||example.com/ads^", "https://example.com/ads.js"));
}

test "adblock.pattern: anchors" {
    var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    try testing.expect(try testMatch(arena, "|https://ads.", "https://ads.example.com/"));
    try testing.expect(!try testMatch(arena, "|https://ads.", "http://ads.example.com/"));

    try testing.expect(try testMatch(arena, "-ad-300x250.gif|", "https://a.com/-ad-300x250.gif"));
    try testing.expect(!try testMatch(arena, "-ad-300x250.gif|", "https://a.com/-ad-300x250.gif?x"));

    // Unanchored patterns are plain substrings.
    try testing.expect(try testMatch(arena, "/banner/ads.", "https://a.com/x/banner/ads.png"));
    try testing.expect(!try testMatch(arena, "/banner/ads.", "https://a.com/banner/x.png"));
}

test "adblock.pattern: option-only filters match every URL" {
    var arena_state = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    try testing.expect(try testMatch(arena, "$script,domain=example.com", "https://anything.test/x"));
}