From 7e69c08c64eb3ed71a01db6af6c232b25f0be830 Mon Sep 17 00:00:00 2001 From: Bob Halley Date: Sun, 10 Aug 2025 10:36:50 -0700 Subject: [PATCH] Add Bounds. --- dns/btreezone.py | 93 +++++++++++++++++++++++++++++++++++++++++ tests/test_btreezone.py | 76 +++++++++++++++++++++++++++++++++ 2 files changed, 169 insertions(+) diff --git a/dns/btreezone.py b/dns/btreezone.py index c749b4ad..6328577b 100644 --- a/dns/btreezone.py +++ b/dns/btreezone.py @@ -12,6 +12,7 @@ # points, and the GLUE flag is set on nodes beneath delegation points. import enum +from dataclasses import dataclass from typing import Callable, MutableMapping, Optional, Tuple, cast import dns.btree @@ -240,6 +241,30 @@ class WritableVersion(dns.zone.WritableVersion): del self.nodes[name] +@dataclass(frozen=True) +class Bounds: + name: dns.name.Name + left: dns.name.Name + right: Optional[dns.name.Name] + closest_encloser: dns.name.Name + is_equal: bool + is_delegation: bool + + def __str__(self): + if self.is_equal: + op = "=" + else: + op = "<" + if self.is_delegation: + zonecut = " zonecut" + else: + zonecut = "" + return ( + f"{self.left} {op} {self.name} < {self.right}{zonecut}; " + f"{self.closest_encloser}" + ) + + @dns.immutable.immutable class ImmutableVersion(dns.zone.Version): def __init__(self, version: dns.zone.Version): @@ -261,6 +286,74 @@ class ImmutableVersion(dns.zone.Version): self.delegations = version.delegations self.delegations.make_immutable() + def bounds(self, name: dns.name.Name | str) -> Bounds: + """Return the 'bounds' of *name* in its zone. + + The bounds information is useful when making an authoritative response, as + it can be used to determine whether the query name is at or beneath a delegation + point. The other data in the ``Bounds`` object is useful for making on-the-fly + DNSSEC signatures. + + The left bound of a name is the name itself (if in the zone), or the greatest + predecessor of the name. + + The right bound of a name is the least successor of the name, or ``None`` if + the name is the greatest name in the zone. + + The closest encloser of a name is *name* itself, if *name* is in the zone; + otherwise it is the name with the largest number of labels in common with + *name* that is in the zone, either explicitly or by the implied existence + of empty non-terminals. + + The bounds *is_equal* field is ``True`` if and only if the name is equal to + its left bound. + + The bounds *is_delegation* field is ``True`` if and only if the left bound is a + zonecut. + """ + assert self.origin is not None + # validate the origin because we may need to relativize + origin = self.zone._validate_name(self.origin) + name = self.zone._validate_name(name) + cut, _ = self.delegations.get_delegation(name) + if cut is not None: + target = cut + is_delegation = True + else: + target = name + is_delegation = False + c = cast(dns.btree.BTreeDict, self.nodes).cursor() + c.seek(target, False) + left = c.prev() + assert left is not None + c.next() # skip over left + while True: + right = c.next() + if right is None or not right.value().is_glue(): + break + left_comparison = left.key().fullcompare(name) + if right is not None: + right_key = right.key() + right_comparison = right_key.fullcompare(name) + else: + right_comparison = ( + dns.name.NAMERELN_COMMONANCESTOR, + -1, + len(origin), + ) + right_key = None + closest_encloser = dns.name.Name( + name[-max(left_comparison[2], right_comparison[2]) :] + ) + return Bounds( + name, + left.key(), + right_key, + closest_encloser, + left_comparison[0] == dns.name.NameRelation.EQUAL, + is_delegation, + ) + class Zone(dns.versioned.Zone): node_factory: Callable[[], dns.node.Node] = Node diff --git a/tests/test_btreezone.py b/tests/test_btreezone.py index 4c3acb7d..b8eb4892 100644 --- a/tests/test_btreezone.py +++ b/tests/test_btreezone.py @@ -14,6 +14,9 @@ $TTL 300 @ ns ns2 ns1 a 10.0.0.1 ns2 a 10.0.0.2 +a txt "a" +c.b.a txt "cba" +b txt "b" sub ns ns1.sub sub ns ns2.sub ns1.sub a 10.0.0.3 @@ -21,6 +24,7 @@ ns2.sub a 10.0.0.4 ns1.sub2 a 10.0.0.5 ns2.sub2 a 10.0.0.6 text txt "here to be after sub2" +z txt "z" """ @@ -158,3 +162,75 @@ def test_delegations_absolute(): def test_delegations_relative(): do_test_delegations(True) + + +def do_test_bounds(relativize: bool): + z = make_example(simple_zone, relativize=relativize) + with z.reader() as txn: + version = cast(dns.btreezone.ImmutableVersion, txn.version) + # tuple is (name, left, right, closest, is_equal, is_delegation) + tests = [ + ("example.", "example.", "a.example.", "example.", True, False), + ("a.z.example.", "z.example.", None, "z.example.", False, False), + ( + "a.b.a.example.", + "a.example.", + "c.b.a.example.", + "b.a.example.", + False, + False, + ), + ( + "d.b.a.example.", + "c.b.a.example.", + "b.example.", + "b.a.example.", + False, + False, + ), + ( + "d.c.b.a.example.", + "c.b.a.example.", + "b.example.", + "c.b.a.example.", + False, + False, + ), + ( + "sub.example.", + "sub.example.", + "ns1.sub2.example.", + "sub.example.", + True, + True, + ), + ( + "ns1.sub.example.", + "sub.example.", + "ns1.sub2.example.", + "sub.example.", + False, + True, + ), + ] + for name, left, right, closest, is_equal, is_delegation in tests: + name = z._validate_name(name) + left = z._validate_name(left) + if right is not None: + right = z._validate_name(right) + closest = z._validate_name(closest) + bounds = version.bounds(name) + print(bounds) + assert bounds.left == left + assert bounds.right == right + assert bounds.closest_encloser == closest + assert bounds.is_equal == is_equal + assert bounds.is_delegation == is_delegation + + +def test_bounds_absolute(): + do_test_bounds(False) + + +def test_bounds_relative(): + do_test_bounds(True) -- 2.47.3