Ordered IP firewall with CIDR rules

Implement an IPv4 firewall that checks addresses against an ordered list of rules.

Each rule is a pair (action, target). action is "ALLOW" or "DENY". target is either a single IPv4 address ("192.168.0.9", which means /32) or a CIDR block ("192.168.0.0/16"). A CIDR block a.b.c.d/p contains every address whose first p bits equal the first p bits of a.b.c.d.

class Firewall:
    def __init__(self, rules: list[tuple[str, str]]): ...
    def is_allowed(self, ip: str) -> bool: ...

Part 1. is_allowed(ip) checks the rules in the order given. The first rule whose target contains ip decides the result. If no rule matches, the address is denied.

Part 2. Add is_range_allowed(cidr: str) -> bool. It returns True only if every address in the block would be allowed by is_allowed. A /8 block has about 16 million addresses, so do not check them one by one.

Constraints:

• Up to a few thousand rules. Prefix lengths are 0 to 32.
• A rule's base address can have host bits set (10.0.0.7/24). Treat it as its network (10.0.0.0/24).
• Malformed addresses or prefixes should raise an error.

Example. Rules, in order:

DENY  10.1.2.3
ALLOW 10.1.0.0/16
DENY  10.0.0.0/8
ALLOW 172.16.5.0/24

• is_allowed("10.1.9.9") returns True (rule 2).
• is_allowed("10.1.2.3") returns False: rule 1 matches before the broader ALLOW.
• is_allowed("8.8.8.8") returns False: no rule matches.
• is_range_allowed("10.1.4.0/22") returns True.
• is_range_allowed("10.1.0.0/16") returns False, because it contains 10.1.2.3.